RS編碼和糾錯算法

2024年2月15日發(fā)(作者：周亞平)

.

Data Matrix將有效信息(數(shù)字字母等)編碼成0~255內(nèi)的數(shù)字表示 （編碼方式參考：/wiki/Data_Matrix）。為了及時發(fā)現(xiàn)數(shù)據(jù)傳輸時的錯誤，使用RS編解碼來進行錯誤檢測校驗。RS碼可以看成伽羅華域GF(2^m)上的元素，dm碼的元素0~255正好對應(yīng)伽羅華域GF(2^8)上的256個元素。通過編碼時添加冗余信息，可以有效校驗數(shù)據(jù)是否正確傳輸。

以下為文獻概要：

1) 介紹如何生成GF(2^m)域，伽羅華域的加法運算為異或運算，乘法運算為指數(shù)相加后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中的數(shù)據(jù)、地址、校驗碼等都可以看成是屬于GF(2) = GF(2)中的元素或稱符號。8GF(2)表示域中有256個元素，除0，1之外的254個元素由本原多項式P(x)生成。本原多m8m項式的特性是得到的余式等于0。CD-ROM用來構(gòu)造GF(2)域的8是

(13－1)

而GF(2)域中的本原元素為

α = (0 0 0 0 0 0 1 0)

下面以一個較簡單例子說明域的構(gòu)造。

8[例13.1] 構(gòu)造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用二進制數(shù)表示域元素得到表13-01所示的對照表

表13-01 GF(2)域中與二進制代碼對照表,

GF(2)域元素

0

α

α

α

α

α

α

α

3654321033

二進制對代碼

(000)

(001)

(010)

(100)

(011)

(110)

(111)

(101)

這樣一來就建立了GF(2)域中的元素與3位二進制數(shù)之間的一一對應(yīng)關(guān)系。用同樣的方法8可建立GF(2)域中的256個元素與8位二進制數(shù)之間的一一對應(yīng)關(guān)系。在糾錯編碼運算過3程中，加、減、乘和除的運算是在伽羅華域中進行。現(xiàn)仍以GF(2)域中運算為例：

加法例：α＋α = 001＋011

= 010 = α

減法例：與加法相同

103.

.

乘法例：α·α = α= α

254(5＋4)mod7

除法例：α/α = α

α/α = α

= α(－2＋7)35－2532

= α

取對數(shù)：log(α) = 5

這些運算的結(jié)果仍然在GF(2)域中。

13.2.2 RS的編碼算法

355RS的編碼就是計算信息碼符多項式m除以校驗碼生成多項式之后的余數(shù)。

在介紹之前需要說明一些符號。在GF(2)域中，符號(n，k)RS的含義如下：

m

n

k

t

表示符號的大小，如m = 8表示符號由8位二進制數(shù)組成

表示碼塊長度，

表示碼塊中的信息長度

表示能夠糾正的錯誤數(shù)目

K=n－k = 2t 表示校驗碼的符號數(shù)

例如，(28，24)RS碼表示碼塊長度共28個符號，其中信息代碼的長度為24，檢驗碼有4個檢驗符號。在這個由28個符號組成的碼塊中，可以糾正在這個碼塊中出現(xiàn)的2個分散的或者2個連續(xù)的符號錯誤，但不能糾正3個或者3個以上的符號錯誤。

對一個信息碼符多項式，RS校驗碼生成多項式的一般形式為

(13－2)

式中，m0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)≥2t (t為要校正的錯誤符號數(shù))。

下面用兩個例子來說明RS碼的編碼原理。

[例13.2] 設(shè)在GF(2)域中的元素對應(yīng)表如表13-01所示。假設(shè)(6，4)RS碼中的4個信息3.

.

符號為m3、m2、m1和m0，信息碼符多項式為

(13－3)

并假設(shè)RS校驗碼的2個符號為Q1和Q0，的剩余多項式為

這個多項式的階次比的階次少一階。

如果K0 = 1，t = 1，由式(13－2)導(dǎo)出的RS校驗碼生成多項式就為

= (13－4)

根據(jù)多項式的運算，由式(13－3)和式(13－4)可以得到

m3x＋m2x＋m1x＋m0x＋Q1x＋Q0 = (x－α)(x－α)Q(x)

當(dāng)用x = α和x = α代入上式時，得到下面的方程組，

254322

經(jīng)過整理可以得到用矩陣表示的(6，4)RS碼的校驗方程：

求解方程組就可得到校驗符號：

.

.

在讀出時的校正子可按下式計算：

[例13.3] 在例13.2中，如果K0 = 0，t = 1，由式(13－2)導(dǎo)出的RS校驗碼生成多項式就為

= (13－5)

根據(jù)多項式的運算，由(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)計算錯誤值。現(xiàn)以例13.3為例介紹RS碼的糾錯算法。

校正子使用下面的方程組來計算：

4

為簡單起見，假定存入光盤的信息符號m3、m2、m1、m0和由此產(chǎn)生的檢驗符號Q1、Q0均為0，讀出的符號為m3′、m2′、m1′、m0′、Q1′和Q0′。

如果計算得到的s0和s1不全為0，則說明有差錯，但不知道有多少個錯，也不知道錯在什么位置和錯誤值。如果只有一個錯誤，則問題比較簡單。假設(shè)錯誤的位置為αx，錯誤值為mx，那么可通過求解下面的方程組：

得知錯誤的位置和錯誤值。

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

如果計算得到s0 = 0，而s1≠0，那基本可斷定至少有兩個錯誤，當(dāng)然出現(xiàn)兩個以上的錯誤不一定都是s0 = 0和s1≠0。如果出現(xiàn)兩個錯誤，而又能設(shè)法找到出錯的位置，那么這兩個錯誤也可以糾正。如已知兩個錯誤和的位置和，那么求解方程組：

2532

就可知道這兩個錯誤值。

CD-ROM中的錯誤校正編碼CIRC和里德-索洛蒙乘積碼(Reed Solomon Product－likeCode，RSPC)就是采用上述方法導(dǎo)出的。

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)的所有符號的數(shù)值表:

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 }

各符號的指數(shù)表：

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、兩指數(shù)相加，2、Mod（255）,3、求新指數(shù)對應(yīng)的符號，例如66*67，指數(shù)分別為expOf(66)=220、expOf(67)=217，新指數(shù)為182，對應(yīng)符號alphaTo(182)=204，即66*67=204。

.