第16章 错误检测和校正
***************************************************************************
16.1 CRC错误检测原理
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码练习与思考题参考文献和站点
***************************************************************************
光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘制造生产技术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出的数据不可能完全正确。据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为3×10－4；沾有指纹的盘的误码率约为6×10－4；有伤痕的盘的误码率约为5×10－３。针对这种情况，激光盘存储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种：
(1) 错误检测：采用CRC(Cyclic Redundancy Code)检测读出数据是否有错。
(2) 错误校正码,采用里德－索洛蒙码(Reed－Solomon Code)，简称为RS码，进行纠错。RS码被认为是性能很好的纠错码。
(3) 交叉交插里德－索洛蒙码CIRC(Cross Interleaved Reed－Solomon Code),这个码的含义可理解为在用RS编译码前后，对数据进行交插处理和交叉处理。
对这些码的理论分析和计算有许多专著作了详尽的深入论述，对不需要开发纠错技术的读者仅需要了解错误检测和校正的一些基本概念即可。
16.1 CRC错误检测原理在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列10101111，用多项式可以表示成：
=
式中的表示代码的位置，或某个二进制数位的位置，前面的系数ai表示码的值。若ai是一位二进制代码，则取值是0或1。称为信息代码多项式。
在模2多项式代数运算中定义的运算规则有：
例如，模2多项式的加法和减法：
从这两个例子中可以看到，对于模2运算来说，代码多项式的加法和减法运算所得的结果相同。所以在做代码多项式的减法时，可用做加法来代替做减法。
代码多项式的除法可按长除法做。例如：
如果一个k位的二进制信息代码多项式为，再增加(n－k)位的校验码，那么增加(n－k)位之后，信息代码多项式在新的数据块中就表示成，如图16-01所示。
图16-01 信息代码结构如果用一个校验码生成多项式去除代码多项式，得到的商假定为，余式为，则可写成
因为模2多项式的加法和减法运算结果相同，所以又可把上式写成：
称为校验码生成多项式。从该式中可以看到，代表新的代码多项式是能够被校验码生成多项式除尽的，即它的余项为0。
例如，CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是
若用二进制表示，则为
=10001000000100001(B)
=11021(H)
假定要写到盘上的信息代码为
=4D6F746F (H)
由于增加了2个字节共16位的校验码，所以信息代码变成,4D6F746F0000(H)。 CRC检验码计算如下：
两数相除的结果，其商可不必关心，其余数为B994(H)就是CRC校验码。把信息代码写到盘上时，将原来的信息代码和CRC码一起写到盘上。在这个例子中，写到盘上的信息代码和CRC码是4D6F746F B994,
4D6F746F
B994
信息代码
CRC码
这个码是能被11021(H)除尽的。
从盘上把这块数据读出时，用同样的CRC码生成多项式去除这块数据，相除后得到的两种可能结果是：①余数为0，表示读出没有出现错误；②余数不为0，表示读出有错。
CD-ROM中也采用了相同的CRC检错。CD-ROM扇区方式01中，有一个4字节共32位的EDC字域，它就是用来存放CRC码。不过，CD-ROM采用的CRC校验码生成多项式与软磁盘采用的生成多项式不同，它是一个32阶的多项式,
计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节0～2063共2064个字节。在EDC中存放的CRC码的次序如下：
EDC：
x24－x31
x16－x23
x8－x15
x0－x7
字节号：
2064
2065
2066
2067
16.2 RS编码和纠错算法
16.2.1,GF(2m)域
RS(Reed-Solomon)码是在伽罗华域(Galois Field，GF)中运算的，因此在介绍RS码之前先简要介绍一下伽罗华域。
CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m) = GF(28)中的元素或称符号。GF(28)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式的特性是得到的余式等于0。CD-ROM用来构造GF(28)域的是
(13－1)
而GF(28)域中的本原元素为
α = (0 0 0 0 0 0 1 0)
下面以一个较简单例子说明域的构造。
[例16.1] 构造GF(23)域的本原多项式假定为
α定义为 = 0的根，即
α3＋α＋1 = 0
和 α3 = α＋1
GF(23)中的元素可计算如下：
0
mod(α3＋α＋1) = 0
α0
mod(α3＋α＋1) = α0 = 1
α1
mod(α3＋α＋1) = α1
α2
mod(α3＋α＋1) = α2
α3
mod(α3＋α＋1) = α＋1
α4
mod(α3＋α＋1) = α2＋α
α5
mod(α3＋α＋1) = α2＋α1＋1
α6
mod(α3＋α＋1) = α2＋1
α7
mod(α3＋α＋1) = α0
α8
mod(α3＋α＋1) = α1
……
用二进制数表示域元素得到表16-01所示的对照表
表16-01 GF(23)域中与二进制代码对照表,
GF(23)域元素
二进制对代码
0
(000)
α0
(001)
α1
(010)
α2
(100)
α3
(011)
α4
(110)
α5
(111)
α6
(101)
这样一来就建立了GF(23)域中的元素与3位二进制数之间的一一对应关系。用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(23)域中运算为例：
加法例：α0＋α3 = 001＋011
= 010 = α1
减法例：与加法相同乘法例：α5·α4 = α(5＋4) mod7
= α2
除法例：α5/α3 = α2
α3/α5 = α－2
= α(－2＋7)
= α5
取对数：log(α5) = 5
这些运算的结果仍然在GF(23)域中。
16.2.2 RS的编码算法
RS的编码就是计算信息码符多项式除以校验码生成多项式之后的余数。
在介绍之前需要说明一些符号。在GF(2m)域中，符号(n，k)RS的含义如下：
M
表示符号的大小，如m = 8表示符号由8位二进制数组成
n
表示码块长度，
k
表示码块中的信息长度
K=n－k = 2t
表示校验码的符号数
t
表示能够纠正的错误数目
例如，(28，24)RS码表示码块长度共28个符号，其中信息代码的长度为24，检验码有4个检验符号。在这个由28个符号组成的码块中，可以纠正在这个码块中出现的2个分散的或者2个连续的符号错误，但不能纠正3个或者3个以上的符号错误。
对一个信息码符多项式，RS校验码生成多项式的一般形式为
(13－2)
式中，K0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)≥2t (t为要校正的错误符号数)。
下面用两个例子来说明RS码的编码原理。
[例16.2] 设在GF(23)域中的元素对应表如表16 01所示。假设(6，4)RS码中的4个信息符号为m3、m2、m1和m0，信息码符多项式为
(13－3)
并假设RS校验码的2个符号为Q1和Q0，的剩余多项式为
这个多项式的阶次比的阶次少一阶。
如果K0 = 1，t = 1，由式(13－2)导出的RS校验码生成多项式就为
= (13－4)
根据多项式的运算，由式(13－3)和式(13－4)可以得到
m3x5＋m2x4＋m1x3＋m0x2＋Q1x＋Q0 = (x－α)(x－α2)Q(x)
当用x = α和x = α2代入上式时，得到下面的方程组，
经过整理可以得到用矩阵表示的(6，4)RS码的校验方程：
求解方程组就可得到校验符号：
在读出时的校正子可按下式计算：
[例16.3] 在例16.2中，如果K0 = 0，t = 1，由式(13－2)导出的RS校验码生成多项式就为
= (13－5)
根据多项式的运算，由(13－3)和(13－5)可以得到下面的方程组：
方程中的αi也可看成符号的位置，此处i = 0，1，…，5。
求解方程组可以得到RS校验码的2个符号为Q1和Q0，
(13－6)
假定mi为下列值：
信息符号
m3 = α0 = 001
m2 = α6 = 101
m1 = α3 = 011
m0 = α2 = 100
校验符号
Q1 = α6 = 101
Q0 = α4 = 110
校正子
s0 = 0
s1 = 0
代入(13－6)式可求得校验符号：
Q1 = α6 = 101
Q0 = α4 = 110
16.2.3 RS码的纠错算法
RS码的错误纠正过程分三步,(1)计算校正子(syndrome)，(2)计算错误位置，(3)计算错误值。现以例16.3为例介绍RS码的纠错算法。
校正子使用下面的方程组来计算：
为简单起见，假定存入光盘的信息符号m3、m2、m1、m0和由此产生的检验符号Q1、Q0均为0，读出的符号为m3′、m2′、m1′、m0′、Q1′和Q0′。
如果计算得到的s0和s1不全为0，则说明有差错，但不知道有多少个错，也不知道错在什么位置和错误值。如果只有一个错误，则问题比较简单。假设错误的位置为αx，错误值为mx，那么可通过求解下面的方程组：
得知错误的位置和错误值。
如果计算得到s0 = α2和s1 = α5，可求得αx = α3和mx = α2，说明m1出了错，它的错误值是α2。校正后的m1 = m1′＋mx,本例中m1=0。
如果计算得到s0 = 0，而s1≠0，那基本可断定至少有两个错误，当然出现两个以上的错误不一定都是s0 = 0和s1≠0。如果出现两个错误，而又能设法找到出错的位置，那么这两个错误也可以纠正。如已知两个错误和的位置和，那么求解方程组：
就可知道这两个错误值。
CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed Solomon Product－like Code，RSPC)就是采用上述方法导出的。
16.3 CIRC纠错技术光盘存储器和其它的存储器一样，经常遇到的错误有两种。一种是由于随机干扰造成的错误，这种错误称随机错误。它的特点是随机的、孤立的，干扰过后再读一次光盘，错误就可能消失。另一种错误是连续多位出错，或连续多个符号出错，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片。这种错误称为突发错误。CIRC(Cross Interleaved Reed Solomon)纠错码综合了交插、延时交插、交叉交插等技术，不仅能纠随机错误，而且对纠突发错误特别有效。
16.3.1 交插技术对纠错来说，分散的错误比较容易得到纠正，但出现一长串的错误时，就较麻烦。正如我们读书看报，如果文中在个别地方出错，根据前后文就容易判断是什么错。如果连续错好多字，就很难判断该处写的是什么。
例如，用X表示出现的错字，一种错误形式为“独在异乡XXX，每逢佳节倍思亲”，这是连续出现的错误，另一种错误形式为“独在异乡X异客，每X佳节倍思X”，这是分散出现的错误。这两种错误形式相比，同样是3个错误，但人们更容易更正后一种形式的错误，更正之后为“独在异乡为异客，每逢佳节倍思亲”。
这个道理很简单，把这种思想用在数字记录系统中对突发错误的更正非常有效。在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交插(interleaving)技术。例如，**************************************************************************
3个(5，3)码块, B1 = (a2，a1，a0，P1，P0)
B2 = (b2，b1，b0，Q1，Q0)
B3 = (c2，c1，c0，R1，R0)
连续排列,
a2 a1 a0 P1 P0
b2 b1 b0 Q1 Q0
c2 c1 c0 R1 R0
排成3行：
a2
a1
a0
P1
P0
b2
b1
b0
Q1
Q0
c2
c1
c0
R1
R0
交插排列：
a2
b2
c2
a1
b1
c1
a0
b0
c0
P1
Q1
R1
P0
Q0
R0
连续错3个：
a2
b2
c2
a1
b1
c1
a0
X
X
X
Q1
R1
P0
Q0
R0
读出后重新排列,
a2
a1
a0
X
P0
b2
b1
X
Q1
Q0
c2
c1
X
R1
R0
**************************************************************************
从这个例子中可以看到，对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续的错误。
一般来说，如果有r个(n，k)码，排成r×n矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若(n，k)码能纠正t个错误，那么这样交插后就可以纠正rt个突发错误。
16.3.2 交叉交插技术交叉交插(cross－interleaving)编码是交插的一种变型。在实际应用中，也是一种重要的技术。现仍以简单的例子说明这种技术思想。
**************************************************************************
(1) 用(5，3)码编码器C2生成的4个码块为:
B1
=
(a2
a1
a0
P1
P0)
B2
=
(b2
b1
b0
Q1
Q0)
B3
=
(c2
c1
c0
R1
R0)
B4
=
(d2
d1
d0
S1
S0)
(2) 交插后再用(6，4)码编码器C1生成5个码块为:
a2
b2
c2
d2
T1
T0
a1
b1
c1
d1
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) 最后一个码块不配对，可以和下一个码块配对。
**************************************************************************
这种编码技术用了两个编码器C2和C1。C2对原码块进行编码得到(5，3)码块，交插后生成由4个符号组成的码块，码块中的符号是交叉存放的，然后再用(6，4)编码器C1去编码。
有关CIRC详细的实现方法请参看文献[7]。
CIRC首先应用在激光唱盘系统中。音频信号的采样率为44.1 kHz，而每次采样有两个16比特的样本，一个来自左声道，一个来自右声道，每个样本用两个GF(28)域中的符号表示，因此每次采样共有4个符号。
为了纠正可能出现的错误，每6次采样共24个符号构成1帧，称为F1帧(F1－Frame)。用一个称为C2的编码器对这24个符号产生4个Q校验符号,Q0，Q1，Q2和Q3。24个声音数据加上4个Q校验符号共28个符号，用称为C1编码器对这28个符号产生4个P校验符号,P0，P1，P2和P3。28个符号加上4个P校验符号共32个符号构成的帧称为F2帧(F2－Frame)。F2帧加上1个字节(即1个符号)的子码共33个符号构成的帧称为F3帧(F3－Frame)。
在实际应用中可对前面介绍的交插技术略加修改，执行交插时不是交插包含有k个校验符的码块，而是交插一个连续系列中的码符，这种交插技术称为延时交插。延时交插之后还可用交叉技术，称为延时交叉交插技术。CD存储器中的CIRC编码器采用了4×F1帧的延时交插方案。1帧延时交插可纠正连续4×F1帧的突发错误。4×F2帧的延时交插可纠正连续16×F1帧突发错误，相当于大约14×F3帧的突发错误。1×F3帧经过EFM编码后产生588位通道位。1位通道位的长度折合成0.277μm的光道长度。14×F3帧突发错误长度相当于
［(16×(24＋4))/33］×588×0.277≈2.2 mm
换句话说，CIRC能纠正在2.2 mm光道上连续存放的448个错误符号! 相当于连续224个汉字错误可以得到纠正。
16.4 RSPC码按ISO/IEC10149的规定，CD-ROM扇区中的ECC码采用GF(28)域上的RSPC码产生172个字节的P校验符号和104个字节的Q校验符号。RS码采用本原多项式
和本原元
α = (00000010)
构造GF(28)域，这已经在上节作了介绍。
第12章已经介绍了CD-ROM的扇区结构。在每个扇区中，字节12～2075和ECC域中的字节2076到2351共2340个字节组成1170个字(word)。每个字s(n)由两个字节B组成，一个称为最高有效位字节MSB，另一个叫做最低有效位字节LSB。第n个字由下面的字节组成，
其中n = 0，1，2，…，1169。
从字节12开始到字节2075共2064个字节组成的数据块排列成24×43的矩阵，如图16 02所示。
NP
0
1
2
3
41
42
0
000
0001
0002
…
…
…
0041
0042
1
0043
0044
0045
…
…
…
0084
0085
HEADER
2
0086
0087
0088
…
…
…
0127
0128
+
P
Q
用户数据
＋
MP
22
0946
0947
0948
…
…
…
0987
0988
部分辅助数据
23
0989
0990
0991
…
…
…
1030
1031
24
1032
1033
1034
1073
1074
P-校验
25
1075
1076
1077
…
…
…
1116
1117
26
1118
1119
1120
…
1143
Q-校验
27
1144
1145
1146
…
1169
0
1
2
…
25
(ISO /IEC1049)
图16－02 RSPC码计算用数据阵列矩阵中的元素是字。这个矩阵要把它想象成两个独立的矩阵才比较好理解和分析，一个是由MSB字节组成的24×43矩阵，另一个是由LSB字节组成的24×43矩阵。
(1) P校验符号用(26，24)RS码产生
43列的每一列用矢量表示，记为Vp。每列有24个字节的数据再加2个字节的P校验字节，用下式表示：
其中：
0，1，2，……，42
0，1，2，……，25
和是P校验字节对这列字节计算得到的是两个P校验字节，称为P校验符号。两个P校验字节加到24行和25行的对应列上，这样构成了一个26×43的矩阵，并且满足方程
其中HP校验矩阵为
2,Q校验符号用(45，43)RS码产生增加P校验字节之后得到了一个26×43矩阵，该矩阵的对角线元素重新排列后得到一个新的矩阵，其结构如图16 03所示。
MQ
0
1
2
40
41
42
Q0
Q1
0
0000
0044
0088
…
…
0642
0686
0730
1118
1144
1
0043
0087
0131
…
…
0685
0729
0773
1119
1145
2
0086
0130
0147
…
…
0728
0772
0816
1120
1146
3
0129
0137
0217
…
…
0771
0815
0859
1121
1147
4
0172
0216
0260
…
…
0814
0858
0902
1122
1148
22
0946
0990
1034
…
…
0470
0514
0558
1140
1166
NQ
23
0989
1033
1077
…
…
0513
0557
0601
1141
1167
24
1032
1076
0002
…
…
0556
0600
0644
1142
1168
25
1075
0001
0045
…
…
0599
0643
0687
1143
1169
(ISO/IEC 10149∶1989)
图16 03 Q校验符号计算用数据阵列每条对角线上的43个MSB字节和LSB字节组成的矢量记为VQ。VQ在26×43矩阵中变成行矢量。第NQ行上的VQ矢量包含的字节如下：
其中：
NQ = 0，1，2，…，25
MQ = 0，1，2，…，42
和是Q校验字节
VQ中的(44*MQ＋43*NQ)字节号运算结果要做mod(1118)运算。用(45，43)RS码产生的两个Q校验字节放到对应VQ矢量的末端，并且满足下面的方程：
其中HQ校验矩阵为
(26，24)RS码和(45，43)RS码可以纠正出现在任何一行和任何一列上的一个错误，并且能相当可靠地检测出行、列中的多重错误。如果在一个阵列中出现多重错误，Reference Technology公司提供有一种名叫Layered ECC的算法，它可以取消多重错误。它的核心思想是交替执行行纠错和列纠错。
例如，假设错误分布如图16-04所示。ECC算法首先计算MSB矩阵和LSB矩阵中每一行的校正子Sri(i = 0，1，…，25)，以及每一列的校正子Scj(j = 0，1，…，44)。因为用(45，43)RS码，所以每一个Sri和每一个Scj都有两个校正子分量。如果Sri = 0，则说明第i行无错；如Scj = 0，说明第j行无错。
图16-04 错码分布举例
ECC算法首先纠正行1、3、17、19和22上分别只有一个的错误。这些错误取消后就纠正列5、9、15和35上分别只有一个的错误。经过一次行列交替纠错后，只剩下C4，25、C7，20、C7，25和C9，20这四个错误。再进行一次行列交替纠错后，就可以消除全部错误。
对于象下面这样分布的错误，ECC算法也可以纠正。
因为RS码纠错算法本身包含找错误的位置和错误值，而错误位置已经由校正子Sr(i－k)、Sri、Sr(i＋m)和Scj、Sc(j＋l)确定，所以只剩下求错误值的问题。这个问题在讨论RS码时已经解决。
对CD-ROM存储器的数据，经CIRC校正后可以使以字节做单位的误码率小于10-9，再经RSPC进行纠错后，字节误码率可以小于10-13，这样就满足了计算机要求误码率小于10-12的要求。
练习与思考题
CRC用于检测错误还是校正错误？
用自己的语言说明错误检测的思想。
什么叫做突发错误？
码块长度为n，码块中的信息长度为k，问(n，k)RS码本身能纠正多少个错误？
要纠正1个符号的错误，至少需要附加多少个校验符？
目前CD存储器中使用的CIRC编码技术能够纠正突发错误的最大长度是多少(按汉字
字符数估算)？
参考文献和站点
ISO/IEC 908,Compact Disc Digital Audio System,1987.
ISO 9660,Volume and File structure of CD-ROM for Information Interchange,1988.
ISO/IEC 10149,Data Interchange on Read Only 120 mm Optical Data Disks(CD-ROM),1989
Scott A.Vanstone and Paul C,van Oorcshot,An Introducton 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.
***************************************************************************
16.1 CRC错误检测原理
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码练习与思考题参考文献和站点
***************************************************************************
光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘制造生产技术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出的数据不可能完全正确。据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为3×10－4；沾有指纹的盘的误码率约为6×10－4；有伤痕的盘的误码率约为5×10－３。针对这种情况，激光盘存储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种：
(1) 错误检测：采用CRC(Cyclic Redundancy Code)检测读出数据是否有错。
(2) 错误校正码,采用里德－索洛蒙码(Reed－Solomon Code)，简称为RS码，进行纠错。RS码被认为是性能很好的纠错码。
(3) 交叉交插里德－索洛蒙码CIRC(Cross Interleaved Reed－Solomon Code),这个码的含义可理解为在用RS编译码前后，对数据进行交插处理和交叉处理。
对这些码的理论分析和计算有许多专著作了详尽的深入论述，对不需要开发纠错技术的读者仅需要了解错误检测和校正的一些基本概念即可。
16.1 CRC错误检测原理在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列10101111，用多项式可以表示成：
=
式中的表示代码的位置，或某个二进制数位的位置，前面的系数ai表示码的值。若ai是一位二进制代码，则取值是0或1。称为信息代码多项式。
在模2多项式代数运算中定义的运算规则有：
例如，模2多项式的加法和减法：
从这两个例子中可以看到，对于模2运算来说，代码多项式的加法和减法运算所得的结果相同。所以在做代码多项式的减法时，可用做加法来代替做减法。
代码多项式的除法可按长除法做。例如：
如果一个k位的二进制信息代码多项式为，再增加(n－k)位的校验码，那么增加(n－k)位之后，信息代码多项式在新的数据块中就表示成，如图16-01所示。
图16-01 信息代码结构如果用一个校验码生成多项式去除代码多项式，得到的商假定为，余式为，则可写成
因为模2多项式的加法和减法运算结果相同，所以又可把上式写成：
称为校验码生成多项式。从该式中可以看到，代表新的代码多项式是能够被校验码生成多项式除尽的，即它的余项为0。
例如，CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是
若用二进制表示，则为
=10001000000100001(B)
=11021(H)
假定要写到盘上的信息代码为
=4D6F746F (H)
由于增加了2个字节共16位的校验码，所以信息代码变成,4D6F746F0000(H)。 CRC检验码计算如下：
两数相除的结果，其商可不必关心，其余数为B994(H)就是CRC校验码。把信息代码写到盘上时，将原来的信息代码和CRC码一起写到盘上。在这个例子中，写到盘上的信息代码和CRC码是4D6F746F B994,
4D6F746F
B994
信息代码
CRC码
这个码是能被11021(H)除尽的。
从盘上把这块数据读出时，用同样的CRC码生成多项式去除这块数据，相除后得到的两种可能结果是：①余数为0，表示读出没有出现错误；②余数不为0，表示读出有错。
CD-ROM中也采用了相同的CRC检错。CD-ROM扇区方式01中，有一个4字节共32位的EDC字域，它就是用来存放CRC码。不过，CD-ROM采用的CRC校验码生成多项式与软磁盘采用的生成多项式不同，它是一个32阶的多项式,
计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节0～2063共2064个字节。在EDC中存放的CRC码的次序如下：
EDC：
x24－x31
x16－x23
x8－x15
x0－x7
字节号：
2064
2065
2066
2067
16.2 RS编码和纠错算法
16.2.1,GF(2m)域
RS(Reed-Solomon)码是在伽罗华域(Galois Field，GF)中运算的，因此在介绍RS码之前先简要介绍一下伽罗华域。
CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m) = GF(28)中的元素或称符号。GF(28)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式的特性是得到的余式等于0。CD-ROM用来构造GF(28)域的是
(13－1)
而GF(28)域中的本原元素为
α = (0 0 0 0 0 0 1 0)
下面以一个较简单例子说明域的构造。
[例16.1] 构造GF(23)域的本原多项式假定为
α定义为 = 0的根，即
α3＋α＋1 = 0
和 α3 = α＋1
GF(23)中的元素可计算如下：
0
mod(α3＋α＋1) = 0
α0
mod(α3＋α＋1) = α0 = 1
α1
mod(α3＋α＋1) = α1
α2
mod(α3＋α＋1) = α2
α3
mod(α3＋α＋1) = α＋1
α4
mod(α3＋α＋1) = α2＋α
α5
mod(α3＋α＋1) = α2＋α1＋1
α6
mod(α3＋α＋1) = α2＋1
α7
mod(α3＋α＋1) = α0
α8
mod(α3＋α＋1) = α1
……
用二进制数表示域元素得到表16-01所示的对照表
表16-01 GF(23)域中与二进制代码对照表,
GF(23)域元素
二进制对代码
0
(000)
α0
(001)
α1
(010)
α2
(100)
α3
(011)
α4
(110)
α5
(111)
α6
(101)
这样一来就建立了GF(23)域中的元素与3位二进制数之间的一一对应关系。用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(23)域中运算为例：
加法例：α0＋α3 = 001＋011
= 010 = α1
减法例：与加法相同乘法例：α5·α4 = α(5＋4) mod7
= α2
除法例：α5/α3 = α2
α3/α5 = α－2
= α(－2＋7)
= α5
取对数：log(α5) = 5
这些运算的结果仍然在GF(23)域中。
16.2.2 RS的编码算法
RS的编码就是计算信息码符多项式除以校验码生成多项式之后的余数。
在介绍之前需要说明一些符号。在GF(2m)域中，符号(n，k)RS的含义如下：
M
表示符号的大小，如m = 8表示符号由8位二进制数组成
n
表示码块长度，
k
表示码块中的信息长度
K=n－k = 2t
表示校验码的符号数
t
表示能够纠正的错误数目
例如，(28，24)RS码表示码块长度共28个符号，其中信息代码的长度为24，检验码有4个检验符号。在这个由28个符号组成的码块中，可以纠正在这个码块中出现的2个分散的或者2个连续的符号错误，但不能纠正3个或者3个以上的符号错误。
对一个信息码符多项式，RS校验码生成多项式的一般形式为
(13－2)
式中，K0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)≥2t (t为要校正的错误符号数)。
下面用两个例子来说明RS码的编码原理。
[例16.2] 设在GF(23)域中的元素对应表如表16 01所示。假设(6，4)RS码中的4个信息符号为m3、m2、m1和m0，信息码符多项式为
(13－3)
并假设RS校验码的2个符号为Q1和Q0，的剩余多项式为
这个多项式的阶次比的阶次少一阶。
如果K0 = 1，t = 1，由式(13－2)导出的RS校验码生成多项式就为
= (13－4)
根据多项式的运算，由式(13－3)和式(13－4)可以得到
m3x5＋m2x4＋m1x3＋m0x2＋Q1x＋Q0 = (x－α)(x－α2)Q(x)
当用x = α和x = α2代入上式时，得到下面的方程组，
经过整理可以得到用矩阵表示的(6，4)RS码的校验方程：
求解方程组就可得到校验符号：
在读出时的校正子可按下式计算：
[例16.3] 在例16.2中，如果K0 = 0，t = 1，由式(13－2)导出的RS校验码生成多项式就为
= (13－5)
根据多项式的运算，由(13－3)和(13－5)可以得到下面的方程组：
方程中的αi也可看成符号的位置，此处i = 0，1，…，5。
求解方程组可以得到RS校验码的2个符号为Q1和Q0，
(13－6)
假定mi为下列值：
信息符号
m3 = α0 = 001
m2 = α6 = 101
m1 = α3 = 011
m0 = α2 = 100
校验符号
Q1 = α6 = 101
Q0 = α4 = 110
校正子
s0 = 0
s1 = 0
代入(13－6)式可求得校验符号：
Q1 = α6 = 101
Q0 = α4 = 110
16.2.3 RS码的纠错算法
RS码的错误纠正过程分三步,(1)计算校正子(syndrome)，(2)计算错误位置，(3)计算错误值。现以例16.3为例介绍RS码的纠错算法。
校正子使用下面的方程组来计算：
为简单起见，假定存入光盘的信息符号m3、m2、m1、m0和由此产生的检验符号Q1、Q0均为0，读出的符号为m3′、m2′、m1′、m0′、Q1′和Q0′。
如果计算得到的s0和s1不全为0，则说明有差错，但不知道有多少个错，也不知道错在什么位置和错误值。如果只有一个错误，则问题比较简单。假设错误的位置为αx，错误值为mx，那么可通过求解下面的方程组：
得知错误的位置和错误值。
如果计算得到s0 = α2和s1 = α5，可求得αx = α3和mx = α2，说明m1出了错，它的错误值是α2。校正后的m1 = m1′＋mx,本例中m1=0。
如果计算得到s0 = 0，而s1≠0，那基本可断定至少有两个错误，当然出现两个以上的错误不一定都是s0 = 0和s1≠0。如果出现两个错误，而又能设法找到出错的位置，那么这两个错误也可以纠正。如已知两个错误和的位置和，那么求解方程组：
就可知道这两个错误值。
CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed Solomon Product－like Code，RSPC)就是采用上述方法导出的。
16.3 CIRC纠错技术光盘存储器和其它的存储器一样，经常遇到的错误有两种。一种是由于随机干扰造成的错误，这种错误称随机错误。它的特点是随机的、孤立的，干扰过后再读一次光盘，错误就可能消失。另一种错误是连续多位出错，或连续多个符号出错，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片。这种错误称为突发错误。CIRC(Cross Interleaved Reed Solomon)纠错码综合了交插、延时交插、交叉交插等技术，不仅能纠随机错误，而且对纠突发错误特别有效。
16.3.1 交插技术对纠错来说，分散的错误比较容易得到纠正，但出现一长串的错误时，就较麻烦。正如我们读书看报，如果文中在个别地方出错，根据前后文就容易判断是什么错。如果连续错好多字，就很难判断该处写的是什么。
例如，用X表示出现的错字，一种错误形式为“独在异乡XXX，每逢佳节倍思亲”，这是连续出现的错误，另一种错误形式为“独在异乡X异客，每X佳节倍思X”，这是分散出现的错误。这两种错误形式相比，同样是3个错误，但人们更容易更正后一种形式的错误，更正之后为“独在异乡为异客，每逢佳节倍思亲”。
这个道理很简单，把这种思想用在数字记录系统中对突发错误的更正非常有效。在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交插(interleaving)技术。例如，**************************************************************************
3个(5，3)码块, B1 = (a2，a1，a0，P1，P0)
B2 = (b2，b1，b0，Q1，Q0)
B3 = (c2，c1，c0，R1，R0)
连续排列,
a2 a1 a0 P1 P0
b2 b1 b0 Q1 Q0
c2 c1 c0 R1 R0
排成3行：
a2
a1
a0
P1
P0
b2
b1
b0
Q1
Q0
c2
c1
c0
R1
R0
交插排列：
a2
b2
c2
a1
b1
c1
a0
b0
c0
P1
Q1
R1
P0
Q0
R0
连续错3个：
a2
b2
c2
a1
b1
c1
a0
X
X
X
Q1
R1
P0
Q0
R0
读出后重新排列,
a2
a1
a0
X
P0
b2
b1
X
Q1
Q0
c2
c1
X
R1
R0
**************************************************************************
从这个例子中可以看到，对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续的错误。
一般来说，如果有r个(n，k)码，排成r×n矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若(n，k)码能纠正t个错误，那么这样交插后就可以纠正rt个突发错误。
16.3.2 交叉交插技术交叉交插(cross－interleaving)编码是交插的一种变型。在实际应用中，也是一种重要的技术。现仍以简单的例子说明这种技术思想。
**************************************************************************
(1) 用(5，3)码编码器C2生成的4个码块为:
B1
=
(a2
a1
a0
P1
P0)
B2
=
(b2
b1
b0
Q1
Q0)
B3
=
(c2
c1
c0
R1
R0)
B4
=
(d2
d1
d0
S1
S0)
(2) 交插后再用(6，4)码编码器C1生成5个码块为:
a2
b2
c2
d2
T1
T0
a1
b1
c1
d1
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) 最后一个码块不配对，可以和下一个码块配对。
**************************************************************************
这种编码技术用了两个编码器C2和C1。C2对原码块进行编码得到(5，3)码块，交插后生成由4个符号组成的码块，码块中的符号是交叉存放的，然后再用(6，4)编码器C1去编码。
有关CIRC详细的实现方法请参看文献[7]。
CIRC首先应用在激光唱盘系统中。音频信号的采样率为44.1 kHz，而每次采样有两个16比特的样本，一个来自左声道，一个来自右声道，每个样本用两个GF(28)域中的符号表示，因此每次采样共有4个符号。
为了纠正可能出现的错误，每6次采样共24个符号构成1帧，称为F1帧(F1－Frame)。用一个称为C2的编码器对这24个符号产生4个Q校验符号,Q0，Q1，Q2和Q3。24个声音数据加上4个Q校验符号共28个符号，用称为C1编码器对这28个符号产生4个P校验符号,P0，P1，P2和P3。28个符号加上4个P校验符号共32个符号构成的帧称为F2帧(F2－Frame)。F2帧加上1个字节(即1个符号)的子码共33个符号构成的帧称为F3帧(F3－Frame)。
在实际应用中可对前面介绍的交插技术略加修改，执行交插时不是交插包含有k个校验符的码块，而是交插一个连续系列中的码符，这种交插技术称为延时交插。延时交插之后还可用交叉技术，称为延时交叉交插技术。CD存储器中的CIRC编码器采用了4×F1帧的延时交插方案。1帧延时交插可纠正连续4×F1帧的突发错误。4×F2帧的延时交插可纠正连续16×F1帧突发错误，相当于大约14×F3帧的突发错误。1×F3帧经过EFM编码后产生588位通道位。1位通道位的长度折合成0.277μm的光道长度。14×F3帧突发错误长度相当于
［(16×(24＋4))/33］×588×0.277≈2.2 mm
换句话说，CIRC能纠正在2.2 mm光道上连续存放的448个错误符号! 相当于连续224个汉字错误可以得到纠正。
16.4 RSPC码按ISO/IEC10149的规定，CD-ROM扇区中的ECC码采用GF(28)域上的RSPC码产生172个字节的P校验符号和104个字节的Q校验符号。RS码采用本原多项式
和本原元
α = (00000010)
构造GF(28)域，这已经在上节作了介绍。
第12章已经介绍了CD-ROM的扇区结构。在每个扇区中，字节12～2075和ECC域中的字节2076到2351共2340个字节组成1170个字(word)。每个字s(n)由两个字节B组成，一个称为最高有效位字节MSB，另一个叫做最低有效位字节LSB。第n个字由下面的字节组成，
其中n = 0，1，2，…，1169。
从字节12开始到字节2075共2064个字节组成的数据块排列成24×43的矩阵，如图16 02所示。
NP
0
1
2
3
41
42
0
000
0001
0002
…
…
…
0041
0042
1
0043
0044
0045
…
…
…
0084
0085
HEADER
2
0086
0087
0088
…
…
…
0127
0128
+
P
Q
用户数据
＋
MP
22
0946
0947
0948
…
…
…
0987
0988
部分辅助数据
23
0989
0990
0991
…
…
…
1030
1031
24
1032
1033
1034
1073
1074
P-校验
25
1075
1076
1077
…
…
…
1116
1117
26
1118
1119
1120
…
1143
Q-校验
27
1144
1145
1146
…
1169
0
1
2
…
25
(ISO /IEC1049)
图16－02 RSPC码计算用数据阵列矩阵中的元素是字。这个矩阵要把它想象成两个独立的矩阵才比较好理解和分析，一个是由MSB字节组成的24×43矩阵，另一个是由LSB字节组成的24×43矩阵。
(1) P校验符号用(26，24)RS码产生
43列的每一列用矢量表示，记为Vp。每列有24个字节的数据再加2个字节的P校验字节，用下式表示：
其中：
0，1，2，……，42
0，1，2，……，25
和是P校验字节对这列字节计算得到的是两个P校验字节，称为P校验符号。两个P校验字节加到24行和25行的对应列上，这样构成了一个26×43的矩阵，并且满足方程
其中HP校验矩阵为
2,Q校验符号用(45，43)RS码产生增加P校验字节之后得到了一个26×43矩阵，该矩阵的对角线元素重新排列后得到一个新的矩阵，其结构如图16 03所示。
MQ
0
1
2
40
41
42
Q0
Q1
0
0000
0044
0088
…
…
0642
0686
0730
1118
1144
1
0043
0087
0131
…
…
0685
0729
0773
1119
1145
2
0086
0130
0147
…
…
0728
0772
0816
1120
1146
3
0129
0137
0217
…
…
0771
0815
0859
1121
1147
4
0172
0216
0260
…
…
0814
0858
0902
1122
1148
22
0946
0990
1034
…
…
0470
0514
0558
1140
1166
NQ
23
0989
1033
1077
…
…
0513
0557
0601
1141
1167
24
1032
1076
0002
…
…
0556
0600
0644
1142
1168
25
1075
0001
0045
…
…
0599
0643
0687
1143
1169
(ISO/IEC 10149∶1989)
图16 03 Q校验符号计算用数据阵列每条对角线上的43个MSB字节和LSB字节组成的矢量记为VQ。VQ在26×43矩阵中变成行矢量。第NQ行上的VQ矢量包含的字节如下：
其中：
NQ = 0，1，2，…，25
MQ = 0，1，2，…，42
和是Q校验字节
VQ中的(44*MQ＋43*NQ)字节号运算结果要做mod(1118)运算。用(45，43)RS码产生的两个Q校验字节放到对应VQ矢量的末端，并且满足下面的方程：
其中HQ校验矩阵为
(26，24)RS码和(45，43)RS码可以纠正出现在任何一行和任何一列上的一个错误，并且能相当可靠地检测出行、列中的多重错误。如果在一个阵列中出现多重错误，Reference Technology公司提供有一种名叫Layered ECC的算法，它可以取消多重错误。它的核心思想是交替执行行纠错和列纠错。
例如，假设错误分布如图16-04所示。ECC算法首先计算MSB矩阵和LSB矩阵中每一行的校正子Sri(i = 0，1，…，25)，以及每一列的校正子Scj(j = 0，1，…，44)。因为用(45，43)RS码，所以每一个Sri和每一个Scj都有两个校正子分量。如果Sri = 0，则说明第i行无错；如Scj = 0，说明第j行无错。
图16-04 错码分布举例
ECC算法首先纠正行1、3、17、19和22上分别只有一个的错误。这些错误取消后就纠正列5、9、15和35上分别只有一个的错误。经过一次行列交替纠错后，只剩下C4，25、C7，20、C7，25和C9，20这四个错误。再进行一次行列交替纠错后，就可以消除全部错误。
对于象下面这样分布的错误，ECC算法也可以纠正。
因为RS码纠错算法本身包含找错误的位置和错误值，而错误位置已经由校正子Sr(i－k)、Sri、Sr(i＋m)和Scj、Sc(j＋l)确定，所以只剩下求错误值的问题。这个问题在讨论RS码时已经解决。
对CD-ROM存储器的数据，经CIRC校正后可以使以字节做单位的误码率小于10-9，再经RSPC进行纠错后，字节误码率可以小于10-13，这样就满足了计算机要求误码率小于10-12的要求。
练习与思考题
CRC用于检测错误还是校正错误？
用自己的语言说明错误检测的思想。
什么叫做突发错误？
码块长度为n，码块中的信息长度为k，问(n，k)RS码本身能纠正多少个错误？
要纠正1个符号的错误，至少需要附加多少个校验符？
目前CD存储器中使用的CIRC编码技术能够纠正突发错误的最大长度是多少(按汉字
字符数估算)？
参考文献和站点
ISO/IEC 908,Compact Disc Digital Audio System,1987.
ISO 9660,Volume and File structure of CD-ROM for Information Interchange,1988.
ISO/IEC 10149,Data Interchange on Read Only 120 mm Optical Data Disks(CD-ROM),1989
Scott A.Vanstone and Paul C,van Oorcshot,An Introducton 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.
