12 错误检和校正.ppt

16 错误检测和校正 为什么要做错误检测与校正 光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘制造生产技术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出的数据不可能完全正确。据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为3×10-4；沾有指纹的盘的误码率约为6×10-4；有伤痕的盘的误码率约为5×10-3。 采用的具体对策 激光盘存储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种： (1) 错误检测：采用CRC(Cyclic Redundancy Code)检测读出数据是否有错。 (2) 错误校正码： 采用里德－索洛蒙码(Reed－Solomon Code)，称为RS码，进行纠错。RS码被认为是性能很好的纠错码。 (3) 交叉交插里德－索洛蒙码CIRC(Cross Interleaved Reed－Solomon Code), 这个码的含义可理解为在用RS编译码前后，对数据进行交插处理和交叉处理。 检错与纠错的基本原理 检错与纠错是指允许在通信过程中产生错误的前提下，能有效的检测出错误并进行纠正，从而提高通信质量。检错与纠错统称为差错控制。 差错控制的主要目的是为了减少传输中的错误，可采取两种方案： 让每个传输的数据单元仅带有足以使接收端发现差错的冗余信息，但不能确定错误位置，因而不能纠正错误，只能发现错误，这是一种检错编码方案。 让每个传输的数据单元带有足够的冗余信息，以便在接收端发现并自动纠正传输错误，这是一种纠错编码方案。 性能参数-效率 效率 定义编码效率R来度量有效性： R＝k/n 其中，k是信息元的个数，n为码长。 性能参数-检错和纠错能力 检错和纠错能力 两个等长码组之间相应位取值不同的数目称为这两个码组的码距。码组集中任意两个码字之间距离的最小值称为最小码距，用d0表示。 最小码距d0直接关系着码的检错和纠错能力，任一(n，k)分组码，若要在码字内： (1)检测e个随机错误，则要求码的最小距离d0 = e+1； (2)纠正t个随机错误，则要求码的最小距离d0 = 2t+1; 检错纠错码举例 奇偶校验码 重复码 等比码 循环冗余校验（CRC） ...... 分组码 简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字，在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n - 2k个码字末被选用，称为禁用码组。 分组码一般可用(n，k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。 循环码 循环码是一类重要的分组码。 之所以称为循环码，是因为其循环性：即循环码组中任一码字循环移位所得的码字仍为该码组中的一个码字。 如： 循环码的多项式描述 对于任一矢量 都可用一个次数不超过n-1的多项式按下式（代码多项式）唯一确定： 它们之间具有相同的物理意义，只是描述方式不同而已 多项式描述时的运算规则 模2运算 加 减 乘 除 取模 循环左移i位： 生成多项式 定理：在一个 (n,k)循环码中，一定存在唯一的次数最低的n-k次首一码多项式g(x): 使所有的码多项式都是g(x)的倍数，即所有码字都可写成 若选 作为生成多项式，则（7，3）码多项式为： 依此将(000)...(111)代入，得到如下结果: 系统循环码 所谓的系统循环码，要求码字的前k位原封不动地照搬信息位，而后面n-k位为校验位，也就是说，希望码多项式具有如下形式： 这里，r(x)是与码字中n-k个校验元相对应的n-k-1位多项式 构成系统多项式的方法 1、将信息多项式m(x)预乘xn-k，即左移n-k位 2、将xn-k m(x)除以g(x)，得余式r(x) 3、系统循环码多项式写成C(x)= xn-k m(x)+r(x) CRC码-举例 求m=（011）的（7，3）系统循环码，其中生成多项式为 CRC检错 用同样的CRC码生成多项式去除码多项式数据，相除后得到的两种可能结果是： ①余数为0，表示读出没有出现错误； ②余数不为0，表示读出有错。 CRC校验可以100%的检测出所有的奇数个随机错误和小于等于r（g(x)的阶数）的突发错误，所以CRC的生成多项式次数越高，误判的概率就越小 CRC错误检测原理与检测码(续1) 模2多项式代数运算规则 CRC错误检测原理与检测码(续2) 模2多项式的除法用长除法 CRC错误检测原理与检测码(续4) 错误检测原理 如果用一个校验码G(x)生成多项式去除代码多项式M(x) ，得到的商假定为Q(