《最新多媒体技术基础3版6章错误检测和校正ppt课件.ppt》由会员分享，可在线阅读，更多相关《最新多媒体技术基础3版6章错误检测和校正ppt课件.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、16章 错误检测和校正2第第16章章 错误检测和校正目录错误检测和校正目录 n16.1 CRC错误检测原理与检测码错误检测原理与检测码16.1.1 CRC错误检测原理16.1.2 CD盘上的错误检测码n16.2 RS编码和纠错算法编码和纠错算法16.2.1 GF(2m)域16.2.2 RS的编码算法16.2.3 RS码的纠错算法n16.3 CIRC纠错技术纠错技术16.3.1 交插技术16.3.2 交叉交插技术n16.4 RSPC码码16章 错误检测和校正916.1 CRC错误检测原理与检测码错误检测原理与检测码(续续5) 代表新的代码多项式，它是能够被校验码生成多项式G(x)除尽的，即它的余
2、项为0n在盘上写数据时，将在盘上写数据时，将xn-kM(x)表示的信息代码和表示的信息代码和表示的余数表示的余数R(x)代码一起写到盘上代码一起写到盘上n从盘上读数据时，将信息代码和余数代码一起读从盘上读数据时，将信息代码和余数代码一起读出，然后用相同的校验码生成多项式出，然后用相同的校验码生成多项式G(x)去除去除n通过判断余数是否为通过判断余数是否为0来确定数据是否有误来确定数据是否有误 ( )( )n kxM xR x16章 错误检测和校正1016.1 CRC错误检测原理与检测码错误检测原理与检测码(续续6)nCD盘上的错误检测码盘上的错误检测码CD-DA盘上的q通道使用的CRC校验码生
3、成多项式 16125( )1G xxxx若用二进制表示，则为 ( )=10001000000100001(B) = 11021(H)G x假定要写到盘上的信息代码M(x)为 ( )=4D6F746F (H)M x由于增加了2个字节的校验码，所以信息代码变成 16( )4D6F746F0000(H)x M x 16章 错误检测和校正1116.1 CRC错误检测原理与检测码错误检测原理与检测码(续续7)两数相除的结果n其商可不必关心，其余数为B994(H)，这就是CRC校验码将信息代码和CRC码一起写到盘上n写到盘上的信息代码和CRC码是4D6F746FB994，它能被错误检测错误检测n从盘上把这
4、块数据读出时，用同样的CRC码生成多项式去除，其结果是：(1) 余数为0，表示读出没有错误；(2) 余数不为0，表示读出有错 ( )11021(H)G x 除尽16章 错误检测和校正1216.1 CRC错误检测原理与检测码错误检测原理与检测码(续续8)nCD-ROM的错误检测的错误检测在CD-ROM扇区方式1中，有一个4字节的EDC域用来存放CRC码。CRC校验码生成多项式是一个32阶的多项式 16152162( )(1)(1)P xxxxxxx计算CRC码时用的数据块是从扇区的开头到用户数据区结束的数据字节，即字节02063。在EDC中存放的CRC码的次序如下 EDCx24x31x16x23
5、X8x15x0 x7字节号206420652066206716章 错误检测和校正1316.2 RS编码和纠错算法编码和纠错算法 n16.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)是 21(1)/( )mxP x8432( )1P xxxxx而GF(28)域中的本原元素(primitive elem
6、ent)为 = (0 0 0 0 0 0 1 0)16章 错误检测和校正1416.2 RS编码和纠错算法编码和纠错算法(续续1)例例16.1 假设构造GF(23)域的本原多项式P(x)为 定义为P(x) = 0的根，即31 = 0和 3 = 1 GF(23)中的元素计算如右表 1)(3xxxP16章 错误检测和校正1516.2 RS编码和纠错算法编码和纠错算法(续续2)用二进制数表示域元素的对照表见表16-1用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系 GF(23)域元素二进制对代码GF(23)域元素二进制对代码 0 (000)3 (011)0 (001)4
7、 (110)1 (010)5 (111)2 (100)6 (101)表表16-1 GF(216-1 GF(23 3) )域中与二进制代码对照表域中与二进制代码对照表( ( ）3( )1P xxx16章 错误检测和校正1616.2 RS编码和纠错算法编码和纠错算法(续续3)伽罗华域中的加、减、乘和除运算031 001+011 = 010 = 54(5+4) mod 72532/35-2(-2+7)5/5log()5以GF(23)域中的运算为例，加法例：减法例：与加法相同乘法例：除法例：取对数：这些运算的结果仍然在GF(23)域中 16章 错误检测和校正1716.2 RS编码和纠错算法编码和纠错算
8、法(续续4)n16.2.2 RS的编码算法的编码算法 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个以上的符号错误 16章 错误检测和校正1816.2 RS编码和纠错算法编码和纠错算法(续续5)对一个信息码符多
9、项式M(x) ，RS校验码生成多项式的一般形式为010( )()KKiiG xx式中，K0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)2t (t为要校正的错误符号数) 例例16.2 假设在GF(23)域中的元素对应表见表16-1，(6，4)RS码中的4个信息符号为m3， m2 ， m1和m0 ，信息码符多项式为，323210( )M xm xm xm xm16章 错误检测和校正1916.2 RS编码和纠错算法编码和纠错算法(续续6)假设RS校验码的2个符号为Q1和Q0， 的剩余多项式为 这个多项式的阶次比的阶次少一阶。2( )( )( )( )n kM x xM x xG xG x
10、01QQ)(xxR如果K0=1，t = 1，则RS校验码生成多项式为0120( )()=()()KKiiG xxxx根据多项式运算规则，可得到54322321010()() ( )m xm xm xm xQ xQxxQ x16章 错误检测和校正2016.2 RS编码和纠错算法编码和纠错算法(续续7)当用x=和x=2代入上式时，得到下面的方程组 54323210102 5242 3222 13210100 ()()()()()0mmmmQQmmmmQQ经过整理可以得到用矩阵表示的(6，4)RS码的校验方程为54321252423222 132101001()()()()()1TQQQQHVHVm
11、mmmQQ16章 错误检测和校正2116.2 RS编码和纠错算法编码和纠错算法(续续8)求解方程组可得到校验符号 55041321030303210QmmmmQmmmm在读出时的校正子可按下式计算 例例16.3 在例16.2中，如果K0=0，t = 1，则RS校验码生成多项式为，01010( )()()()KKiiG xxxx16章 错误检测和校正2216.2 RS编码和纠错算法编码和纠错算法(续续9)根据多项式的运算，可得到下面的方程组32101054323210100 0mmmmQQmmmmQQ方程中的i 可看成符号mi 的位置，此处的i=0，1，5求解方程组可得到RS校验码的2个符号Q1
12、和Q02531321036403210QmmmmQmmmm16章 错误检测和校正2316.2 RS编码和纠错算法编码和纠错算法(续续10)假定mi (信息符号)为下列值n m3 = 0 = 001n m2 = 6 = 101n m1 = 3 = 011n m0 = 2 = 100可求得校验符号6140101110QQ16章 错误检测和校正2416.2 RS编码和纠错算法编码和纠错算法(续续11)n16.2.3 RS码的纠错算法码的纠错算法RS码的错误纠正过程分三步n (1)计算校正子(syndrome)n(2)计算错误位置和错误值n(3) 纠正错误现以现以【例【例16.3】为例介绍为例介绍RS
13、码的纠错算法码的纠错算法校正子使用下面的方程组来计算：032101054321321010 smmmmQQsmmmmQQ16章 错误检测和校正2516.2 RS编码和纠错算法编码和纠错算法(续续12)n为简单起见，假定存入光盘的信息符号为m3，m2，m1，m0，由此产生的检验符号Q1和Q0均为0，读出的符号为 (1) 计算s1和s0n如果计算得到的s1和s0都为0，则说明没有错误；如果计算得到的s1和s0不全为0，则说明有错，进入下一步(2) 计算错误位置和错误值ns1和s0不全为0说明有错，但不知道有多少个错，也不知道错在什么位置和错误值。如果只有一个错误，并假设错误的位置为x，错误值为mx
14、，那么可通过求解下面的方程组得知错误的位置和错误值：321010mmmmQQ， ，和01xxxsmsm16章 错误检测和校正2616.2 RS编码和纠错算法编码和纠错算法(续续13)n例如，计算得到s0=2和s1=5，则可求得x=3和mx=2，说明m1出了错，它的错误值是2(3) 纠正错误n知道了错误位置和错误值后就可纠正。纠正后的m1= m1+mx。本例中m1=0n如果计算得到的结果为s0=0和s10，则基本上可断定至少有两个错误，已超出了纠错能力。CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed Solomon Productlike Code，RSPC)都是采用上述方法
15、导出的 16章 错误检测和校正2716.3 CIRC纠错技术纠错技术光盘存储器和其他存储器一样，经常遇到的错误有两种n(1) 随机错误：由随机干扰造成的错误，其特点是随机的和孤立的，干扰过后再读一次光盘，错误就可能消失n(2) 突发错误：连续多位出错或连续多个符号出错，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片CIRC(Cross Interleaved Reed Solomon)纠错码综合了交插、延时交插、交叉交插等技术，不仅能够纠正随机错误，而且对纠正突发错误特别有效16章 错误检测和校正2816.3 CIRC纠错技术纠错技术(续续1)n16.3.1 交插技术交插技
16、术对纠错来说，分散的错误比较容易得到纠正，而对一长串的连续错误，就比较麻烦n我们读书看报，如果文中在个别地方出错，根据前后文就容易判断是什么错。如果连续错的字比较多，就很难判断该处写的是什么。n例如，用X表示出现的错字，两种错误形式u“独在异乡XXX，每逢佳节倍思亲”，这是连续出现的错误u“独在异乡X异客，每X佳节倍思X”，这是分散出现的错误n哪种错误形式更容易纠正？把这种思想用在数字记录系统中，对纠正突发错误的更正非常有效n在光盘上记录数据时，把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交插(interleaving)技术 16章
17、 错误检测和校正2916.3 CIRC纠错技术纠错技术(续续2)【例】 3个(5，3)码块121010221010321010( )( )( )Ba a a P PBb b b Q QBc c c R R排成3行a2a1a0P1P0b2b1b0Q1Q0c2c1c0R1R0连续排列成：a2a1a0P1P0b2b1b0Q1Q0c2c1c0R1R0交插排列：a2b2c2a1b1c1a0b0c0P1Q1R1P0Q0R0连续错3个：a2b2c2a1b1c1a0X XXQ1R1P0Q0R0读出后重新排列： a2a1a0X P0b2b1X Q1Q0c2c1X R1R016章 错误检测和校正3016.3 CI
18、RC纠错技术纠错技术(续续3)从这个例子中可以看到n对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续错误如果有r个 (n，k)码，每个(n，k)码能纠正t个错误，排成rn矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，那么可纠正tr个突发错误16章 错误检测和校正3116.3 CIRC纠错技术纠错技术(续续4)n16.3.2 交叉交插技术交叉交插技术 交叉交插(crossinterleaving)编码是交插的一种变型，有实际的应用价值 【例【例16.4】 假设存储12个符号
19、(a2, a1, a0, b2,，d2, d1, d0)，交叉交插步骤如下：(1) 用(5，3)码编码器C2生成4个码块121010221010321010421010( )( )( )( )Ba a a P PBb b b Q QBc c c R RBd d d S S16章 错误检测和校正3216.3 CIRC纠错技术纠错技术(续续5)(2) 交插后用(6，4)码编码器C1生成5个码块a2b2c2d2T1T0a1b1c1d1U1U0a0B0c0d0V1V0P1Q1R1S1W1W0P0Q0R0S0X1X0(3) 再交插，交插的码块数可以是2、3、4或5。以交插2个码块为例：a2a1b2b1c
20、2c1d2d1T1U1T0U0a0P1b0Q1c0R1d0S1(4) 最后一个码块不配对，可以和下一个码块配对 16章 错误检测和校正3316.4 RSPC码码按ISO/IEC 10149(ECMA-130)规定，CD-ROM扇区中的ECC码采用GF(28)域上的RSPC码，产生172个字节的P校验符号和104个字节的Q校验符号RS码采用本原多项式1)(2348xxxxxP和本原元 = (00000010) 构造GF(28)域CD-ROM的扇区16章 错误检测和校正3416.4 RSPC码码( (续续1)1)CD-ROM的扇区2352字节同步字节12字节扇区地址4字节用户数据2048字节EDC
21、4字节未用8字节ECC276字节按ISO/IEC 10149(ECMA-130)规定，CD-ROM扇区中的ECC码采用GF(28)域上的RSPC码，产生172个字节的P校验符号和104个字节的Q校验符号RS码采用本原多项式1)(2348xxxxxP和本原元 = (00000010) 构造GF(28)域16章 错误检测和校正3516.4 RSPC码码( (续续2)2)n从字节12开始到字节2075共2064个字节组成的数据块排列成2443矩阵，见图16-2u矩阵中的元素是字。这个矩阵要把它想象成两个独立的矩阵才比较好理解和分析，一个是由MSB字节组成的2443矩阵，另一个是由LSB字节组成的24
22、43矩阵。 n字节122075和ECC域中的字节2076到2351共2340个字节组成1170个字(word)n每个字由两个字节B组成，一个称为最高有效位字节(MSB)，另一个称为最低有效位字节(LSB)。第n个字由下面的字节组成 ( )MSBB(213)LSBB(212)s nnn其中n = 0，1，2，1169 16章 错误检测和校正3616.4 RSPC码码( (续续3)3)图16-2 RSPC码计算用数据阵列 16章 错误检测和校正3716.4 RSPC码码( (续续4)4)1. P校验符号用校验符号用(26，24)RS码产生码产生43列的每一列用矢量表示，记为Vp。每列有24个字节的
23、数据再加2个字节的P校验字节，用下式表示 (43 0)(43 1)(43 2)()(43)()(43 22)(43 23)(43 24)(43 25)pppPppppppsNsNsNssMNVssNsNsNsN 是P校验字节 其中, 0, 1, 2, , 420, 1, 2, , 25(43 24)(43 25)ppppNMsNsN和16章 错误检测和校正3816.4 RSPC码码( (续续5)5)对这列字节计算得到的是两个P校验字节称为P校验符号。两个P校验字节加到24行和25行的对应列上，这样构成了一个2643的矩阵，并且满足方程0PPHV252421111111pH其中Hp校验矩阵为16
24、章 错误检测和校正3916.4 RSPC码码( (续续6)6)2. Q校验符号用校验符号用(45，43)RS码产生码产生n增加P校验字节后得到2643矩阵，将该矩阵的对角线元素重新排列后得到一个新的矩阵，其结构见图16-3 图16-3 Q校验符号计算用数据阵列 16章 错误检测和校正4016.4 RSPC码码( (续续7)7)n每条对角线上的43个MSB字节和LSB字节组成的矢量记为VQ。VQ在2643矩阵中变成行矢量。第NQ行上的VQ矢量包含如下字节(44 043)(44 1 43)(44 243)( )(4443)( )(44 41 43)(44 4243)(43 26 )(44 26 )
25、QQQQQQQQQQsNsNsNssMNVssNsNsNsN 其中，NQ = 0，1，2，25MQ = 0，1，2，42是Q校验字节(43 26)(44 26)QQsNsN和16章 错误检测和校正4116.4 RSPC码码( (续续8)8)nVQ中的(44*MQ43*NQ)字节号运算结果要做mod(1118)运算。用(45，43)RS码产生的两个Q校验字节放到对应VQ矢量末端，并满足下面的方程：0QQHV其中HQ校验矩阵为444321111111QH(26，24)RS码和码和(45，43)RS码可纠正出现在任何一码可纠正出现在任何一行和任何一列上的一个错误，并且能相当可靠地检行和任何一列上的一
26、个错误，并且能相当可靠地检测出行、列中的多重错误测出行、列中的多重错误n如果在一个阵列中出现多重错误，Reference Technology公司提供有一种名叫Layered ECC的算法，它可以取消多重错误。它的核心思想是交替执行行纠错和列纠错 16章 错误检测和校正42第第16章章 错误检测和校正参考文献错误检测和校正参考文献 n参考文献和站点参考文献和站点ISO/IEC 908. Compact Disc Digital Audio System. 1987ISO 9660. Volume and File structure of CD-ROM for Information Inte
27、rchange. 1988ISO/IEC 10149. 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. 19931.林福宗 .陆达. 多媒体与CD-ROM. 北京：清华大学出版社，1995.3 2008-07-0143END第16章 错误检测和校正