第16章错误检测和校正.pptVIP

第16章错误检测和校正第16章错误检测和校正第1页，共38页，星期日，2025年，2月5日16.1CRC错误检测原理在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序用多项式可以表示成：式中的xi表示代码的位置，或某个二进制数位的位置，xi前面的系数ai表示码的值。若ai是一位二进制代码，则取值是0或1。称M(x)为信息代码多项式。=第2页，共38页，星期日，2025年，2月5日在模2多项式代数运算中定义的运算规则有：例如，模2多项式的加法和减法：****结论：对于模2运算来说，代码多项式的加法和减法运算所得的结果相同。在做代码多项式的减法时，可用做加法来代替做减法。第3页，共38页，星期日，2025年，2月5日代码多项式的除法可按长除法做。例如第4页，共38页，星期日，2025年，2月5日如果一个k位的二进制信息代码多项式为M(x)，再增加(n－k)位的校验码，那么增加(n－k)位之后，信息代码多项式在新的数据块中就表示成xn-kM(x)，如图16-01所示。图16-01信息代码结构(n－k)(n－k)第5页，共38页，星期日，2025年，2月5日如果用一个校验码生成多项式G(x)去除代码多项式，得到的商假定为Q(x)，余式为R(x)，则可写成因为模2多项式的加法和减法运算结果相同，所以又可把上式写成：G(x)称为校验码生成多项式。从该式中可以看到，代表新的代码多项式xn-kM(x)+R(x)是能够被校验码生成多项式除尽的，即它的余项为0。第6页，共38页，星期日，2025年，2月5日例如，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)。第7页，共38页，星期日，2025年，2月5日CRC检验码计算如下：两数相除的结果，其商可不必关心，其余数为B994(H)就是CRC校验码。把信息代码写到盘上时，将原来的信息代码和CRC码一起写到盘上。在这个例子中，写到盘上的信息代码和CRC码是4D6F746FB994,4D6F746FB994信息代码CRC码这个码是能被11021(H)除尽的。从盘上把这块数据读出时，用同样的CRC码生成多项式去除这块数据，相除后得到的两种可能结果是：①余数为0，表示读出没有出现错误；②余数不为0，表示读出有错。739第8页，共38页，星期日，2025年，2月5日 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字节号：2064206520662067第9页，共38页，星期日，2025年，2月5日16.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)域中的本原元素为: α＝第10页，共38页，星期日，2025年，2月5日[例13.1]构造GF(23)域的本原多项式P(x)假定为 P(x)=x3+x+1 α定义为P(x)=0的根，即 α3＋α＋1=0

和 α3=α＋1x7+1/P(x)=？？？第11页，共38页，星期日，2025年，2月5日0mod(α3＋α＋1)=0α0mod(α3＋α＋1)=α0=1α1mod(α3＋α＋1)=