RS编译码

2024年2月15日发(作者：条分缕析)

一．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个连续根m0,，m02t1作为g(x)的根来构造生成多项式g(x)=(x+m0)(x+m01)(x2t1m0)

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

只要将信息码多项式m(x)=mk1xk1m1xm0 乘以xnk次，然后以g(x)为模，求出余式q(x)便可以得到系统码。

q（x）= m(x)

xnkmodg(x)=qnk1xnk1q1xq0

C(x)= m(x)

xnk+ q（x）

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

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

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

xnk+ m(x)

xnkmodg(x)=2x143x109x5x33x13

编码的实现：

1）首先构造有限域，RS码的性质和运算法则均定义在Galois域上，Galois域是能进行加减乘除运算的有限个元素的封闭集合，它的加减运算符合结合律、交换律和分配律。有限域中的元素有两种表示方法：即指数形式和多项式形式。乘除法运算需用元素指数形式，加减法运算要用多项式形式。

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

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

GF（24） 元素表 最小多项式为x4x1

序号i 指数形式 多项式形式

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

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

nk2t

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

nk3）对信息数据进行编码

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)。

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

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

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

若信道产生t个错误，则e（x）=Yixli 式中，YiGF(2m)，xli称为错误i1t位置数，说明错误发生在r（x）中的第nli位，错误值是Yi.

00Yt0

0Y100m0n1m0n2()()m01n1m01n2T()SHET=()m02t1n1m02t1n2))((1m011m02t11m0m0li1m0li2m0lit)))(((YYY12t=

li1li2lit2t12t12t1mmm000Y1()Y2()Yt()sjYii1tjlir(j)i1jYixi （*）

t1）首先计算伴随式，定义伴随多项式s(x)1s1xs2x2stxt若S（x）=0，则表示接收到的码字没有错误或者发生了无法检测的错误。输出原接收码字。用Horner法实现sir(i){((rn1irn2)irn3)ir1}ir0

2）用BM迭代算法求错误位置多项式，由（*）式中的2t个方程求出2t个未知数xi，Yi。分两步进行，先解出错误位置数xi，再求出错误值。

定义错误位置多项式为(x)(1xix)11xtxt

i1t若xk11为错误位置则(xk)0两边乘以xkt，得

tt1xk1xkt0,k1,2,t

上式jt两1Ykxk边jt1再乘以jjYkxk,jm0,,m0t1得YkxktYkxk0,k1,2,t

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

作乘积s(x)(x)并用(x)11x2x2表示，由（**）式可得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)

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

11(j1)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)(0)(x)1，(x)1，D（0）=0，d0s1

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

D(j)i1(j)首先计算djsj1sj1ii

若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)

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

11(j1)D（j+1）=max（D（j），j-i+D（i））

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

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

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

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

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

(nl)l代入(x)=0

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

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

3）错误值的计算

用Forney算法

Y(xixii1)'(xi1)

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

si1Ykxjk

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

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

得出(x)Ykxkxk11xkx=(x)-(x)

Yixix1x(x)+(x)Yjxjx=(x)-(x)

ixjj11ixjx得YxrxYjxjxiix(1jx)+(x)=(x)-(x)

ij1jj1j1ix

jx代入rx1i得Yixix1i(1jxjx11i)=(xi)

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

ij1j****）

（

代入xi1得-xi11(xi)xi(1xjxi)

i1j1ij'1r代入（****）式得-Yixixi得错误值Yi

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

xixi1'xi(xi)1(xi)'1