RS编码和纠错算法

2024年2月15日发(作者：周亚平)

.

Data Matrix将有效信息(数字字母等)编码成0~255内的数字表示 （编码方式参考：/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-Masy 算法都是为了快速求解方程组，从而纠错)。

3) 附录部分为GF(2^8)上的元素列表。

13.2 RS编码和纠错算法

13.2.1. GF(2)域

RS(Reed-Solomon)码在伽罗华域(Galois Field，GF)中运算的，因此在介绍RS码之前先简要介绍一下伽罗华域。

CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2) = GF(2)中的元素或称符号。8GF(2)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多m8m项式的特性是得到的余式等于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

α

α

α

α

α

α

α

α

α

……

87654321033mod(α＋α＋1) = 0

mod(α＋α＋1) = α = 1

mod(α＋α＋1) = α

mod(α＋α＋1) = α

mod(α＋α＋1) = α＋1

mod(α＋α＋1) = α＋α

mod(α＋α＋1) = α＋α＋1

mod(α＋α＋1) = α＋1

mod(α＋α＋1) = α

mod(α＋α＋1) = α

3131303用二进制数表示域元素得到表13-01所示的对照表

表13-01 GF(2)域中与二进制代码对照表,

GF(2)域元素

0

α

α

α

α

α

α

α

3654321033

二进制对代码

(000)

(001)

(010)

(100)

(011)

(110)

(111)

(101)

这样一来就建立了GF(2)域中的元素与3位二进制数之间的一一对应关系。用同样的方法8可建立GF(2)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过3程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(2)域中运算为例：

加法例：α＋α = 001＋011

= 010 = α

减法例：与加法相同

103.

.

乘法例：α·α = α= α

254(5＋4)mod7

除法例：α/α = α

α/α = α

= α(－2＋7)35－2532

= α

取对数：log(α) = 5

这些运算的结果仍然在GF(2)域中。

13.2.2 RS的编码算法

355RS的编码就是计算信息码符多项式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个信息3.

.

符号为m3、m2、m1和m0，信息码符多项式为

(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 = α代入上式时，得到下面的方程组，

254322

经过整理可以得到用矩阵表示的(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

6462360.

.

Q0 = α = 110

13.2.3 RS码的纠错算法

RS码的错误纠正过程分三步： (1)计算校正子(syndrome)，(2)计算错误位置，(3)计算错误值。现以例13.3为例介绍RS码的纠错算法。

校正子使用下面的方程组来计算：

4

为简单起见，假定存入光盘的信息符号m3、m2、m1、m0和由此产生的检验符号Q1、Q0均为0，读出的符号为m3′、m2′、m1′、m0′、Q1′和Q0′。

如果计算得到的s0和s1不全为0，则说明有差错，但不知道有多少个错，也不知道错在什么位置和错误值。如果只有一个错误，则问题比较简单。假设错误的位置为αx，错误值为mx，那么可通过求解下面的方程组：

得知错误的位置和错误值。

如果计算得到s0 = α和s1 = α，可求得αx = α和mx = α，说明m1出了错，它的错误值2是α。校正后的m1 = m1′＋mx ，本例中m1=0。

如果计算得到s0 = 0，而s1≠0，那基本可断定至少有两个错误，当然出现两个以上的错误不一定都是s0 = 0和s1≠0。如果出现两个错误，而又能设法找到出错的位置，那么这两个错误也可以纠正。如已知两个错误和的位置和，那么求解方程组：

2532

就可知道这两个错误值。

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 reprentation

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_1101(45 )

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_0111(199)

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)

a^203 1110_0000(224)

a^204 1101_1101(221)

a^205 1010_0111(167)

a^206 0101_0011(83 )

a^207 1010_0110(166)

.

.

a^208 0101_0001(81 )

a^209 1010_0010(162)

a^210 0101_1001(89 )

a^211 1011_0010(178)

a^212 0111_1001(121)

a^213 1111_0010(242)

a^214 1111_1001(249)

a^215 1110_1111(239)

a^216 1100_0011(195)

a^217 1001_1011(155)

a^218 0010_1011(43 )

a^219 0101_0110(86 )

a^220 1010_1100(172)

a^221 0100_0101(69 )

a^222 1000_1010(138)

a^223 0000_1001(9 )

a^224 0001_0010(18 )

a^225 0010_0100(36 )

a^226 0100_1000(72 )

a^227 1001_0000(144)

a^228 0011_1101(61 )

a^229 0111_1010(122)

a^230 1111_0100(244)

a^231 1111_0101(245)

a^232 1111_0111(247)

a^233 1111_0011(243)

a^234 1111_1011(251)

a^235 1110_1011(235)

a^236 1100_1011(203)

a^237 1000_1011(139)

a^238 0000_1011(11 )

a^239 0001_0110(22 )

a^240 0010_1100(44 )

a^241 0101_1000(88 )

a^242 1011_0000(176)

a^243 0111_1101(125)

a^244 1111_1010(250)

a^245 1110_1001(233)

a^246 1100_1111(207)

a^247 1000_0011(131)

a^248 0001_1011(27 )

a^249 0011_0110(54 )

a^250 0110_1100(108)

a^251 1101_1000(216)

.

.

a^252 1010_1101(173)

a^253 0100_0111(71 )

a^254 1000_1110(142)

附录2

GF(2^8)的所有符号的数值表:

alphaTo=

{ 1, 2, 4, 8, 16, 32, 64, 128, 45, 90, 180, 69, 138, 57, 114, 228,

229, 231, 227, 235, 251, 219, 155, 27, 54, 108, 216, 157, 23, 46, 92, 184,

93, 186, 89, 178, 73, 146, 9, 18, 36, 72, 144, 13, 26, 52, 104, 208,

141, 55, 110, 220, 149, 7, 14, 28, 56, 112, 224, 237, 247, 195, 171, 123,

246, 193, 175, 115, 230, 225, 239, 243, 203, 187, 91, 182, 65, 130, 41, 82,

164, 101, 202, 185, 95, 190, 81, 162, 105, 210, 137, 63, 126, 252, 213, 135,

35, 70, 140, 53, 106, 212, 133, 39, 78, 156, 21, 42, 84, 168, 125, 250,

217, 159, 19, 38, 76, 152, 29, 58, 116, 232, 253, 215, 131, 43, 86, 172,

117, 234, 249, 223, 147, 11, 22, 44, 88, 176, 77, 154, 25, 50, 100, 200,

189, 87, 174, 113, 226, 233, 255, 211, 139, 59, 118, 236, 245, 199, 163, 107,

214, 129, 47, 94, 188, 85, 170, 121, 242, 201, 191, 83, 166, 97, 194, 169,

127, 254, 209, 143, 51, 102, 204, 181, 71, 142, 49, 98, 196, 165, 103, 206,

177, 79, 158, 17, 34, 68, 136, 61, 122, 244, 197, 167, 99, 198, 161, 111,

222, 145, 15, 30, 60, 120, 240, 205, 183, 67, 134, 33, 66, 132, 37, 74,

148, 5, 10, 20, 40, 80, 160, 109, 218, 153, 31, 62, 124, 248, 221, 151,

3, 6, 12, 24, 48, 96, 192, 173, 119, 238, 241, 207, 179, 75, 150, 0 }

各符号的指数表：

expOf=

{ 255, 0, 1, 240, 2, 225, 241, 53, 3, 38, 226, 133, 242, 43, 54, 210,

4, 195, 39, 114, 227, 106, 134, 28, 243, 140, 44, 23, 55, 118, 211, 234,

5, 219, 196, 96, 40, 222, 115, 103, 228, 78, 107, 125, 135, 8, 29, 162,

244, 186, 141, 180, 45, 99, 24, 49, 56, 13, 119, 153, 212, 199, 235, 91,

6, 76, 220, 217, 197, 11, 97, 184, 41, 36, 223, 253, 116, 138, 104, 193,

229, 86, 79, 171, 108, 165, 126, 145, 136, 34, 9, 74, 30, 32, 163, 84,

245, 173, 187, 204, 142, 81, 181, 190, 46, 88, 100, 159, 25, 231, 50, 207,

57, 147, 14, 67, 120, 128, 154, 248, 213, 167, 200, 63, 236, 110, 92, 176,

7, 161, 77, 124, 221, 102, 218, 95, 198, 90, 12, 152, 98, 48, 185, 179,

42, 209, 37, 132, 224, 52, 254, 239, 117, 233, 139, 22, 105, 27, 194, 113,

230, 206, 87, 158, 80, 189, 172, 203, 109, 175, 166, 62, 127, 247, 146, 66,

137, 192, 35, 252, 10, 183, 75, 216, 31, 83, 33, 73, 164, 144, 85, 170,

246, 65, 174, 61, 188, 202, 205, 157, 143, 169, 82, 72, 182, 215, 191, 251,

47, 178, 89, 151, 101, 94, 160, 123, 26, 112, 232, 21, 51, 238, 208, 131,

.

.

58, 69, 148, 18, 15, 16, 68, 17, 121, 149, 129, 19, 155, 59, 249, 70,

214, 250, 168, 71, 201, 156, 64, 60, 237, 130, 111, 20, 93, 122, 177, 150 }

符号的运算：

a+b：=a^b，例如66+67=66^67=1

a*b：1、两指数相加，2、Mod（255）,3、求新指数对应的符号，例如66*67，指数分别为expOf(66)=220、expOf(67)=217，新指数为182，对应符号alphaTo(182)=204，即66*67=204。

.