RS纠错算法

2024年2月15日发(作者：华北科技学院吧)

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、 乘运算定义为元素的指数相加后进行模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) 的所有元素：

因为α 为p(x)的根 得到 ++1=0 或 =+1 (根据运算规则)

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

元素

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位二进制数组成

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1R(x)QixiQ3x3Q2x2Q1x1Q0

i0这个多项式的阶次比的阶次少一阶。

如果K0 = 1，t = 1，由式(13－2)导出的RS校验码生成多项式就为

=

(xa)(xa2)(xa3)(xa4)根据多项式的运算，由式(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)计算错误值。现以例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后所得的数据就是纠错后的数据。