第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码的校验方程： 求解方程组就可得到校验符号： 在读出时的校正子可按下式计算：