错误检测和校正.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第16章 错误检测和校正,错误检测和校正,优选错误检测和校正,1/24/2026,2,在模2多项式代数运算中定义的运算规则有：,例如，模2多项式的加法和减法：*,结论：,对于模2运算来说，代码多项式的加法和减法运算所得的结果相同。,在做代码多项式的减法时，可用做加法来代替做减法。,1/24/2026,3,代码多项式的除法可按长除法做。,例如,1/24/2026,4,如果一个,k,位的二进制信息代码多项式为M(x)，再增加(,nk,)位的校验码，那么增加(,nk,)位之后，信息代码多项式在新的数据块中就表示成 x,n-k,M(x)，如图16-01所示。,图16-01 信息代码结构,(,nk,),(,nk,),1/24/2026,5,如果用一个校验码生成多项式G(x)去除代码多项式，得到的商假定为Q(x)，余式为R(x)，则可写成,因为模2多项式的加法和减法运算结果相同，所以又可把上式写成：,G(x)称为校验码生成多项式。,从该式中可以看到，代表新的代码多项式 x,n-k,M(x)+R(x)是能够被校验码生成多项式 除尽的，即它的余项为0。,1/24/2026,6,例如，CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是:,G(x)=x,16,+x,12,+x,5,+1,若用二进制表示，则为:,G(x)=10001000000100001(B),=11021(H),假定要写到盘上的信息代码 M(x)为,M(x)=4D6F746F(H),由于增加了2个字节共16位的校验码，所以信息代码变成x,16,M(x):4D6F746F0000(H)。,1/24/2026,7,CRC检验码计算如下：,两数相除的结果，其商可不必关心，其余数为B994(H)就是CRC校验码。把信息代码写到盘上时，将原来的信息代码和CRC码一起写到盘上。在这个例子中，写到盘上的信息代码和CRC码是4D6F746F B994,4D6F746F,B994,信息代码,CRC码,这个码是能被11021(H)除尽的。,从盘上把这块数据读出时，用同样的CRC码生成多项式去除这块数据，相除后得到的两种可能结果是：,余数为0，表示读出没有出现错误；,余数不为0，表示读出有错。,73,9,1/24/2026,8,CD-ROM中也采用了相同的CRC检错。CD-ROM扇区方式01中，有一个4字节共32位的EDC字域，它就是用来存放CRC码。,P(x)=(x,16,+x,15,+x,2,+1)(x,16,+x,2,+x+1),计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节02063共2064个字节。在EDC中存放的CRC码的次序如下：,EDC：,x,24,x,31,x,16,x,23,x,8,x,15,x,0,x,7,字节号：,2064,2065,2066,2067,1/24/2026,9,16.2 RS编码和纠错算法,16.2.1.GF(2,m,)域 *,伽罗华域(Galois Field，GF),CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2,m,)=GF(2,8,)中的元素或称符号。GF(2,8,)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式P(x)的特性是 得到的余式等于0。,CD-ROM用来构造GF(2,8,)域的 是,P(x)=x,8,+x,4,+x,3,+x,2,+1,而GF(2,8,)域中的本原元素为,:,（00000010）,1/24/2026,10,=11021(H),由于增加了2个字节共16位的校验码，所以信息代码变成x16M(x):4D6F746F0000(H)。,例如，CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是:,若用二进制表示，则为:,B1=(a2a1a0P1P0),=010=1,余数不为0，表示读出有错。,这个码是能被11021(H)除尽的。,m2=6=101,M(x)=m3x3+m2x2+m1x+m0(163)并假设RS校验码的2个符号为Q1和Q0，,两数相除的结果，其商可不必关心，其余数为B994(H)就是CRC校验码。,一般来说，如果有r个(n，k)码，排成 r n 矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若(n，k)码能纠正t 个错误，那么这样交插后就可以纠正r t 个突发错误。,在模2多项式代数运算中定义的运算规则有：,mod(31)=0,Np=0,1,2,42,例13.1 构造GF(2,3,)域的本原多项式P(x)假定为P(x)=x,3,+x+1,定义为 P(x)=0的根，即,3,1=0和,3,=1,x,7,+1/P(x)=？,1/24/2026,11,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,GF(23)中的元素可计算如下：,1/24/2026,12,如果计算得到s0=0，而s10，那基本可断定至少有两个错误,由于增加了2个字节共16位的校验码，所以信息代码变成x16M(x):4D6F746F0000(H)。,(4)最后一个码块不配对，可以和下一个码块配对。,c2 c1 c0 R1 R0,相当于连续224个汉字错误可以得到纠正。,(ISO/IEC1049）,另一个叫做最低有效位字节LSB。,b2b1b0Q1Q0,这个多项式的阶次比G(x)的阶次少一阶。,mod(31)=1,假定要写到盘上的信息代码 M(x)为,定义为 P(x)=0的根，即,Q1=6=101,建立了GF(23)域中的元素与3位二进制数之间的一一对应关系。,用一个称为C2的编码器对这24个符号产生4个Q校验符号：Q0，Q1，Q2和Q3。,表,16-01,GF(2,3,)域中与二进制代码对照表,P(x)=x,3,+x+1,GF(2,3,)域元素,二进制对代码,0,(000),0,(001),1,(010),2,(100),3,(011),4,(110),5,(111),6,(101),建立了GF(2,3,)域中的元素与3位二进制数之间的一一对应关系。,用同样的方法可建立GF(2,8,)域中的256个元素与8位二进制数之间的一一对应关系。,1/24/2026,13,现仍以GF(2,3,)域中运算为例：,加法例：,0,3,=001011,=010=,1,减法例：与加法相同,乘法例：,5,4,=(54)mod7,=,2,除法例：,5,/,3,=,2,3,/,5,=,2,=,(27),=,5,取对数：log(,5,)=5,这些运算的结果仍然在GF(2,3,)域中。,1/24/2026,14,16.2.2 RS的编码算法,RS的编码,就是计算信息码符多项式M(x)除以校验码生成多项式G(x)之后的余数。,在GF(2,m,)域中，符号(n，k)RS的含义如下：,m表示符号的大小，如 m=8表示符号由8位二进 制数组成,n表示码块长度，k 表示码块中的信息长度,K=nk=2t表示校验码的符号数,t表示能够纠正的错误数目,例如，(28，24)RS码表示码块长度共28个符号，其中信息代码的长度为24，检验码有4个检验符号。,1/24/2026,15,对一个信息码符多项式M(x)，RS校验码生成多项式的一般形式为:,(16-2),式中，K,0,是偏移量，通常取K,0,=0或K,0,=1，,而K=(,n-k,)2,t,(,t,为要校正的错误符号数)。,1/24/2026,16,例13.2,设在GF(2,3,)域中的元素对应表如表,16-01,所示。假设(6，4)RS码中的4个信息符号为m,3,、m,2,、m,1,和m,0,，信息码符多项式 M(x)为,M(x)=m,3,x,3,+m,2,x,2,+m,1,x+m,0,(163),并假设RS校验码的2个符号为Q,1,和Q,0,，,的剩余多项式 为,R(x)=Q,1,x+Q,0,这个多项式的阶次比G(x)的阶次少一阶。,1/24/2026,17,如果K,0,=1，,t,=1，由式(162)导出的RS校验码生成多项式就为,(16-4),根据多项式的运算，由式(163)和式(164)可以得到,m,3,x,5,m,2,x,4,m,1,x,3,m,0,x,2,Q,1,x,Q,0,=(,x,)(,x,2,),Q,(,x,),当用,x,=和,x,=,2,代入上式时，得到下面的方程组，,m,3,5,m,2,4,+m,1,3,+Q,1,+Q,0,=0,m,3,(,2,),5,+m,2,(,2,),4,+m,1,(,2,),3,+m,0,(,2,),2,+Q,1,2,+Q,0,=0,1/24/2026,18,图16-01 信息代码结构,由于随机干扰造成的错误；,CD存储器中的CIRC编码器采用了4F1帧的延时交插方案。,现仍以GF(23)域中运算为例：,m1=3=011,(1)用(5，3)码编码器C2生成的4个码块为:,取对数：log(5)=5,Q0=4=110,b2b1b0Q1Q0,CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m)=GF(28)中的元素或称符号。,由于增加了2个字节共16位的校验码，所以信息代码变成x16M(x):4D6F746F0000(H)。,校正子使用下面的方程组来计算：,若用二进制表示，则为:,如果计算得到s0=0，而s10，那基本可断定至少有两个错误,求解方程组就可得到校验符号：,经过整理可以得到用矩阵表示的(6，4)RS码的校验方程：,求解方程组就可得到校验符号：,Q,1,=m,3,5,+m,2,5,+m,1,0,+m,0,4,Q,0,=m,3,+m,2,3,+m,1,0,+m,0,3,在读出时的校正子可按下式计算：,1/24/2026,19,例16.3,在例16.2中，如果K,0,=0，,t,=1，由式,(162),导出的RS校验码生成多项式就为。注：前为K,0,=1,（165）,根据多项式的运算，由,(163),和(165)可以得到下面的方程组：,方程中的,i,也可看成符号的位置，此处 i=0，1，5。,1/24/2026,20,求解方程组可以得到RS校验码的2个符号为Q,1,和Q,0,，,（16-6）,假定,m,i,为下列值：,代入(166)式可求得校验符号：,Q,1,=,6,=101,Q,0,=,4,=110,信息符号,m,3,=,0,=001,m,2,=,6,=101,m,1,=,3,=011,m,0,=,2,=100,校验符号,Q,1,=,6,=101,Q,0,=,4,=110,校正子,s,0,=0,s,1,=0,1/24/2026,21,16.2.3 RS码的纠错算法,RS码的错误纠正过程分三步：,(1)计算校正子(syndrome)；,(2)计算错误位置；,(3)计算错误值。,1/24/2026,22,以例16.3为例介绍RS码的纠错算法。,校正子使用下面的方程组来计算：,为简单起见，假定存入光盘的信息符号m,3,、m,2,、m,1,、m,0,和由此产生的检验符号Q,1,、Q,0,均为0，读出的符号为m,3,、m,2,、m,1,、m,0,、Q,1,和Q,0,。,如果只有一个错误，假设错误的位置为,x,，错误值为m,x,，那么可通过求解下面的方程组：,得知错误的位置和错误值。,1/24/2026,23,如果计算得到s,0,=,2,和s,1,=,5,，可求得,x,=,3,和m,x,=,2,，,说明m1出了错，它的错误值是,2,（见表）。校正后的m,1,=m,1,m,x,，本例中m,1,=0。,如果计算得到s,0,=0，而s,1,0，那基本可断定至少有两个错误,如已知两个错误明显 m,x1,和m,x2,的位置,x1,和,x2,，那么求解方程组：,就可知道这两个错误值。,1/24/2026,24,16.3 CIRC纠错技术,经常遇到的两种错误：,随机错误：,由于随机干扰造成的错误；,特点是随机的、孤立的，干扰过后再读一次光盘，错误就可能消失。,突发错误：,连续多位出错，或连续多个符号出错；,如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片。,1/24/2026,25,16.3.1 交插技术,交插(interleaving)技术,在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正。,例如，,3个(5，3)码块：,B1=(a,2,，a,1,，a,0,，P,1,，P,0,),B2=(b,2,，b,1,，b,0,，Q,1,，Q,0,),B3=(c,2,，c,1,，c,0,，R,1,，R,0,),排成3行：,a,2,a,1,a,0,P,1,P,0,b,2,b,1,b,0,Q,1,Q,0,c,2,c,1,c,0,R,1,R,0,连续排列,a,2,a,1,a,0,P,1,P,0,b,2,b,1,b,0,Q,1,Q,0,c,2,c,1,c,0,R,1,R,0,1/24/2026,26,一般来说，如果有,r,个(,n，k),码，排成,r n,矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若(,n，k,)码能纠正,t,个错误，那么这样交插后就可以纠正,r t,个突发错误。,交插排列：,a,2,b,2,c,2,a,1,b,1,c,1,a,0,b,0,c,0,P,1,Q,1,R,1,P,0,Q,0,R,0,连续错3个：,a,2,b,2,c,2,a,1,b,1,c,1,a,0,X,X,X,Q,1,R,1,P,0,Q,0,R,0,读出后重新排列：,a,2,a,1,a,0,X,P,0,b,2,b,1,X,Q,1,Q,0,c,2,c,1,X,R,1,R,0,从这个例子中可以看到，,对连续排列，每个码块中只能出现一个错误才能纠正。,而交插记录后，读出的3个连续错误经还原后可把它们分散到3 个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续的错误。,1/24/2026,27,16.3.2 交叉交插(crossinterleaving)技术,例子说明,(1)用(5，3)码编码器C,2,生成的4个码块为:,B1=(a2a1a0P1P0),B2=(b2b1b0Q1Q0),B3=(c2c1c0R1R0),B4=(d2d1d0S1S0),(2)交插后再用(6，4)码编码器C,1,生成5个码块为:,a,2,b,2,c,2,d,2,T,1,T,0,a,1,b,1,c,1,d,1,U,1,U,0,a,0,b,0,c,0,d,0,V,1,V,0,P,1,Q,1,R,1,S,1,W,1,W,0,P,0,Q,0,R,0,S,0,X,1,X,0,1/24/2026,28,(3)再交插，交插的码块数可以是 2、3、4或5。以交插 2个码块为例：,a,2,a,1,b,2,b,1,c,2,c,1,d,2,d,1,T,1,U,1,T,0,U,0,a,0,P,1,b,0,Q,1,c,0,R,1,d,0,S,1,(4)最后一个码块不配对，可以和下一个码块配对。,这种编码技术用了两个编码器C,2,和C,1,。,C,2,对原码块进行编码得到(5，3)码块，,交插后生成由4个符号组成的码块，,然后再用(6，4)编码器C,1,去编码。,1/24/2026,29,F,1,帧(F,1,Frame)：,每6次采样共24个符号构成1帧。,用一个称为C,2,的编码器对这24个符号产生4个Q校验符号：Q,0,，Q,1,，Q,2,和Q,3,。,24个声音数据加上4个Q校验符号共28个符号，用称为C,1,编码器对这28个符号产生4个P校验符号：P,0,，P,1,，P,2,和P,3,。,F,2,帧(F,2,Frame)：,28个符号加上4个P校验符号共32个符号构成的帧。,F,3,帧(F,3,Frame)：,F,2,帧加上1个字节(即1个符号)的子码共33个符号构成的帧。,延时交插,执行交插时不是交插包含有,k,个校验符的码块，而是交插一个连续系列中的码符。,1/24/2026,30,CD存储器中的CIRC编码器采用了4F,1,帧的延时交插方案。,1帧延时交插可纠正连续4F,1,帧的突发错误。,4F,2,帧的延时交插可纠正连续16F,1,帧突发错误，相当于大约14F,3,帧的突发错误。,1F,3,帧经过EFM编码后产生588位通道位。,1位通道位的长度折合成0.277m的光道长度。,14F,3,帧突发错误长度相当于,(16(244)/335880.2772.2 mm,CIRC能纠正在2.2 mm光道上连续存放的448个错误符号!,相当于连续224个汉字错误可以得到纠正。,1/24/2026,31,16.4 RSPC码,每个字,s(n),由两个字节B组成，,一个称为最高有效位字节MSB，,另一个叫做最低有效位字节LSB。,第n个字由下面的字节组成，,其中,n,=0，1，2，1169。,从字节12开始到字节2075共2064个字节组成的数据块排列成2443的矩阵，如图16-02所示。,1/24/2026,32,N,P,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,用户数据,M,P,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）,图1602 RSPC码计算用数据阵列,1/24/2026,33,(1)P校验符号用(26，24)RS码产生,43列的每一列用矢量表示，记为Vp。每列有24个字节的数据再加2个字节的P校验字节，用下式表示：,其中：,N,p,=0,1,2,42,M,p,=0,1,2,25,s(43*24+N,p,),和,s(43*25+N,p,),是,P校验字节,；,对这列字节计算得到的是两个P校验字节，称为P校验符号。,1/24/2026,34,两个P校验字节加到24行和25行的对应列上，这样构成了一个2643的矩阵，并且满足方程,H,p,V,p,=0,其中HP校验矩阵为,1/24/2026,35,(2)Q校验符号用(45，43)RS码产生,增加P校验字节之后得到了一个2643矩阵，该矩阵的对角线元素重新排列后得到一个新的矩阵，其结构如图16-03,(Q校验符号计算用数据阵列),所示。,M,Q,0,1,2,40,41,42,Q,0,Q,1,0,0000,0044,0088,0642,0686,0730,1118,1144,1,0043,0087,0131,0685,0729,0773,1119,1145,2,0086,0130,0147,0728,0772,0816,1120,1146,3,0129,0137,0217,0771,0815,0859,1121,1147,4,0172,0216,0260,0814,0858,0902,1122,1148,22,0946,0990,1034,0470,0514,0558,1140,1166,N,Q,23,0989,1033,1077,0513,0557,0601,1141,1167,24,1032,1076,0002,0556,0600,0644,1142,1168,25,1075,0001,0045,0599,0643,0687,1143,1169,(ISO/IEC 101491989),1/24/2026,36,