光盘错误检测和校正

第 13 章 错误检测和校正光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘 制造生产技术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出 的数据不可能完全正确。据有关厂家的测试和统计，一片未使用过的只读光盘， 其原始误码率约为3X104；沾有指纹的盘的误码率约为6X104；有伤痕的盘的 误码率约为5X10-3。针对这种情况，激光盘存储器采用了功能强大的错误码检 测和纠正措施。采用的具体对策归纳起来有三种：(1) 错误检测：采用CRC(Cyclic Redundancy Code)检测读出数据是否有错。(2) 错误校正码：采用里德一索洛蒙码(Reed Solomon Code),简称为RS 码，进行纠错。 RS 码被认为是性能很好的纠错码。(3) 交叉交插里德索洛蒙码 CIRC(Cross Interleaved ReedSolomon Code),这个码的含义可理解为在用RS编译码前后，对数据进行交插处理和交叉 处理。对这些码的理论分析和计算有许多专著作了详尽的深入论述，对不需要开发 纠错技术的读者仅需要了解错误检测和校正的一些基本概念即可。13.1 CRC 错误检测原理在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列 10101111，用多项式可以表示成：M(x) = ax7 + ax6 + ax5 + ax4+ ax3 + ax2 + ax1+ ax0 76543210 = x7+ x6+ x5+ x4+ x3+ x2+ x1+ 1式中的xi表示代码的位置，或某个二进制数位的位置，xi前面的系数a表示码i的值。若a是一位二进制代码，则取值是0或1。M(x)称为信息代码多项式。i在模2多项式代数运算中定义的运算规则有：1xi + 1xi = 0-1xi = 1xi例如，模 2 多项式的加法和减法：x4 -P x3-)x4+ 1从这两个例子中可以看到，对于模2运算来说，代码多项式的加法和减法运 算所得的结果相同。所以在做代码多项式的减法时，可用做加法来代替做减法。代码多项式的除法可按长除法做。例如：+ 21疋 + 1) J /+ 疋如果一个k位的二进制信息代码多项式为M(x),再增加(nk)位的校验码, 那么增加(nk)位之后，信息代码多项式在新的数据块中就表示成xn-kM(x), 如图13-01 所示。如果用一个校验码生成多项式G(x)去除代码多项式xn-kM(x),得到的商假定为 Q(x) ，余式为 R(x) ，则可写成xn-kM(x)= Q(x)G(x) + R(x)因为模2 多项式的加法和减法运算结果相同，所以又可把上式写成： xn-kM(x) + R(x)= Q(x)G(x)G(x) 称为校验码生成多项式。从该式中可以看到，代表新的代码多项式 xn-kM(x) + R(x) 是能够被校验码生成多项式 G(x) 除尽的，即它的余项为0。例如，CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是 G(x) = x16 + x12 + x5 + 1若用二进制表示，则为G(x) = 100010000000100001(B) = 11021(H) 假定要写到盘上的信息代码 M(x) 为M(x) = 4D6F746F (H) 由于增加了2个字节共16位的校验码，所以信息代码变成 x16M(x):4D6F746F0000(H) 。 CRC 检验码计算如下：49F99B1411021) 4D6F746F0000440849637499129F61D6FF1EF9039F9912992B6099129BA490BB16B15FB0 110212字节的 4F910CRC裱血码 440開 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 + x15+ x2+ 1)(x16 + x2 + x+ 1)计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字 节，即字节02063共2064个字节。在EDC中存放的CRC码的次序如下：EDC：X24X31X16一X23X8 X15X0 X7字节号：206420652066206713.2 RS 编码和纠错算法13.2.1. GF(2m)域RS(Reed-Solomon)码在伽罗华域(Galois Field, GF)中运算的，因此在介绍 RS 码之前先简要介绍一下伽罗华域。CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m) = GF(2*)中 的元素或称符号。GF(28)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式P(x)的特性是PS)，得到的余式等于0。 CD-ROM用来构造GF(2Q域的P(x)是P(x) = x8+ x4+x3 + x2 + 1 (13 1)而GF(28)域中的本原元素为a = (0 0 0 0 0 0 1 0) 下面以一个较简单例子说明域的构造。例131构造GF(2s)域的本原多项式P(x)假定为P(x) = x3+ x+ 1a 定义为 P(x) = 0的根，即a 3 a 1 = 0和 a 3 = a +1GF(2s)中的元素可计算如下：0mod(a 3+a +1) = 0a 0mod(a 3+a +1) = a 0 = 1a 1mod(a 3+a +1) = a 1a 2mod(a 3+a +1) = a 2a 3mod(a 3+a +1) = a +1a 4mod(a 3+a +1) = a 2+aa 5mod(a 3+a +1) = a 2+a 1+1a 6mod(a 3+a +1) = a 2+1a 7mod(a 3+a +1) = a 0a 8mod(a 3+a +1) = a 1用二进制数表示域元素得到表13-01所示的对照表表13-01 GF(23)域中与二进制代码对照表,P(x)=GF(23)域元素二进制对代码0(000)a 0(001)a 1(010)a 2(100)a 3(011)a 4(110)a 5(111)a 6(101)这样一来就建立了 GF(2J域中的元素与3位二进制数之间的一一对应关系。 用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的对应关系。在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。现仍 以 GF(23) 域中运算为例：加法例：a o+a 3 = 001 + 011 = 010 = a 1 减法例：与加法相同乘法例： a 5 a 4 = a (5+4)mod7 = a 2除法例： a 5/a 3 = a 2a 3/a 5 = a -2 = a (2+7) = a 5取对数： log(a 5) = 5这些运算的结果仍然在GF(23)域中。13.2.2 RS 的编码算法RS的编码就是计算信息码符多项式M(x)除以校验码生成多项式之后的余 数。在介绍之前需要说明一些符号。在GF(2m)域中，符号(n, k)RS的含义如下:mnkK=n k = 2tt表示符号的大小，如m = 8表示符号由8位二进制数组成 表示码块长度 表示码块中的信息长度 表示校验码的符号数 表示能够纠正的错误数目例如，(28, 24)RS码表示码块长度共28个符号，其中信息代码的长度为24, 检验码有4个检验符号。在这个由28个符号组成的码块中，可以纠正在这个码 块中出现的2个分散的或者2个连续的符号错误，但不能纠正3个或者3个以上 的符号错误。对一个信息码符多项式M(x), RS校验码生成多项式的一般形式为%)=冇(口和) “(13 2)式中，m是偏移量，通常取K = 0或K= 1,而(n-k)$2t (t为要校正的错误 0 0 0符号数) 。下面用两个例子来说明 RS 码的编码原理。例13.2设在GF(23)域中的元素对应表如表13-01所示。假设(6, 4)RS 码中的4个信息符号为，信息码符多项式M(x)为M(x) =mx3+ mx2 + m x + m (133)3210并假设RS校验码的2个符号为Q和Q ,的剩余多项式10R(x)为R(x) = Q(x)+ Q 这个多项式的阶次比 G(x) 的阶次少一阶。如果K = 1, t = 1,由式(13 2)导出的RS校验码生成多项式就为 0=-= (xa )(xa 2)(134)根据多项式的运算,由式(133)和式(134)可以得到mx5mx4mx3mx2QxQ = (x a )(x a 2)Q(x) 当用 x = a 和 x = a 2代入上式时,得到下面的方程组, m3 a5 + nij a4 + nij a3 + nj a2 + Qi(x + Qo = 01 tn3( a2)5 + tn a2)4 +( a2)3 + 吨 oc2)2 + Qia2 + Q = 0经过整理可以得到用矩阵表示的(6, 4)RS码的校验方程:HqxvJ = O校iJ总 / i* 1 厂(/尸 M 3尸 3尸 3)】1VQ = m3 m2 mi mQ Ql Qo .求解方程组就可得到校验符号：Q = nig a5 + 垃2 (X5 +(X0 + q a4Q = a + a? + m】a。+ g a?在读出时的校正子可按下式计算：q = nig + m2 口4十垃厲孑十口Q(x + Qql 巧=m3(a5)2 +a4)2 + ma3)2 + n( a2)2 + Qj a2 + Qo例133在例13.2中，如果K = 0, t = 1,由式(13 2)导出的RS校验 码生成多项式就为GW=n(x-C)z= (xa o)(xa 1) (13 5)根据多项式的运算,由(133)和(135)可以得到下面的方程组：jn4ni；24mi + g + Qi + QQ= m3 a5 -i-nij a4 -i-mj a3 -i-n a2 -I- Qj + Qo = 0方程中的a i也可看成符号的位置，此处i = 0, 1, 5。 求解方程组可以得到RS校验码的2个符号为Q和Q ,10Qi= ocmg + am? + ocmi + 区弓口 Qo=僅点十 厲4垃_|_ 厲现 (3_6)假定 m 为下列值：i信息符号m = a 0 = 0013m = a 6 = 1012m = a 3 = 0111m = a 2 = 1000校验符号Q = a 6 = 101 1Q = a 4 = 1100校正子s = 00s = 01代入(136)式可求得校验符号Q = a 6 = 101 1Q = a 4 = 110013.2.3 RS 码的纠错算法RS码的错误纠正过程分三步：(1)计算校正子(syndrome), (2)计算错误位 置，(3)计算错误值。现以例13.3为例介绍RS码的纠错算法。校正子使用下面的方程组来计算：巧=nig 口5十m：2 口4十了十g 厲？ + q鼻Qq为简单起见，假定存入光盘的信息符号 m 、m 、m 、 m 和由此产生的检验符 3210号Q、Q均为0，读出的符号为m 、m 、m 、m 、Q 和Q 。1 0321010如果计算得到的 s 和 s 不全为 0，则说明有差错，但不知道有多少个错，也 不知道错在什么位置和0错误1值。如果只有一个错误，则问题比较简单。假设错误 的位置为a，错误值为m，那么可通过求解下面的方程组：xx他=口得知错误的位置和错误值。如果计算得到 s = a 2和 s = a 5，可求得 a = a 3和 m = a 2，说明 m 出01xx1了错，它的错误值是a 2。校正后的m二m +m，本例中m=0。1 1x1如果计算得到s = 0，而s #0，那基本可断定至少有两个错误，当然出现 两个以上的错误不一定都是s = 0和s #0。如果出现两个错误，而又能设法找 到出错的位置，那么这两个错误也可以纠正。如已知两个错误m和m的位置a x1x2x1和 a ，那么求解方程组：x2叫+叫2 =閒1叫珥1 +叫疇2 =辺就可知道这两个错误值。CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed Solomon Product like Code，RSPC)就是采用上述方法导出的。13.3 CIRC 纠错技术光盘存储器和其它的存储器一样，经常遇到的错误有两种。一种是由于随机 干扰造成的错误，这种错误称随机错误。它的特点是随机的、孤立的，干扰过后 再读一次光盘，错误就可能消失。另一种错误是连续多位出错，或连续多个符号 出错，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大 片。这种错误称为突发错误。CIRC(Cross In terleaved Reed Solomon)纠错码综 合了交插、延时交插、交叉交插等技术，不仅能纠随机错误，而且对纠突发错误 特别有效。13.3.1 交插技术对纠错来说，分散的错误比较容易得到纠正，但出现一长串的错误时，就较 麻烦。正如我们读书看报，如果文中在个别地方出错，根据前后文就容易判断是 什么错。如果连续错好多字，就很难判断该处写的是什么。例如，用X表示出现的错字，一种错误形式为“独在异乡XXX,每逢佳节倍 思亲”，这是连续出现的错误，另一种错误形式为“独在异乡X异客，每X佳节 倍思X”，这是分散出现的错误。这两种错误形式相比，同样是3个错误，但人 们更容易更正后一种形式的错误，更正之后为“独在异乡为异客，每逢佳节倍思 亲”。这个道理很简单，把这种思想用在数字记录系统中对突发错误的更正非常有 效。在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片 错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交插 (in terleaving)技术。例如,3 个(5， 3)码块： B = (a a， a， P， P)12 ， 1010B =(b，b ，b ，Q ，Q)2 21010B = (c， c， c， R， R)3 21010连续排列：a a a P P2 1 0 1 0b b b Q Q2 10 10c c c R R2 10 10排成3行：aaaPP21010bbbQQ21010cccRR21010交插排列：a2b2c2a1b1c1a0b0c0P1Q1R1P0Q0R0连续错3个：a2b2c2a1b1c1a0XXXQ1R1P0Q0R0读出后重新排列：a2a1a0XP0b2b1XQ1Q0c2c1XR1R0从这个例子中可以看到，对连续排列，每个码块中只能出现一个错误才能纠 正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中， 每个码块可以纠正1个错误，总计可以纠正3个连续的错误。一般来说，如果有r个(n, k)码，排成rX n矩阵，按列交插后存储或传送, 读出或接收时恢复成原来的排列，若(n, k)码能纠正t个错误，那么这样交插后 就可以纠正rt个突发错误。13.3.2 交叉交插技术交叉交插(cross in terleaving)编码是交插的一种变型。在实际应用中， 也是一种重要的技术。现仍以简单的例子说明这种技术思想。(1) 用(5, 3)码编码器C生成的4个码块为：2B=(a a a P P)1 2 1 0 1 0B=(b b b Q Q)2 2 1 0 1 0B=(c c c R R)3 21010B=(d d d S S)4 21010(2) 交插后再用(6, 4)码编码器C生成5个码块为：1abc dTT222210abc dUU111110abcdVV000010PQRSWW111110PQRSXX 000010(3) 再交插，交插的码块数可以是2、3、4或5。以交插2个码块为例： aabbc c ddTUTUaPbQc RdS21212121110001010101(4) 最后一个码块不配对，可以和下一个码块配对。这种编码技术用了两个编码器C和C。对原码块进行编码得到(5,3)码块,2 1 2 交插后生成由4个符号组成的码块,码块中的符号是交叉存放的,然后再用(6, 4)编码器q去编码。有关CIRC详细的实现方法请参看文献7。CIRC首先应用在激光唱盘系统中。音频信号的采样率为44.1 kHz，而每次 采样有两个16比特的样本,一个来自左声道,一个来自右声道,每个样本用两 个GF(2Q域中的符号表示，因此每次采样共有4个符号。为了纠正可能出现的错误，每6次采样共24个符号构成1帧，称为匚帧(匚 Frame)。用一个称为C?的编码器对这24个符号产生4个Q校验符号：Q，Q】， Q和Q。24个声音数据加上4个Q校验符号共28个符号，用称为C编码器对这23128个符号产生4个P校验符号：P，P，P和P。28个符号加上4个P校验符 0123号共32个符号构成的帧称为F?帧(F Frame)。F帧加上1个字节(即1个符号) 的子码共33个符号构成的帧称为F帧(F Frame)。33在实际应用中可对前面介绍的交插技术略加修改，执行交插时不是交插包含 有k个校验符的码块，而是交插一个连续系列中的码符，这种交插技术称为延时 交插。延时交插之后还可用交叉技术，称为延时交叉交插技术。CD存储器中的 CIRC编码器采用了 4XF帧的延时交插方案。1帧延时交插可纠正连续4XF帧 的突发错误4XF帧的延时交插可纠正连续16XF帧突发错误，相当于大约2114XF帧的突发错误。1XF帧经过EFM编码后产生588位通道位。1位通道位的 33长度折合成0.277 “m的光道长度14XF帧突发错误长度相当于3(16X(24 + 4)/33X588X0.2772.2 mm 换句话说，CIRC能纠正在2.2 mm光道上连续存放的448个错误符号!相当于连 续224个汉字错误可以得到纠正。13.4 RSPC 码按 ISO/IEC10149 的规定， CD-ROM 扇区中的 ECC 码采用 GF(28) 域上的 RSPC 码产生172个字节的P校验符号和104个字节的Q校验符号。RS码采用本原多 项式P(x) = x8+ x4+x3 + x2 + 1和本原元a = (00000010)构造GF(28)域，这已经在上节作了介绍。第12章已经介绍了 CD-ROM的扇区结构。在每个扇区中，字节122075和 ECC域中的字节2076到2351共2340个字节组成1170个字(word)。每个字s(n) 由两个字节B组成，一个称为最高有效位字节MSB，另一个叫做最低有效位字节 LSB。第n个字由下面的字节组成，s(n) = MSBB(2n + 13) + LSBB(2n + 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 1169012 25(ISO/IEC1049)图 1302 RSPC 码计算用数据阵列矩阵中的元素是字。这个矩阵要把它想象成两个独立的矩阵才比较好理解和 分析，一个是由MSB字节组成的24X43矩阵，另一个是由LSB字节组成的24X43 矩阵。(1) P校验符号用(26, 24)RS码产生43列的每一列用矢量表示，记为V。每列有24个字节的数据再加2个字节 的 P 校验字节，用下式表示：s(43*0 + )&(43*1 +亿)s(43*2 + )巩)严 s(43MP + Np)s(43*22 + )s(43*23 + )s(43*24 + )s(43*25 + )其中：N = 0 ，1，2，42 pM = 0 ，1，2，25s(43*24+N )和 s(43*25+N )是 P 校验字节对这列字节计算得到的是两个P校验字节，称为P校验符号。两个P校验字节加到24行和25行的对应列上，这样构成了一个26X43的矩阵，并且满足方H X V = 0 其中 H 校验矩阵为P(2) Q校验符号用(45, 43)RS码产生增加P校验字节之后得到了一个26X43矩阵，该矩阵的对角线元素重新排 列后得到一个新的矩阵，其结构如图13-03所示。MQ012404142Q0Q10000000440088 064206860730111811441004300870131 068507290773111911452008601300147 072807720816112011463012901370217 077108150859112111474017202160260 0814085809021122114822094609901034 04700514055811401166NQ23098910331077 0513055706011141116724103210760002 0556060006441142116825107500010045 05990643068711431169(ISO/IEC 10149：1989)图13-03 Q校验符号计算用数据阵列每条对角线上的43个MSB字节和LSB字节组成的矢量记为V。V在26X43 矩阵中变成行矢量。第N行上的V矢量包含的字节如下： QQs(44*1 + 43*) s(44*2 + 43*27d) 疏 )s(AAMQ +43*咛吐 )成44*41 + 43*%)巩44*42 + 43*%)s(43*26 +s(44*26 +其中：N = 0，1，2，25 QM = 0，1，2，42 Qs(43*26+N)和s(44*25+N )和是Q校验字节V中的(44*M +43 *N)字节号运算结果要做mod(1118)运算。用(45, 43)RSQQQ码产生的两个Q校验字节放到对应V矢量的末端，并且满足下面的方程：QHX V = 0 其中H校验矩阵为Q_ 1 1 - 1 1 1珥=/ / - /应1(26, 24)RS码和(45, 43)RS码可以纠正出现在任何一行和任何一列上的一 个错误，并且能相当可靠地检测出行、列中的多重错误。如果在一个阵列中出现 多重错误，Reference Technology公司提供有一种名叫Layered ECC的算法， 它可以取消多重错误。它的核心思想是交替执行行纠错和列纠错。例如，假设错误分布如图13-04所示。ECC算法首先计算MSB矩阵和LSB矩 阵中每一行的校正子S (i = 0, 1，25),以及每一列的校正子S (j = 0, 1，, ricj44)。因为用(45, 43)RS码，所以每一个S和每一个S都有两个校正子分量。 如果s = 0,则说明第i行无错；如s =ri0,说明第jj行无错。ricj图 13-04 错码分布举例ECC算法首先纠正行1、3、17、19和22上分别只有一个的错误。这些错误 取消后就纠正列5、 9、 15和35上分别只有一个的错误。经过一次行列交替纠错 后，只剩下C 、C 、C 和C 这四个错误。再进行一次行列交替纠错后，4，25 7，20 7，259，20就可以消除全部错误。对于象下面这样分布的错误，ECC算法也可以纠正。因为RS码纠错算法本身包含找错误的位置和错误值，而错误位置已经由校 正子S 、S、S 和S、S确定，所以只剩下求错误值的问题。这个问r（ik） rir（im）cj c（jl）题在讨论RS码时已经解决。对CD-ROM存储器的数据，经CIRC校正后可以使以字节做单位的误码率小于 10-9,再经RSPC进行纠错后，字节误码率可以小于10-13,这样就满足了计算机要 求误码率小于 10-12的要求。练习与思考题1. CRC用于检测错误还是校正错误?2. 用自己的语言说明错误检测的思想。3. 什么叫做突发错误？4. 码块长度为n码块中的信息长度为k,问(n, k)RS码本身能纠正多少个 错误？5. 要纠正 1 个符号的错误,至少需要附加多少个校验符？6. 目前CD存储器中使用的CIRC编码技术能够纠正突发错误的最大长度是多 少(按汉字字符数估算)？参考文献和站点 ISO/IEC 908. Compact Disc Digital Audio System. 1987. ISO 9660. Volume and File structure of CD-ROM for Information Interchange. 1988. ISO/IEC 10149. Data Interchange on Read Only 120 mm Optical Data Disks(CD-ROM). 1989 Scott A.Vanstone and Paul C. van Oorcshot. An Introducton Error Correcting Codes with Application. Kluwer, Academic Publishers, 1989 Philips and Sony. System Description CD-ROM XA Compact Disk Read Only Memory extended Architecture. May, 1991 PhilipsandSonyCorporation.CD-IFullFunctionalSpecification. 1993.林福宗，陆达.多媒体与CD-ROM.北京：清华大学出版社，1995.3.