《多媒体技术基础》第3版第16章_错误检测和校正

多媒体技术基础(第3版)第16章错误检测和校正林福宗清华大学计算机科学与技术系[e-mail]2008年9月2011年1月23日第16章错误检测和校正2/43第16章错误检测和校正目录16.1CRC错误检测原理与检测码16.1.1CRC错误检测原理16.1.2CD盘上的错误检测码16.2RS编码和纠错算法16.2.1GF(2m)域16.2.2RS的编码算法16.2.3RS码的纠错算法16.3CIRC纠错技术16.3.1交插技术16.3.2交叉交插技术16.4RSPC码2011年1月23日第16章错误检测和校正3/43第16章错误检测和校正——前言光盘存储器需要纠错由于光盘材料性能、光盘制造技术水平、驱动器性能和使用不当等诸多原因，从盘上读出的数据不可能完全正确据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为3×10-4，沾有指纹的盘的误码率约为6×10-4，有伤痕的盘的误码率约为5×10-3光盘存储器采用了三种错误检测和纠正措施错误检测：采用循环冗余码(cyclicredundancycode，CRC)检测读出数据是否有错错误校正：采用里德－索洛蒙码(Reed-SolomonCode,RS)进行纠错交叉交插里德-索洛蒙码(CrossInterleavedReed-SolomonCode，CIRC),这个码的含义可理解为在用RS编译码前后，对数据进行交插和交叉处理2011年1月23日第16章错误检测和校正4/4316.1CRC错误检测原理与检测码CRC错误检测原理代码多项式在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列10101111，用多项式可以表示成765432107654321075321()1Mxaxaxaxaxaxaxaxaxxxxxx　　　式中,xi表示代码的位置或某个二进制数位的位置，前面的系数ai表示码的值，取值为0或1。M(x)称为信息代码多项式2011年1月23日第16章错误检测和校正5/4316.1CRC错误检测原理与检测码(续1)模2多项式代数运算规则11011iiiixxxx模2多项式的加法和减法代码多项式的模2加法和模2减法运算所得的结果相同，所以可用加法来代替减法2011年1月23日第16章错误检测和校正6/4316.1CRC错误检测原理与检测码(续2)模2多项式的除法用长除法2011年1月23日第16章错误检测和校正7/4316.1CRC错误检测原理与检测码(续3)代码多项式的结构如果一个k位的二进制信息代码多项式为M(x)，增加(n－k)位的校验码后，信息代码多项式在新的数据块中就表示成xn-kM(x)，见图16-1图16-1信息代码结构2011年1月23日第16章错误检测和校正8/4316.1CRC错误检测原理与检测码(续4)错误检测原理如果用一个校验码G(x)生成多项式去除代码多项式M(x)，得到的商假定为Q(x)，余式为R(x)，则可写成()()()()()nkMxRxxQxGxGx()()()()nkxMxQxGxRx因模2多项式的加法和减法运算结果相同，故可把上式写成()()()()nkxMxRxQxGx2011年1月23日第16章错误检测和校正9/4316.1CRC错误检测原理与检测码(续5)代表新的代码多项式，它是能够被校验码生成多项式G(x)除尽的，即它的余项为0在盘上写数据时，将xn-kM(x)表示的信息代码和表示的余数R(x)代码一起写到盘上从盘上读数据时，将信息代码和余数代码一起读出，然后用相同的校验码生成多项式G(x)去除通过判断余数是否为0来确定数据是否有误()()nkxMxRx2011年1月23日第16章错误检测和校正10/4316.1CRC错误检测原理与检测码(续6)CD盘上的错误检测码CD-DA盘上的q通道使用的CRC校验码生成多项式16125()1Gxxxx若用二进制表示，则为()=10001000000100001(B)=11021(H)Gx假定要写到盘上的信息代码M(x)为()=4D6F746F(H)Mx由于增加了2个字节的校验码，所以信息代码变成16()4D6F746F0000(H)xMx2011年1月23日第16章错误检测和校正11/4316.1CRC错误检测原理与检测码(续7)两数相除的结果其商可不必关心，其余数为B994(H)，这就是CRC校验码将信息代码和CRC码一起写到盘上写到盘上的信息代码和CRC码是4D6F746FB994，它能被错误检测从盘上把这块数据读出时，用同样的CRC码生成多项式去除，其结果是：(1)余数为0，表示读出没有错误；(2)余数不为0，表示读出有错()11021(H)Gx除尽2011年1月23日第16章错误检测和校正12/4316.1CRC错误检测原理与检测码(续8)CD-ROM的错误检测在CD-ROM扇区方式1中，有一个4字节的EDC域用来存放CRC码。CRC校验码生成多项式是一个32阶的多项式16152162()(1)(1)Pxxxxxxx计算CRC码时用的数据块是从扇区的开头到用户数据区结束的数据字节，即字节0～2063。在EDC中存放的CRC码的次序如下EDCx24－x31x16－x23X8－x15x0－x7字节号20642065206620672011年1月23日第16章错误检测和校正13/4316.2RS编码和纠错算法16.2.1.GF(2m)域CD-ROM中的数据、地址、校验码等都可看成是属于GF(2m)=GF(28)中的元素或称符号。GF(28)表示域中有256个元素，除0和1之外的254个元素由本原多项式(primitivepolynomial)P(x)生成。本原多项式P(x)的特性是得到的余式等于0CD-ROM用来构造GF(28)域的P(x)是21(1)/()mxPx8432()1Pxxxxx而GF(28)域中的本原元素(primitiveelement)为α=(00000010)2011年1月23日第16章错误检测和校正14/4316.2RS编码和纠错算法(续1)[例16.1]假设构造GF(23)域的本原多项式P(x)为α定义为P(x)=0的根，即α3＋α＋1=0和α3=α＋1GF(23)中的元素计算如右表1)(3xxxP2011年1月23日第16章错误检测和校正15/4316.2RS编码和纠错算法(续2)用二进制数表示域元素的对照表见表16-1用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系GF(23)域元素二进制对代码GF(23)域元素二进制对代码0(000)α3(011)α0(001)α4(110)α1(010)α5(111)α2(100)α6(101)表16-1GF(23)域中与二进制代码对照表(）3()1Pxxx2011年1月23日第16章错误检测和校正16/4316.2RS编码和纠错算法(续3)伽罗华域中的加、减、乘和除运算031001+011=010=54(5+4)mod72532/35-2(-2+7)5/5log()5以GF(23)域中的运算为例，加法例：减法例：与加法相同乘法例：除法例：取对数：这些运算的结果仍然在GF(23)域中2011年1月23日第16章错误检测和校正17/4316.2RS编码和纠错算法(续4)16.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个分散的或2个连续的符号错误，但不能纠正3个或3个以上的符号错误2011年1月23日第16章错误检测和校正18/4316.2RS编码和纠错算法(续5)对一个信息码符多项式M(x)，RS校验码生成多项式的一般形式为010()()KKiiGxx式中，K0是偏移量，通常取K0=0或K0=1，而(n-k)≥2t(t为要校正的错误符号数)[例16.2]假设在GF(23)域中的元素对应表见表16-1，(6，4)RS码中的4个信息符号为m3，m2，m1和m0，信息码符多项式为，323210()Mxmxmxmxm2011年1月23日第16章错误检测和校正19/4316.2RS编码和纠错算法(续6)假设RS校验码的2个符号为Q1和Q0，的剩余多项式为这个多项式的阶次比的阶次少一阶。2()()()()nkMxxMxxGxGx01QQ)(xxR如果K0=1，t=1，则RS校验码生成多项式为0120()()=()()KKiiGxxxx根据多项式运算规则，可得到54322321010()()()mxmxmxmxQxQxxQx2011年1月23日第16章错误检测和校正20/4316.2RS编码和纠错算法(续7)当用x=α和x=α2代入上式时，得到下面的方程组543232101025242322213210100()()()()()0mmmmQQmmmmQQ经过整理可以得到用矩阵表示的(6，4)RS码的校验方程为54321252423222132101001()()()()()1TQQQQHVHVmmmmQQ2011年1月23日第16章错误检测和校正21/4316.2RS编码和纠错算法(续8)求解方程组可得到校验符号55041321030303210QmmmmQmmmm在读出时的校正子可按下式计算[例16.3]在例16.2中，如果K0=0，t=1，则RS校验码生成多项式为，01010()()()()KKiiGxxxx2011年1月23日第16章错误检测和校正22/4316.2RS编码和纠错算法(续9)根据多项式的运算，可得到下面的方程组321010543232101000mmmmQQmmmmQQ方程中的αi可看成符号mi的位置，此处的i=0，1，…，5求解方程组可得到RS校验码的2个符号Q1和Q02531321036403210QmmmmQmmmm2011年1月23日第16章错误检测和校正23/4316.2RS编码和纠错算法(续10)假定mi(信息符号)为下列值m3=α0=001m2=α6=101m1=α3=011m0=α2=100可求得校验符号6140101110QQ2011年1月23日第16章错误检测和校正24/4316.2RS编码和纠错算法(续11)16.2.3RS码的纠错算法RS码的错误纠正过程分三步(1)计算校正子(syndrome)(2)计算错误位置和错误值(3)纠正错误现以【例16.3】为例介绍RS码的纠错算法校正子使用下面的方程组来计算：032101054321321010smmmmQQsmmmmQQ2011年1月23日第16章错误检测和校正25/4316.2RS编码和纠错算法(续12)为简单起见，假定存入光盘的信息符号为m3，m2，m1，m0，由此产生的检验符号Q1和Q0均为0，读出的符号为(1)计算s1和s0如果计算得到的s1和s0都为0，则说明没有错误；如果计算得到的s1和s0