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

《多媒体技术基础3版6章错误检测和校正.ppt》由会员分享，可在线阅读，更多相关《多媒体技术基础3版6章错误检测和校正.ppt（43页珍藏版）》请在三一办公上搜索。

1、多媒体技术基础(第3版)第16章 错误检测和校正,林福宗清华大学 计算机科学与技术系2008年9月,16章 错误检测和校正,2,第16章 错误检测和校正目录,16.1 CRC错误检测原理与检测码16.1.1 CRC错误检测原理16.1.2 CD盘上的错误检测码16.2 RS编码和纠错算法16.2.1 GF(2m)域16.2.2 RS的编码算法16.2.3 RS码的纠错算法16.3 CIRC纠错技术16.3.1 交插技术16.3.2 交叉交插技术16.4 RSPC码,16章 错误检测和校正,3,第16章 错误检测和校正前言,光盘存储器需要纠错由于光盘材料性能、光盘制造技术水平、驱动器性能和使用不

2、当等诸多原因，从盘上读出的数据不可能完全正确据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为310-4，沾有指纹的盘的误码率约为610-4，有伤痕的盘的误码率约为510-3光盘存储器采用了三种错误检测和纠正措施错误检测：采用循环冗余码(cyclic redundancy code，CRC)检测读出数据是否有错错误校正：采用里德索洛蒙码(Reed-Solomon Code,RS)进行纠错交叉交插里德-索洛蒙码(Cross Interleaved Reed-Solomon Code，CIRC),这个码的含义可理解为在用RS编译码前后，对数据进行交插和交叉处理,16章 错误检测和校正

3、,4,16.1 CRC错误检测原理与检测码,CRC错误检测原理代码多项式在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列10101111，用多项式可以表示成,式中,xi表示代码的位置或某个二进制数位的位置，前面的系数ai表示码的值，取值为0或1。M(x)称为信息代码多项式,16章 错误检测和校正,5,16.1 CRC错误检测原理与检测码(续1),模2多项式代数运算规则,模2多项式的加法和减法,代码多项式的模2加法和模2减法运算所得的结果相同，所以可用加法来代替减法,16章 错误检测和校正,6,16.1 CRC错误检测原理与检测码(续2),模2多项式的除法用

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

5、项式，它是能够被校验码生成多项式G(x)除尽的，即它的余项为0在盘上写数据时，将xn-kM(x)表示的信息代码和表示的余数R(x)代码一起写到盘上从盘上读数据时，将信息代码和余数代码一起读出，然后用相同的校验码生成多项式G(x)去除通过判断余数是否为0来确定数据是否有误,16章 错误检测和校正,10,16.1 CRC错误检测原理与检测码(续6),CD盘上的错误检测码CD-DA盘上的q通道使用的CRC校验码生成多项式,若用二进制表示，则为,假定要写到盘上的信息代码M(x)为,由于增加了2个字节的校验码，所以信息代码变成,16章 错误检测和校正,11,16.1 CRC错误检测原理与检测码(续7),

6、两数相除的结果其商可不必关心，其余数为B994(H)，这就是CRC校验码将信息代码和CRC码一起写到盘上写到盘上的信息代码和CRC码是4D6F746FB994，它能被错误检测从盘上把这块数据读出时，用同样的CRC码生成多项式去除，其结果是：(1)余数为0，表示读出没有错误；(2)余数不为0，表示读出有错,除尽,16章 错误检测和校正,12,16.1 CRC错误检测原理与检测码(续8),CD-ROM的错误检测在CD-ROM扇区方式1中，有一个4字节的EDC域用来存放CRC码。CRC校验码生成多项式是一个32阶的多项式,计算CRC码时用的数据块是从扇区的开头到用户数据区结束的数据字节，即字节020

7、63。在EDC中存放的CRC码的次序如下,16章 错误检测和校正,13,16.2 RS编码和纠错算法,16.2.1.GF(2m)域CD-ROM中的数据、地址、校验码等都可看成是属于GF(2m)=GF(28)中的元素或称符号。GF(28)表示域中有256个元素，除0和1之外的254个元素由本原多项式(primitive polynomial)P(x)生成。本原多项式P(x)的特性是 得到的余式等于0CD-ROM用来构造GF(28)域的P(x)是,而GF(28)域中的本原元素(primitive element)为=(0 0 0 0 0 0 1 0),16章 错误检测和校正,14,16.2 RS编

8、码和纠错算法(续1),例16.1 假设构造GF(23)域的本原多项式P(x)为 定义为P(x)=0的根，即31=0和 3=1 GF(23)中的元素计算如右表,16章 错误检测和校正,15,16.2 RS编码和纠错算法(续2),用二进制数表示域元素的对照表见表16-1,用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系,表16-1 GF(23)域中与二进制代码对照表(）,16章 错误检测和校正,16,16.2 RS编码和纠错算法(续3),伽罗华域中的加、减、乘和除运算,以GF(23)域中的运算为例，加法例：,减法例：与加法相同乘法例：,除法例：,取对数：,这些运算的

9、结果仍然在GF(23)域中,16章 错误检测和校正,17,16.2 RS编码和纠错算法(续4),16.2.2 RS的编码算法 RS的编码就是计算信息码符多项式M(x)除以校验码生成多项式G(x)之后的余数在GF(2m)域中，符号(n，k)RS的含义如下,例如，(28，24)RS码表示码块的长度为共28个符号，其中信息代码长度为24个符号，检验码有4个检验符号，可纠正其中出现的2个分散的或2个连续的符号错误，但不能纠正3个或3个以上的符号错误,16章 错误检测和校正,18,16.2 RS编码和纠错算法(续5),对一个信息码符多项式M(x)，RS校验码生成多项式的一般形式为,式中，K0是偏移量，通

10、常取K0=0或K0=1，而(n-k)2t(t为要校正的错误符号数),例16.2 假设在GF(23)域中的元素对应表见表16-1，(6，4)RS码中的4个信息符号为m3，m2，m1和m0，信息码符多项式为，,16章 错误检测和校正,19,16.2 RS编码和纠错算法(续6),假设RS校验码的2个符号为Q1和Q0，的剩余多项式为 这个多项式的阶次比的阶次少一阶。,如果K0=1，t=1，则RS校验码生成多项式为,根据多项式运算规则，可得到,16章 错误检测和校正,20,16.2 RS编码和纠错算法(续7),当用x=和x=2代入上式时，得到下面的方程组,经过整理可以得到用矩阵表示的(6，4)RS码的校

11、验方程为,16章 错误检测和校正,21,16.2 RS编码和纠错算法(续8),求解方程组可得到校验符号,在读出时的校正子可按下式计算,例16.3 在例16.2中，如果K0=0，t=1，则RS校验码生成多项式为，,16章 错误检测和校正,22,16.2 RS编码和纠错算法(续9),根据多项式的运算，可得到下面的方程组,方程中的i 可看成符号mi 的位置，此处的i=0，1，5,求解方程组可得到RS校验码的2个符号Q1和Q0,16章 错误检测和校正,23,16.2 RS编码和纠错算法(续10),假定mi(信息符号)为下列值 m3=0=001 m2=6=101 m1=3=011 m0=2=100可求得

12、校验符号,16章 错误检测和校正,24,16.2 RS编码和纠错算法(续11),16.2.3 RS码的纠错算法RS码的错误纠正过程分三步(1)计算校正子(syndrome)(2)计算错误位置和错误值(3)纠正错误现以【例16.3】为例介绍RS码的纠错算法校正子使用下面的方程组来计算：,16章 错误检测和校正,25,16.2 RS编码和纠错算法(续12),为简单起见，假定存入光盘的信息符号为m3，m2，m1，m0，由此产生的检验符号Q1和Q0均为0，读出的符号为(1)计算s1和s0如果计算得到的s1和s0都为0，则说明没有错误；如果计算得到的s1和s0不全为0，则说明有错，进入下一步(2)计算错

13、误位置和错误值s1和s0不全为0说明有错，但不知道有多少个错，也不知道错在什么位置和错误值。如果只有一个错误，并假设错误的位置为x，错误值为mx，那么可通过求解下面的方程组得知错误的位置和错误值：,16章 错误检测和校正,26,16.2 RS编码和纠错算法(续13),例如，计算得到s0=2和s1=5，则可求得x=3和mx=2，说明m1出了错，它的错误值是2(3)纠正错误知道了错误位置和错误值后就可纠正。纠正后的m1=m1+mx。本例中m1=0如果计算得到的结果为s0=0和s10，则基本上可断定至少有两个错误，已超出了纠错能力。CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed

14、Solomon Productlike Code，RSPC)都是采用上述方法导出的,16章 错误检测和校正,27,16.3 CIRC纠错技术,光盘存储器和其他存储器一样，经常遇到的错误有两种(1)随机错误：由随机干扰造成的错误，其特点是随机的和孤立的，干扰过后再读一次光盘，错误就可能消失(2)突发错误：连续多位出错或连续多个符号出错，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片CIRC(Cross Interleaved Reed Solomon)纠错码综合了交插、延时交插、交叉交插等技术，不仅能够纠正随机错误，而且对纠正突发错误特别有效,16章 错误检测和校正,28,1

15、6.3 CIRC纠错技术(续1),16.3.1 交插技术对纠错来说，分散的错误比较容易得到纠正，而对一长串的连续错误，就比较麻烦我们读书看报，如果文中在个别地方出错，根据前后文就容易判断是什么错。如果连续错的字比较多，就很难判断该处写的是什么。例如，用X表示出现的错字，两种错误形式“独在异乡XXX，每逢佳节倍思亲”，这是连续出现的错误“独在异乡X异客，每X佳节倍思X”，这是分散出现的错误哪种错误形式更容易纠正？把这种思想用在数字记录系统中，对纠正突发错误的更正非常有效在光盘上记录数据时，把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交

16、插(interleaving)技术,16章 错误检测和校正,29,16.3 CIRC纠错技术(续2),【例】3个(5，3)码块,排成3行,16章 错误检测和校正,30,16.3 CIRC纠错技术(续3),从这个例子中可以看到对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续错误如果有r个(n，k)码，每个(n，k)码能纠正t个错误，排成rn矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，那么可纠正tr个突发错误,16章 错误检测和校正,31,16.3 CIRC纠错技术(续4)

17、,16.3.2 交叉交插技术 交叉交插(crossinterleaving)编码是交插的一种变型，有实际的应用价值【例16.4】假设存储12个符号(a2,a1,a0,b2,，d2,d1,d0)，交叉交插步骤如下：(1)用(5，3)码编码器C2生成4个码块,16章 错误检测和校正,32,16.3 CIRC纠错技术(续5),(2)交插后用(6，4)码编码器C1生成5个码块,(3)再交插，交插的码块数可以是2、3、4或5。以交插2个码块为例：,(4)最后一个码块不配对，可以和下一个码块配对,16章 错误检测和校正,33,16.4 RSPC码,按ISO/IEC 10149(ECMA-130)规定，CD

18、-ROM扇区中的ECC码采用GF(28)域上的RSPC码，产生172个字节的P校验符号和104个字节的Q校验符号RS码采用本原多项式,和本原元,=(00000010),构造GF(28)域,CD-ROM的扇区,16章 错误检测和校正,34,16.4 RSPC码(续1),CD-ROM的扇区,按ISO/IEC 10149(ECMA-130)规定，CD-ROM扇区中的ECC码采用GF(28)域上的RSPC码，产生172个字节的P校验符号和104个字节的Q校验符号RS码采用本原多项式,和本原元,=(00000010),构造GF(28)域,16章 错误检测和校正,35,16.4 RSPC码(续2),从字节

19、12开始到字节2075共2064个字节组成的数据块排列成2443矩阵，见图16-2矩阵中的元素是字。这个矩阵要把它想象成两个独立的矩阵才比较好理解和分析，一个是由MSB字节组成的2443矩阵，另一个是由LSB字节组成的2443矩阵。,字节122075和ECC域中的字节2076到2351共2340个字节组成1170个字(word)每个字由两个字节B组成，一个称为最高有效位字节(MSB)，另一个称为最低有效位字节(LSB)。第n个字由下面的字节组成,其中n=0，1，2，1169,16章 错误检测和校正,36,16.4 RSPC码(续3),图16-2 RSPC码计算用数据阵列,16章 错误检测和校正

20、,37,16.4 RSPC码(续4),1.P校验符号用(26，24)RS码产生43列的每一列用矢量表示，记为Vp。每列有24个字节的数据再加2个字节的P校验字节，用下式表示,是P校验字节,其中,16章 错误检测和校正,38,16.4 RSPC码(续5),对这列字节计算得到的是两个P校验字节称为P校验符号。两个P校验字节加到24行和25行的对应列上，这样构成了一个2643的矩阵，并且满足方程,其中Hp校验矩阵为,16章 错误检测和校正,39,16.4 RSPC码(续6),2.Q校验符号用(45，43)RS码产生增加P校验字节后得到2643矩阵，将该矩阵的对角线元素重新排列后得到一个新的矩阵，其结

21、构见图16-3,图16-3 Q校验符号计算用数据阵列,16章 错误检测和校正,40,16.4 RSPC码(续7),每条对角线上的43个MSB字节和LSB字节组成的矢量记为VQ。VQ在2643矩阵中变成行矢量。第NQ行上的VQ矢量包含如下字节,其中，NQ=0，1，2，25MQ=0，1，2，42,是Q校验字节,16章 错误检测和校正,41,16.4 RSPC码(续8),VQ中的(44*MQ43*NQ)字节号运算结果要做mod(1118)运算。用(45，43)RS码产生的两个Q校验字节放到对应VQ矢量末端，并满足下面的方程：,其中HQ校验矩阵为,(26，24)RS码和(45，43)RS码可纠正出现在

22、任何一行和任何一列上的一个错误，并且能相当可靠地检测出行、列中的多重错误如果在一个阵列中出现多重错误，Reference Technology公司提供有一种名叫Layered ECC的算法，它可以取消多重错误。它的核心思想是交替执行行纠错和列纠错,16章 错误检测和校正,42,第16章 错误检测和校正参考文献,参考文献和站点ISO/IEC 908.Compact Disc Digital Audio System.1987ISO 9660.Volume and File structure of CD-ROM for Information Interchange.1988ISO/IEC 10

23、149.Data Interchange on Read Only 120 mm Optical Data Disks(CD-ROM).1989Scott A.Vanstone and Paul C.van Oorcshot.An Introduction Error Correcting Codes with Application.Kluwer,Academic Publishers,1989Philips and Sony.System Description CD-ROM XA Compact Disk Read Only Memory extended Architecture.May,1991Philips and Sony Corporation.CD-I Full Functional Specification.1993林福宗.陆达.多媒体与CD-ROM.北京：清华大学出版社，1995.3,END,第16章 错误检测和校正,