RS编码和纠错算法
GF(2)域
RS(Reed-Solomon)码在伽罗华域(Galois Field，GF)中运算的，因此在介绍RS码之前先简要介绍一下伽罗华域。
CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2) = GF(2)中的元素或称符号。
8
GF(2)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多
m8
m项式的特性是得到的余式等于0。CD-ROM用来构造GF(2)域的
8
是
(13－1)
而GF(2)域中的本原元素为 α = (0 0 0 0 0 0 1 0)
下面以一个较简单例子说明域的构造。
8
[例13.1] 构造GF(2)域的本原多项式
3
假定为
α定义为
3
= 0的根，即
α＋α＋1 = 0 和 α = α＋1
GF(2)中的元素可计算如下：
0 α α α α α α 5 4321033
mod(α＋α＋1) = 0 mod(α＋α＋1) = α = 1 mod(α＋α＋1) = α mod(α＋α＋1) = α mod(α＋α＋1) = α＋1 mod(α＋α＋1) = α＋α mod(α＋α＋1) = α＋α＋1 3213233231303α α α …… 8 7 6 mod(α＋α＋1) = α＋1 mod(α＋α＋1) = α mod(α＋α＋1) = α 313032用二进制数表示域元素得到表13-01所示的对照表
表13-01 GF(2)域中与二进制代码对照表, GF(2)域元素 0 α α α α α α α 3
654321033
二进制对代码 (000) (001) (010) (100) (011) (110) (111) (101) 这样一来就建立了GF(2)域中的元素与3位二进制数之间的一一对应关系。用同样的方法可
8
建立GF(2)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过程中，
3
加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(2)域中运算为例：
加法例：α＋α = 001＋011 = 010 = α
1 0
3
减法例：与加法相同 乘法例：α·α = α= α
2
5
4
(5＋4)mod7
除法例：α/α = αα/α = α= α= α
(－2＋7) 3
5
－2
532
5
取对数：log(α) = 5
这些运算的结果仍然在GF(2)域中。
RS的编码算法
3
5
RS的编码就是计算信息码符多项式
m除以校验码生成多项式之后的余数。
在介绍之前需要说明一些符号。在GF(2)域中，符号(n，k)RS的含义如下：
m n k t
表示符号的大小，如m = 8表示符号由8位二进制数组成 表示码块长度， 表示码块中的信息长度 表示能够纠正的错误数目
K=n－k = 2t 表示校验码的符号数
例如，(28，24)RS码表示码块长度共28个符号，其中信息代码的长度为24，检验码有4个检验符号。在这个由28个符号组成的码块中，可以纠正在这个码块中出现的2个分散的或者2个连续的符号错误，但不能纠正3个或者3个以上的符号错误。
对一个信息码符多项式，RS校验码生成多项式的一般形式为
(13－2)
式中，m0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)≥2t (t为要校正的错误符号数)。 下面用两个例子来说明RS码的编码原理。
[例13.2] 设在GF(2)域中的元素对应表如表13-01所示。假设(6，4)RS码中的4个信息符号为m3、m2、m1和m0，信息码符多项式
为
3
(13－3)
并假设RS校验码的2个符号为Q1和Q0，的剩余多项式为
这个多项式的阶次比
的阶次少一阶。
如果K0 = 1，t = 1，由式(13－2)导出的RS校验码生成多项式就为
= (13－4)
根据多项式的运算，由式(13－3)和式(13－4)可以得到 m3x＋m2x＋m1x＋m0x＋Q1x＋Q0 = (x－α)(x－α)Q(x) 当用x = α和x = α代入上式时，得到下面的方程组，
2
5
4
3
2
2
经过整理可以得到用矩阵表示的(6，4)RS码的校验方程：
求解方程组就可得到校验符号：
在读出时的校正子可按下式计算：
[例13.3] 在例13.2中，如果K0 = 0，t = 1，由式(13－2)导出的RS校验码生成多项式就为
= (13－5)
根据多项式的运算，由(13－3)和(13－5)可以得到下面的方程组：
方程中的α也可看成符号的位置，此处i = 0，1，…，5。 求解方程组可以得到RS校验码的2个符号为Q1和Q0，
i(13－6)
假定mi为下列值：
信息符号 m3 = α = 001 m2 = α = 101 m1 = α = 011 m0 = α = 100 校验符号 Q1 = α = 101 Q0 = α = 110 校正子 s0 = 0 s1 = 0 代入(13－6)式可求得校验符号：
Q1 = α = 101 Q0 = α = 110 RS码的纠错算法
RS码的错误纠正过程分三步： (1)计算校正子(syndrome)，(2)计算错误位置，(3)计算错误值。现以例13.3为例介绍RS码的纠错算法。 校正子使用下面的方程组来计算：
46
462360
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库RS编码和纠错算法在线全文阅读。
相关推荐：