多媒体技术基础3版6章错误检测和校正

《多媒体技术基础3版6章错误检测和校正》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多媒体技术基础(第3版)第16章错误检测和校正林福宗清华大学计算机科学与技术系linfz@mail.tsinghua.edu.cn2008年9月第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码2第16章错误检测和校正第16章错误检测和校正——前言光盘存储器需要纠错由于光盘材

2、料性能、光盘制造技术水平、驱动器性能和使用不当等诸多原因，从盘上读出的数据不可能完全正确据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为3×10-4，沾有指纹的盘的误码率约为6×10-4，有伤痕的盘的误码率约为5×10-3光盘存储器采用了三种错误检测和纠正措施错误检测：采用循环冗余码(cyclicredundancycode，CRC)检测读出数据是否有错错误校正：采用里德－索洛蒙码(Reed-SolomonCode,RS)进行纠错交叉交插里德-索洛蒙码(CrossInterleavedReed-SolomonCode，

3、CIRC),这个码的含义可理解为在用RS编译码前后，对数据进行交插和交叉处理3第16章错误检测和校正16.1CRC错误检测原理与检测码CRC错误检测原理代码多项式在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列10101111，用多项式可以表示成式中,xi表示代码的位置或某个二进制数位的位置，前面的系数ai表示码的值，取值为0或1。M(x)称为信息代码多项式4第16章错误检测和校正16.1CRC错误检测原理与检测码(续1)模2多项式代数运算规则模2多项式的加法和减法代码多项式的模2加法和模2减法运

4、算所得的结果相同，所以可用加法来代替减法5第16章错误检测和校正16.1CRC错误检测原理与检测码(续2)模2多项式的除法用长除法6第16章错误检测和校正16.1CRC错误检测原理与检测码(续3)代码多项式的结构如果一个k位的二进制信息代码多项式为M(x)，增加(n－k)位的校验码后，信息代码多项式在新的数据块中就表示成xn-kM(x)，见图16-1图16-1信息代码结构7第16章错误检测和校正16.1CRC错误检测原理与检测码(续4)错误检测原理如果用一个校验码G(x)生成多项式去除代码多项式M(x)，得到的商假定为Q(x)，余式为

5、R(x)，则可写成因模2多项式的加法和减法运算结果相同，故可把上式写成8第16章错误检测和校正16.1CRC错误检测原理与检测码(续5)代表新的代码多项式，它是能够被校验码生成多项式G(x)除尽的，即它的余项为0在盘上写数据时，将xn-kM(x)表示的信息代码和表示的余数R(x)代码一起写到盘上从盘上读数据时，将信息代码和余数代码一起读出，然后用相同的校验码生成多项式G(x)去除通过判断余数是否为0来确定数据是否有误9第16章错误检测和校正16.1CRC错误检测原理与检测码(续6)CD盘上的错误检测码CD-DA盘上的q通道使用的CRC

6、校验码生成多项式若用二进制表示，则为假定要写到盘上的信息代码M(x)为由于增加了2个字节的校验码，所以信息代码变成10第16章错误检测和校正16.1CRC错误检测原理与检测码(续7)两数相除的结果其商可不必关心，其余数为B994(H)，这就是CRC校验码将信息代码和CRC码一起写到盘上写到盘上的信息代码和CRC码是4D6F746FB994，它能被错误检测从盘上把这块数据读出时，用同样的CRC码生成多项式去除，其结果是：(1)余数为0，表示读出没有错误；(2)余数不为0，表示读出有错除尽11第16章错误检测和校正16.1CRC错误检测原

7、理与检测码(续8)CD-ROM的错误检测在CD-ROM扇区方式1中，有一个4字节的EDC域用来存放CRC码。CRC校验码生成多项式是一个32阶的多项式计算CRC码时用的数据块是从扇区的开头到用户数据区结束的数据字节，即字节0～2063。在EDC中存放的CRC码的次序如下EDCx24－x31x16－x23X8－x15x0－x7字节号206420652066206712第16章错误检测和校正16.2RS编码和纠错算法16.2.1.GF(2m)域CD-ROM中的数据、地址、校验码等都可看成是属于GF(2m)=GF(28)中的元素或称符号。G

8、F(28)表示域中有256个元素，除0和1之外的254个元素由本原多项式(primitivepolynomial)P(x)生成。本原多项式P(x)的特性是得到的余式等于0CD-ROM用来构造GF(28)域的P(x)是而G