RS编码和纠错算法

1、Data Matrix将有效信息(数字字母等)编码成0255内的数字表示 （编码方式参考：/wiki/Data_Matrix）。为了及时发现数据传输时的错误，使用RS编解码来进行错误检测校验。RS码可以看成伽罗华域GF(2m)上的元素，dm码的元素0255正好对应伽罗华域GF(28)上的256个元素。通过编码时添加冗余信息，可以有效校验数据是否正确传输。以下为文献概要：1) 介绍如何生成GF(2m)域，伽罗华域的加法运算为异或运算，乘法运算为指数相加后mod(2m)。2) 实例分析如何编码及纠错。(实际上就是求解多项式方程组的过程，在实际工程算法中运

2、用到的钱氏搜索法(Chien Search)，Berlekamp-Massey 算法都是为了快速求解方程组，从而纠错)。3) 附录部分为GF(28)上的元素列表。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

3、(28)域的是(131)而GF(28)域中的本原元素为 = (0 0 0 0 0 0 1 0)下面以一个较简单例子说明域的构造。例13.1 构造GF(23)域的本原多项式假定为定义为 = 0的根，即31 = 0和 3 = 1GF(23)中的元素可计算如下：0mod(31) = 00mod(31) = 0 = 11mod(31) = 12mod(31) = 23mod(31) = 14mod(31) = 25mod(31) = 2116mod(31) = 217mod(31) = 08mod(31) = 1用二进制数表示域元素得到表13-01所示的对照表表

4、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)域中运算为例：加法例：03 = 001011= 010 = 1减法例：与加法相同乘法例：5·4 = (54) mod7= 2除法例：5/3&

5、#160;= 23/5 = 2= (27)= 5取对数：log(5) = 5这些运算的结果仍然在GF(23)域中。13.2.2 RS的编码算法RS的编码就是计算信息码符多项式除以校验码生成多项式之后的余数。在介绍之前需要说明一些符号。在GF(2m)域中，符号(n，k)RS的含义如下：m表示符号的大小，如m = 8表示符号由8位二进制数组成n表示码块长度，k表示码块中的信息长度K=nk = 2t表示校验码的符号数t表示能够纠正的错误数目例如，(28，24)RS码表示码块长度共28个符号，其中信息代码的长度为24，检验码有4个检验符号。在这个由28个符号组成的码块中，可以纠正在

6、这个码块中出现的2个分散的或者2个连续的符号错误，但不能纠正3个或者3个以上的符号错误。对一个信息码符多项式，RS校验码生成多项式的一般形式为 (132)式中，m0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)2t (t为要校正的错误符号数)。下面用两个例子来说明RS码的编码原理。例13.2 设在GF(23)域中的元素对应表如表13-01所示。假设(6，4)RS码中的4个信息符号为m3、m2、m1和m0，信息码符多项式为 (133)并假设RS校验码的2个符号为Q1和Q0，的剩余多项式为这个多项式的阶次比的阶次少一阶。如果K0

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

8、;(135)根据多项式的运算，由(133)和(135)可以得到下面的方程组：方程中的i也可看成符号的位置，此处i = 0，1，5。求解方程组可以得到RS校验码的2个符号为Q1和Q0， (136)假定mi为下列值：信息符号m3 = 0 = 001m2 = 6 = 101m1 = 3 = 011m0 = 2 = 100校验符号Q1 = 6 = 101Q0 = 4 = 110校正子s0 = 0s1 = 0代入(136)式可求得校验符号：Q1&

9、#160;= 6 = 101Q0 = 4 = 11013.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，那么

10、可通过求解下面的方程组：得知错误的位置和错误值。如果计算得到s0 = 2和s1 = 5，可求得x = 3和mx = 2，说明m1出了错，它的错误值是2。校正后的m1 = m1mx ，本例中m1=0。如果计算得到s0 = 0，而s10，那基本可断定至少有两个错误，当然出现两个以上的错误不一定都是s0 = 0和s10。如果出现两个错误，而又能设法找到出错的位置，那么这两个错误也可以纠正。如已知两个错误和的位置和，那么求解方程组：就可知道这两个错误值。CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed&#

11、160;Solomon ProductlikeCode，RSPC)就是采用上述方法导出的。CopyRight © Octopus 2000 附录1GF(8) 元素如下 GF(28 ) 1+x2+x3+x4+x8Field element(polynomial notation)  4-tuple representation           0         &

12、#160;                   0000_0000(0  )           1                 

13、60;           0000_0001(1  )           a1                         

14、0; 0000_0010(2  )           a2                           0000_0100(4  )      

15、60;    a3                           0000_1000(8  )           a4      &

16、#160;                    0001_0000(16 )           a5                 &

17、#160;         0010_0000(32 )           a6                           0100_0000(64

18、 )           a7                           1000_0000(128)           a8&

19、#160;                          0001_1101(29 )           a9           &

20、#160;               0011_1010(58 )           a10                      

21、    0111_0100(116)           a11                          1110_1000(232)      &#

22、160;    a12                          1100_1101(205)           a13       

23、60;                  1000_0111(135)           a14                   &#

24、160;      0001_0011(19 )           a15                          0010_0110(38 )   

25、0;       a16                          0100_1100(76 )           a17     

26、;                     1001_1000(152)           a18                

27、0;         0010_1101(45 )           a19                          0101_1010(90 ) 

28、          a20                          1011_0100(180)           a21  &

29、#160;                       0111_0101(117)           a22              

30、            1110_1010(234)           a23                          1100

31、_1001(201)           a24                          1000_1111(143)          

32、a25                          0000_0011(3  )           a26          

33、60;               0000_0110(6  )           a27                     

34、60;    0000_1100(12 )           a28                          0001_1000(24 )      

35、;     a29                          0011_0000(48 )           a30       

36、                   0110_0000(96 )           a31                   

37、;       1100_0000(192)           a32                          1001_1101(157)   &

38、#160;       a33                          0010_0111(39 )           a34    &#

39、160;                     0100_1110(78 )           a35                &

40、#160;         1001_1100(156)           a36                          0010_0101(37 )

41、60;          a37                          0100_1010(74 )           a38 

42、0;                        1001_0100(148)           a39             

43、60;            0011_0101(53 )           a40                          0

44、110_1010(106)           a41                          1101_0100(212)         

45、0; a42                          1011_0101(181)           a43           

46、;               0111_0111(119)           a44                      

47、0;   1110_1110(238)           a45                          1100_0001(193)       

48、    a46                          1001_1111(159)           a47        &

49、#160;                 0010_0011(35 )           a48                    

50、      0100_0110(70 )           a49                          1000_1100(140)    &#

51、160;      a50                          0000_0101(5  )           a51    

52、0;                     0000_1010(10 )           a52                

53、60;         0001_0100(20 )           a53                          0010_1000(40 ) 

54、;          a54                          0101_0000(80 )           a55  

55、                        1010_0000(160)           a56              

56、;            0101_1101(93 )           a57                          101

57、1_1010(186)           a58                          0110_1001(105)          

58、 a59                          1101_0010(210)           a60           &

59、#160;              1011_1001(185)           a61                       

60、   0110_1111(111)           a62                          1101_1110(222)       &#

61、160;   a63                          1010_0001(161)           a64        

62、60;                 0101_1111(95 )           a65                    &#

63、160;     1011_1110(190)           a66                          0110_0001(97 )    

64、0;      a67                          1100_0010(194)           a68      

65、;                    1001_1001(153)           a69                 

66、0;        0010_1111(47 )           a70                          0101_1110(94 )  

67、         a71                          1011_1100(188)           a72   &

68、#160;                      0110_0101(101)           a73               

69、           1100_1010(202)           a74                          1000_1001(

70、137)           a75                          0000_1111(15 )           a76

71、60;                         0001_1110(30 )           a77            &#

72、160;             0011_1100(60 )           a78                        &

73、#160; 0111_1000(120)           a79                          1111_0000(240)        

74、60;  a80                          1111_1101(253)           a81         

75、0;                1110_0111(231)           a82                     

76、60;    1101_0011(211)           a83                          1011_1011(187)      

77、;     a84                          0110_1011(107)           a85       

78、                   1101_0110(214)           a86                   

79、;       1011_0001(177)           a87                          0111_1111(127)   &

80、#160;       a88                          1111_1110(254)           a89    &#

81、160;                     1110_0001(225)           a90                &

82、#160;         1101_1111(223)           a91                          1010_0011(163)

83、60;          a92                          0101_1011(91 )           a93 

84、0;                        1011_0110(182)           a94             

85、60;            0111_0001(113)           a95                          1

86、110_0010(226)           a96                          1101_1001(217)         

87、0; a97                          1010_1111(175)           a98           

88、;               0100_0011(67 )           a99                      

89、0;   1000_0110(134)           a100                         0001_0001(17 )        

90、;   a101                         0010_0010(34 )           a102         

91、0;               0100_0100(68 )           a103                      &#

92、160;  1000_1000(136)           a104                         0000_1101(13 )        

93、60;  a105                         0001_1010(26 )           a106          &#

94、160;              0011_0100(52 )           a107                       

95、  0110_1000(104)           a108                         1101_0000(208)         &

96、#160; a109                         1011_1101(189)           a110           

97、              0110_0111(103)           a111                       

98、0; 1100_1110(206)           a112                         1000_0001(129)          

99、; a113                         0001_1111(31 )           a114           

100、0;             0011_1110(62 )           a115                         0

101、111_1100(124)           a116                         1111_1000(248)           a1

102、17                         1110_1101(237)           a118            &#

103、160;            1100_0111(199)           a119                         1001_

104、0011(147)           a120                         0011_1011(59 )           a121&#

105、160;                        0111_0110(118)           a122             

106、            1110_1100(236)           a123                         1100_0101

107、(197)           a124                         1001_0111(151)           a125 

108、                        0011_0011(51 )           a126             

109、0;           0110_0110(102)           a127                         1100_1100(204

110、)           a128                         1000_0101(133)           a129 

111、0;                       0001_0111(23 )           a130              &#

112、160;          0010_1110(46 )           a131                         0101_1100(92 )

113、60;          a132                         1011_1000(184)           a133  &#

114、160;                      0110_1101(109)           a134               

115、          1101_1010(218)           a135                         1010_1001(169) &

116、#160;         a136                         0100_1111(79 )           a137   

117、                      1001_1110(158)           a138               

118、0;         0010_0001(33 )           a139                         0100_0010(66 )  

119、;         a140                         1000_0100(132)           a141   

120、0;                     0001_0101(21 )           a142                &#

121、160;        0010_1010(42 )           a143                         0101_0100(84 )  

122、60;        a144                         1010_1000(168)           a145    &#

123、160;                    0100_1101(77 )           a146                 

124、        1001_1010(154)           a147                         0010_1001(41 )   &

125、#160;       a148                         0101_0010(82 )           a149     

126、                    1010_0100(164)           a150                 

127、0;       0101_0101(85 )           a151                         1010_1010(170)    

128、;       a152                         0100_1001(73 )           a153     

129、0;                   1001_0010(146)           a154                  &#

130、160;      0011_1001(57 )           a155                         0111_0010(114)    

131、60;      a156                         1110_0100(228)           a157      &#

132、160;                  1101_0101(213)           a158                   

133、      1011_0111(183)           a159                         0111_0011(115)     &

134、#160;     a160                         1110_0110(230)           a161       

135、                  1101_0001(209)           a162                   

136、0;     1011_1111(191)           a163                         0110_0011(99 )      

137、;     a164                         1100_0110(198)           a165       

138、0;                 1001_0001(145)           a166                    &#

139、160;    0011_1111(63 )           a167                         0111_1110(126)      

140、60;    a168                         1111_1100(252)           a169        &#

141、160;                1110_0101(229)           a170                     

142、    1101_0111(215)           a171                         1011_0011(179)       &

143、#160;   a172                         0111_1011(123)           a173         

144、                1111_0110(246)           a174                     

145、0;   1111_0001(241)           a175                         1111_1111(255)        

146、;   a176                         1110_0011(227)           a177         

147、0;               1101_1011(219)           a178                      &#

148、160;  1010_1011(171)           a179                         0100_1011(75 )        

149、60;  a180                         1001_0110(150)           a181          &#

150、160;              0011_0001(49 )           a182                       

151、  0110_0010(98 )           a183                         1100_0100(196)         &

152、#160; a184                         1001_0101(149)           a185           

153、              0011_0111(55 )           a186                       

154、0; 0110_1110(110)           a187                         1101_1100(220)          

155、; a188                         1010_0101(165)           a189           

156、0;             0101_0111(87 )           a190                         1

157、010_1110(174)           a191                         0100_0001(65 )           a1

158、92                         1000_0010(130)           a193            &#

159、160;            0001_1001(25 )           a194                         0011_

160、0010(50 )           a195                         0110_0100(100)           a196&#

161、160;                        1100_1000(200)           a197             

162、            1000_1101(141)           a198                         0000_0111

163、(7  )           a199                         0000_1110(14 )           a200&

164、#160;                        0001_1100(28 )           a201             

165、;            0011_1000(56 )           a202                         0111_000

166、0(112)           a203                         1110_0000(224)           a204 

167、;                        1101_1101(221)           a205             

168、60;           1010_0111(167)           a206                         0101_0011(83

169、 )           a207                         1010_0110(166)           a208 

170、60;                       0101_0001(81 )           a209              &

171、#160;          1010_0010(162)           a210                         0101_1001(89 )&#

172、160;          a211                         1011_0010(178)           a212  &

173、#160;                      0111_1001(121)           a213               

174、;          1111_0010(242)           a214                         1111_1001(249) 

175、          a215                         1110_1111(239)           a216   

176、;                      1100_0011(195)           a217               

177、60;         1001_1011(155)           a218                         0010_1011(43 ) 

178、0;         a219                         0101_0110(86 )           a220   

179、60;                     1010_1100(172)           a221                &

180、#160;        0100_0101(69 )           a222                         1000_1010(138)  &#

181、160;        a223                         0000_1001(9  )           a224   &#

182、160;                     0001_0010(18 )           a225                

183、         0010_0100(36 )           a226                         0100_1000(72 )  &

184、#160;        a227                         1001_0000(144)           a228    

185、                     0011_1101(61 )           a229                

186、0;        0111_1010(122)           a230                         1111_0100(244)   

187、;        a231                         1111_0101(245)           a232    

188、0;                    1111_0111(247)           a233                 &#

189、160;       1111_0011(243)           a234                         1111_1011(251)   

190、60;       a235                         1110_1011(235)           a236     &#

191、160;                   1100_1011(203)           a237                  

192、       1000_1011(139)           a238                         0000_1011(11 )    &

193、#160;      a239                         0001_0110(22 )           a240      

194、                   0010_1100(44 )           a241                  

195、0;      0101_1000(88 )           a242                         1011_0000(176)           a243                         0111_110