RS码编译码算法的实现(学习RS码极为有用)

1、文章编号:049026756(20000620868205RS 码编译码算法的实现陶德元,何小海,吴志华(四川大学电子信息学院,成都610064摘要:作者在详细分析了RS 码原理与性质的基础上,详尽地推导了RS 码的编译码过程,并通过实例说明其具体应用.关键词:RS 码;伽罗华域;非二元码;编码;译码中图分类号:TN914.31文献标识码:ARS 码的纠错能力非常强,尤其是对那些突发性成片的干扰特别有效,但因它的译码比较复杂,且专门介绍译码过程的资料很少,所以不少人情愿使用纠错能力较弱的其它方法也不想投入更多的精力把RS 码的译码钻透,这就严重影响了RS 码的推广应用.为此,我们在进一步讲清R

2、S 码的原理与性质的基础上,对编码与译码作了详细介绍,并通过实例把编译码的每一步骤都交待得非常清楚,以达到举一反三之目的.1RS 码的原理与性质在非二元码中,如果p 是素数,q 是p 的任意次幂,则存在着由伽罗华域GF (q 产生的q 元码.一个q 元(n ,k 循环码的生成多项式是x n -1的因式,它是以GF (q 域上的元素为系数的n -k 次多项式.对任意选择的正整数s 及v ,存在长度为n =q s -1的q 元BCH 码.它只用2sv 个校验位就能纠正v 个错误.当s =1时的q 元BCH 码称为RS 码.它是一类非二元BCH 码.RS 码的一个重要性质是,真正的最小距离与设计距离

3、总是相等的.每种RS 码都是一个最大距离可分码,这是因为其最小距离等于n -k +1.当省掉RS 码的某些信息符号后,分组长度缩短,但最小距离并不减少,故任何一种缩短的码仍是一个最大距离可分码.RS 码的另一个重要性质是,在其码字内的任何k 个位置都可用作信息集合.(n ,k RS 码中,输入信息分成k m 比特一组,每组包括k 个符号,每个符号由m 比特组成.一个纠v 个符号错误的RS 码有如下参数:码长n =2m -1信息段k 监督段n -k =2v 最小码距d =2v +1符号符号符号符号或m (2m -1比特或k m 比特或m (n -k 比特或m (2v +1比特对于纠v 个错误符号

4、的RS 码生成多项式为g (x =(x +a (x +a 2(x +a 3(x +a 4(x +a 2v (1收稿日期:20002102232000年12月第37卷第6期四川大学学报(自然科学版Journal of Sichuan University (Natural Science Edition Dec.2000其中a 为GF (2m 上的本原元.显然,g (x 的全部根为a ,a 2,a 2v .它的系数是GF (2m 的元素.由g (x 生成的码是(n ,n -2v 循环码.它包括所有那些能被g (x 除尽,系数是GF (2m 的元素次数不大于n -1的多项式.RS 码的编译码是基于

5、一组码元而不是单独的0或1,这也是RS 码纠错能力特别强的原因,并且这种特点使得RS 码特别适合处理突发成片的错误.2RS 码的编码由于RS 码是循环码的一种,因此,它的编码方法与一般循环码的编码方法完全一致.用信息码多项式m k -1x k -1+m k -2x k -2+m 0升x n -k 位后去除生成多项式g (x ,所得余式r (x 为监督多项式,将监督多项式置于升x n -k 位的信息多项式之后,就形成RS 码.因此RS 码的编码变成用除法求余的过程,由于纠v 个符号错误的生成多项式为g (x =2v i =1(x +a i =2vi =0g i x i (2a 是有限域GF (2

6、m 的元素.设输入信息码为m (x ,编码后的码组为c (x ,则c (x =x n -k m (x +x n -k m (x mod g (x (33RS 码的译码差错控制编码中译码的好坏是应用的关键,而译码算法通常比编码复杂.相比之下,RS 码的译码算法又要比其它译码复杂得多,这是因为RS 码是一种非二元循环码,它不再具备特征为2的域的运算等性质.并且RS 码的译码不仅要找出错误位置,而且还要找出对应错误位置的错误大小,因此增加了译码的难度.RS 码的译码也是从计算接收码字的伴随式入手.3.1计算多个伴随式值S k假设T (x =t 0+t 1x +t n -1x n -1是发送的码矢.设

7、R (x =r 0+r 1x +r n -1x n -1是相应的接收的码矢.则由信道引起的错误图样为e (x =R (x -T (x =e 0+e 1x +e n -1xn -1这里e i =r i -v i 是GF (2m 的元素.设错误图样e (x 含有v 个错误(非零元素分别位于x 1,x 2,x v,则e (x =e 1x 1+e 2x 2+e v x v 因此为决定e (x ,我们需知道错误位置x i 及错误值e i .2v 个伴随式元素是通过把a i 代入接收多项式R (x 而得到,如果s k =0,认为接收无误;若s k 0,由s k 找出错误图样.因为R (a i =e (a

8、i +T (a i =e (a i (T (a i =0,因此S 1=R (a =e 1x 1+e v x vS 2=R (a 2=e 1(x 12+e v (x v 2S 2v =R (a 2v =e 1(x 12v +e v (x v 2v (4968第6期陶德元等:RS 码编译码算法的实现078四川大学学报(自然科学版第37卷3.2由伴随式值确定差错定位多项式由上式直接求解e i和x i非常困难,因为它是一个非线性联立方程组,一般不直接求解,而是将其转换为一组线性方程.为求出v个错误位置x i,可构造以v个错误位置x i为根的一元v次线性方程(x=x i v+1x i v-1+v=0i=

9、1,2,v(5i显然,以x i的任何次幂与上式相乘后该式仍为零,现以e i x j i与其相乘,可写出e i x i v+j+1e i x i v+j-1+v e i x j i=0i=1,2,v(6将(6式对i=1,2,v相加,由式(4可得S v+j+1S v+j-1+v S j=0(7由(7式定义的方程式叫牛顿恒等式,以纠v个差错的非二元RS码为例,我们已计算出2v个伴随式值S1,S2,S2v.由(7式,令j由1取至v,可构成v个线性系数的联立方程.S v+1+1S v+v S1=0S v+2+1S v+1+v S2=0(8S2v+1S2v-1+v S v=0通过解联立方程,利用克莱姆法则

10、可求得(x的系数1v.这种方法运算量比较大,但很适合用计算机编程实现.并且容易理解,简单易行.3.3求出错误位置值求得一元v次线性方程的系数后,我们可以解出其根,即错误位置,但不宜直接求解,而是采用直接代入的方法,对于(x=x t i+1x t-1i+t=0i=1,2,ti设先考虑发送的高阶次比特,以便先对a n-1定位式进行根测试,当代入a i(i=n-1,n-2,0求得(a i为零时,说明第i个码元发生错误.这种循环的方法非常适合于用计算机实现.3.4由所得的错误位置值计算错误值把上面计算的错误位置值代入式(4,以与求1v相同的方法解联立方程组可得错误值.3.5对所标的差错位置及错误值进行

11、纠正在对应的错误位置,加上相应的错误值,即完成纠错.4编译码的实现下面通过实例说明RS码的编译码方法.为便于计算,我们以距离小于7的码为例,而距离大于7的码可以此类推.在举例之前先讨论一下纠1个错误的BCH码(15,11循环汉明码.由其g(x=m1(x =x4+x+1得监督矩阵为H=111101011001000 011110101100100 001111010110010 111010110010001可记为H=a14a13a12a2a1a0,a i是有限域元素,能表错误位置数,可以进行加法和乘法运算.加法运算如同矢量算法相加一样,码组逐位相加(模2和.如a14+a12=1001T+111

12、1T=0110T=a5乘法运算时指数相加,但以n=2m-1为模.如a5a11=a16=a1mod15例构造能纠正2个错误,码长为15符号的RS码.由n=15,t=2可得m=4,r=11,d=5.因此RS码为(15,11码,生成多项式为g(x=(x+a(x+a2(x+a3(x+a4=x4+a13x3+a6x2+a3x+a104.1编码假设待发送的信息码组为m=(a2000a30000a90,用码组多项式可表示为m(x= a2x10+a3x6+a9x,则编码后的码组多项式为T(x=x n-k m(x+x n-k m(xmod g(x=a2x14+a3x10+a9x5+x3+a3x+a13即:T=(

13、a2000a30000a90a00a3a13.4.2译码假设接收码组R发生了2个错误,位置为第5位和11位,分别由a9错成为a6,0错成为a,则:R=(a200aa30000a60a00a3a13R(x=a2x14+ax11+a3x10+a6x5+x3+a3x+a13(1计算多个伴随式值S1=R(a=a2a14+aa11+a3a10+a6a5+a3+a3a+a13=a16mod15+a12+a13+a11+a3+a4+a13=0010T+1111T+1101T+1110T+1000T+0011T+1101T=a3同理S2=R(a2=a2,S3=R(a3=a8,S4=R(a4=a5,S5=R(a

14、5=a12,S6=R(a6=a13(2由伴随式值确定差错定位多项式对于距离小于7的RS码,能通过伴随式决定接收码字发生的错误数目.若S k=0,则没有错误.若D3=S1S3S5+S1S24+S22S5+S330,则有3个错误存在;若D3=0与D2=S1S3+S220,则有两个错误存在;若D3=D2=0与S10,则有一个错误存在.1=(S1S4+S3S2/D2=(a3a5+a8a2/a13=(a8+a10/a13=(0101T+0111T/a13=a1/a13=a32=(S2S4+S23/D2=a178第6期陶德元等:RS码编译码算法的实现278四川大学学报(自然科学版第37卷(3求出错误位置值

15、由各系数确定差错定位式:(x=x2+a3x+a.依次代入a14, a13,a0,当x=a5或a11时(x=0,因此错误位置为a5和a11即第5位和第11位.(4由所得的错误位置值计算差错值令x1=a5,x2=a11把错误位置值代入(4式,可解出错误值e1=(s1x2+s2/(x1x2+x21=(a3a11+a2/(a5a11+a10=(a11+a2/(a5a11+a10=a13/a8=a5e2=(s1x1+s2/(x1x2+x22=a(5对所标的差错位置及错误值进行纠正接收的码字在第5位错误值为a5和第11位错误值为a,把错误值a5和a加到对应的错误位置第5位和第11位,即a5+a6=0110

16、T+1100T=1010T=a9和a+a=0010T+0010T=0得纠错后的码组为(a2000a30000a90a00a3a13,就是原发送的码组,则圆满完成译码任务.参考文献:1傅海阳,赵品勇.SDH微波通信系统M.北京:人民邮电出版社,2000.2王新梅,肖国镇.纠错码原理与算法M.西安:西安电子科技大学出版社,1996.3归绍升.纠错编码技术和应用M.上海:上海交通大学出版社,1988.THE IMPL EMENTATION OF RS ENCODING AN D DECODINGTA O De2yuan,H E Xiao2hai,W U Zhi2hua(College of Electronic Information,Sichuan University,Chengdu610064,ChinaAbstract:Of all kinds of error2control encoding techniques in communication system,RS code is widely used fo