文档介绍：CRC错误检测原理
在纠错编码代数中, 把以二进制数字表示一个数据系列看成一个多项式。 比如, 二进制数字序列10101111, 用多项式能够表示成:
式中xi表示代码位置, 或某个二进制数位位置, xi前面系数ai表示码值。 若ai是一位二进制代码, 则取值是0或1。 M(x)称为信息代码多项式。
在模2多项式代数运算中定义运算规则有:
比如, 模2多项式加法和减法:
从这两个例子中能够看到, 对于模2运算来说, 代码多项式加法和减法运算所得结果相同。 所以在做代码多项式减法时, 可用做加法来替换做减法。
代码多项式除法可按长除法做。 比如:
假如一个k位二进制信息代码多项式为M(x), 再增加(n－k)位校验码, 那么增加(n－k)位以后, 信息代码多项式在新数据块中就表示成xn-kM(x), 图16-01所表示。
图16-01 信息代码结构
假如用一个校验码生成多项式G(x)去除代码多项式xn-kM(x), 得到商假定为Q(x), 余式为R(x), 则可写成
因为模2多项式加法和减法运算结果相同, 所以又可把上式写成:
G(x)称为校验码生成多项式。 从该式中能够看到, 代表新代码多项式xn-kM(x)+R(x)是能够被校验码生成多项式G(x)除尽, 即它余项为0。
比如, CD盘中q通道和软磁盘存放器中使用CRC校验码生成多项式是
G(x)=x16+x12+x5+1
若用二进制表示, 则为
G(x)=00001(B)
=11021(H)
假定要写到盘上信息代码M(x)为
M(x)=4D6F746F (H)
因为增加了2个字节共16位校验码, 所以信息代码变成x16M(x): 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
GF(2m)域
RS(Reed-Solomon)码是在伽罗华域(Galois Field, GF)中运算, 所以在介绍RS码之前先简明介绍一下伽罗华域。
CD-ROM中数据、 地址、 校验码等全部能够看成是属于GF(2m) = GF(28)中元素或称符号。 GF(28)表示域中有256个元素, 除0, 1之外254个元素由本原多项式P(x)生成。 本原多项式P(x)特征是得到余式等于0。 CD-ROM用来结构GF(28)域P(x)是
P(x)=x8+x4+x3+x2+1 (13－1)
而GF(28)域中本原元素为
α = (0 0 0 0 0 0 1 0)
下面以一个较简单例子说明域结构。
[] 结构GF(23)域本原多项式P(x)假定为
P(x)=x3+x+1
α定义为P(x) = 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
α