错误检测和校正.ppt

《错误检测和校正.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、16错误检测和校正为什么要做错误检测与校正光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘制造生产技术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出的数据不可能完全正确。据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为3×10-4；沾有指纹的盘的误码率约为6×10-4；有伤痕的盘的误码率约为5×10-3。采用的具体对策激光盘存储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种：(1)错误检测：采用CRC(CyclicRedundancyCode)检测读出数据是否有错。(2)错

2、误校正码：采用里德－索洛蒙码(Reed－SolomonCode)，称为RS码，进行纠错。RS码被认为是性能很好的纠错码。(3)交叉交插里德－索洛蒙码CIRC(CrossInterleavedReed－SolomonCode),这个码的含义可理解为在用RS编译码前后，对数据进行交插处理和交叉处理。检错与纠错的基本原理检错与纠错是指允许在通信过程中产生错误的前提下，能有效的检测出错误并进行纠正，从而提高通信质量。检错与纠错统称为差错控制。差错控制的主要目的是为了减少传输中的错误，可采取两种方案：让每个传输的数据单元仅带有足以使接收端发现差错的冗

3、余信息，但不能确定错误位置，因而不能纠正错误，只能发现错误，这是一种检错编码方案。让每个传输的数据单元带有足够的冗余信息，以便在接收端发现并自动纠正传输错误，这是一种纠错编码方案。性能参数-效率效率定义编码效率R来度量有效性：R＝k/n其中，k是信息元的个数，n为码长。性能参数-检错和纠错能力检错和纠错能力两个等长码组之间相应位取值不同的数目称为这两个码组的码距。码组集中任意两个码字之间距离的最小值称为最小码距，用d0表示。最小码距d0直接关系着码的检错和纠错能力，任一(n，k)分组码，若要在码字内：(1)检测e个随机错误，则要求码的最小距

4、离d0>=e+1；(2)纠正t个随机错误，则要求码的最小距离d0>=2t+1;检错纠错码举例奇偶校验码重复码等比码循环冗余校验（CRC）......分组码简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字，在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码字末被选用，称为禁用码组。分组码一般可用(n，k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。循环码循环码是一类重要的

5、分组码。之所以称为循环码，是因为其循环性：即循环码组中任一码字循环移位所得的码字仍为该码组中的一个码字。如：循环码的多项式描述对于任一矢量都可用一个次数不超过n-1的多项式按下式（代码多项式）唯一确定：它们之间具有相同的物理意义，只是描述方式不同而已多项式描述时的运算规则模2运算加减乘除取模循环左移i位：生成多项式定理：在一个(n,k)循环码中，一定存在唯一的次数最低的n-k次首一码多项式g(x):使所有的码多项式都是g(x)的倍数，即所有码字都可写成若选作为生成多项式，则（7，3）码多项式为：依此将(000)...(111)代入，得到如下

6、结果:系统循环码所谓的系统循环码，要求码字的前k位原封不动地照搬信息位，而后面n-k位为校验位，也就是说，希望码多项式具有如下形式：这里，r(x)是与码字中n-k个校验元相对应的n-k-1位多项式构成系统多项式的方法1、将信息多项式m(x)预乘xn-k，即左移n-k位2、将xn-km(x)除以g(x)，得余式r(x)3、系统循环码多项式写成C(x)=xn-km(x)+r(x)CRC码-举例求m=（011）的（7，3）系统循环码，其中生成多项式为CRC检错用同样的CRC码生成多项式去除码多项式数据，相除后得到的两种可能结果是：①余数为0，表示

7、读出没有出现错误；②余数不为0，表示读出有错。CRC校验可以100%的检测出所有的奇数个随机错误和小于等于r（g(x)的阶数）的突发错误，所以CRC的生成多项式次数越高，误判的概率就越小CRC错误检测原理与检测码(续1)模2多项式代数运算规则模2多项式的加法和减法代码多项式的模2加法和模2减法运算所得的结果相同，所以可用加法来代替减法CRC错误检测原理与检测码(续2)模2多项式的除法用长除法CRC错误检测原理与检测码(续4)错误检测原理如果用一个校验码G(x)生成多项式去除代码多项式M(x)，得到的商假定为Q(x)，余式为R(x)，则可写成

8、因模2多项式的加法和减法运算结果相同，故可把上式写成CRC错误检测原理与检测码(续5)代表新的代码多项式，它是能够被校验码生成多项式G(x)除尽的，即它的余项为0在盘上写数据时，