光盘错误检测和校正

光盘错误检测和校正光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘制造生产技术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出的数据不可能完全正确。据有关厂家的测试和统计，一片未使用过的只读光盘，某原始误码率约为3x10-4；沾有指纹的盘的误码率约为6x10-4；有伤痕的盘的误码率约为5x10-3。针对这种情况，激光盘存储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种：⑴错误检测：采用CRC(CyclicRedundancyCode)检测读出数据是否有错。⑵错误校正码：采用里德一索洛蒙码(Reed—SolomonCode)，简称为RS码，进行纠错。RS码被认为是性能很好的纠错码。(3)交叉交插里德一索洛蒙码C旧C(CrossInterleavedReed—SolomonCode),这个码的含义可理解为在用RS编译码前后，对数据进行交插处理和交叉处理。对这些码的理论分析和计算有许多专著作了详尽的深入论述，对不需要开发纠错技术的读者仅需要了解错误检测和校正的一些基本概念即可。1.CRC错误检测原理在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列10101111，用多项式可以表示成：+a.x5+a-x4+ +机/+ +anx°■-■" r U —* *T —1 X U式中的'表示代码的位置，或某个二进制数位的位置，/前面的系数气表示码的值。若气是一位二进制代码，则取值是0或1。纨称为信息代码多项式。在模2多项式代数运算中定义的运算规则有:1/=lx3例如，模2多项式的加法和减法:

从这两个例子中可以看到，对于模2运算来说，代码多项式的加法和减法运算所得的结果相同。所以在做代码多项式的减法时，可用做加法来代替做减法。代码多项式的除法可按长除法做。例如：X3 +工+1IK+1）工4+投+ +1工'+工K+1如果一个k位的二进制信息代码多项式为M"），再增加（n—k）位的校验码，那么增加（n一k）位之后，信息代码多项式在新的数据块中就表示成芝项次⑴，如图13-01所示。 WM（x） WM（x） 新的信息代码多项式校验位图13-01信息代码结构123左-1k止+1如果用一个校验码生成多项式去除代码多项式若小财3），得到的商假定为03），余式为衣"），则可写成xK-kM(x)=Q(x)G(x)+因为模2多项式的加法和减法运算结果相同，所以又可把上式写成:Lg)+反(x)=Q(x)G(x)&3)称为校验码生成多项式。从该式中可以看到，代表新的代码多项式zg)*%)是能够被校验码生成多项式占3)除尽的，即它的余项为0。例如，CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是x)=x16+x12+/+1若用二进制表示，则为G3)=100010000000100001(B)=11021(H)假定要写到盘上的信息代码财3)为沮("=4D6F746F(H)由于增加了2个字节共16位的校验码，所以信息代码变成^啾⑴:4D6F746F0000(H)。CRC检验码计算如下：49F99B1411021)4D6F746F0000440849637499129 F61D6FF1EF9039F9912992B6099129BA490BB16B15FB0110212字节的4F910CRC校蠢码44翊 ►B944两数相除的结果，其商可不必关心，其余数为B994(H)就是CRC校验码。把信息代码写到盘上时，将原来的信息代码和CRC码一起写到盘上。在这个例子中，写到盘上的信息代码和CRC码是4D6F746FB994,4D6F746FB994信息代码CRC码这个码是能被11021(H)除尽的。从盘上把这块数据读出时，用同样的CRC码生成多项式去除这块数据，相除后得到的两种可能结果是：①余数为0，表示读出没有出现错误；②余数不为0，表示读出有错。CD-ROM中也采用了相同的CRC检错。CD-ROM扇区方式01中，有一个4字节共32位的EDC字域，它就是用来存放CRC码。不过，CD-ROM采用的CRC校验码生成多项式与软磁盘采用的生成多项式不同，它是一个32阶的多项式，P(x)=(x16+尹+.+1)(/5+/+工+1)计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节0〜2063共2064个字节。在EDC中存放的CRC码的次序如下：EDC：X24—X31X16—X23X8—X15X0—X7字节号：|20642065206620672.RS编码和纠错算法13.2.1.GF(2m)域RS(Reed-Solomon)码在伽罗华域(GaloisField,GF)中运算的，因此在介绍RS码之前先简要介绍一下伽罗华域。CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m)=GF(28)中的元素或称符号。GF(28)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多广+1项式汽#的特性是F3)得到的余式等于0。CD-ROM用来构造GF(28)域的*Q是S…+—F(13—1)而GF(28)域中的本原元素为a=(00000010)下面以一个较简单例子说明域的构造。［例13.1］构造GF(23)域的本原多项式尹3)假定为P(x)=x3+x+1a定义为『3)=0的根，即a3+a+1=0和a3=a+1GF(23)中的元素可计算如下：0mod(a3+a+1)=0a0mod(a3+a+1)=a0=1a1mod(a3+a+1)=a1a2mod(a3+a+1)=a2a3mod(a3+a+1)=a+1a4mod(a3+a+1)=a2+aa5mod(a3+a+1)=a2+a1+1a6mod(a3+a+1)=a2+1a7mod(a3+a+1)=a0a8mod(a3+a+1)=a1 用二进制数表示域元素得到表13-01所示的对照表表13-01GF(23)域中与二进制代码对照表，影对=事+二+1GF(23)域元素二进制对代码0(000)a0(001)a1(010)a2(100)a3(011)a4(110)a5(111)a6(101)这样一来就建立了GF(23)域中的元素与3位二进制数之间的一一对应关系。用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(23)域中运算为例：加法例：a0+a3=001+011=010=a1减法例：与加法相同乘法例：a5•a4=a(5+4)mod?=a2除法例：a5/a3=a2a3/a5=a-2=a(-2+7)

取对数：log(a5)=5这些运算的结果仍然在GF(23)域中。13.2.2RS的编码算法RS的编码就是计算信息码符多项式财3)除以校验码生成多项式之后的余数。在介绍之前需要说明一些符号。在GF(2m)域中，符号(n，k)RS的含义如下：m 表示符号的大小，如m=8表示符号由8位二进制数组成n 表示码块长度，k 表示码块中的信息长度K=n-k=2t表示校验码的符号数t 表示能够纠正的错误数目例如，(28,24)RS码表示码块长度共28个符号，其中信息代码的长度为24,检验码有4个检验符号。在这个由28个符号组成的码块中，可以纠正在这个码块中出现的2个分散的或者2个连续的符号错误，但不能纠正3个或者3个以上的符号错误。对一个信息码符多项式财3)，RS校验码生成多项式的一般形式为抑 (13-2)式中，m0是偏移量，通常取K0=0或K0=1，而(n-k)32t(t为要校正的错误符号数)。下面用两个例子来说明RS码的编码原理。［例13.2］设在GF(23)域中的元素对应表如表13-01所示。假设(6,4)RS码中的4个信息符号为m3、m2、口］和m0，信息码符多项式泣⑴为M⑴=m^+m折+叩+!^(13-3)并假设RS并假设RS校验码的2个符号为Q"「Q0， "顷Q的剩余多项式阳为衣⑴=Qm+Qo这个多项式的阶次比的阶次少一阶。如果K0=1,t=1,由式(13—2)导出的RS校验码生成多项式就为&(对=[](厂卢)v队捍 =(f)(f)(13—4)根据多项式的运算，由式(13—3)和式(13—4)可以得到m3X5+m2X4+m1X3+m0X2+Q1X+Q0=(x—a)(x—a2)Q(x)当用x=a和x=a2代入上式时，得到下面的方程组，「找’+顷妒+nil找’+瑚)a■"+Qia+Q()=口1 £岬+电纨")4+m】(a2)3+观cc2)2+Qia2-1-Qo=0经过整理可以得到用矩阵表示的(6,4)RS码的校验方程：aHqxvJ=O_部 比* 孑/M1[Q (云沪(奸(时1VQ=Im3m2mim0QlQo.求解方程组就可得到校验符号：lQ]=nim妒+a?+皿a?+吸妒[Qo=m；；a+m猝3+a口+吸波在读出时的校正子可按下式计算：%=瑚+ 妒+ni]妒+吸(X?+Q]a+Qo[$i=m3(a5)24 a4)2-I-mi(a3)2+n^(a2)2+Qia2+Qo[例13.3]在例13.2中，如果K0=0,t=1,由式(13—2)导出的RS校验码生成多项式就为(13—5)根据多项式的运算，由(13—3)和(13—5)可以得到下面的方程组:zm3+m2+ni1+n^+Q1+Q0=0Im3”+普也'+nil +瑚)oc"+Qioci+Q()=Cl方程中的ai也可看成符号的位置，此处i=0,1,…，5。求解方程组可以得到RS校验码的2个符号为Q"「Q0,CQi=anim+ +妒mi+a'mo(13-6)Qo=a3m3+a6m2+a4nij+an^(13-6)假定mi为下列值:信息符号m3=a0=001m2=a6=101m1=a3=011m0=a2=100校验符号Q1=a6=101Q0=a4=110校正子s0=0s1=0代入(13-6)式可求得校验符号：Q1=a6=101Q0=a4=11013.2.3RS码的纠错算法(3)计算错RS码的错误纠正过程分三步：(1)计算校正子(syndrome),(2)计算错误位置，误值。现以例13.3为例介绍RS码的纠错算法。(3)计算错校正子使用下面的方程组来计算：s0=m3+n^+m1+m0+Q1+Q0印=mm纨彳+ 纨+吸+Q]a+Q(jTOC\o"1-5"\h\z为简单起见，假定存入光盘的信息符号m、m、m、m和由此产生的检验符号Q、Q均为0,3 2 10 1 0读出的符号为m，、m，、m，、m，、Q'和Q‘。32101 0如果计算得到的S0和si不全为0,则说明有差错，但不知道有多少个错，也不知道错在什么位置和错误值。如果只有一个错误，则问题比较简单。假设错误的位置为x，错误值为mx，那么可通过求解下面的方程组： ' '得知错误的位置和错误值。如果计算得到s0=a2和si=a5,可求得ax=a3和mx=a2,说明mi出了错，它的错误值是a2。校正后的mi=m「+mx，本例中m「0。如果计算得到S0=0，而si^0，那基本可断定至少有两个错误，当然出现两个以上的错误不一定都是s0=0和si^0:如果出现两个错误，而又能设法找到出错的位置，那么这两个错误也可以纠正。如已知两个错误幽"和沸而的位置％1和"樽，那么求解方程组：S1+斜疽期1g探1+用演=si就可知道这两个错误值。CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(ReedSolomonProduct-likeCode，RSPC)就是采用上述方法导出的。3.CIRC纠错技术光盘存储器和其它的存储器一样，经常遇到的错误有两种。一种是由于随机干扰造成的错误，这种错误称随机错误。它的特点是随机的、孤立的，干扰过后再读一次光盘，错误就可能消失。另一种错误是连续多位出错，或连续多个符号出错，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片。这种错误称为突发错误°CIRC(CrossInterleavedReedSolomon)纠错码综合了交插、延时交插、交叉交插等技术，不仅能纠随机错误，而且对纠突发错误特别有效。13.3.1交插技术对纠错来说，分散的错误比较容易得到纠正，但出现一长串的错误时，就较麻烦。正如我们读书看报，如果文中在个别地方出错，根据前后文就容易判断是什么错。如果连续错好多字，就很难判断该处写的是什么。例如，用X表示出现的错字，一种错误形式为“独在异乡XXX，每逢佳节倍思亲”，这是连续出现的错误，另一种错误形式为“独在异乡X异客，每X佳节倍思X”，这是分散出现的错误。这两种错误形式相比，同样是3个错误，但人们更容易更正后一种形式的错误，更正之后为“独在异乡为异客，每逢佳节倍思亲”。这个道理很简单，把这种思想用在数字记录系统中对突发错误的更正非常有效。在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交插（interleaving）技术。例如，口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个3个：5,3）码块:B=(aa，a，P，P)12， 1 0 1 0B=(b，b，b，Q，Q)221010B=3(C2，匕，C0，R1，R0)连续排列：aaaPPb2b1b0Q1Q0C2C1C0R1R0排成3行:aaaPP21010bbbQQ21010CCCRR交插排列：a2b2c2a1b1c1a0b0c0P1Q1R1P0Q0R0连续错3个：a2b2c2a1b1c1a0XXXQ1R1P0QoR0读出后重新排列：a_2-1a1a_0-iXP_0-1b_2-1bi1iXQ1Q0c——2-1c1XR111R1—0-口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个从这个例子中可以看到，对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续的错误。一般来说，如果有r个（n，k）码，排成rXn矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若（n，k）码能纠正t个错误，那么这样交插后就可以纠正rt个突发错误。13.3.2交叉交插技术交叉交插（cross—interleaving）编码是交插的一种变型。在实际应用中，也是一种重要的技术。现仍以简单的例子说明这种技术思想。口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口*个*个**********************************************************************用(5,3)码编码器q生成的4个码块为:B1=(a2a1a0P1P0)B=(bbbQQ)221010B=(cccRR)321010B4=(d2d1d0S1S0)交插后再用(6,4)码编码器C1生成5个码块为:abcdTT222210abcdUU111110abcdVV000010PQRSWW111110P0Q0R0S0X1X0再交插，交插的码块数可以是2、3、4或5。以交插2个码块为例：气a1b2bic2cid2diT1U1T0U0a°P1b0Q1c°R1d0S1•••最后一个码块不配对，可以和下一个码块配对。""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个这种编码技术用了两个编码器C2和q。C2对原码块进行编码得到(5,3)码块，交插后生成由4个符号组成的码块，码块中的符号是交叉存放的，然后再用(6,4)编码器C1去编码。有关CIRC详细的实现方法请参看文献［7］。CIRC首先应用在激光唱盘系统中。音频信号的采样率为44.1kHz，而每次采样有两个16比特的样本，一个来自左声道，一个来自右声道，每个样本用两个GF(28)域中的符号表示，因此每次采样共有4个符号。为了纠正可能出现的错误，每6次采样共24个符号构成1帧，称为F1帧(孔一Frame)。用一个称为C2的编码器对这24个符号产生4个Q校验符号：Q0，Q1，Q：和Q3。24个声音数据加上4个Q校验符号共28个符号，用称为C1编码器对这28个符号产生4个P校验符号:P0,P1，P2和P3。28个符号加上4个P校验符号共32个符号构成的帧称为F2帧(F2—Frame)。F；帧加上1个字节(即1个符号)的子码共33个符号构成的帧称为％帧(F「Frame)。在实际应用中可对前面介绍的交插技术略加修改，执行交插时不是交插包含有k个校验符的码块，而是交插一个连续系列中的码符，这种交插技术称为延时交插。延时交插之后还可用交叉技术，称为延时交叉交插技术。CD存储器中的CIRC编码器采用了4XF1帧的延时交插方案。1帧延时交插可纠正连续4XF1帧的突发错误。4XF2帧的延时交插可纠正连续16XF1帧突发错误，相当于大约14XF3帧的突发错误。1XF3帧经过EFM编码后产生588位通道位。1位通道位的长度折合成0.277Mm的光道长度。14xF3帧突发错误长度相当于[(16X(24+4))/331X588X0.277^2.2mm换句话说，CIRC能纠正在2.2mm光道上连续存放的448个错误符号！相当于连续224个汉字错误可以得到纠正。4.RSPC码按ISO/IEC10149的规定，CD-ROM扇区中的ECC码采用GF(28)域上的RSPC码产生172个字节的P校验符号和104个字节的Q校验符号。RS码采用本原多项式P(x)=/+/+/+普+1和本原元a=(00000010)构造GF(28)域，这已经在上节作了介绍。第12章已经介绍了CD-ROM的扇区结构。在每个扇区中，字节12〜2075和ECC域中的字节2076到2351共2340个字节组成1170个字(word)。每个字s(n)由两个字节B组成，一个称为最高有效位字节MSB,另一个叫做最低有效位字节LSB。第n个字由下面的字节组成，成扪=MSB[B(2«+13]+LSB[B(2«+12]其中n=0，1，2，…，1169。从字节12开始到字节2075共2064个字节组成的数据块排列成24X43的矩阵，如图13-02所示。—NP01234142000000010002………004100421004300440045………00840085HEADER2008600870088………01270128+PQ用户数据+MP22094609470948………09870988部分辅助数据23098909900991………103010312410321033103410731074P-校验25107510761077………1116111726111811191120…1143Q-校验27114411451146…11691「01...25I(ISO/IEC1049)图13-02RSPC码计算用数据阵列矩阵中的元素是字。这个矩阵要把它想象成两个独立的矩阵才比较好理解和分析，一个是由MSB字节组成的24X43矩阵，另一个是由LSB字节组成的24X43矩阵。(1)P校验符号用(26,24)RS码产生43列的每一列用矢量表示，记为Vp。每列有24个字节的数据再加2个字节的P校验字节，用下式表示： "%(43*0+叭)'s(4E+拉J吕(43Q+&J吕( )V 瓦43*刈+纯)s(43*22+^)s(43*23+^)成43*泌+、')瓦43*25+纯)其中：、一0，1，2，......，42=P0，1，2，……，25UF)和g心+昭)是p校验字节对这列字节计算得到的是两个P校验字节，称为P校验符号。两个P校验字节加到24行和25行的对应列上，这样构成了一个26X43的矩阵，并且满足方程HrxVr=0其中Hp校验矩阵为

11 1 11 1 !'CE2 CE1 1(2)Q校验符号用(45,43)RS码产生增加P校验字节之后得到了一个26X43矩阵，该矩阵的对角线元素重新排列后得到一个新的矩阵，其结构如图13-03所示。MQ012404142Q0Q10000000440088……064206860730111811441004300870131……068507290773111911452008601300147……072807720816112011463012901370217……077108150859112111474017202160260……0814085809021122114822094609901034……04700514055811401166NQ23098910331077……0513055706011141116724103210760002……0556060006441142116825107500010045……05990643068711431169(ISO/IEC10149:1989)图13-03Q校验符号计算用数据阵列TOC\o"1-5"\h\z每条对角线上的43个MSB字节和LSB字节组成的矢量记为Vq。Vq在26X43矩阵中变成行矢量。第N行上的V矢量包含的字节如下： °°Q Q沼4*。+43*气)威44*1+43*蚓)I洲4*2+43*吨)成 …… )VQ=\o"CurrentDocument"s(A4*Mb+43*气)

，( …… )VQ=\o"CurrentDocument"《4*41+43*%瓦44*42+43*既)s(43*26+ "s(44*26+ Nq)

其中：NQ=0,1,2,…，25Mq=0,1,2，…，42143*26+将和s=(44*26+时是Q校验字节VQ中的(44*Mq+43*Nq)字节号运算结果要做mod(1118)运算。用(45,43)RS码产生的两个Q校验字节放到对应V矢量的末端，并且满足下面的方程：Hqf=0Hqf=0其中Hq校验矩阵为_rii-Hq=[c44.(26,24)RS码和(45,■11T-CE2EE1143)RS码可以纠正出现在任何一行和任何一列上的一个错误，并且能相当可靠地检测出行、列中的多重错误。如果在一个阵列中出现多重错误，ReferenceTechnology公司提供有一种名叫LayeredECC的算法，它可以取消多重错误。它的核心思想是交替执行行纠错和列纠错。例如，假设错误分布如图13-04所示。ECC算法首先计算MSB矩阵和LSB矩阵中每一行的校正子SE(i=0,1,„,25)，以及每一列的校正子Scj(j=0,1,„,44)。因为用(45,43)RS码，所以每一个Sri和每一个Scj都有两个校正子分量。如果Sri=0,则说明第i行无错；如Scj=0,说明第j行无错。"01234567391011121314151617181920212223242526272829303132333435363738394041424344i121416171819202122232425Sn：iSriSr3Sr4a■jiSr7jiSiy■jia■a■■jia■Srl5Srl5SrlQjijiSr22jia■Sr25ScO-J,_-J,Sc5-J,Sc9J,J,Sc15-J, S«:20 -J,Sc25-J, -J,