《第16章错误检测和校正.ppt》由会员分享，可在线阅读，更多相关《第16章错误检测和校正.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第16章章 错误检测和校正错误检测和校正第第16章错误检测和章错误检测和校正校正现在学习的是第1页，共38页16.1 CRC错误检测原理错误检测原理 在纠错编码代数中，把以二进制数字表示的一在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。个数据系列看成一个多项式。例如，二进制数字序列例如，二进制数字序列10101111，用多项式可以表示成：，用多项式可以表示成：式中的式中的 xi表示代码的位置，或某个二进制数位的位置，表示代码的位置，或某个二进制数位的位置，xi前面的系数前面的系数a i表示码的值。若表示码的值。若a i是一位二进制代码，是一位二进制代码，则取值是则取值是0
2、或或1。称称 M(x)为为信息代码多项式信息代码多项式。=现在学习的是第2页，共38页在模在模2多项式代数运算中定义的运算规则有：多项式代数运算中定义的运算规则有：例如，模例如，模2多项式的加法和减法：多项式的加法和减法：*结论：结论：对于模对于模2运算来说，代码多项式的加法和减法运算所得的运算来说，代码多项式的加法和减法运算所得的结果相同。结果相同。在做代码多项式的减法时，可用做加法来代替做减法。在做代码多项式的减法时，可用做加法来代替做减法。现在学习的是第3页，共38页代码多项式的除法可按长除法做。代码多项式的除法可按长除法做。例如例如 现在学习的是第4页，共38页如果一个如果一个k位的二
3、进制位的二进制信息代码多项式信息代码多项式为为M(x)，再增加，再增加(nk)位的校验码，那位的校验码，那么增加么增加(nk)位之后，信息代码多项式在新的数据块中就表示成位之后，信息代码多项式在新的数据块中就表示成 xn-kM(x)，如图如图16-01所示。所示。图图16-01 信息代码结构信息代码结构(nk)(nk)现在学习的是第5页，共38页如果用一个校验码生成多项式如果用一个校验码生成多项式G(x)去除代码多项式去除代码多项式，得到的商假定为，得到的商假定为Q(x)，余式为，余式为R(x)，则可写成，则可写成因为模因为模2多项式的加法和减法运算结果相同，所以又可把上式写成：多项式的加法和
4、减法运算结果相同，所以又可把上式写成：G(x)称为校验码生成多项式。称为校验码生成多项式。从该式中可以看到，代表新的代码多项式从该式中可以看到，代表新的代码多项式 xn-kM(x)+R(x)是能够被校验码生成多项是能够被校验码生成多项式式 除尽的，即它的余项为除尽的，即它的余项为0。现在学习的是第6页，共38页例如，例如，CD盘中的盘中的q通道和软磁盘存储器中使用的通道和软磁盘存储器中使用的CRC校验码生成多项式是校验码生成多项式是:G(x)=x16+x12+x5+1若用二进制表示，则为若用二进制表示，则为:G(x)=10001000000100001(B)=11021(H)假定要写到盘上的信
5、息代码假定要写到盘上的信息代码 M(x)为为M(x)=4D6F746F(H)由于增加了由于增加了2个字节共个字节共16位的校验码，所以信息代码变成位的校验码，所以信息代码变成x16M(x):4D6F746F0000(H)。现在学习的是第7页，共38页CRC检验码计算如下：检验码计算如下：两数相除的结果，其两数相除的结果，其商可不商可不必关心必关心，其，其余数余数为为B994(H)就就是是CRC校验码校验码。把信息代码。把信息代码写到盘上时，将原来的信息写到盘上时，将原来的信息代码和代码和CRC码一起写到盘上。码一起写到盘上。在这个例子中，写到盘上的信息在这个例子中，写到盘上的信息代码和代码和C
6、RC码是码是4D6F746F B994,4D6F746F4D6F746FB994B994信息代码信息代码CRCCRC码码这个码是能被这个码是能被11021(H)除尽除尽的。的。从盘上把这块数据从盘上把这块数据读出时，用同样的读出时，用同样的CRC码生成多项式码生成多项式去除这块数据，相除去除这块数据，相除后得到的两种可能结后得到的两种可能结果是：果是：余数为余数为0，表示，表示读出没有出现错误；读出没有出现错误；余数不为余数不为0，表示，表示读出有错。读出有错。73 9现在学习的是第8页，共38页CD-ROM中也采用了相同的中也采用了相同的CRC检错。检错。CD-ROM扇区方式扇区方式01中，
7、有一个中，有一个4字节共字节共32位的位的EDC字域，它就是用来存放字域，它就是用来存放CRC码。码。P(x)=(x16+x15+x2+1)(x16+x2+x+1)计算计算CRC码时用的数据块是从扇区的开头到用户数据区结码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节束为止的数据字节，即字节02063共共2064个字节。在个字节。在EDC中存放的中存放的CRC码的次序如下：码的次序如下：EDCEDC：x x2424x x3131x x1616x x2323x x8 8x x1515x x0 0 x x7 7字节号：字节号：206420642065206520662066206
8、72067现在学习的是第9页，共38页16.2 RS编码和纠错算法编码和纠错算法 16.2.1.GF(2m)域域 *伽罗华域伽罗华域(Galois Field，GF)CD-ROM中的数据、地址、校验码等都可以看成是属于中的数据、地址、校验码等都可以看成是属于GF(2m)=GF(28)中的元素或称符号。中的元素或称符号。GF(28)表示域中有表示域中有256个元素，除个元素，除0，1之外的之外的254个元素由本原多项式个元素由本原多项式P(x)生成。本原多项式生成。本原多项式P(x)的特性是的特性是 得到的余式等于得到的余式等于0。CD-ROM用来构造用来构造GF(28)域的域的 是是P(x)=
9、x8+x4+x3+x2+1而而GF(28)域中的本原元素为域中的本原元素为:（00000010）现在学习的是第10页，共38页例例13.1 构造构造GF(23)域的本原多项式域的本原多项式P(x)假定假定为为P(x)=x3+x+1定义为定义为 P(x)=0的根，即的根，即31=0和和 3=1x7+1/P(x)=？现在学习的是第11页，共38页0 0 mod(mod(3 31)=01)=00 0mod(mod(3 31)=1)=0 0=1=11 1mod(mod(3 31)=1)=1 12 2mod(mod(3 31)=1)=2 23 3 mod(mod(3 31)=1)=1 14 4 mod(
10、mod(3 31)=1)=2 25 5 mod(mod(3 31)=1)=2 21 11 16 6 mod(mod(3 31)=1)=2 21 17 7 mod(mod(3 31)=1)=0 08 8 mod(mod(3 31)=1)=1 1GF(23)中的元素可计算如下：中的元素可计算如下：现在学习的是第12页，共38页表表16-01 GF(23)域中与二进制代码对照表域中与二进制代码对照表,P(x)=x3+x+1 GF(2GF(23 3)域元素域元素二进制对代码二进制对代码0 0(000)(000)0 0 (001)(001)1 1 (010)(010)2 2 (100)(100)3 3
11、(011)(011)4 4 (110)(110)5 5 (111)(111)6 6 (101)(101)建立了建立了GF(23)域中的元素与域中的元素与3位二进制数之间的一一位二进制数之间的一一对应关系。对应关系。用同样的方法可建立用同样的方法可建立GF(28)域中的域中的256个元素与个元素与8位二进制数之间的一一对应关系。位二进制数之间的一一对应关系。现在学习的是第13页，共38页现仍以现仍以GF(23)域中运算为例：域中运算为例：加法例：加法例：03=001011 =010=1减法例：与加法相同减法例：与加法相同乘法例：乘法例：54=(54)mod7 =2除法例：除法例：5/3=23/5
12、=2 =(27)=5取对数：取对数：log(5)=5这些运算的结果仍然在这些运算的结果仍然在GF(23)域中。域中。现在学习的是第14页，共38页16.2.2 RS的编码算法的编码算法 RS的编码的编码就是计算信息码符多项式就是计算信息码符多项式M(x)除以校验码生成多项式除以校验码生成多项式G(x)之后的之后的余数余数。在在GF(2m)域中，符号域中，符号(n，k)RS的含义如下：的含义如下：m表示符号的大小，如表示符号的大小，如 m=8表示符号由表示符号由8位二进位二进 制数组成制数组成n表示码块长度，表示码块长度，k 表示码块中的信息长表示码块中的信息长度度K=nk=2t表示校验码的符号
13、数表示校验码的符号数t表示能够纠正的错误数目表示能够纠正的错误数目例如，例如，(28，24)RS码表示码块长度共码表示码块长度共28个符号，其中个符号，其中信息代码的长度为信息代码的长度为24，检验码有，检验码有4个检验符号。个检验符号。现在学习的是第15页，共38页对一个信息码符多项式对一个信息码符多项式M(x)，RS校验码生成多项校验码生成多项式的一般形式为式的一般形式为:(16-2)式中，式中，K0是偏移量，通常取是偏移量，通常取K0=0或或K0=1，而而K=(n-k)2t(t为要校正的错误符号数为要校正的错误符号数)。现在学习的是第16页，共38页例例13.2 设在设在GF(23)域中
14、的元素对应表如表域中的元素对应表如表16-01所示所示。假。假设设(6，4)RS码中的码中的4个信息符号为个信息符号为m3、m2、m1和和m0，信息码符多项式，信息码符多项式 M(x)为为 M(x)=m3x3+m2x2+m1x+m0(163)并假设并假设RS校验码的校验码的2个符号为个符号为Q1和和Q0，的剩余多项式的剩余多项式 为为 R(x)=Q1x+Q0这个多项式的阶次比这个多项式的阶次比G(x)的阶次少一阶。的阶次少一阶。现在学习的是第17页，共38页如果如果K0=1，t=1，由式，由式(162)导出的导出的RS校验码生校验码生成多项式就为成多项式就为(16-4)根据多项式的运算，由式根
15、据多项式的运算，由式(163)和式和式(164)可以可以得到得到m3x5m2x4m1x3m0 x2Q1xQ0 =(x)(x2)Q(x)当用当用x=和和x=2代入上式时，得到下面的方程组，代入上式时，得到下面的方程组，m35m24+m13+Q1+Q0=0m3(2)5+m2(2)4+m1(2)3+m0(2)2+Q12+Q0=0现在学习的是第18页，共38页经过整理可以得到用矩阵表示的经过整理可以得到用矩阵表示的(6，4)RS码的校验码的校验方程：方程：求解方程组就可得到校验符号：求解方程组就可得到校验符号：Q1=m35 +m25 +m10 +m04Q0=m3+m23 +m10 +m03在读出时的校
16、正子可按下式计算：在读出时的校正子可按下式计算：现在学习的是第19页，共38页例例16.3 在例在例16.2中，如果中，如果K0=0，t=1，由式，由式(162)导出的导出的RS校验码生成校验码生成多项式就为。多项式就为。注：前为注：前为K0=1（165）根据多项式的运算，由根据多项式的运算，由(163)和和(165)可以得到下面的方程组：可以得到下面的方程组：方程中的方程中的i也可看成符号的位置，此处也可看成符号的位置，此处 i=0，1，5。现在学习的是第20页，共38页求解方程组可以得到求解方程组可以得到RS校验码的校验码的2个符号为个符号为Q1和和Q0，（16-6）假定假定mi为下列值：
17、为下列值：代入代入(166)式可求得校验符号：式可求得校验符号：Q1=6=101Q0=4=110信息符号信息符号m m3 3=0 0=001=001m m2 2=6 6=101=101m m1 1=3 3=011=011m m0 0=2 2=100=100校验符号校验符号Q Q1 1=6 6=101=101Q Q0 0=4 4=110=110校正子校正子s s0 0=0=0s s1 1=0=0现在学习的是第21页，共38页16.2.3 RS码的纠错算法码的纠错算法RS码的错误纠正过程分三步：码的错误纠正过程分三步：(1)计算校正子计算校正子(syndrome)；(2)计算错误位置；计算错误位置
18、；(3)计算错误值。计算错误值。现在学习的是第22页，共38页以例以例16.3为例介绍为例介绍RS码的纠错算法。码的纠错算法。校正子使用下面的方程组来计算：校正子使用下面的方程组来计算：为简单起见，假定存入光盘的信息符号为简单起见，假定存入光盘的信息符号m3、m2、m1、m0和由此产生的检验符号和由此产生的检验符号Q1、Q0均为均为0，读出的符号为，读出的符号为m3、m2、m1、m0、Q1和和Q0。如果只有一个错误，假设错误的位置为如果只有一个错误，假设错误的位置为x，错误值，错误值为为mx，那么可通过求解下面的方程组：，那么可通过求解下面的方程组：得知错误的位置和错误值。得知错误的位置和错误
19、值。现在学习的是第23页，共38页如果计算得到如果计算得到s0=2和和s1=5，可求得，可求得x=3和和mx=2，说明说明m1出了错，它的错误值是出了错，它的错误值是2（见表）（见表）。校正后的。校正后的m1=m1mx，本例中，本例中m1=0。如果计算得到如果计算得到s0=0，而，而s10，那基本可断定至少，那基本可断定至少有两个错误有两个错误如已知两个错误明显如已知两个错误明显 mx1和和mx2 的位置的位置 x1和和x2，那么求，那么求解方程组：解方程组：就可知道这两个错误值。就可知道这两个错误值。现在学习的是第24页，共38页16.3 CIRC纠错技术纠错技术经常遇到的两种错误：经常遇到
20、的两种错误：随机错误随机错误：由于随机干扰造成的错误由于随机干扰造成的错误；特点是随机的、孤立的，干扰过后再读一次光盘，错误就特点是随机的、孤立的，干扰过后再读一次光盘，错误就可能消失。可能消失。突发错误突发错误：连续多位出错，或连续多个符号出错；连续多位出错，或连续多个符号出错；如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片。一错就错一大片。现在学习的是第25页，共38页16.3.1 交插技术交插技术交插交插(interleaving)技术技术在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出在光盘上记录数据时
21、，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正。现一片错误时，这些错误就分散到各处，错误就容易得到纠正。例如，例如，3个个(5，3)码块：码块：B1=(a2，a1，a0，P1，P0)B2=(b2，b1，b0，Q1，Q0)B3=(c2，c1，c0，R1，R0)排成排成3行：行：a2a1a0P1P0b2b1b0Q1Q0c2c1c0R1R0连续排列连续排列a a2 2 a a1 1 a a0 0 P P1 1 P P0 0b b2 2 b b1 1 b b0 0 Q Q1 1 Q Q0 0c c2 2 c c1 1 c c0 0 R R1 1 R R
22、0 0现在学习的是第26页，共38页一般来说，如果有一般来说，如果有r个个(n，k)码，排成码，排成 r n 矩阵，按列交插后存储或传送，读出或接矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若收时恢复成原来的排列，若(n，k)码能纠正码能纠正t 个错误，那么这样交插后就可以纠正个错误，那么这样交插后就可以纠正r t 个突发错误。个突发错误。交插排列：交插排列：a2b2c2a1b1c1a0b0c0P P1Q Q1R R1P P0Q Q0R R0连续错连续错3 3个：个：a2b2c2a1b1c1a0X XX XX XQ Q1R R1P P0Q Q0R R0读出后重新排列：读出后重新排
23、列：a2a1a0X XP P0b2b1X XQ Q1Q Q0c2c1X XR R1R R0从这个例子中可以看到，从这个例子中可以看到，对连续排列，每个码块中只能出现一个错误才能纠正。对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的而交插记录后，读出的3个连续错误经还原后可把它们分散到个连续错误经还原后可把它们分散到3 个码个码块中，每个码块可以纠正块中，每个码块可以纠正1个错误，总计可以纠正个错误，总计可以纠正3个连续的错误。个连续的错误。现在学习的是第27页，共38页16.3.2 交叉交插交叉交插(crossinterleaving)技术技术例子说明例子说明(1)用用(5
24、，3)码编码器码编码器C2生成的生成的4个码块为个码块为:B1=(a2a1a0P1P0)B2=(b2b1b0Q1Q0)B3=(c2c1c0R1R0)B4=(d2d1d0S1S0)(2)交插后再用交插后再用(6，4)码编码器码编码器C1生成生成5个码块为个码块为:a2b2c2d2T1T0a1b1c1d1U1U0a0b0c0d0V1V0P1Q1R1S1W1W0P0Q0R0S0X1X0现在学习的是第28页，共38页(3)再交插，交插的码块数可以是再交插，交插的码块数可以是 2、3、4或或5。以交插。以交插 2个码块为例：个码块为例：a2a1b2b1c2c1d2d1T1U1T0U0a0P1b0Q1c0
25、R1d0S1(4)最后一个码块不配对，可以和下一个码块配对。最后一个码块不配对，可以和下一个码块配对。这种编码技术用了两个编码器这种编码技术用了两个编码器C2和和C1。C2对原码块进行编码得到对原码块进行编码得到(5，3)码块，码块，交插后生成由交插后生成由4个符号组成的码块，个符号组成的码块，然后再用然后再用(6，4)编码器编码器C1去编码。去编码。现在学习的是第29页，共38页F1帧帧(F1Frame)：每每6次采样共次采样共24个符号构成个符号构成1帧。帧。用一个称为用一个称为C2的编码器对这的编码器对这24个符号产生个符号产生4个个Q校验符号校验符号：Q0，Q1，Q2和和Q3。24个声
26、音数据加上个声音数据加上4个个Q校验符号共校验符号共28个符号，用称为个符号，用称为C1编码器对这编码器对这28个符号产生个符号产生4个个P校验符号校验符号：P0，P1，P2和和P3。F2帧帧(F2Frame)：28个符号加上个符号加上4个个P校验符号共校验符号共32个符号构成的帧。个符号构成的帧。F3帧帧(F3Frame)：F2帧加上帧加上1个字节个字节(即即1个符号个符号)的子码共的子码共33个符号构成的帧。个符号构成的帧。延时交插延时交插执行交插时不是交插包含有执行交插时不是交插包含有k个校验符的码块，而是交插个校验符的码块，而是交插一个连续系列中的码符。一个连续系列中的码符。现在学习的
27、是第30页，共38页CD存储器中的存储器中的CIRC编码器采用了编码器采用了4F1帧的延时交帧的延时交插方案。插方案。1帧延时交插可纠正连续帧延时交插可纠正连续4F1帧的突发错误。帧的突发错误。4F2帧的延时交插可纠正连续帧的延时交插可纠正连续16F1帧突发错误，相当于帧突发错误，相当于大约大约14F3帧的突发错误。帧的突发错误。1F3帧经过帧经过EFM编码后产生编码后产生588位通道位。位通道位。1位通道位的长度折合成位通道位的长度折合成0.277m的光道长度。的光道长度。14F3帧突发错误长度相当于帧突发错误长度相当于(16(244)/335880.2772.2 mmCIRC能能纠正纠正在
28、在2.2 mm光道上光道上连续连续存放的存放的448个错误个错误符号符号!相当于相当于连续连续224个汉字错误个汉字错误可以得到可以得到纠正纠正。现在学习的是第31页，共38页16.4 RSPC码码 每个字每个字s(n)由两个字节由两个字节B组成，组成，一个称为最高有效位字节一个称为最高有效位字节MSB，另一个叫做最低有效位字节另一个叫做最低有效位字节LSB。第第n个字由下面的字节组成，个字由下面的字节组成，其中其中n=0，1，2，1169。从字节从字节12开始到字节开始到字节2075共共2064个字节组成的数据块排列成个字节组成的数据块排列成2443的矩的矩阵，如图阵，如图16-02所示。所
29、示。现在学习的是第32页，共38页N NP P 01234142000000010002 004100421004300440045 00840085HEADERHEADER2008600870088 01270128+P PQ Q 用户数据用户数据 M MP P22094609470948 09870988部分辅助数据部分辅助数据 23098909900991 10301031 24103210331034 10731074P-P-校验校验 25107510761077 11161117 261118111911201143 Q-Q-校验校验 271144114511461169 01225
30、(ISO/IEC1049）图图1602 RSPC码计算用数据阵列码计算用数据阵列现在学习的是第33页，共38页(1)P校验符号用校验符号用(26，24)RS码产生码产生 43列的每一列用矢量表示，记为列的每一列用矢量表示，记为Vp。每列有。每列有24个字个字节的数据再加节的数据再加2个字节的个字节的P校验字节，用下式表示：校验字节，用下式表示：其中：Np=0,1,2,42Mp=0,1,2,25s(43*24+Np)和s(43*25+Np)是P校验字节校验字节；对这列字节计算得到的是两个对这列字节计算得到的是两个P校校验字节，称为验字节，称为P校验符号校验符号。现在学习的是第34页，共38页两个
31、两个P校验字节加到校验字节加到24行和行和25行的对应列上，这样构成了行的对应列上，这样构成了一个一个2643的矩阵，并且满足方程的矩阵，并且满足方程 HpVp=0其中其中HP校验矩阵为校验矩阵为 现在学习的是第35页，共38页(2)Q校验符号用校验符号用(45，43)RS码产生码产生增加增加P校验字节之后得到了一个校验字节之后得到了一个2643矩阵，该矩阵的对角线矩阵，该矩阵的对角线元素重新排列后得到一个新的矩阵，其结构如图元素重新排列后得到一个新的矩阵，其结构如图16-03(Q校验符号校验符号计算用数据阵列计算用数据阵列)所示。所示。M MQ Q012404142Q Q0 0Q Q1 10
32、00000044008806420686073011181144100430087013106850729077311191145200860130014707280772081611201146301290137021707710815085911211147401720216026008140858090211221148 2209460990103404700514055811401166N NQ Q23098910331077051305570601114111672410321076000205560600064411421168251075000100450599064306871
33、1431169(ISO/IEC 101491989)现在学习的是第36页，共38页每条对角线上的每条对角线上的43个个MSB字节和字节和LSB字节组成的矢字节组成的矢量记为量记为VQ。VQ在在2643矩阵中变成行矢量。第矩阵中变成行矢量。第NQ行上的行上的VQ矢量包含的字节如下：矢量包含的字节如下：其中：其中：NQ=0，1，2，25MQ=0，1，2，42 和和 是是Q校验字节校验字节VQ中的中的(44*MQ43*NQ)字节号运算结果要做字节号运算结果要做mod(1118)运运算。算。现在学习的是第37页，共38页用用(45，43)RS码产生的两个码产生的两个Q校验字节放到对应校验字节放到对应VQ矢量的末端，并且满足下面的方程：矢量的末端，并且满足下面的方程：其中其中HQ校验矩阵为校验矩阵为(26，24)RS码和码和(45，43)RS码可以纠正出现在任何一行码可以纠正出现在任何一行和任何一列上的一个错误，并且能相当可靠地检测出行、和任何一列上的一个错误，并且能相当可靠地检测出行、列中的多重错误。列中的多重错误。Layered ECC的算法的算法:可以取消多重错误。可以取消多重错误。核心思想是交替执行行纠错和列纠错。核心思想是交替执行行纠错和列纠错。现在学习的是第38页，共38页