RS糾錯編碼原理

2024年2月15日發(作者：愛情可以有)

RS基本概念

GF(2m)域

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

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

q

)個符號

且具有以下性質：

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

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

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

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

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

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

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

8104GF(24) 的所有元素

例：m=4,本原多項式

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

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

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

元素

0

a

a

a

a

a

a

a

a

76523243210多項式表示

0

1

a

a

a

a+1

a+a mod

p(a)

a+a mod

p(a)

a+a+1mod

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

28a+1mod

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)

3323232320101

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位二進制數組成

n 表示碼塊長度，

k 表示碼塊中的信息長度

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

t 表示能夠糾正的錯誤數目

RS的編碼算法

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

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

(13－2)

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

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?1的剩余多項式為

R(x)??i?0Qixi?Q3x3?Q2x2?Q1x1?Q0

的階次少一階。 這個多項式的階次比如果K0 = 1，t = 1，由式(13－2)導出的RS校驗碼生成多項式就為

234(x?a)(x?a)(x?a)(x?a)(13－4) =

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

M(x)+R(x)=

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

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

?m10a14?m9a13?......?m0a4?Q3a3?Q2a2?Q1a1?Q0?0?28268642?m10a?m9a?......?m0a?Q3a?Q2a?Q1a?Q0?0

?423912963?m10a?m9a?......?m0a?Q3a?Q2a?Q1a?Q0?0?ma56?ma52?......?ma16?Qa12?Qa8?Qa4?Q?0903210?10令m10a14?m9a13?......?m0a4=n0

m10a28?m9a26?......?m0a8=n1

m10a42?m9a39?......?m0a12=n2

m10a56?m9a52?......?m0a16=n3

解得：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)計算錯誤值?，F以例13.3為例介紹RS碼的糾錯算法。

1、 求出校正子：

sj??rixi?0

1414?ix?aj對于一組接收到的數據：

接收到的數據：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，則無錯；否則執行下面的步驟以求出錯值及位置。

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后所得的數據就是糾錯后的數據。