第16章错误检测和校正 水水水水*水水水水冰客水水水水水水水水水水水客水水水水水水冰水水水水冰水水水水水水水水水水水水水冰水水水冰水水水水水水水水*水水冰水水水冰水 16.1cRC错误检测原理 16.2RS编码和纠错算法 16.2.1.GF(2)域 16.2.2RS的编码算法 16.2.3RS码的纠错算法 16.3CIRC纠错技术 16.3.1交插技术 16.3.2交叉交插技术 6.4RSPC码 练习与思考题 参考文献和站点 水冰水水求水水水水客水水水水冰求水水水水水求水水水冰客水客水水冰水水*水冰客水本水水水冰客水水水水水冰水水水水水水冰求*水冰冰客水水 光盘、磁盘和磁带一类的数据记录媒体一样,由于盘的制作材料的性能、盘制造生产技 术水平的限制、驱动器的性能以及使用不当等诸多原因,从盘上读出的数据不可能完全正确。 据有关厂家的测试和统计,一片未使用过的只读光盘,其原始误码率约为3×10-:沾有指 纹的盘的误码率约为6×10-;有伤痕的盘的误码率约为5×10-3。针对这种情况,激光盘存 储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种: (1)错误检测:采用CRC( Cyclic redundancy Code)检测读出数据是否有铑 (2)错误校正码:采用里德一索洛蒙码(Reed- Solomon code),简称为RS码,进行纠 错。RS码被认为是性能很好的纠错码 (3)交叉交插里德一索洛蒙码CIRC( Cross interleaved reed- Solomon code),这个码 的含义可理解为在用RS编译码前后,对数据进行交插处理和交叉处理。 对这些码的理论分析和计算有许多专著作了详尽的深入论述,对不需要开发纠错技术的 读者仅需要了解错误检测和校正的一些基本概念即可 16.1CRC错误检测原理 在纠错编码代数中,把以二进制数字表示的一个数据系列看成一个多项式。例如,二进 制数字序列10101111用多项式可以表示成: M(x)=a,x'+ax+asx+a4r+ax+a,"+a,x+aox =x7+x5+x3+x2+x1+1 式中的x表示代码的位置,或某个二进制数位的位置,x前面的系数a表示码的值。若a; 是一位二进制代码,则取值是0或1。M(x)称为信息代码多项式。 在模2多项式代数运算中定义的运算规则有 Ix+Ix=0 例如,模2多项式的加法和减法 +x+1 +x+1 )x3+x2+x 从这两个例子中可以看到,对于模2运算来说,代码多项式的加法和减法运算所得的结 果相同。所以在做代码多项式的减法时,可用做加法来代替做减法。 代码多项式的除法可按长除法做。例如
第16章 错误检测和校正 *************************************************************************** 16.1 CRC错误检测原理 16.2 RS编码和纠错算法 16.2.1. GF(2m )域 16.2.2 RS的编码算法 16.2.3 RS码的纠错算法 16.3 CIRC纠错技术 16.3.1 交插技术 16.3.2 交叉交插技术 16.4 RSPC码 练习与思考题 参考文献和站点 *************************************************************************** 光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘制造生产技 术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出的数据不可能完全正确。 据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为3×10－4；沾有指 纹的盘的误码率约为6×10－4；有伤痕的盘的误码率约为5×10－３。针对这种情况，激光盘存 储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种： (1) 错误检测：采用CRC(Cyclic Redundancy Code)检测读出数据是否有错。 (2) 错误校正码： 采用里德－索洛蒙码(Reed－Solomon Code)，简称为RS码，进行纠 错。RS码被认为是性能很好的纠错码。 (3) 交叉交插里德－索洛蒙码CIRC(Cross Interleaved Reed－Solomon Code), 这个码 的含义可理解为在用RS编译码前后，对数据进行交插处理和交叉处理。 对这些码的理论分析和计算有许多专著作了详尽的深入论述，对不需要开发纠错技术的 读者仅需要了解错误检测和校正的一些基本概念即可。 16.1 CRC错误检测原理 在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进 制数字序列10101111，用多项式可以表示成： 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 M (x) = a x + a x + a x + a x + a x + a x + a x + a x = 1 7 5 3 2 1 x + x + x + x + x + 式中的 i x 表示代码的位置，或某个二进制数位的位置， i x 前面的系数ai表示码的值。若ai 是一位二进制代码，则取值是0或1。 M (x) 称为信息代码多项式。 在模2多项式代数运算中定义的运算规则有： i i i i x x x x 1 1 1 1 0 − = + = 例如，模2多项式的加法和减法： 从这两个例子中可以看到，对于模2运算来说，代码多项式的加法和减法运算所得的结 果相同。所以在做代码多项式的减法时，可用做加法来代替做减法。 代码多项式的除法可按长除法做。例如：
16章错误检测和校正 xy +x+1 +1 如果一个k位的二进制信息代码多项式为M(x),再增加(n-k)位的校验码,那么增加 (n-A位之后,信息代码多项式在新的数据块中就表示成x”M(x),如图16-01所示。 位 k n-1)位 1213…k1kk+… 2M(x) -R(x) 新的信息代码多项式 校验位 图16-01信息代码结构 如果用一个校验码生成多项式G(x)去除代码多项式xM(x),得到的商假定为 Q(x),余式为R(x),则可写成 G(r)O(r)+R(r) G(x) x-M(x)=o(xG(x)+R(x) 因为模2多项式的加法和减法运算结果相同,所以又可把上式写成: M(x)+R(x)=o(x)G(x) G(x)称为校验码生成多项式。从该式中可以看到,代表新的代码多项式xn-M(x)+R(x) 是能够被校验码生成多项式G(x)除尽的,即它的余项为0。 例如,CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是 G(x) 若用二进制表示,则为 G(x)=10001000000060 11021(H) 假定要写到盘上的信息代码M(x)为 M(x)=4D6F746F(H 由于增加了2个字节共16位的校验码,所以信息代码变成x°M(x):4D6F746F00() C检验码计算如下
第16章 错误检测和校正 2 如果一个k位的二进制信息代码多项式为 M (x) ，再增加(n－k)位的校验码，那么增加 (n－k)位之后，信息代码多项式在新的数据块中就表示成 x M (x) n−k ，如图16-01所示。 图16-01 信息代码结构 如果用一个校验码生成多项式 G(x) 去除代码多项式 x M (x) n−k ，得到的商假定为 Q(x) ，余式为 R(x) ，则可写成 ( ) ( ) ( ) ( ) ( ) G x R x Q x G x M x x n k = + − x M(x) Q(x)G(x) R(x) n k = + − 因为模2多项式的加法和减法运算结果相同，所以又可把上式写成： x M(x) R(x) Q(x)G(x) n k + = − G(x) 称为校验码生成多项式。从该式中可以看到，代表新的代码多项式 x M(x) R(x) n k + − 是能够被校验码生成多项式 G(x) 除尽的，即它的余项为0。 例如，CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是 ( ) 1 16 12 5 G x = x + x + x + 若用二进制表示，则为 G(x) =10001000000100001(B) =11021(H) 假定要写到盘上的信息代码 M (x) 为 M (x) =4D6F746F (H) 由于增加了2个字节共16位的校验码，所以信息代码变成 ( ) 16 x M x : 4D6F746F0000(H)。 CRC检验码计算如下：
16章错误检测和校正 49F99B14 11021)4D6F746F000 44084 96734 99129 FFlEF 9039F 99129 92B60 BA490 15FB0 11021 2字节的4910 CRC校验码 B994 两数相除的结果,其商可不必关心,其余数为B994(H)就是CRC校验码。把信息代码写到 盘上时,将原来的信息代码和CRC码一起写到盘上。在这个例子中,写到盘上的信息代码和 CRC码是4D6F746FB994, B994 信息代码R码 这个码是能被11021(H除尽的。 从盘上把这块数据读出时,用同样的CRC码生成多项式去除这块数据,相除后得到的两 种可能结果是:①余数为0,表示读出没有出现错误;②余数不为0,表示读出有错 CD-ROM中也采用了相同的CRC检错。CD-ROM扇区方式01中,有一个4字节共32位的EDC字 域,它就是用来存放CRC码。不过,CD-ROM采用的CRC校验码生成多项式与软磁盘采用的生成 多项式不同,它是一个32阶的多项式 P(x)=( 计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节,即字节0~ 2063共2064个字节。在EDC中存放的CRC码的次序如下 x6-x3 x-x 字节号:2064 2065 2066 2067 16.2RS编码和纠错算法 16.2.1.GF(2域 RS(Reed- Solomon)码是在伽罗华域( Galois field,GF)中运算的,因此在介绍RS码之前 先简要介绍一下伽罗华域。 CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2)=GF(2)中的元素或称符号 GF(2)表示域中有256个元素,除0,1之外的254个元素由本原多项式P(x)生成。本原多项式 P(x)的特性是 x2得到的余式等于0。 CD-ROMA用来构造GF(2)域的P(x)是 P(x) P +x+x+x+ 而GF(2)域中的本原元素为 (00000010
第16章 错误检测和校正 3 两数相除的结果，其商可不必关心，其余数为B994(H)就是CRC校验码。把信息代码写到 盘上时，将原来的信息代码和CRC码一起写到盘上。在这个例子中，写到盘上的信息代码和 CRC码是4D6F746F B994, 4D6F746F B994 信息代码 CRC码 这个码是能被11021(H)除尽的。 从盘上把这块数据读出时，用同样的CRC码生成多项式去除这块数据，相除后得到的两 种可能结果是：①余数为0，表示读出没有出现错误；②余数不为0，表示读出有错。 CD-ROM中也采用了相同的CRC检错。CD-ROM扇区方式01中，有一个4字节共32位的EDC字 域，它就是用来存放CRC码。不过，CD-ROM采用的CRC校验码生成多项式与软磁盘采用的生成 多项式不同，它是一个32阶的多项式, ( ) ( 1)( 1) 16 15 2 16 2 P x = x + x + x + x + x + x + 计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节0～ 2063共2064个字节。在EDC中存放的CRC码的次序如下： EDC： x 24－x 31 x 16－x 23 x 8－x 15 x 0－x 7 字节号： 2064 2065 2066 2067 16.2 RS编码和纠错算法 16.2.1. GF(2m )域 RS(Reed-Solomon)码是在伽罗华域(Galois Field，GF)中运算的，因此在介绍RS码之前 先简要介绍一下伽罗华域。 CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m ) = GF(28 )中的元素或称符号。 GF(28 )表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式 P(x) 的特性是 ( ) 1 2 1 P x x m + − 得到的余式等于0。CD-ROM用来构造GF(2 8 )域的 P(x) 是 ( ) 1 8 4 3 2 P x = x + x + x + x + (13－1) 而GF(28 )域中的本原元素为 α = (0 0 0 0 0 0 1 0)
16章错误检测和校正 下面以一个较简单例子说明域的构造。 [例16.1构造GF(2)域的本原多项式P(x)假定为 P(x)=x3+x+1 a定义为P(x)=0的根,即 和 GF(2)中的元素可计算如下 mod(a+a+1) mod(a2+a+1)=a0=1 mod (a+a+1) mod(a3+a+1)=a+1 od(a23+a+1) mod(a2+a+1)=a2+a2+1 mod( a mod(a+a +1)=a (a2+a+1) 用二进制数表示域元素得到表16-01所示的对照表 表16-01GF(2)域中与二进制代码对照表,P(x)=x3+x+1 GF(2)域元素 二进制对代码 aaa (10 (01 0 (010 (110) aaa (111) 这样一来就建立了GF(2)域中的元素与3位二进制数之间的一一对应关系。用同样的方 法可建立GF(②2)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过程 中,加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(2)域中运算为例 加法例:a°+a3=001+011 010 减法例:与加法相同 乘法例:a5·a4=a6+0mn 除法例:a5/a3=a2 (-2+7) 取对数:1og(a5)=5 这些运算的结果仍然在GF(2)域中
第16章 错误检测和校正 4 下面以一个较简单例子说明域的构造。 [例16.1] 构造GF(23 )域的本原多项式 P(x) 假定为 ( ) 1 3 P x = x + x + α定义为 P(x) = 0的根，即 α3＋α＋1 = 0 和 α3 = α＋1 GF(23 )中的元素可计算如下： 0 mod(α3＋α＋1) = 0 α 0 mod(α 3＋α＋1) = α 0 = 1 α1 mod(α3＋α＋1) = α1 α 2 mod(α 3＋α＋1) = α 2 α3 mod(α3＋α＋1) = α＋1 α 4 mod(α 3＋α＋1) = α 2＋α α5 mod(α3＋α＋1) = α2＋α1＋1 α 6 mod(α 3＋α＋1) = α 2＋1 α7 mod(α3＋α＋1) = α0 α 8 mod(α 3＋α＋1) = α 1 …… 用二进制数表示域元素得到表16-01所示的对照表 表16-01 GF(23 )域中与二进制代码对照表, ( ) 1 3 P x = x + x + GF(23 )域元素 二进制对代码 0 (000) α0 (001) α 1 (010) α2 (100) α 3 (011) α4 (110) α5 (111) α6 (101) 这样一来就建立了GF(23 )域中的元素与3位二进制数之间的一一对应关系。用同样的方 法可建立GF(28 )域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过程 中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(23 )域中运算为例： 加法例：α0＋α3 = 001＋011 = 010 = α1 减法例：与加法相同 乘法例：α5·α4 = α (5＋4) mod7 = α 2 除法例：α5 /α 3 = α 2 α 3 /α 5 = α －2 = α (－2＋7) = α5 取对数：log(α 5 ) = 5 这些运算的结果仍然在GF(23 )域中
16章错误检测和校正 16.2.2RS的编码算法 RS的编码就是计算信息码符多项式M(x)除以校验码生成多项式G(x)之后的余数← 在介绍之前需要说明一些符号。在GF(2)域中,符号(n,kRS的含义如下 M 表示符号的大小,如m=8表示符号由8位二进制数组成 表示码块长度 表示码块中的信息长度 n-k=2t表示校验码的符号数 表示能够纠正的错误数目 例如,(28,24)RS码表示码块长度共28个符号,其中信息代码的长度为24,检验码有4 个检验符号。在这个由28个符号组成的码块中,可以纠正在这个码块中出现的2个分散的或 者2个连续的符号错误,但不能纠正3个或者3个以上的符号错误 对一个信息码符多项式M(x),RS校验码生成多项式的一般形式为 (x)=1(x (13-2) 式中,A是偏移量,通常取而=0或=1,而(n-k≥2t(t为要校正的错误符号数)。 下面用两个例子来说明RS码的编码原理 [例16.2]设在GF(2)域中的元素对应表如表16-01所示。假设(6,4)RS码中的4个信息 符号为m、、m和m,信息码符多项式M(x)为 M(x)=m3x+m2x+m x+mo (13-3) 并假设RS校验码的2个符号为Q和Q, M(x) M(x) 的剩余多项式R(x)为 G(x) R(x)=Qx+ Qo 这个多项式的阶次比G(x)的阶次少一阶 如果K=1,t=1,由式(13-2)导出的RS校验码生成多项式就为 x)=l(x-ako*)=(x-a)x-a) (13-4) 根据多项式的运算,由式(13-3)和式(13-4)可以得到 m3.x+m2 x+mix+mox+Qix+Qo=(x-a)(x-a)Q(x) 当用x=a和x=a2代入上式时,得到下面的方程组, m3 a+m a+mia+mo a*+Qla +Q0=0 mnx(a252+mg∞24+m1(a23+m(a2)2+Q2a2+Q=0 经过整理可以得到用矩阵表示的(6,4)RS码的校验方程: HoyO=0 0(a2)5(a2)()3(a2)2(a2) 求解方程组就可得到校验符号: Qo=m3a+ma flee kma Q1-m3a5+my a5+m,ao 在读出时的校正子可按下式计算:
第16章 错误检测和校正 5 16.2.2 RS的编码算法 RS的编码就是计算信息码符多项式 M (x) 除以校验码生成多项式 G(x) 之后的余数。 在介绍之前需要说明一些符号。在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个以上的符号错误。 对一个信息码符多项式 M (x) ，RS校验码生成多项式的一般形式为 − = + = − 1 0 ( ) ( ) 0 K i K i G x x (13－2) 式中，K0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)≥2t (t为要校正的错误符号数)。 下面用两个例子来说明RS码的编码原理。 [例16.2] 设在GF(23 )域中的元素对应表如表16-01所示。假设(6，4)RS码中的4个信息 符号为m3、m2、m1和m0，信息码符多项式 M (x) 为 1 0 2 2 3 M (x) = m3 x + m x + m x + m (13－3) 并假设RS校验码的2个符号为Q1和Q0， ( ) ( ) ( ) ( ) 2 G x M x x G x M x x n k = − 的剩余多项式 R(x) 为 Q1 Q0 R(x) = x + 这个多项式的阶次比 G(x) 的阶次少一阶。 如果K0 = 1，t = 1，由式(13－2)导出的RS校验码生成多项式就为 − = + = − 1 0 ( ) ( ) 0 K i K i G x x = ( )( ) 2 x − x − (13－4) 根据多项式的运算，由式(13－3)和式(13－4)可以得到 m3x 5＋m2x 4＋m1x 3＋m0x 2＋Q1x＋Q0 = (x－α)(x－α2 )Q(x) 当用x = α和x = α2代入上式时，得到下面的方程组， 经过整理可以得到用矩阵表示的(6，4)RS码的校验方程： 求解方程组就可得到校验符号： 在读出时的校正子可按下式计算：
16章错误检测和校正 + 1=ma(a5)2+m(a4+m1(x32+m0(a2)2+Q1a2+Q [例16.3]在例16.2中,如果K。=0,t=1,由式(13-2)导出的RS校验码生成多项式 就为 G(x)=I(x-ako+)=(x-aXx-a) 13-5) 根据多项式的运算,由(13-3)和(13-5)可以得到下面的方程组: m+m2+m1+m+Q1+Q0=0 Q1a2+Q0=0 方程中的a也可看成符号的位置,此处i=0,1,…,5。 求解方程组可以得到RS校验码的2个符号为Q和Q0 Q0=a3m+am2+a·m1+ (13-6) 假定m为下列值 信息符号画=a。=001 a6=101 011 100 校验符号Q=a°=101 110 校正子|s0=0 代入(13-6)式可求得校验符号: Q o 110 16.2.3RS码的纠错算法 RS码的错误纠正过程分三步:(1)计算校正子( syndrome),(2)计算错误位置,(3)计算 错误值。现以例16.3为例介绍RS码的纠错算法 校正子使用下面的方程组来计算 为简单起见,假定存入光盘的信息符号m、m、m、m和由此产生的检验符号Q、Q均为 0,读出的符号为m′、m′、m′、m′、Q1′和Q 果计算得到的s和s不全为0,则说明有差错,但不知道有多少个错,也不知道错在什 么位置和错误值。如果只有一个错误,则问题比较简单。假设错误的位置为α,错误值为 那么可通过求解下面的方程组 So=mx 得知错误的位置和错误值 如果计算得到S=a2和s1=a5,可求得ax=a3和m=a2,说明m出了错,它的错 误值是a2。校正后的m=m+m,本例中m=0。 如果计算得到so=0,而s1≠0,那基本可断定至少有两个错误,当然出现两个以上的错 误不一定都是so=0和s1≠0。如果出现两个错误,而又能设法找到出错的位置,那么这两个 错误也可以纠正。如已知两个错误m21和m2的位置ax和a2,那么求解方程组:
第16章 错误检测和校正 6 [例16.3] 在例16.2中，如果K0 = 0，t = 1，由式(13－2)导出的RS校验码生成多项式 就为 − = + = − 1 0 ( ) ( ) 0 K i K i G x x = ( )( ) 0 1 x − x − (13－5) 根据多项式的运算，由(13－3)和(13－5)可以得到下面的方程组： 方程中的αi 也可看成符号的位置，此处i = 0，1，…，5。 求解方程组可以得到RS校验码的2个符号为Q1和Q0， (13－6) 假定mi为下列值： 信息符号 m3 = α0 = 001 m2 = α 6 = 101 m1 = α 3 = 011 m0 = α 2 = 100 校验符号 Q1 = α6 = 101 Q0 = α4 = 110 校正子 s0 = 0 s1 = 0 代入(13－6)式可求得校验符号： Q1 = α6 = 101 Q0 = α4 = 110 16.2.3 RS码的纠错算法 RS码的错误纠正过程分三步： (1)计算校正子(syndrome)，(2)计算错误位置，(3)计算 错误值。现以例16.3为例介绍RS码的纠错算法。 校正子使用下面的方程组来计算： 为简单起见，假定存入光盘的信息符号m3、m2、m1、m0和由此产生的检验符号Q1、Q0均为 0，读出的符号为m3′、m2′、m1′、m0′、Q1′和Q0′。 如果计算得到的s0和s1不全为0，则说明有差错，但不知道有多少个错，也不知道错在什 么位置和错误值。如果只有一个错误，则问题比较简单。假设错误的位置为αx，错误值为 mx，那么可通过求解下面的方程组： 得知错误的位置和错误值。 如果计算得到s0 = α2和s1 = α5，可求得αx = α3和mx = α2，说明m1出了错，它的错 误值是α2。校正后的m1 = m1′＋mx ，本例中m1=0。 如果计算得到s0 = 0，而s1≠0，那基本可断定至少有两个错误，当然出现两个以上的错 误不一定都是s0 = 0和s1≠0。如果出现两个错误，而又能设法找到出错的位置，那么这两个 错误也可以纠正。如已知两个错误 mx1 和 mx2 的位置 x1 和 x2 ，那么求解方程组：
16章错误检测和校正 1m1(%n+mn2(%2=81 就可知道这两个错误值。 CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码〔 Reed solomon Product-1ike code,RSPC)就是采用上述方法导出的 16.3CIRC纠错技术 光盘存储器和其它的存储器一样,经常遇到的错误有两种。一种是由于随机干扰造成的 错误,这种错误称随机错误。它的特点是随机的、孤立的,干扰过后再读一次光盘,错误就 可能消失。另一种错误是连续多位出错,或连续多个符号出错,如盘片的划伤、沾污或盘本 身的缺陷都可能出现这种错误,一错就错一大片。这种错误称为突发错误。CIRC( Cross Interleaved Reed Solomon)纠错码综合了交插、延时交插、交叉交插等技术,不仅能纠随 机错误,而且对纠突发错误特别有效。 16.3.1交插技术 对纠错来说,分散的错误比较容易得到纠正,但出现一长串的错误时,就较麻烦。正如 我们读书看报,如果文中在个别地方出错,根据前后文就容易判断是什么错。如果连续错好 多字,就很难判断该处写的是什么。 例如,用X表示出现的错字,一种错误形式为“独在异乡XX,每逢佳节倍思亲”,这是 连续出现的错误,另一种错误形式为“独在异乡X异客,每X佳节倍思X”,这是分散出现的 错误。这两种错误形式相比,同样是3个错误,但人们更容易更正后一种形式的错误,更正 之后为“独在异乡为异客,每逢佳节倍思亲”。 这个道理很简单,把这种思想用在数字记录系统中对突发错误的更正非常有效。在光盘 上记录数据时,如果把本该连续存放的数据错开放,那么当出现一片错误时,这些错误就分 散到各处,错误就容易得到纠正,这种技术就称为交插( interleaving)技术。例如 水水本水水水水水冰水水水冰水水水冰*水水水水水水冰冰水水水冰水水水冰水冰客水水水水客水水水客水冰客水水水客*水冰水水水水水水水水水水 3个(5,3)码块:B1=(a,a1,a,P1,Po) B2=(b2,b1,bo,Q1,Q) B3=(c2,c1,co,R1,R) 连续排列: b2 排成3行: ao pi Po b2 b bo Q Qo C2 Ci Co ri Ro 交插排列 ao bo c 连续错3个: Cr ao xx xQ1, Po Qo Ro 读出后重新排列:[ a2 ar ao X po b: brx Q, QoC2 CI X R, Ro *求水冰水水水求水冰客水水水客水冰本*水冰水水水率水冰*水水冰水水水冰水水水水水水客*水水水客水水水水水冰水水半水水水水客水冰客 从这个例子中可以看到,对连续排列,每个码块中只能出现一个错误才能纠正。而交插 记录后,读出的3个连续错误经还原后可把它们分散到3个码块中,每个码块可以纠正1个错 误,总计可以纠正3个连续的错误 般来说,如果有r个(m,k码,排成rXn矩阵,按列交插后存储或传送,读出或接收 时恢复成原来的排列,若(n,A)码能纠正t个错误,那么这样交插后就可以纠正rt个突发错
第16章 错误检测和校正 7 就可知道这两个错误值。 CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed Solomon Product－like Code，RSPC)就是采用上述方法导出的。 16.3 CIRC纠错技术 光盘存储器和其它的存储器一样，经常遇到的错误有两种。一种是由于随机干扰造成的 错误，这种错误称随机错误。它的特点是随机的、孤立的，干扰过后再读一次光盘，错误就 可能消失。另一种错误是连续多位出错，或连续多个符号出错，如盘片的划伤、沾污或盘本 身的缺陷都可能出现这种错误，一错就错一大片。这种错误称为突发错误。CIRC(Cross Interleaved Reed Solomon)纠错码综合了交插、延时交插、交叉交插等技术，不仅能纠随 机错误，而且对纠突发错误特别有效。 16.3.1 交插技术 对纠错来说，分散的错误比较容易得到纠正，但出现一长串的错误时，就较麻烦。正如 我们读书看报，如果文中在个别地方出错，根据前后文就容易判断是什么错。如果连续错好 多字，就很难判断该处写的是什么。 例如，用X表示出现的错字，一种错误形式为“独在异乡XXX，每逢佳节倍思亲”，这是 连续出现的错误，另一种错误形式为“独在异乡X异客，每X佳节倍思X”，这是分散出现的 错误。这两种错误形式相比，同样是3个错误，但人们更容易更正后一种形式的错误，更正 之后为“独在异乡为异客，每逢佳节倍思亲”。 这个道理很简单，把这种思想用在数字记录系统中对突发错误的更正非常有效。在光盘 上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分 散到各处，错误就容易得到纠正，这种技术就称为交插(interleaving)技术。例如， ************************************************************************** 3个(5，3)码块： B1 = (a2，a1，a0，P1，P0) B2 = (b2，b1，b0，Q1，Q0) B3 = (c2，c1，c0，R1，R0) 连续排列： a2 a1 a0 P1 P0 b2 b1 b0 Q1 Q0 c2 c1 c0 R1 R0 排成3行： a2 a1 a0 P1 P0 b2 b1 b0 Q1 Q0 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个连续的错误。 一般来说，如果有r个(n，k)码，排成r×n矩阵，按列交插后存储或传送，读出或接收 时恢复成原来的排列，若(n，k)码能纠正t个错误，那么这样交插后就可以纠正rt个突发错 误
16章错误检测和校正 16.3.2交叉交插技术 交叉交插( cross- interleaving)编码是交插的一种变型。在实际应用中,也是一种重 要的技术。现仍以简单的例子说明这种技术思想。 *水本事水水水半水求水*水水水客水水水水水本水水*水冰水*本水水水水客水水水水*水水水水水冰水客水水冰水水水水水水水水水本事水水水半水客* (1)用(5,3)码编码器C2生成的4个码块为 B, =(a2 a, ao P Po) B2 (b 2 b bo Q1 Qo (c2 CI co ri ro (2)交插后再用(6,4)码编码器C生成5个码块为 b2 c2 d2 t b i c d u uo bo do v vo P, Qu P。Q cRR XI Xo 3)再交插,交插的码块数可以是2、3、4或5。以交插2个码块为例 az a b2 bi c2 c d, d t u to uo ao p bo Q co ri do si.. (4)最后一个码块不配对,可以和下一个码块配对 冰事水冰水水冰水水水冰客水客水水冰客水水水客水水水水水冰水水水客水水水半客水冰水求水水客水水冰*水水水水水冰水水水冰本水水客水水冰客 这种编码技术用了两个编码器C2和C1。C2对原码块进行编码得到(5,3)码块,交插后生 成由4个符号组成的码块,码块中的符号是交叉存放的,然后再用(6,4)编码器C去编码 有关CIRC详细的实现方法请参看文献[7] CIRC首先应用在激光唱盘系统中。音频信号的采样率为44.1kHz,而每次采样有两个16 比特的样本,一个来自左声道,一个来自右声道,每个样本用两个GF(2)域中的符号表示, 因此每次采样共有4个符号。 为了纠正可能出现的错误,每6次采样共24个符号构成1帧,称为F帧(F1- Frame)。用一 个称为C的编码器对这24个符号产生4个Q校验符号:Q,Q1,Q2和Q3。24个声音数据加上4个 Q校验符号共28个符号,用称为C编码器对这28个符号产生4个P校验符号:P0,P1,P2和P3 28个符号加上4个P校验符号共32个符号构成的帧称为F2帧(F2- Frame)。F2帧加上1个字节(即 1个符号)的子码共33个符号构成的帧称为F帧(F3- Frame)。 在实际应用中可对前面介绍的交插技术略加修改,执行交插时不是交插包含有k个校验 符的码块,而是交插一个连续系列中的码符,这种交插技术称为延时交插。延时交插之后还 可用交叉技术,称为延时交叉交插技术。CD存储器中的CIRC编码器采用了4×F帧的延时交 插方案。1帧延时交插可纠正连续4×F1帧的突发错误。4×F2帧的延时交插可纠正连续16×F1 帧突发错误,相当于大约14×F帧的突发错误。1×F3帧经过EFM编码后产生588位通道位 位通道位的长度折合成0.277μm的光道长度。14×F3帧突发错误长度相当于 [(16×(24+4))/33]×588×0.277≈2.2mm 换句话说,CIRC能纠正在2.2m光道上连续存放的448个错误符号!相当于连续224个汉字错 误可以得到纠正 16.4RSPC码 按ISO/IEC10149的规定,CD-ROM扇区中的ECC码采用GF(2)域上的RSPC码产生172个字节 的P校验符号和104个字节的Q校验符号。RS码采用本原多项式
第16章 错误检测和校正 8 16.3.2 交叉交插技术 交叉交插(cross－interleaving)编码是交插的一种变型。在实际应用中，也是一种重 要的技术。现仍以简单的例子说明这种技术思想。 ************************************************************************** (1) 用(5，3)码编码器C2生成的4个码块为: B1 = (a2 a1 a0 P1 P0) B2 = (b2 b1 b0 Q1 Q0) B3 = (c2 c1 c0 R1 R0) B4 = (d2 d1 d0 S1 S0) (2) 交插后再用(6，4)码编码器C1生成5个码块为: a2 b2 c2 d2 T1 T0 a1 b1 c1 d1 U1 U0 a0 b0 c0 d0 V1 V0 P1 Q1 R1 S1 W1 W0 P0 Q0 R0 S0 X1 X0 (3) 再交插，交插的码块数可以是2、3、4或5。以交插2个码块为例： a2 a1 b2 b1 c2 c1 d2 d1 T1 U1 T0 U0 a0 P1 b0 Q1 c0 R1 d0 S1 … (4) 最后一个码块不配对，可以和下一个码块配对。 ************************************************************************** 这种编码技术用了两个编码器C2和C1。C2对原码块进行编码得到(5，3)码块，交插后生 成由4个符号组成的码块，码块中的符号是交叉存放的，然后再用(6，4)编码器C1去编码。 有关CIRC详细的实现方法请参看文献[7]。 CIRC首先应用在激光唱盘系统中。音频信号的采样率为44.1 kHz，而每次采样有两个16 比特的样本，一个来自左声道，一个来自右声道，每个样本用两个GF(28 )域中的符号表示， 因此每次采样共有4个符号。 为了纠正可能出现的错误，每6次采样共24个符号构成1帧，称为F1帧(F1－Frame)。用一 个称为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帧(F2－Frame)。F2帧加上1个字节(即 1个符号)的子码共33个符号构成的帧称为F3帧(F3－Frame)。 在实际应用中可对前面介绍的交插技术略加修改，执行交插时不是交插包含有k个校验 符的码块，而是交插一个连续系列中的码符，这种交插技术称为延时交插。延时交插之后还 可用交叉技术，称为延时交叉交插技术。CD存储器中的CIRC编码器采用了4×F1帧的延时交 插方案。1帧延时交插可纠正连续4×F1帧的突发错误。4×F2帧的延时交插可纠正连续16×F1 帧突发错误，相当于大约14×F3帧的突发错误。1×F3帧经过EFM编码后产生588位通道位。1 位通道位的长度折合成0.277μm的光道长度。14×F3帧突发错误长度相当于 ［(16×(24＋4))/33］×588×0.277≈2.2 mm 换句话说，CIRC能纠正在2.2 mm光道上连续存放的448个错误符号! 相当于连续224个汉字错 误可以得到纠正。 16.4 RSPC码 按ISO/IEC10149的规定，CD-ROM扇区中的ECC码采用GF(28 )域上的RSPC码产生172个字节 的P校验符号和104个字节的Q校验符号。RS码采用本原多项式
16章错误检测和校正 P(x)=x+x+x+x2+1 和本原元 a=(00000010) 构造GF(②)域,这已经在上节作了介绍 第12章已经介绍了CD-ROM的扇区结构。在每个扇区中,字节12~2075和EC域中的字节 2076到2351共2340个字节组成1170个字(word)。每个字s()由两个字节B组成,一个称为最 高有效位字节MSB,另一个叫做最低有效位字节LSB。第n个字由下面的字节组成, s(n)=MSB[B(2n+13]+LSB[B(2n+12] 其中n=0,1,2,…,1169 从字节12开始到字节2075共2064个字节组成的数据块排列成24×43的矩阵,如图16-02 所示
第16章 错误检测和校正 9 ( ) 1 8 4 3 2 P x = x + x + x + x + 和本原元 α = (00000010) 构造GF(28 )域，这已经在上节作了介绍。 第12章已经介绍了CD-ROM的扇区结构。在每个扇区中，字节12～2075和ECC域中的字节 2076到2351共2340个字节组成1170个字(word)。每个字s(n)由两个字节B组成，一个称为最 高有效位字节MSB，另一个叫做最低有效位字节LSB。第n个字由下面的字节组成， s(n) = MSB[B(2n +13] + LSB[B(2 n +12] 其中n = 0，1，2，…，1169。 从字节12开始到字节2075共2064个字节组成的数据块排列成24×43的矩阵，如图16-02 所示
16章错误检测和校正 0 0010002…· 00410042 1op4360440045 00840085 HEADER 2op8600879088 01270128 用户数据 220p4609470948 0980988部分辅助数据 24103210331034 10731074 P-校验 25107510761077…… 11161117 26111811191120 1143 Q-校验 27114411451146 1169 (IS0/IEC1049) 图16—02RSPC码计算用数据阵列 矩阵中的元素是字。这个矩阵要把它想象成两个独立的矩阵才比较好理解和分析,一个 是由MSB字节组成的24×43矩阵,另一个是由LSB字节组成的24×43矩阵 1)P校验符号用(26,24)RS码产生 43列的每一列用矢量表示,记为V。每列有24个字节的数据再加2个字节的P校验字节, 用下式表示 s(43*0+Nn) S(43*1+N) (43*2+Nn) s(43*Mp+N S(43*22+N) S(43*23+N) (43*24+Nn) (43*25+N 其中: s(43*24+N)和s(43*25+N)是P校验字节 对这列字节计算得到的是两个P校验字节,称为P校验符号。两个P校验字节加到24行和 25行的对应列上,这样构成了一个26×43的矩阵,并且满足方程 H 其中H校验矩阵为
第16章 错误检测和校正 10 NP 0 1 2 3 41 42 0 000 0001 0002 … … … 0041 0042 1 0043 0044 0045 … … … 0084 0085 HEADER 2 0086 0087 0088 … … … 0127 0128 + P Q 用户数据 ＋ MP 22 0946 0947 0948 … … … 0987 0988 部分辅助数据 23 0989 0990 0991 … … … 1030 1031 24 1032 1033 1034 1073 1074 P-校验 25 1075 1076 1077 … … … 1116 1117 26 1118 1119 1120 … 1143 Q-校验 27 1144 1145 1146 … 1169 0 1 2 … 25 (ISO /IEC1049) 图16－02 RSPC码计算用数据阵列 矩阵中的元素是字。这个矩阵要把它想象成两个独立的矩阵才比较好理解和分析，一个 是由MSB字节组成的24×43矩阵，另一个是由LSB字节组成的24×43矩阵。 (1) P校验符号用(26，24)RS码产生 43列的每一列用矢量表示，记为Vp。每列有24个字节的数据再加2个字节的P校验字节， 用下式表示： + + + + + + + + = (43 25 ) (43 24 ) (43 23 ) (43 22 ) ( ) (43 ) ( ) (43 2 ) (43 1 ) (43 0 ) p p p p P p p p p s N s N s N s N s s M N s s N s N s N Vp 其中： N p = 0，1，2，……，42 M p = 0，1，2，……，25 (43 24 ) Np s + 和 (43 25 ) N p s + 是P校验字节 对这列字节计算得到的是两个P校验字节，称为P校验符号。两个P校验字节加到24行和 25行的对应列上，这样构成了一个26×43的矩阵，并且满足方程 HP VP ＝ 0 其中HP校验矩阵为 = 1 1 1 1 1 1 25 24 2 1 Hp
