光盘错误检测和校正

《光盘错误检测和校正》由会员分享，可在线阅读，更多相关《光盘错误检测和校正（14页珍藏版）》请在金锄头文库上搜索。

1、第 13 章 错误检测和校正 光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘制造生产技术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出的数据不可能完全正确。据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为 3104 ；沾有指纹的盘的误码率约为 6104 ；有伤痕的盘的误码率约为 510 。针对这种情况，激光盘存储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种：(1) 错误检测：采用 CRC(Cyclic Redundancy Code)检测读出数据是否有错。(2) 错误校正码： 采用里德索洛蒙码(ReedSolomon Co

2、de)，简称为RS 码，进行纠错。RS 码被认为是性能很好的纠错码。(3) 交叉交插里德索洛蒙码 CIRC(Cross Interleaved ReedSolomon Code), 这个码的含义可理解为在用 RS 编译码前后，对数据进行交插处理和交叉处理。对这些码的理论分析和计算有许多专著作了详尽的深入论述，对不需要开发纠错技术的读者仅需要了解错误检测和校正的一些基本概念即可。13.1 CRC 错误检测原理 在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列 10101111，用多项式可以表示成：M(x) = a 7x7 + a6x6 + a5x5 + a4

3、x4 + a3x3 + a2x2 + a1x1 + a0x0= x 7 + x6 + x5 + x4 + x3 + x2 + x1 + 1式中的 xi表示代码的位置，或某个二进制数位的位置，x i前面的系数 ai表示码的值。若 ai是一位二进制代码，则取值是 0 或 1。M(x)称为信息代码多项式。在模 2 多项式代数运算中定义的运算规则有：1x i + 1xi = 0-1x i = 1xi例如，模 2 多项式的加法和减法：从这两个例子中可以看到，对于模 2 运算来说，代码多项式的加法和减法运算所得的结果相同。所以在做代码多项式的减法时，可用做加法来代替做减法。代码多项式的除法可按长除法做。例

4、如：如果一个 k 位的二进制信息代码多项式为 M(x)，再增加( n k)位的校验码，那么增加( n k)位之后，信息代码多项式在新的数据块中就表示成 x n-kM(x) ，如图 13-01 所示。图 13-01 信息代码结构如果用一个校验码生成多项式 G(x) 去除代码多项式 x n-kM(x)，得到的商假定为 Q(x) ，余式为 R(x)，则可写成x n-kM(x) = Q(x)G(x) + R(x)因为模 2 多项式的加法和减法运算结果相同，所以又可把上式写成：x n-kM(x) + R(x) = Q(x)G(x)G(x) 称为校验码生成多项式。从该式中可以看到，代表新的代码多项式 x

5、n-kM(x) + R(x) 是能够被校验码生成多项式 G(x) 除尽的，即它的余项为 0。例如，CD 盘中的 q 通道和软磁盘存储器中使用的 CRC 校验码生成多项式是G(x) = x 16 + x12 + x5 + 1若用二进制表示，则为G(x) = 100010000000100001(B) = 11021(H)假定要写到盘上的信息代码 M(x) 为M(x) = 4D6F746F (H)由于增加了 2 个字节共 16 位的校验码，所以信息代码变成 x 16M(x): 4D6F746F0000(H)。 CRC 检验码计算如下：两数相除的结果，其商可不必关心，其余数为 B994(H)就是 C

6、RC 校验码。把信息代码写到盘上时，将原来的信息代码和 CRC 码一起写到盘上。在这个例子中，写到盘上的信息代码和 CRC 码是 4D6F746FB994,4D6F746F B994信息代码 CRC 码这个码是能被 11021(H)除尽的。从盘上把这块数据读出时，用同样的 CRC 码生成多项式去除这块数据，相除后得到的两种可能结果是：余数为 0，表示读出没有出现错误；余数不为 0，表示读出有错。CD-ROM 中也采用了相同的 CRC 检错。CD-ROM 扇区方式 01 中，有一个 4 字节共 32 位的 EDC 字域，它就是用来存放 CRC 码。不过，CD-ROM 采用的 CRC 校验码生成多

7、项式与软磁盘采用的生成多项式不同，它是一个 32 阶的多项式,P(x) = (x 16 + x15 + x2 + 1)(x16 + x2 + x + 1) 计算 CRC 码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节 02063 共 2064 个字节。在 EDC 中存放的 CRC 码的次序如下：EDC： x24x 31 x16x 23 x8x 15 x0x 7字节号： 2064 2065 2066 206713.2 RS 编码和纠错算法 13.2.1. GF(2m)域RS(Reed-Solomon)码在伽罗华域(Galois Field，GF)中运算的，因此在介绍 RS 码

8、之前先简要介绍一下伽罗华域。CD-ROM 中的数据、地址、校验码等都可以看成是属于 GF(2m) = GF(28)中的元素或称符号。GF(2 8)表示域中有 256 个元素，除 0，1 之外的 254 个元素由本原多项式 P(x)生成。本原多项式 P(x)的特性是 ，得到的余式等于0。CD-ROM 用来构造 GF(28) 域的 P(x)是P(x) = x 8 + x4 +x3 + x2 + 1 (131)而 GF(28)域中的本原元素为 = (0 0 0 0 0 0 1 0)下面以一个较简单例子说明域的构造。例 13.1 构造 GF(23)域的本原多项式 P(x)假定为P(x) = x 3 +

9、 x + 1 定义为 P(x) = 0 的根，即 31 = 0和 3 = 1GF(2 3)中的元素可计算如下：0 mod( 31) = 0 0 mod( 31) = 0 = 1 1 mod( 31) = 1 2 mod( 31) = 2 3 mod( 31) = 1 4 mod( 31) = 2 5 mod(31) = 2 11 6 mod( 31) = 21 7 mod( 31) = 0 8 mod( 31) = 1 用二进制数表示域元素得到表 13-01 所示的对照表表 13-01 GF(23)域中与二进制代码对照表,P(x) = GF(23)域元素 二进制对代码0 (000) 0 (00

10、1) 1 (010) 2 (100) 3 (011) 4 (110) 5 (111) 6 (101)这样一来就建立了 GF(23)域中的元素与 3 位二进制数之间的一一对应关系。用同样的方法可建立 GF(28)域中的 256 个元素与 8 位二进制数之间的一一对应关系。在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以 GF(23)域中运算为例：加法例： 0 3 = 001011 = 010 = 1减法例：与加法相同乘法例： 5 4 = (54) mod7 = 2除法例： 5/ 3 = 2 3/ 5 = -2 = (27) = 5取对数：log( 5) = 5这些运算的结果仍

11、然在 GF(23)域中。13.2.2 RS 的编码算法RS 的编码就是计算信息码符多项式 M(x)除以校验码生成多项式之后的余数。在介绍之前需要说明一些符号。在 GF(2m)域中，符号(n，k)RS 的含义如下：m表示符号的大小，如 m = 8 表示符号由 8 位二进制数组成n表示码块长度k表示码块中的信息长度K=nk = 2t表示校验码的符号数t表示能够纠正的错误数目例如，(28，24)RS 码表示码块长度共 28 个符号，其中信息代码的长度为24，检验码有 4 个检验符号。在这个由 28 个符号组成的码块中，可以纠正在这个码块中出现的 2 个分散的或者 2 个连续的符号错误，但不能纠正 3

12、 个或者 3个以上的符号错误。对一个信息码符多项式 M(x)，RS 校验码生成多项式的一般形式为(132)式中，m 0是偏移量，通常取 K0 = 0 或 K0= 1，而(n-k)2t(t 为要校正的错误符号数)。下面用两个例子来说明 RS 码的编码原理。例 13.2 设在 GF(23)域中的元素对应表如表 13-01 所示。假设(6，4)RS码中的 4 个信息符号为，信息码符多项式 M(x)为M(x) = m 3x3 + m2x + m1x + m0(133)并假设 RS 校验码的 2 个符号为 Q1和 Q0， 的剩余多项式 R(x)为R(x) = Q 1(x) + Q0这个多项式的阶次比 G

13、(x)的阶次少一阶。如果 K0 = 1，t = 1，由式(132)导出的 RS 校验码生成多项式就为= (x)(x 2)(134)根据多项式的运算，由式(133)和式(134)可以得到m 3x5m 2x4m 1x3m 0x2Q 1xQ 0 = (x)(x 2)Q(x)当用 x = 和 x = 2代入上式时，得到下面的方程组，经过整理可以得到用矩阵表示的(6，4)RS 码的校验方程：求解方程组就可得到校验符号：在读出时的校正子可按下式计算：例 13.3 在例 13.2 中，如果 K0 = 0，t = 1，由式(132)导出的 RS 校验码生成多项式就为= (x 0)(x 1) (135)根据多项

14、式的运算，由(133)和(135)可以得到下面的方程组：方程中的 i也可看成符号的位置，此处 i = 0，1，5。求解方程组可以得到 RS 校验码的 2 个符号为 Q1和 Q0，(136)假定 mi为下列值：信息符号m 3 = 0 = 001m 2 = 6 = 101m 1 = 3 = 011m 0 = 2 = 100校验符号 Q 1 = 6 = 101Q0 = 4 = 110校正子 s 0 = 0s1 = 0 代入(136)式可求得校验符号：Q 1 = 6 = 101Q 0 = 4 = 11013.2.3 RS 码的纠错算法RS 码的错误纠正过程分三步： (1)计算校正子(syndrome)

15、，(2)计算错误位置，(3)计算错误值。现以例 13.3 为例介绍 RS 码的纠错算法。校正子使用下面的方程组来计算：为简单起见，假定存入光盘的信息符号 m3、m 2、m 1、m 0和由此产生的检验符号 Q1、Q 0均为 0，读出的符号为 m3、m 2、m 1、m 0、Q 1和 Q0。如果计算得到的 s0和 s1不全为 0，则说明有差错，但不知道有多少个错，也不知道错在什么位置和错误值。如果只有一个错误，则问题比较简单。假设错误的位置为 x，错误值为 mx，那么可通过求解下面的方程组：得知错误的位置和错误值。如果计算得到 s0 = 2和 s1 = 5，可求得 x= 3和 mx = 2，说明 m1出了错，它的错误值是 2。校正后的 m1= m1m x ，本例中 m1=0。如果计算得到 s0 = 0，而 s10，那基本可断定至少有两个错误，当然出现两个以上的错误不一定都是 s0 = 0 和 s10。如果出现两个错误，而又能设法找到出错的位置，那么这两个错误也可以纠正。如已知两个错误 mx1和 mx2的位置 x1和 x2，那么求解方程组：就可知道这两个错误值