RS糾錯算法

2024年2月15日發(fā)(作者：華北科技學院吧)

RS基本概念

GF(2m)域

域在RS 編碼理論中起著至關重要的作用。

簡單點說域GF(2m) 有2

(設2

=

q

)個符號

且具有以下性質：

012m-1域中的每個元素都可以用a，a，a，a 的和來表示。除0、1外其余所有元素由本原多項mm式P(x)生成。本原多項式的特性是得到的余式等于0。

在糾錯編碼運算過程中，加、減、乘和除的運算是在伽羅華域中進行

在GF域上的加、減、乘、除運算定義如下（GF(2)為例）：

1、 加、減運算均定義為元素的二進制表示方式進行異或運算。如：a+a，先查表，18101將其化為二進制表示方式得0101+0111，經過異或運算得0010，再查表得a，即：a+a= a。8101減運算與加運算相同，即：a-a= a。

2、 乘運算定義為元素的指數(shù)相加后進行模15運算后所得的新元素，但若有一個元素7137135為0，則相乘結果為0。如：a*a，(7+13)mod 15=5，即a*a= a。

3、 除運算定義為元素的指數(shù)相減后進行模15運算后所得的新元素(指數(shù)為正數(shù))。若595911被除數(shù)為0，則結果為0。如：a/a，(5-9)mod 15=11，即a/a= a。

下面以一個較簡單例子說明域的構造。

8104GF(24) 的所有元素

例： m=4,本原多項式

p(x)=x4 +x+1 求GF(2) 的所有元素：

因為α 為p(x)的根 得到? +?+1=0 或? =?+1 (根據(jù)運算規(guī)則)

由此可以得到域的所有元素

元素

0

a

a

a

a

a

a

a

a

76523243210444多項式表示

0

1

a

a

a

a+1

a+a mod

p(a)

a+a mod

p(a)

a+a+1 mod

p(a)

332二進制表示

0000

0001

0010

0100

1000

0011

0110

1100

1011

十六進制表示

0

1

2

4

8

3

6

C

B

a

a

a

a

a

a

a

8a+1 mod

p(a)

a+a mod

p(a)

a+a+1 mod

p(a)

a+a+1 mod

p(a)

a+a+a+1 mod

p(a)

a+a+1 mod

p(a)

a+1 mod

p(a)

33232322320101

1010

0111

1110

1111

1101

1001

5

A

7

E

F

D

9

符號(n，k)RS

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

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

n 表示碼塊長度，

k 表示碼塊中的信息長度

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

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

RS的編碼算法

本項目RS糾錯算法選擇在GF(24)域上的RS(15,11)碼，碼長n=15字符，碼元長k=11字符，碼距d=5，糾錯能力t=2字符，每字符為4bits，即一個碼組合7.5字節(jié)。每11個有效字節(jié)加4個糾錯字節(jié)。每一幀報文分成若干組，以11個字節(jié)為一組，對這11個字節(jié)作糾錯，生成4字節(jié)里德-所羅門碼糾錯碼，和前11個字節(jié)一起共15個字節(jié)構成糾錯后的一組報文。一幀報文以每11個字節(jié)分組后，若最后一組字節(jié)數(shù)不滿11個字節(jié)，剩余字節(jié)填77H，湊滿11個字節(jié)再進行糾錯。

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

(13－2)

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

413362310對于R（15，11）對應生成多項式為g(x)=

x+ax+ax+ax+a

信息碼符多項式為

M(x)??mixii?0k?1 (13－3)

并假設RS校驗碼的4個符號為Q3 Q2Q1和Q0，的剩余多項式為

n??k?1R(x)?Qixi?Q3x3?Q2x2?Q1x1?Q0

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

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

=

(x?a)(x?a2)(x?a3)(x?a4)根據(jù)多項式的運算，由式(13－3)和式(13－4)可以得到

M(x)+R(x)=

(x?a)(x?a2)(x?a3)(x?a4)Q(x)

當用x = a x = a2 x = a3 x = a4代入上式時，得到下面的方程組，

?m1413?10a?m9a?......?m0a4?Q3a3?Q2a2?Q1a1?Q0?0??m2826864210a?m9a?......?m0a?Q3a?Q2a?Q1a?Q0?0?ma42??m12963

109a?0a?Q3a?Q2a?Q1a?Q0?0??ma56?ma52?......?ma16?Qa12?Qa8109032?Q1a4?Q0?0令m1410a?m139a?......?m0a4=n0

m2610a28?m9a?......?m80a=n1

m4210a?m9a39?......?m0a12=n2

m565210a?m9a?......?m0a16=n3

－4) (13

解得：Q3=a13(n3-n2)+a3(n2-n1)+a1(n1-n0)

Q2=a9(n3-n2)+a3(n2-n1)+a13(n1-n0)

Q1=

a11(n3-n2)+a2(n2-n1)+a1(n1-n0)

Q0=

a4(n3-n2)+a1(n2-n1)+a5(n1-n0)+n0

RS碼的糾錯算法

RS碼的錯誤糾正過程分三步： (1)計算校正子(syndrome)，(2)計算錯誤位置，(3)計算錯誤值。現(xiàn)以例13.3為例介紹RS碼的糾錯算法。

1、 求出校正子：

sj??rixi?0

1414?ix?aj對于一組接收到的數(shù)據(jù)：

接收到的數(shù)據(jù)：68 31 00 31 00 68 4b 05 35 01 00 b7 2a 55 dc

分兩小組：08 06 01 03 00 00 01 03 00 00 08 07 0b 0a 02 (I-1)

06 0b 04 05 00 05 03 01 00 00 00 05 05 0c 0d (I-2)

對應r14……r0

代入上式求出s1,s2,s3,s4(sj);

2、 判斷若Sj

(j=1,2,3,4) 均為0，則無錯；否則執(zhí)行下面的步驟以求出錯值及位置。

23、 求出錯位多項式d(x)=dz2x+dz0x+dz1=0的根，即為錯值位置，其中：

dz2?s1s2s2s3，dz1?s3s4s2s3，dz0?s1s2s3s4若dz2=0，則只有一個根x1=s3/s2

。

否則用代入法求出x1，x2，即把x的所有15個可能值代入錯位多項式，若結果為0，則即是一個根。

4、 求出錯值ew1,ew2。

若dz2=0，ew=s1/s2，否則

2ew1?s1x2?s22x1x2?x1yew2?s1x1?s22x1x2?x25、 糾錯時在對應的x=a，r(14-y)處，加上對應錯值即可完成糾錯。如根為

38474x1=a，x2=a，ew1=a，ew2=a，則在r(14-3)=r(11)上加ew1即a，在r(14-8)= r(6)7上加ew2即a后所得的數(shù)據(jù)就是糾錯后的數(shù)據(jù)。