12 错误检测和校正.ppt

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

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

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

4、码 重复码 等比码 循环冗余校验（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)代入，得到如下结果:,系统循环码,所谓的系统循环码，要求码字的前k位原封不动地照搬信息位，而后面n-k位为校验位，也就是说，希望码多项式具有如下形式： 这里，r(x)是与码

6、字中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的生成多项式次数越高，误判的概率就

7、越小,CRC错误检测原理与检测码(续1),模2多项式代数运算规则,模2多项式的加法和减法,代码多项式的模2加法和模2减法运算所得的结果相同，所以可用加法来代替减法,CRC错误检测原理与检测码(续2),模2多项式的除法用长除法,CRC错误检测原理与检测码(续4),错误检测原理 如果用一个校验码G(x)生成多项式去除代码多项式M(x) ，得到的商假定为Q(x)，余式为R(x)，则可写成,因模2多项式的加法和减法运算结果相同，故可把上式写成,CRC错误检测原理与检测码(续5),代表新的代码多项式，它是能够被校验码生成多项式G(x)除尽的，即它的余项为0 在盘上写数据时，将xn-kM(x)表示的信息代

8、码和表示的余数R(x)代码一起写到盘上 从盘上读数据时，将信息代码和余数代码一起读出，然后用相同的校验码生成多项式G(x)去除 通过判断余数是否为0来确定数据是否有误,CRC错误检测原理与检测码(续6),CD盘上的错误检测码 CD-DA盘上的q通道使用的CRC校验码生成多项式,若用二进制表示，则为,假定要写到盘上的信息代码M(x)为,由于增加了2个字节的校验码，所以信息代码变成,CRC错误检测原理与检测码(续7),两数相除的结果 其商可不必关心，其余数为B994(H)，这就是CRC校验码 将信息代码和CRC码一起写到盘上 写到盘上的信息代码和CRC码是4D6F746FB994，它能被 错误检测

9、 从盘上把这块数据读出时，用同样的CRC码生成多项式去除，其结果是：(1) 余数为0，表示读出没有错误；(2) 余数不为0，表示读出有错,除尽,CRC错误检测原理与检测码(续8),CD-ROM的错误检测 在CD-ROM扇区方式1中，有一个4字节的EDC域用来存放CRC码。CRC校验码生成多项式是一个32阶的多项式,计算CRC码时用的数据块是从扇区的开头到用户数据区结束的数据字节，即字节02063。在EDC中存放的CRC码的次序如下,CRC生成多项式的一点说明,CRC生成多项式G(x)的结构与检错效果是经过严格的数学分析和实验后确定的，有相应的国际标准，例如： 软磁盘存储器中使用的CRC校验码生

10、成多项式是 CD-ROM采用的CRC校验码生成多项式是一个32阶的多项式：,CD-ROM的EDC字域,计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节02063共2064个字节。在EDC中存放的CRC码的次序如下：,RS（里德-索洛蒙）码,RS码是一种分组码，其码字分为km bit为一组，每组包括k个符号，每个符号由m bit组成，而不是1bit，也就是说，在RS码中是以一个符号为单位处理的。 RS码一般表示为（n，k）或（n，k，m）,RS码的编码方法,已知生成多项式G（x），求k个mbit的符号mk-1 , . m1 , m0的（n，k，m）RS码的编码步骤如下

11、： 构造信息码符多项式M(x)=mk-1xk-1+.+m1x+m0 求剩余多项式R(x)=Qr-1Xr-1+Q1x+Q0 (r=n-k)，即 的余数,如何用mbit符号作为M(x)的系数,引入概念： 假设每个符号有m个bit，则存在最高次数为m的多项式P(x)（本原多项式，这里我们不介绍什么叫本原多项式，因为这里牵扯到太多的数学问题，我们假设本原多项式是已知的）。其本原元素为 （ 为本原多项式的根，即P（ ）=0），则有：2m个符号都可以用的幂来表示（同样这里我们也不介绍为什么，如果有兴趣的同学可以参阅近世代数相关理论）。,如何用mbit符号作为M(x)的系数,mbit符号可用本原元素的幂进行

12、表示，方法如下： 对元素（0, , 2. q-1)(其中q=2m-2)，分别求其模P（）的值，得到的系数即为i所对应的二进制代码。,举例：,如3bit符号的本原多项式为P(x)=x3+x+1 ，其本原元为，则：,对应的运算,生成多项式G（X）的一般形式,对一个信息码符多项式 ，RS校验码生成多项式的一般形式为 式中，K0是偏移量，通常取K0 = 0或K0 = 1，而K=(n-k)2t (t为要校正的错误符号数)。,举例：,求（6，4，3）RS码，假设已知 m3 = 001m2 = 101m1 = 011m0 = 100 本原多项式已知为P(x)=x3+x+1,RS码纠错算法,RS码的错误纠正过

13、程分三步： (1)计算校正子(syndrome) (2)计算错误位置 (3)计算错误值。 （参见书本P299） 举例,16.3 CIRC纠错技术,光盘存储器和其它的存储器一样，经常遇到的错误有两种: 一种是由于随机干扰造成的错误，这种错误称随机错误。它的特点是随机的、孤立的，干扰过后再读一次光盘，错误就可能消失。 另一种错误是连续多位出错，或连续多个符号出错，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片。这种错误称为突发错误。 CIRC(Cross Interleaved Reed Solomon)纠错码综合了交插、延时交插、交叉交插等技术，不仅能纠随机错误，而且对纠突发

14、错误特别有效。,16.3.1交插技术,同样多的错误，人们更容易纠正分散的错误。 例如，用X表示出现的错字，一种错误形式为“掩X X X ，雪中送炭，鸡犬不宁”，这是连续出现的错误，另一种错误形式为“掩X盗铃，雪中X炭，鸡犬不X”，这是分散出现的错误。这两种错误形式相比，同样是3个错误，但人们更容易更正后一种形式的错误。 这个道理很简单，把这种思想用在数字记录系统中对突发错误的更正非常有效。在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交插(interleaving)技术。,举例,3个(5，3)码块： B1 =

15、(a2，a1，a0，P1，P0) B2 = (b2，b1，b0，Q1，Q0) B3 = (c2，c1，c0，R1，R0) 交插排列： a2 b2 c2 a1 b1 c1 a0 b0 c0 P1 Q1 R1 P0 Q0 R0 连续错3个： a2 b2 c2 a1 b1 c1 a0 X X X Q1 R1 P0 Q0 R0 读出后重新排列： a2 a1 a0 X P0 b2 b1 X Q1 Q0 c2 c1 X R1 R0,从这个例子中可以看到，对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3

16、个连续的错误。 一般来说，如果有r个(n，k)码，排成rn矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若(n，k)码能纠正t个错误，那么这样交插后就可以纠正rt个突发错误。,16.3.2 交叉交插技术,交叉交插(crossinterleaving)编码是交插的一种变型。在实际应用中，也是一种重要的技术。现仍以简单的例子说明这种技术思想。 例子见书本P300,CIRC首先应用在激光唱盘系统中。音频信号的采样率为44.1 kHz，而每次采样有两个16比特的样本，一个来自左声道，一个来自右声道，每个样本用两个8bit的符号表示，因此每次采样共有4个符号。 为了纠正可能出现的错误，每6次

17、采样共24个符号构成1帧，称为F1帧(F1Frame)。用一个称为C2的编码器对这24个符号产生4个Q校验符号： Q0，Q1，Q2和Q3。24个声音数据加上4个Q校验符号共28个符号，用称为C1编码器对这28个符号产生4个P校验符号： P0，P1，P2和P3。28个符号加上4个P校验符号共32个符号构成的帧称为F2帧(F2Frame)。F2帧加上1个字节(即1个符号)的子码共33个符号构成的帧称为F3帧(F3Frame)。,16.4里德-索洛蒙盛积码（RSPC）,按ISO/IEC10149的规定， CD-ROM扇区中的ECC码采用RSPC码产生172个字节的P校验符号和104个字节的Q校验符号。RS码采用本原多项式 和本原元 = (00000010),