RS编码及纠错算法.docx

Data Matrix将有效信息(数字字母等)编码成0~255内的数字表示 （编码方式参考：http://en.wikipedia.org/wiki/Data_Matrix）。为了及时发现数据传输时的错误，使用RS编解码来进行错误检测校验。RS码可以看成伽罗华域GF(2^m)上的元素，dm码的元素0~255正好对应伽罗华域GF(2^8)上的256个元素。通过编码时添加冗余信息，可以有效校验数据是否正确传输。

以下为文献概要：
1) 介绍如何生成GF(2^m)域，伽罗华域的加法运算为异或运算，乘法运算为指数相加后mod(2^m)。
2) 实例分析如何编码及纠错。(实际上就是求解多项式方程组的过程，在实际工程算法中运用到的钱氏搜索法(Chien Search)，Berlekamp-Massey 算法都是为了快速求解方程组，从而纠错)。
3) 附录部分为GF(2^8)上的元素列表。
13.2 RS编码和纠错算法
13.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)
下面以一个较简单例子说明域的构造。
[例13.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
……

用二进制数表示域元素得到表13-01所示的对照表
表13-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)域中。
13.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)
式中，m0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)≥2t (t为要校正的错误符号数)。
下面用两个例子来说明RS码的编码原理。
[例13.2] 设在GF(23)域中的元素对应表如表13-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码的校验方程：

求解方程组就可得到校验符号：

在读出时的校正子可按下式计算：

[例13.3] 在例13.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
13.2.3 RS码的纠错算法
RS码的错误纠正过程分三步： (1)计算校正子(syndrome)，(2)计算错误位置，(3)计算错误值。现以例13.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－likeCode，RSPC)就是采用上述方法导出的。

CopyRight © Octopus 2000 

附录1
GF(8) 元素如下 GF(2^8 ) 1+x^2+x^3+x^4+x^8
Field element(polynomial notation)  4-tuple representation
           0                             0000_0000(0  )
           1                             0000_0001(1  )
           a^1                           0000_0010(2  )
           a^2                           0000_0100(4  )
           a^3                           0000_1000(8  )
           a^4                           0001_0000(16 )
           a^5                           0010_0000(32 )
           a^6                           0100_0000(64 )
           a^7                           1000_0000(128)
           a^8                           0001_1101(29 )
           a^9                           0011_1010(58 )
           a^10                          0111_0100(116)
           a^11                          1110_1000(232)
           a^12                          1100_1101(205)
           a^13                          1000_0111(135)
           a^14                          0001_0011(19 )
           a^15                          0010_0110(38 )
           a^16                          0100_1100(76 )
           a^17                          1001_1000(152)
           a^18                          0010_110145 )
           a^19                          0101_1010(90 )
           a^20                          1011_0100(180)
           a^21                          0111_0101(117)
           a^22                          1110_1010(234)
           a^23                          1100_1001(201)
           a^24                          1000_1111(143)
           a^25                          0000_0011(3  )
           a^26                          0000_0110(6  )
           a^27                          0000_1100(12 )
           a^28                          0001_1000(24 )
           a^29                          0011_0000(48 )
           a^30                          0110_0000(96 )
           a^31                          1100_0000(192)
           a^32                          1001_1101(157)
           a^33                          0010_0111(39 )
           a^34                          0100_1110(78 )
           a^35                          1001_1100(156)
           a^36                          0010_0101(37 )
           a^37                          0100_1010(74 )
           a^38                          1001_0100(148)
           a^39                          0011_0101(53 )
           a^40                          0110_1010(106)
           a^41                          1101_0100(212)
           a^42                          1011_0101(181)
           a^43                          0111_0111(119)
           a^44                          1110_1110(238)
           a^45                          1100_0001(193)
           a^46                          1001_1111(159)
           a^47                          0010_0011(35 )
           a^48                          0100_0110(70 )
           a^49                          1000_1100(140)
           a^50                          0000_0101(5  )
           a^51                          0000_1010(10 )
           a^52                          0001_0100(20 )
           a^53                          0010_1000(40 )
           a^54                          0101_0000(80 )
           a^55                          1010_0000(160)
           a^56                          0101_1101(93 )
           a^57                          1011_1010(186)
           a^58                          0110_1001(105)
           a^59                          1101_0010(210)
           a^60                          1011_1001(185)

           a^61                          0110_1111(111)
           a^62                          1101_1110(222)
           a^63                          1010_0001(161)
           a^64                          0101_1111(95 )
           a^65                          1011_1110(190)
           a^66                          0110_0001(97 )
           a^67                          1100_0010(194)
           a^68                          1001_1001(153)
           a^69                          0010_1111(47 )
           a^70                          0101_1110(94 )
           a^71                          1011_1100(188)
           a^72                          0110_0101(101)
           a^73                          1100_1010(202)
           a^74                          1000_1001(137)
           a^75                          0000_1111(15 )
           a^76                          0001_1110(30 )
           a^77                          0011_1100(60 )
           a^78                          0111_1000(120)
           a^79                          1111_0000(240)
           a^80                          1111_1101(253)
           a^81                          1110_0111(231)
           a^82                          1101_0011(211)
           a^83                          1011_1011(187)
           a^84                          0110_1011(107)
           a^85                          1101_0110(214)
           a^86                          1011_0001(177)
           a^87                          0111_1111(127)
           a^88                          1111_1110(254)
           a^89                          1110_0001(225)
           a^90                          1101_1111(223)
           a^91                          1010_0011(163)
           a^92                          0101_1011(91 )
           a^93                          1011_0110(182)
           a^94                          0111_0001(113)
           a^95                          1110_0010(226)
           a^96                          1101_1001(217)
           a^97                          1010_1111(175)
           a^98                          0100_0011(67 )
           a^99                          1000_0110(134)
           a^100                         0001_0001(17 )
           a^101                         0010_0010(34 )
           a^102                         0100_0100(68 )
           a^103                         1000_1000(136)
           a^104                         0000_1101(13 )
           a^105                         0001_1010(26 )
           a^106                         0011_0100(52 )
           a^107                         0110_1000(104)
           a^108                         1101_0000(208)
           a^109                         1011_1101(189)
           a^110                         0110_0111(103)
           a^111                         1100_1110(206)
           a^112                         1000_0001(129)
           a^113                         0001_1111(31 )
           a^114                         0011_1110(62 )
           a^115                         0111_1100(124)
           a^116                         1111_1000(248)
           a^117                         1110_1101(237)
           a^118                         1100_0111199)
           a^119                         1001_0011(147)
           a^120                         0011_1011(59 )
           a^121                         0111_0110(118)
           a^122                         1110_1100(236)
           a^123                         1100_0101(197)
           a^124                         1001_0111(151)
           a^125                         0011_0011(51 )
           a^126                         0110_0110(102)
           a^127                         1100_1100(204)
           a^128                         1000_0101(133)
           a^129                         0001_0111(23 )
           a^130                         0010_1110(46 )
           a^131                         0101_1100(92 )
           a^132                         1011_1000(184)
           a^133                         0110_1101(109)
           a^134                         1101_1010(218)
           a^135                         1010_1001(169)
           a^136                         0100_1111(79 )
           a^137                         1001_1110(158)
           a^138                         0010_0001(33 )
           a^139                         0100_0010(66 )
           a^140                         1000_0100(132)
           a^141                         0001_0101(21 )
           a^142                         0010_1010(42 )
           a^143                         0101_0100(84 )
           a^144                         1010_1000(168)
           a^145                         0100_1101(77 )
           a^146                         1001_1010(154)
           a^147                         0010_1001(41 )
           a^148                         0101_0010(82 )
           a^149                         1010_0100(164)
           a^150                         0101_0101(85 )
           a^151                         1010_1010(170)
           a^152                         0100_1001(73 )
           a^153                         1001_0010(146)
           a^154                         0011_1001(57 )
           a^155                         0111_0010(114)
           a^156                         1110_0100(228)
           a^157                         1101_0101(213)
           a^158                         1011_0111(183)
           a^159                         0111_0011(115)
           a^160                         1110_0110(230)

           a^161                         1101_0001(209)
           a^162                         1011_1111(191)
           a^163                         0110_0011(99 )
           a^164                         1100_0110(198)
           a^165                         1001_0001(145)
           a^166                         0011_1111(63 )
           a^167                         0111_1110(126)
           a^168                         1111_1100(252)
           a^169                         1110_0101(229)
           a^170                         1101_0111(215)
           a^171                         1011_0011(179)
           a^172                         0111_1011(123)
           a^173                         1111_0110(246)
           a^174                         1111_0001(241)
           a^175                         1111_1111(255)
           a^176                         1110_0011(227)
           a^177                         1101_1011(219)
           a^178                         1010_1011(171)
           a^179                         0100_1011(75 )
           a^180                         1001_0110(150)
           a^181                         0011_0001(49 )
           a^182                         0110_0010(98 )
           a^183                         1100_0100(196)
           a^184                         1001_0101(149)
           a^185                         0011_0111(55 )
           a^186                         0110_1110(110)
           a^187                         1101_1100(220)
           a^188                         1010_0101(165)
           a^189                         0101_0111(87 )
           a^190                         1010_1110(174)
           a^191                         0100_0001(65 )
           a^192                         1000_0010(130)
           a^193                         0001_1001(25 )
           a^194                         0011_0010(50 )
           a^195                         0110_0100(100)
           a^196                         1100_1000(200)
           a^197                         1000_1101(141)
           a^198                         0000_0111(7  )
           a^199                         0000_1110(14 )
           a^200                         0001_1100(28 )
           a^201                         0011_1000(56 )
           a^202                         0111_0000(112)