错误检测和校正

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,16 错误检测和校正,1,为什么要做错误检测与校正,光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘制造生产技术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出的数据不可能完全正确。据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为310,-4,；沾有指纹的盘的误码率约为610,-4,；有伤痕的盘的误码率约为510,-3,。,2,采用的具体对策,激光盘存储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种：,(1) 错误检测：采用CRC(Cyclic Redundancy Code)检测读出数据是否有错。,(2) 错误校正码： 采用里德索洛蒙码(ReedSolomon Code)，称为RS码，进行纠错。RS码被认为是性能很好的纠错码。,(3) 交叉交插里德索洛蒙码CIRC(Cross Interleaved ReedSolomon Code), 这个码的含义可理解为在用RS编译码前后，对数据进行交插处理和交叉处理。,3,检错与纠错的基本原理,检错与纠错是指允许在通信过程中产生错误的前提下，能有效的检测出错误并进行纠正，从而提高通信质量。检错与纠错统称为差错控制。,差错控制的主要目的是为了减少传输中的错误，可采取两种方案：,让每个传输的数据单元仅带有足以使接收端发现差错的冗余信息，但不能确定错误位置，因而不能纠正错误，只能发现错误，这是一种检错编码方案。,让每个传输的数据单元带有足够的冗余信息，以便在接收端发现并自动纠正传输错误，这是一种纠错编码方案。,4,性能参数-效率,效率,定义编码效率R来度量有效性：,Rk/n,其中，k是信息元的个数，n为码长。,5,性能参数-检错和纠错能力,检错和纠错能力,两个等长码组之间相应位取值不同的数目称为这两个码组的码距。码组集中任意两个码字之间距离的最小值称为最小码距，用d,0,表示。,最小码距d,0,直接关系着码的检错和纠错能力，任一(n，k)分组码，若要在码字内：,(1)检测e个随机错误，则要求码的最小距离d,0,= e+1；,(2)纠正t个随机错误，则要求码的最小距离d,0,= 2t+1;,6,检错纠错码举例,奇偶校验码,重复码,等比码,循环冗余校验（CRC）,.,7,分组码,简单地说，分组码是对每段k位长的信息组以一定的规则增加r个,监督元,，组成长为n的码字，在二进制情况下，共有2,k,个不同的,信息组,，相应地可得到2,k,个不同的码字，称为,许用码组,。其余2,n,- 2,k,个码字末被选用，称为,禁用码组,。,分组码一般可用(n，k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。,8,循环码,循环码是一类重要的分组码。,之所以称为循环码，是因为其循环性：即循环码组中任一码字循环移位所得的码字仍为该码组中的一个码字。,如：,9,循环码的多项式描述,对于任一矢量,都可用一个次数不超过n-1的多项式按下式（代码多项式）唯一确定：,它们之间具有相同的物理意义，只是描述方式不同而已,10,多项式描述时的运算规则,模2运算,加,减,乘,除,取模,循环左移i位：,11,生成多项式,定理：在一个 (n,k)循环码中，一定存在唯一的次数最低的n-k次首一码多项式g(x):,使所有的码多项式都是g(x)的倍数，即所有码字都可写成,12,若选 作为生成多项式，则（7，3）码多项式为：,依此将(000).(111)代入，得到如下结果:,13,系统循环码,所谓的系统循环码，要求码字的前k位原封不动地照搬信息位，而后面n-k位为校验位，也就是说，希望码多项式具有如下形式：,这里，r(x)是与码字中n-k个校验元相对应的n-k-1位多项式,14,构成系统多项式的方法,1、将信息多项式m(x)预乘x,n-k,，即左移n-k位,2、将x,n-k,m(x)除以g(x)，得余式r(x),3、系统循环码多项式写成C(x)= x,n-k,m(x)+r(x),15,CRC码-举例,求m=（011）的（7，3）系统循环码，其中生成多项式为,16,CRC检错,用同样的CRC码生成多项式去除码多项式数据，相除后得到的两种可能结果是：,余数为0，表示读出没有出现错误；,余数不为0，表示读出有错。,CRC校验可以100%的检测出所有的奇数个随机错误和小于等于r（g(x)的阶数）的突发错误，所以CRC的生成多项式次数越高，误判的概率就越小,17,CRC生成多项式的一点说明,CRC生成多项式G(x)的结构与检错效果是经过严格的数学分析和实验后确定的，有相应的国际标准，例如：,软磁盘存储器中使用的CRC校验码生成多项式是,CD-ROM采用的CRC校验码生成多项式是一个32阶的多项式：,18,CD-ROM的EDC字域,计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节02063共2064个字节。在EDC中存放的CRC码的次序如下：,EDC：,x,24,x,31,x,16,x,23,x,8,x,15,x,0,x,7,字节号：,2064,2065,2066,2067,19,RS（里德-索洛蒙）码,RS码是一种分组码，其码字分为k,m bit为一组，每组包括k个符号，每个符号由m bit组成，而不是1bit，也就是说，在RS码中是以一个符号为单位处理的。,RS码一般表示为（n，k）或（n，k，m）,20,RS码的编码方法,已知生成多项式G（x），求k个mbit的符号m,k-1, . m,1, m,0,的（n，k，m）RS码的编码步骤如下：,构造信息码符多项式M(x)=m,k-1,x,k-1,+.+m,1,x+m,0,求剩余多项式R(x)=Q,r-1,X,r-1,+Q,1,x+Q,0,(r=n-k)，即,的余数,21,如何用mbit符号作为M(x)的系数,引入概念：,假设每个符号有m个bit，则存在最高次数为m的多项式P(x)（本原多项式，这里我们不介绍什么叫本原多项式，因为这里牵扯到太多的数学问题，我们假设本原多项式是已知的）。其本原元素为 （ 为本原多项式的根，即P（ ）=0），则有：2,m,个符号都可以用的幂来表示（同样这里我们也不介绍为什么，如果有兴趣的同学可以参阅近世代数相关理论）。,22,如何用mbit符号作为M(x)的系数,mbit符号可用本原元素的幂进行表示，方法如下：,对元素（0, , ,2,. ,q-1,)(其中q=2,m,-2)，分别求其模P（）的值，得到的系数即为,i,所对应的二进制代码。,23,举例：,如3bit符号的本原多项式为P(x)=x,3,+x+1 ，其本原元为，则：,24,对应的运算,25,生成多项式G（X）的一般形式,对一个信息码符多项式 ，RS校验码生成多项式的一般形式为,式中，K,0,是偏移量，通常取K,0,= 0或K,0,= 1，而K=(n-k)2t (t为要校正的错误符号数)。,26,举例：,求（6，4，3）RS码，假设已知,m3 = 001m2 = 101m1 = 011m0 = 100,本原多项式已知为P(x)=x,3,+x+1,27,RS码纠错算法,RS码的错误纠正过程分三步：,(1)计算校正子(syndrome),(2)计算错误位置,(3)计算错误值。,（参见书本P299）,举例,28,16.3 CIRC纠错技术,光盘存储器和其它的存储器一样，经常遇到的错误有两种:,一种是由于随机干扰造成的错误，这种错误称随机错误。它的特点是随机的、孤立的，干扰过后再读一次光盘，错误就可能消失。,另一种错误是连续多位出错，或连续多个符号出错，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片。这种错误称为突发错误。,CIRC(Cross Interleaved Reed Solomon)纠错码综合了交插、延时交插、交叉交插等技术，不仅能纠随机错误，而且对纠突发错误特别有效。,29,16.3.1交插技术,同样多的错误，人们更容易纠正分散的错误。,例如，用X表示出现的错字，一种错误形式为“掩X X X ，雪中送炭，鸡犬不宁”，这是连续出现的错误，另一种错误形式为“掩X盗铃，雪中X炭，鸡犬不X”，这是分散出现的错误。这两种错误形式相比，同样是3个错误，但人们更容易更正后一种形式的错误。,这个道理很简单，把这种思想用在数字记录系统中对突发错误的更正非常有效。在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交插(interleaving)技术。,30,举例,3个(5，3)码块：,B1 = (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,31,从这个例子中可以看到，对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续的错误。,一般来说，如果有r个(n，k)码，排成rn矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若(n，k)码能纠正t个错误，那么这样交插后就可以纠正rt个突发错误。,32,16.3.2 交叉交插技术,交叉交插(crossinterleaving)编码是交插的一种变型。在实际应用中，也是一种重要的技术。现仍以简单的例子说明这种技术思想。,例子见书本P300,33,CIRC首先应用在激光唱盘系统中。音频信号的采样率为44.1 kHz，而每次采样有两个16比特的样本，一个来自左声道，一个来自右声道，每个样本用两个8bit的符号表示，因此每次采样共有4个符号。,为了纠正可能出现的错误，每6次采样共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)。,34,16.4里德-索洛蒙盛积码（RSPC）,按ISO/IEC10149的规定， CD-ROM扇区中的ECC码采用RSPC码产生172个字节的P校验符号和104个字节的Q校验符号。RS码采用本原多项式,和本原元 = (00000010),35,编码步骤,步骤：,1、CD-ROM的每个扇区中从字节12开始到字节2075共2064个字节组成的数据块排列成2443的矩阵,2、P校验符号用(26，24)RS码产生,3、Q校验符号用(45，43)RS码产生,(26，24)RS码和(45，43)RS码可以纠正出现在任何一行和任何一列上的一个错误，并且能相当可靠地检测出行、列中的多重错误。如果在一个阵列中出现多重错误，Reference Technology公司提供有一种名叫Layered ECC的算法，它可以取消多重错误。它的核心思想是交替执行行纠错和列纠错。,36,P校验,37,Q校验,38,举例,39,