第16章错误检测和校正

第16章错误检测和校正2/3/2023116.1CRC错误检测原理在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列10101111，用多项式可以表示成：式中的xi表示代码的位置，或某个二进制数位的位置，xi前面的系数ai表示码的值。若ai是一位二进制代码，则取值是0或1。称M(x)为信息代码多项式。

=2/3/20232在模2多项式代数运算中定义的运算规则有：例如，模2多项式的加法和减法：****结论：对于模2运算来说，代码多项式的加法和减法运算所得的结果相同。在做代码多项式的减法时，可用做加法来代替做减法。2/3/20233代码多项式的除法可按长除法做。例如2/3/20234如果一个k位的二进制信息代码多项式为M(x)，再增加(n－k)位的校验码，那么增加(n－k)位之后，信息代码多项式在新的数据块中就表示成xn-kM(x)，如图16-01所示。图16-01信息代码结构(n－k)(n－k)2/3/20235如果用一个校验码生成多项式G(x)去除代码多项式，得到的商假定为Q(x)，余式为R(x)，则可写成因为模2多项式的加法和减法运算结果相同，所以又可把上式写成：

G(x)称为校验码生成多项式。从该式中可以看到，代表新的代码多项式xn-kM(x)+R(x)是能够被校验码生成多项式除尽的，即它的余项为0。

2/3/20236例如，CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是: G(x)=x16+x12+x5+1若用二进制表示，则为: G(x)=10001000000100001(B) =11021(H)假定要写到盘上的信息代码M(x)为 M(x)=4D6F746F(H)由于增加了2个字节共16位的校验码，所以信息代码变成x16M(x):4D6F746F0000(H)。2/3/20237CRC检验码计算如下：两数相除的结果，其商可不必关心，其余数为B994(H)就是CRC校验码。把信息代码写到盘上时，将原来的信息代码和CRC码一起写到盘上。在这个例子中，写到盘上的信息代码和CRC码是4D6F746FB994,4D6F746FB994信息代码CRC码这个码是能被11021(H)除尽的。从盘上把这块数据读出时，用同样的CRC码生成多项式去除这块数据，相除后得到的两种可能结果是：①余数为0，表示读出没有出现错误；②余数不为0，表示读出有错。

73

92/3/20238 CD-ROM中也采用了相同的CRC检错。CD-ROM扇区方式01中，有一个4字节共32位的EDC字域，它就是用来存放CRC码。 P(x)=(x16+x15+x2+1)(x16+x2+x+1) 计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节0～2063共2064个字节。在EDC中存放的CRC码的次序如下：EDC：x24－x31x16－x23x8－x15x0－x7字节号：20642065206620672/3/2023916.2RS编码和纠错算法16.2.1.GF(2m)域****伽罗华域(GaloisField，GF)

CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m)=GF(28)中的元素或称符号。GF(28)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式P(x)的特性是 得到的余式等于0。CD-ROM用来构造GF(28)域的是 P(x)=x8+x4+x3+x2+1而GF(28)域中的本原元素为:

α＝（00000010）2/3/202310[例13.1]构造GF(23)域的本原多项式P(x)假定为 P(x)=x3+x+1 α定义为P(x)=0的根，即 α3＋α＋1=0

和 α3=α＋1x7+1/P(x)=？？？2/3/2023110mod(α3＋α＋1)=0α0mod(α3＋α＋1)=α0=1α1mod(α3＋α＋1)=α1α2mod(α3＋α＋1)=α2α3

mod(α3＋α＋1)=α＋1α4

mod(α3＋α＋1)=α2＋αα5mod(α3＋α＋1)=α2＋α1＋1α6mod(α3＋α＋1)=α2＋1α7mod(α3＋α＋1)=α0α8mod(α3＋α＋1)=α1……

GF(23)中的元素可计算如下：

2/3/202312表16-01GF(23)域中与二进制代码对照表,P(x)=x3+x+1GF(23)域元素二进制对代码0(000)α0

(001)α1

(010)α2

(100)α3

(011)α4

(110)α5

(111)α6

(101) 建立了GF(23)域中的元素与3位二进制数之间的一一对应关系。 用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系。2/3/202313现仍以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)域中。2/3/20231416.2.2RS的编码算法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个检验符号。2/3/202315对一个信息码符多项式M(x)，RS校验码生成多项式的一般形式为: (16-2) 式中，K0是偏移量，通常取K0=0或K0=1， 而K=(n-k)≥2t(t为要校正的错误符号数)。2/3/202316[例13.2]设在GF(23)域中的元素对应表如表16-01所示。假设(6，4)RS码中的4个信息符号为m3、m2、m1和m0，信息码符多项式M(x)为 M(x)=m3x3+m2x2+m1x+m0 (16－3)

并假设RS校验码的2个符号为Q1和Q0，

的剩余多项式为 R(x)=Q1x+Q0这个多项式的阶次比G(x)的阶次少一阶。2/3/202317 如果K0=1，t=1，由式(16－2)导出的RS校验码生成多项式就为(16-4) 根据多项式的运算，由式(16－3)和式(16－4)可以得到 m3x5＋m2x4＋m1x3＋m0x2＋Q1x＋Q0

=(x－α)(x－α2)Q(x) 当用x=α和x=α2代入上式时，得到下面的方程组， m3α5＋m2α4+m1α3+Q1α+Q0=0 m3(α2)5+m2(α2)4+m1(α2)3+m0(α2)2+Q1α2+Q0=02/3/202318 经过整理可以得到用矩阵表示的(6，4)RS码的校验方程： 求解方程组就可得到校验符号： Q1=m3α5+m2α5+m1α0+m0α4 Q0=m3α+m2α3+m1α0+m0α3 在读出时的校正子可按下式计算：2/3/202319[例16.3] 在例16.2中，如果K0=0，t=1，由式(16－2)导出的RS校验码生成多项式就为。注：前为K0=1（16－5）

根据多项式的运算，由(16－3)和(16－5)可以得到下面的方程组：方程中的αi也可看成符号的位置，此处i=0，1，…，5。

2/3/202320 求解方程组可以得到RS校验码的2个符号为Q1和Q0，（16-6） 假定mi为下列值： 代入(16－6)式可求得校验符号： Q1=α6=101 Q0=α4=110信息符号m3=α0=001m2=α6=101m1=α3=011m0=α2=100校验符号Q1=α6=101Q0=α4=110校正子s0=0s1=02/3/20232116.2.3RS码的纠错算法RS码的错误纠正过程分三步：(1)计算校正子(syndrome)；(2)计算错误位置；(3)计算错误值。2/3/202322以例16.3为例介绍RS码的纠错算法。校正子使用下面的方程组来计算： 为简单起见，假定存入光盘的信息符号m3、m2、m1、m0和由此产生的检验符号Q1、Q0均为0，读出的符号为m3′、m2′、m1′、m0′、Q1′和Q0′。如果只有一个错误，假设错误的位置为αx，错误值为mx，那么可通过求解下面的方程组：

得知错误的位置和错误值。2/3/202323如果计算得到s0=α2和s1=α5，可求得αx=α3和mx=α2，说明m1出了错，它的错误值是α2（见表）。校正后的m1=m1′＋mx，本例中m1=0。如果计算得到s0=0，而s1≠0，那基本可断定至少有两个错误如已知两个错误明显mx1和mx2的位置αx1和αx2，那么求解方程组： 就可知道这两个错误值。2/3/20232416.3CIRC纠错技术经常遇到的两种错误：随机错误：由于随机干扰造成的错误；特点是随机的、孤立的，干扰过后再读一次光盘，错误就可能消失。突发错误：连续多位出错，或连续多个符号出错；如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片。2/3/20232516.3.1交插技术交插(interleaving)技术在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正。 例如，3个(5，3)码块：B1=(a2，a1，a0，P1，P0)B2=(b2，b1，b0，Q1，Q0)B3=(c2，c1，c0，R1，R0)排成3行：a2 a1 a0 P1 P0b2 b1 b0 Q1 Q0c2 c1 c0 R1 R0连续排列a2a1a0

P1P0b2b1b0

Q1Q0c2c1c0

R1R02/3/202326一般来说，如果有r个(n，k)码，排成r×n

矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若(n，k)码能纠正t个错误，那么这样交插后就可以纠正rt个突发错误。交插排列：a2b2c2a1b1c1a0b0c0P1Q1R1P0Q0R0连续错3个：a2b2c2a1b1c1a0XXXQ1R1P0Q0R0读出后重新排列：a2a1a0XP0b2b1XQ1Q0c2c1XR1R0从这个例子中可以看到，对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续的错误。2/3/20232716.3.2交叉交插(cross－interleaving)技术例子说明(1)用(5，3)码编码器C2生成的4个码块为:B1=(a2a1a0P1P0)B2=(b2b1b0Q1Q0)B3=(c2c1c0R1R0)B4=(d2d1d0S1S0)(2)交插后再用(6，4)码编码器C1生成5个码块为:a2 b2 c2 d2 T1 T0a1 b1 c1 d1 U1 U0a0 b0 c0 d0 V1 V0P1 Q1 R1 S1 W1 W0P0 Q0 R0 S0 X1 X02/3/202328(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去编码。2/3/202329F1帧(F1－Frame)：每6次采样共24个符号构成1帧。用一个称为C2的编码器对这24个符号产生4个Q校验符号：Q0，Q1，Q2和Q3。24个声音数据加上4个Q校验符号共28个符号，用称为C1编码器对这28个符号产生4个P校验符号：P0，P1，P2和P3。F2帧(F2－Frame)：28个符号加上4个P校验符号共32个符号构成的帧。F3帧(F3－Frame)：F2帧加上1个字节(即1个符号)的子码共33个符号构成的帧。延时交插执行交插时不是交插包含有k个校验符的码块，而是交插一个连续系列中的码符。2/3/202330CD存储器中的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.2mm CIRC能纠正在2.2mm光道上连续存放的448个错误符号! 相当于连续224个汉字错误可以得到纠正。2/3/20233116.4RSPC码每个字s(n)由两个字节B组成，一个称为最高有效位字节MSB，另一个叫做最低有效位字节LSB。 第n个字由下面的字节组成，其中n=0，1，2，…，1169。 从字节12开始到字节2075共2064个字节组成的数据块排列成24×43的矩阵，如图16-02所示。2/3/202332

NP

0123

…

4142

000000010002………00410042

1004300440045………00840085HEADER

2008600870088………01270128+…

P

Q

用户数据

＋MP22094609470948………09870988部分辅助数据

23098909900991………10301031

24103210331034

10731074P-校验

25107510761077………11161117

26111811191120…1143

Q-校验

27114411451146…1169

012…25

(ISO/IEC1049）图16－02RSPC码计算用数据阵列2/3/202333(1)P校验符号用(26，24)RS码产生 43列的每一列用矢量表示，记为Vp。每列有24个字节的数据再加2个字节的P校验字节，用下式表示：其中：

Np=0,1,2,,42 Mp=0,1,2,,25s(43*24+Np)和s(43*25+Np)是P校验字节；对这列字节计算得到的是两个P校验字节，称为P校验符号。2/3/202334

两个P校验字节加到24行和25行的对应列上，这样构成了一个26×43的矩阵，并且满足方程

Hp×Vp=0其中HP校验矩阵为

2/3/202335(2)Q校验符号用(45，43)RS码产生增加P校验字节之后得到了一个26×43矩阵，该矩阵的对角线元素重新排列后得到一个新的矩阵，其结构如图16-03(Q校验符号计算用数据阵列)所示。

MQ

012

404142Q0Q10000000440088……06420686073011181144

1004300870131……06850729077311191145

2008601300147……07280772081611201146

3012901370217……07710815085911211147

4017202160260……08140858090211221148

22094609901034……04700514055811401166NQ23098910331077……05130557060111411167

24103210760002……05560600064411421168