RS编译码

一．RS码

RS码是有限域GF（p^m）上，码长为n=p^m-1的本原BCH码，它是多进制的BCH码。

RS码不但可以纠正随机错误、突发错误以及二者的组合，而且可以用来构造其它码类。

在计算机中数据是以二进制的形式存在，所以p通常取值为2。

RS码的参数：符号取自GF(2^m)，纠t个错的RS(n,k)码的定义如下：

符号大小m．表示符号比特数为m位。码块总长度为n个符号，其中信息长度k个符号，校验位长度K=n—k个符号。RS码的纠错能力是出码块中的冗余数据校验码的长度K决定的。在码块中的错误位置事先并不知道的情况下，RS(n，k)码可以纠正t=K／2个错误符号。显然t值越大，RS码的纠错能力越强，但与之相对应的是更复杂的算法，更长的运算时间，更低效的数据传输率。

RS码既可以纠随机错又可以纠突发错。但RS码中采用符号这一特性使得它特别适用于产生突发错的场合。因为不论一个符号中错了多少位，在RS解码过程中。它只会被认为是产生了一个符号错。一个可以纠t个符号的RS码，它至少可以纠一个(t-1)m+1个连续比特组成的突发错，而当随机错恰好都不在同一个符号中时只能纠正t个比特的随机错。

二．RS码编码

对于GF(2^m)来说，若域中非零元素a的级是2^m-1，则将a称为本原域元素。设

符号取自GF(2^m)，纠t个错的RS(n,k)码,它的最小距离d=2t+1，则由本原域元素a的2t

m0m0个连续根,，002t1作为g(x)的根来构造生成多项式

m(x2t1m0)mg(x)=(x+)(x+)

1通常情况下取通常取m0 = 0或m0 = 1

只要将信息码多项式m(x)=mk1x式q(x)便可以得到系统码。

k1m1xm0 乘以x次，然后以g(x)为模，求出余

nknkqq（x）= m(x) xmodg(x)=nk1xnk1q1xq0

nkxC(x)= m(x) + q（x）

例 构造能纠正2个错误，码长为15符号的RS码

n=15，t=2可得m=4，k=11，d=5．因此RS码为(15，11)码，生成多项式为g(x)=(x+)(x+)(x+)(x+) =xxx2344133623x10

假设待发送的信息码组为m(x)=m(x) xnkm(x)2x103x69x则编码后的码组多项式为C(x)=

+ m(x) xmodg(x)=xnk2143x109x5x33x13编码的实现：

1）首先构造有限域，RS码的性质和运算法则均定义在Galois域上，Galois域是能进行加减乘除运算的有限个元素的封闭集合，它的加减运算符合结合律、交换律和分配律。

有限域中的元素有两种表示方法：即指数形式和多项式形式。乘除法运算需用元素指数形式，加减法运算要用多项式形式。

指数形式表示多项式形式的十迸制值为i的元素，它的指数形式的指数

指数形式为i的元素它的多项式形式

GF（24） 元素表 最小多项式为x4x1 序号i 指数形式 多项式形式

m(x2tm0)m2)构造生成多项式g(x)=(x+)(x+)

0012(x2t)1m0 设 = 1 g(x)=(x+)(x+)

nk2t

g(x)gnkxnkg1xg0g，nk=1

3）对信息数据进行编码

RS时域编码原理图（n-k级时域编码器）其电路特征是一个实现除法求模运算的线性反馈移位寄存器，该方法得到的是系统码。

信息码组从高位到低位送入线性反馈移位寄存器，每一个码元一方面经过控制开关送出编码器，另一方面该码元与移位寄存器Dnk的输出进行异或运算，结果作为feedback反馈回电路与系数g[O]到g[n-k-1]相乘后再与各个移位寄存器的输出进行异或运算。当所有的信息码元都输入线性反馈移位寄存器后，n-k个移位寄存器中的值就是生成的n-k个校验码元。这样信息码元在前，校验码元在后，这就完成了编码。

三．RS码的译码

基于伴随式的译码算法，由于其译码过程较为简单，译码速度快，是最为常用的译码算法。伴随式译码的一般步骤为：

1)计算接收码字r(x)的2t个伴随式si，i=l，2，…2t；

2)求出错误位置多项式，确定错误位置；

3)求出错误位置上的错误值：

4)由步骤2和步骤3得到错误图样E(x)的多项式，则纠错后的码字多项式c(x)

为：c(x)=r(x)-e(x)。

n1c(x)c1xc0 cxn1假设发送的码字为：

n1r(x)r1xr0 xrn1由于在传输过程中发生了错误，接收到的码字为：

n1e1xe0 exn1错误图案是：e（x)=r(x)-c(x)=

若信道产生t个错误，则e（x）=i1Yixlitm)liGF(Y2i 式中，，x称为错误位置数，

说明错误发生在r（x）中的第nli位，错误值是Yi.

m0n1m0n2))((m01n1m01n2)()(n1m02t1n2THT(m02t1))(SE=1m011m02t11m000Yt00Y100

m0li1m0li2m0lit)))(((YYY12tlilili12t2t12t12t1Y1(m0Y2(m0Yt(m0))) =

sjYii1tjlir(j)i1Yixitj （*）

2ts(x)1xssxsx12t1）首先计算伴随式，定义伴随多项式若S（x）=0，则表

示接收到的码字没有错误或者发生了无法检测的错误。输出原接收码字。用Horner法实

iiiiir(){(())}r0 srrrrn1n2n31i现

2）用BM迭代算法求错误位置多项式，由（*）式中的2t个方程求出2t个未知数xi，

Yi。分两步进行，先解出错误位置数xi，再求出错误值。

定义错误位置多项式为

(x)(1xix)11xtxti1t

1tt11tt0,k1,2,t ()0xxxxxk1k若k为错误位置则两边乘以k，得k上式

1Ykxk两

jt1边再

j乘以

jYkxk,jm0,,m0t1得

YkxkjttYkxk0,k1,2,t

tsj0对k求和得sjt1sjt1 （**）

2(x)1xs(x)(x)x12作乘积并用表示，由（**）式可得t+1次以上系数为0。

得关键方程s(x)(x)(x)modx2t1

用关键方程求(x)的迭代译码算法：

用迭代方法求解到第j步时，求得满足

s(x)(j)(x)(j)(x)modxj1的解(j)(x)，(j)(x)。

在第j+1步时以xj2(j)(x)(j)(x)为模，，不再满足上式。

所以引入一个差值dj，使下式成立

s(x)(j)(x)(j)(x)djxj1modxj2 （***）

(j)t(j)(j)(x)11xD(j)x

将（***）式左边展开推出

djsj1sj1iii1D(j)(j)将dj代入关键方程求解得

(j1)(x)(j)(x)djdixji(i)(x)

11(j1)(x)(j)(x)djdixji(i)(x)

I是j之前的某一行，它在所有j行之前各行中的i-D（i）最大，且di0

D（j+1）=max（D（j），j-i+D（i））

迭代过程如下：

设定初值为(1)(x)1，(1)(x)0，D（-1）=0，d11

(0)(x)1，(0)(x)1，D（0）=0，d0s1

开始迭代 j=1，2，……2t

首先计算

djsj1sj1iii1D(j)(j)

若dj=0则(j1)(x)(j)(x)

(j1)(x)(j)(x) D（j+1）=D（j）

若dj0则找出j之前的某一行i，它在所有j行之前各行中的i-D（i）最大，且di0

(j1)(x)(j)(x)djdixji(i)(x)

11(j1)(x)(j)(x)djdixji(i)(x)

D（j+1）=max（D（j），j-i+D（i））

(2t)(x)(2t)(x)一直迭代2t次，得到的，即为所求的(x)和(x)

判断(x)次数是否大于t，如果大于t说明有不可纠的错误，如果小于等于t则求(x)=0的根，即为错误位置数。

3）用钱氏搜索求错误位置

r(x)rn1xn1r1xr0

(nl)nl(nl)l(x)rnl判断是否错误，是否是错误位置数，判断是否是的根，代

入(x)=0

11lttl0 则rnl有错

11lttl0 则rnl正确

3）错误值的计算

用Forney算法

Yixi(xi)1'(xi)

1若实际产生的错误个数t

siYkxkk1j

Ykxkxi1isixsixi1i1=1+k11xkx s(x)1s1xs2x21Ykxkxs(x)(x)=（1+k11xkx）(x)=(x)modx21

由于恒等式左边最高次数为2

Ykxkx得出(x)k11xkx=(x)-(x)

Yixix1xix(x)(x)+

Yjxjxj11xjxji=(x)-(x)

Yixix(1xjx)得

j1ijr+(x)Yjxjxj11xjxji=(x)-(x)

Yixixi代入xi得

11j1ij1(1xjxi)r1(=xi) （****）

rxi(1xjx)因为'(x)i1ij1j

rxi(1xj1代入

x1111xi)ii得-xi'(xi)ij1j

代入（****）式得-Yixix1x1'i(x1ii)(x1i)

i(xi1)得错误值

Yix'(xi1)