多媒体技术基础(第3版) 第16章 错误检测和校正

Presentation on theme: "多媒体技术基础(第3版) 第16章 错误检测和校正"— Presentation transcript:

1 多媒体技术基础(第3版) 第16章 错误检测和校正
林福宗 清华大学 计算机科学与技术系 2008年9月

2 第16章 错误检测和校正目录 16.1 CRC错误检测原理与检测码 16.2 RS编码和纠错算法 16.3 CIRC纠错技术
CD盘上的错误检测码 16.2 RS编码和纠错算法 GF(2m)域 RS的编码算法 RS码的纠错算法 16.3 CIRC纠错技术 交插技术 交叉交插技术 16.4 RSPC码 2019年4月11日 第16章 错误检测和校正

3 第16章 错误检测和校正——前言 光盘存储器需要纠错 光盘存储器采用了三种错误检测和纠正措施
由于光盘材料性能、光盘制造技术水平、驱动器性能和使用不当等诸多原因，从盘上读出的数据不可能完全正确 据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为3×10-4，沾有指纹的盘的误码率约为6×10-4，有伤痕的盘的误码率约为5×10-3 光盘存储器采用了三种错误检测和纠正措施 错误检测：采用循环冗余码(cyclic redundancy code，CRC)检测读出数据是否有错 错误校正： 采用里德－索洛蒙码(Reed-Solomon Code, RS)进行纠错 交叉交插里德-索洛蒙码 (Cross Interleaved Reed-Solomon Code，CIRC), 这个码的含义可理解为在用RS编译码前后，对数据进行交插和交叉处理 2019年4月11日 第16章 错误检测和校正

4 16.1 CRC错误检测原理与检测码 CRC错误检测原理 代码多项式
在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列 ，用多项式可以表示成 式中, xi表示代码的位置或某个二进制数位的位置，前面的系数ai表示码的值，取值为0或1。M(x)称为信息代码多项式 2019年4月11日 第16章 错误检测和校正

5 16.1 CRC错误检测原理与检测码(续1) 模2多项式代数运算规则 模2多项式的加法和减法
代码多项式的模2加法和模2减法运算所得的结果相同，所以可用加法来代替减法 2019年4月11日 第16章 错误检测和校正

6 16.1 CRC错误检测原理与检测码(续2) 模2多项式的除法用长除法 2019年4月11日 第16章 错误检测和校正

7 16.1 CRC错误检测原理与检测码(续3) 代码多项式的结构
如果一个k位的二进制信息代码多项式为M(x) ，增加(n－k)位的校验码后，信息代码多项式在新的数据块中就表示成xn-kM(x)，见图16-1 图16-1 信息代码结构 2019年4月11日 第16章 错误检测和校正

8 16.1 CRC错误检测原理与检测码(续4) 错误检测原理
如果用一个校验码G(x)生成多项式去除代码多项式M(x) ，得到的商假定为Q(x)，余式为R(x)，则可写成 因模2多项式的加法和减法运算结果相同，故可把上式写成 2019年4月11日 第16章 错误检测和校正

9 16.1 CRC错误检测原理与检测码(续5) 代表新的代码多项式，它是能够被校验码生成多项式G(x)除尽的，即它的余项为0
在盘上写数据时，将xn-kM(x)表示的信息代码和表示的余数R(x)代码一起写到盘上 从盘上读数据时，将信息代码和余数代码一起读出，然后用相同的校验码生成多项式G(x)去除 通过判断余数是否为0来确定数据是否有误 2019年4月11日 第16章 错误检测和校正

10 16.1 CRC错误检测原理与检测码(续6) CD盘上的错误检测码 CD-DA盘上的q通道使用的CRC校验码生成多项式 若用二进制表示，则为
假定要写到盘上的信息代码M(x)为 由于增加了2个字节的校验码，所以信息代码变成 2019年4月11日 第16章 错误检测和校正

11 16.1 CRC错误检测原理与检测码(续7) 两数相除的结果 将信息代码和CRC码一起写到盘上 错误检测
其商可不必关心，其余数为B994(H)，这就是CRC校验码 将信息代码和CRC码一起写到盘上 写到盘上的信息代码和CRC码是4D6F746FB994，它能被 错误检测 从盘上把这块数据读出时，用同样的CRC码生成多项式去除，其结果是：(1) 余数为0，表示读出没有错误；(2) 余数不为0，表示读出有错 除尽 2019年4月11日 第16章 错误检测和校正

12 16.1 CRC错误检测原理与检测码(续8) CD-ROM的错误检测
在CD-ROM扇区方式1中，有一个4字节的EDC域用来存放CRC码。CRC校验码生成多项式是一个32阶的多项式 计算CRC码时用的数据块是从扇区的开头到用户数据区结束的数据字节，即字节0～2063。在EDC中存放的CRC码的次序如下 EDC x24－x31 x16－x23 X8－x15 x0－x7 字节号 2064 2065 2066 2067 2019年4月11日 第16章 错误检测和校正

13 而GF(28)域中的本原元素(primitive element)为
16.2 RS编码和纠错算法 GF(2m)域 CD-ROM中的数据、地址、校验码等都可看成是属于GF(2m) = GF(28)中的元素或称符号。GF(28)表示域中有256个元素，除0和1之外的254个元素由本原多项式(primitive polynomial)P(x)生成。本原多项式P(x)的特性是 得到的余式等于0 CD-ROM用来构造GF(28)域的P(x)是 而GF(28)域中的本原元素(primitive element)为 α = ( ) 2019年4月11日 第16章 错误检测和校正

14 16.2 RS编码和纠错算法(续1) [例16.1] 假设构造GF(23)域的本原多项式P(x)为
α3 = α＋1 GF(23)中的元素计算如右表 2019年4月11日 第16章 错误检测和校正

15 16.2 RS编码和纠错算法(续2) 用二进制数表示域元素的对照表见表16-1
表16-1 GF(23)域中与二进制代码对照表( ） GF(23)域元素 二进制对代码 (000) α3 (011) α0 (001) α4 (110) α1 (010) α5 (111) α2 (100) α6 (101) 用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系 2019年4月11日 第16章 错误检测和校正

16 16.2 RS编码和纠错算法(续3) 伽罗华域中的加、减、乘和除运算 以GF(23)域中的运算为例， 加法例： 减法例：与加法相同 乘法例：
除法例： 取对数： 这些运算的结果仍然在GF(23)域中 2019年4月11日 第16章 错误检测和校正

17 16.2 RS编码和纠错算法(续4) 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个以上的符号错误 2019年4月11日 第16章 错误检测和校正

18 16.2 RS编码和纠错算法(续5) 对一个信息码符多项式M(x) ，RS校验码生成多项式的一般形式为
式中，K0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)≥2t (t为要校正的错误符号数) [例16.2] 假设在GF(23)域中的元素对应表见表16-1，(6，4)RS码中的4个信息符号为m3， m2 ， m1和m0 ，信息码符多项式为， 2019年4月11日 第16章 错误检测和校正

19 16.2 RS编码和纠错算法(续6) 假设RS校验码的2个符号为Q1和Q0， 的剩余多项式为 这个多项式的阶次比的阶次少一阶。
如果K0=1，t = 1，则RS校验码生成多项式为 根据多项式运算规则，可得到 2019年4月11日 第16章 错误检测和校正

20 16.2 RS编码和纠错算法(续7) 当用x=α和x=α2代入上式时，得到下面的方程组 经过整理可以得到用矩阵表示的(6，4)RS码的
校验方程为 2019年4月11日 第16章 错误检测和校正

21 16.2 RS编码和纠错算法(续8) 求解方程组可得到校验符号 在读出时的校正子可按下式计算
[例16.3] 在例16.2中，如果K0=0，t = 1，则RS校验码生成多项式为， 2019年4月11日 第16章 错误检测和校正

22 16.2 RS编码和纠错算法(续9) 根据多项式的运算，可得到下面的方程组 求解方程组可得到RS校验码的2个符号Q1和Q0
方程中的αi 可看成符号mi 的位置，此处的i=0，1，…，5 求解方程组可得到RS校验码的2个符号Q1和Q0 2019年4月11日 第16章 错误检测和校正

23 16.2 RS编码和纠错算法(续10) 假定mi (信息符号)为下列值 m3 = α0 = 001 m2 = α6 = 101
可求得校验符号 2019年4月11日 第16章 错误检测和校正

24 16.2 RS编码和纠错算法(续11) 16.2.3 RS码的纠错算法 RS码的错误纠正过程分三步
(1)计算校正子(syndrome) (2)计算错误位置和错误值 (3) 纠正错误 现以【例16.3】为例介绍RS码的纠错算法 校正子使用下面的方程组来计算： 2019年4月11日 第16章 错误检测和校正

25 16.2 RS编码和纠错算法(续12) (1) 计算s1和s0 (2) 计算错误位置和错误值
为简单起见，假定存入光盘的信息符号为m3，m2，m1，m0，由此产生的检验符号Q1和Q0均为0，读出的符号为 (1) 计算s1和s0 如果计算得到的s1和s0都为0，则说明没有错误；如果计算得到的s1和s0不全为0，则说明有错，进入下一步 (2) 计算错误位置和错误值 s1和s0不全为0说明有错，但不知道有多少个错，也不知道错在什么位置和错误值。如果只有一个错误，并假设错误的位置为αx，错误值为mx，那么可通过求解下面的方程组得知错误的位置和错误值： 2019年4月11日 第16章 错误检测和校正

26 16.2 RS编码和纠错算法(续13) 例如，计算得到s0=α2和s1=α5，则可求得αx=α3和mx=α2，说明m1出了错，它的错误值是α2 (3) 纠正错误 知道了错误位置和错误值后就可纠正。纠正后的m1= m'1+mx。本例中m1=0 如果计算得到的结果为s0=0和s1≠0，则基本上可断定至少有两个错误，已超出了纠错能力。 CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed Solomon Product－like Code，RSPC)都是采用上述方法导出的 2019年4月11日 第16章 错误检测和校正

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

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

29 16.3 CIRC纠错技术(续2) 【例】 3个(5，3)码块 排成3行 a2 a1 a0 P1 P0 b2 b1 b0 Q1 Q0 c2
连续排列成： a2 a1 a0 P1 P0 b2 b1 b0 Q1 Q0 c2 c1 c0 R1 R0 交插排列： 连续错3个： X 读出后重新排列： 2019年4月11日 第16章 错误检测和校正

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

31 16.3 CIRC纠错技术(续4) 交叉交插技术 交叉交插(cross－interleaving)编码是交插的一种变型，有实际的应用价值 【例16.4】 假设存储12个符号(a2, a1, a0, b2,…，d2, d1, d0)，交叉交插步骤如下： (1) 用(5，3)码编码器C2生成4个码块 2019年4月11日 第16章 错误检测和校正

32 16.3 CIRC纠错技术(续5) (2) 交插后用(6，4)码编码器C1生成5个码块 a2 b2 c2 d2 T1 T0 a1 b1 c1
U1 U0 a0 B0 c0 d0 V1 V0 P1 Q1 R1 S1 W1 W0 P0 Q0 R0 S0 X1 X0 (3) 再交插，交插的码块数可以是2、3、4或5。以交插2个码块为例： a2 a1 b2 b1 c2 c1 d2 d1 T1 U1 T0 U0 a0 P1 b0 Q1 c0 R1 d0 S1 … (4) 最后一个码块不配对，可以和下一个码块配对 2019年4月11日 第16章 错误检测和校正

33 16.4 RSPC码 按ISO/IEC 10149(ECMA-130)规定，CD-ROM扇区中的ECC码采用GF(28)域上的RSPC码，产生172个字节的P校验符号和104个字节的Q校验符号 RS码采用本原多项式 和本原元 α = ( ) 构造GF(28)域 CD-ROM的扇区 2019年4月11日 第16章 错误检测和校正

34 16.4 RSPC码(续1) 按ISO/IEC 10149(ECMA-130)规定，CD-ROM扇区中的ECC码采用GF(28)域上的RSPC码，产生172个字节的P校验符号和104个字节的Q校验符号 RS码采用本原多项式 和本原元 α = ( ) 构造GF(28)域 CD-ROM的扇区 2352字节 同步字节 12字节 扇区地址 4字节 用户数据 2048字节 EDC 未用 8字节 ECC 276字节 2019年4月11日 第16章 错误检测和校正

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

36 16.4 RSPC码(续3) 图16-2 RSPC码计算用数据阵列 2019年4月11日 第16章 错误检测和校正

37 16.4 RSPC码(续4) 1. P校验符号用(26，24)RS码产生
43列的每一列用矢量表示，记为Vp。每列有24个字节的数据再加2个字节的P校验字节，用下式表示 其中, 是P校验字节 2019年4月11日 第16章 错误检测和校正

38 16.4 RSPC码(续5) 对这列字节计算得到的是两个P校验字节称为P校验符号。两个P校验字节加到24行和25行的对应列上，这样构成了一个26×43的矩阵，并且满足方程 其中Hp校验矩阵为 2019年4月11日 第16章 错误检测和校正

39 16.4 RSPC码(续6) 2. Q校验符号用(45，43)RS码产生
2019年4月11日 第16章 错误检测和校正

40 16.4 RSPC码(续7) 每条对角线上的43个MSB字节和LSB字节组成的矢量记为VQ。VQ在26×43矩阵中变成行矢量。第NQ行上的VQ矢量包含如下字节 其中， NQ = 0，1，2，…，25 MQ = 0，1，2，…，42 是Q校验字节 2019年4月11日 第16章 错误检测和校正

41 16.4 RSPC码(续8) VQ中的(44*MQ＋43*NQ)字节号运算结果要做mod(1118)运算。用(45，43)RS码产生的两个Q校验字节放到对应VQ矢量末端，并满足下面的方程： 其中HQ校验矩阵为 (26，24)RS码和(45，43)RS码可纠正出现在任何一行和任何一列上的一个错误，并且能相当可靠地检测出行、列中的多重错误 如果在一个阵列中出现多重错误，Reference Technology公司提供有一种名叫Layered ECC的算法，它可以取消多重错误。它的核心思想是交替执行行纠错和列纠错 2019年4月11日 第16章 错误检测和校正

42 第16章 错误检测和校正参考文献 参考文献和站点
ISO/IEC 908. Compact Disc Digital Audio System. 1987 ISO Volume and File structure of CD-ROM for Information Interchange. 1988 ISO/IEC Data Interchange on Read Only 120 mm Optical Data Disks (CD-ROM). 1989 Scott A.Vanstone and Paul C. van Oorcshot. An Introduction Error Correcting Codes with Application. Kluwer, Academic Publishers, 1989 Philips and Sony. System Description CD-ROM XA Compact Disk Read Only Memory extended Architecture. May, 1991 Philips and Sony Corporation. CD-I Full Functional Specification. 1993 林福宗 .陆达. 多媒体与CD-ROM. 北京：清华大学出版社，1995.3 2019年4月11日 第16章 错误检测和校正

43 END 第16章 错误检测和校正