基于 IT库的一种 RS 码编译码系统的设计与实现.doc

《基于 IT库的一种 RS 码编译码系统的设计与实现.doc》由会员分享，可在线阅读，更多相关《基于 IT库的一种 RS 码编译码系统的设计与实现.doc（16页珍藏版）》请在三一办公上搜索。

1、精品论文大集合基于 IT+库的一种 RS 码编译码系统的设计与实现赵明 北京邮电大学数字通信实验室，北京（100876） E-mail: noudou摘 要：BCH 码是一类广泛使用的线性纠错码，具有数学结构严密，理论研究透彻，实现简单，有成熟的编译码算法的支持等诸多优点，在深空通信，现代移动通信系统，存储设备等 多个领域都有广泛应用。IT+ 库是一个基于矩阵运算的高性能数值运算函数库，广泛用于 数字信号处理、通信系统仿真等领域。本文将首先介绍 BCH 码相关的理论要点，而后利用 IT+ 库提供的便利工具设计并实现一个 RS 码的编译码系统以作为 BCH 码的一个特例。最后， 还讨论了一些和代

2、码及 BM 算法有关的具体问题。关键词：BCH 码 IT+库 RS 码 BM 算法 中图分类号：TN911.221.引言BCH 码最初是由霍昆格姆于 1959 年，博斯和雷-查德胡里于 1960 年分别提出的。BCH 码 的名字就分别取自于这三人的名字中的一个字母。BCH 码是迄今为止所发现的一类很好的线 性纠错码。它的纠错能力强，构造方便，译码简单。由于它有严格的代数结构，因此它是迄 今为止研究得最为详细，取得的成果最多的码类之一。1960 年彼德逊从理论上解决了二进制 BCH 码的译码算法。稍后，格林斯坦和齐勒尔把 BCH 码推广到了多进制的情形。1966 年伯列坎普提出了 BCH 码的迭

3、代译码算法，大大加快了 译码速度，同时也降低了译码设备的复杂度，从而解决了 BCH 码的实用化问题。后来，梅西 又对该算法进行了改进，并指出它和最长线性移位寄存器理论之间的联系。因此，人们将这 个改进后的算法称为 BM 算法。RS 码是一种特殊的多进制 BCH 码，最初由里德和索洛蒙于 1960 年提出。RS 码具有很强 的纠错能力，尤其在纠正突发错误上有优势。本文将使用 BCH 码的一般译码算法完成 RS 码 的译码。2.有限域理论概述- 16 -首先要引入域的一般定义1：设集合 F ，F 对二元运算+和*均封闭，且以下条件满足：lF 对运算+是 Abel 群（记恒元为 0）；lF*对运算*

4、是 Abel 群（记恒元为 e）；l对a，b，c F，有 a b + c = ab + ac ；则称 F 为域。（F* = F0；Abel 群即交换群）。可见，所谓的域就是一个满足一系列约束条件的非空集合。而集合中的元素究竟是什么 我们并不关心，我们关心的只是元素之间是否存在运算关系以及这些运算关系是否满足定义 中的约束条件。域中元素的个数叫做域的阶。有限阶的域叫做有限域，也叫做伽罗华域。阶数为 q 的有2限域记作 GF(q)。有定理表明，有限域的阶数只能是素数或者素数的正整数次幂。引入了有限域之后，就可以将有限域中的元素当成码字中的符号，而编码或译码算法则是建立在有限域的元素之间的运算关系之

5、上的。所谓的运算关系在有限域的定义中已经十分 明确了。为了方便下文的陈述，我们还有必要定义一些常用的概念。设a GF(q)，且a 0，则使an = 1成立的最小正整数 n 称为非零元 a 的阶数。在有限域 GF(q)中，若非零元 a 的阶是 q-1，则称 a 是本原元。有限域的本原元即有限域的乘法群的生成元。设 , GF qm , ，若 能表示成 q l 的形式，l 为正整数，则称 与 是共轭的。设 F 是有限域，Fq 是 F 的子域（含 q 个元素）。设 是 F 中任一元素，定义 在 F 上的 极小多项式为 所适合的Fq x中首项系数为 e 的次数最低的多项式。3. RS 码的构造首先引入

6、RS 码的定义3：GF q (q 2)上，码长 N=q-1 的本原 BCH 码称为 RS 码。本文要构造的是 16 进制的 RS 码，因此首先要构造 GF(16)。根据文献2，在F2 x上,四次本原多项式之一为p x = x4 + x + 1设GF 16 = 0,1, , 2 , , 14 ，其中 是本原元。根据本原多项式的性质可知：p = 4 + + 1 = 0或自然还有 4 = + 1 5 = + 1 = 2 + 依此类推，可得到GF 16 中所有元素关于1, , 2 , 3 的线性组合表达式，如下：表 1 GF(16)中所有元素的二进制表示式基GF 16 元素1 2 3000001100

7、00100 20010 30001 41100 50110 60011 71101 81010 90101 101110 110111 121111 131011 141001从编码的角度来看，这张表实际上确定了码符号（GF 16 的元素）与四比特组之间的一一对应关系。码元符号集构造完毕后，还要构造编码器。RS 码属于循环码的范畴，因此可以通过确 定其生成多项式来完全确定码字。根据文献2，若假设 RS 码能纠正 3 个错误，则生成多项式为：g x = x + x + 2 x + 6= 6 + 9x + 6 x2 + 4 x3 + 14 x4 + 10 x5 + x6据此，可以很容易地构造循环码

8、编码器，从而完成 RS 码的编码。综上所述，我们已经构造了一个能纠正 3 个错误的（15，9）RS 码。4.译码算法BCH 码的通用译码算法如下m3（这里假设GF 2表示生成多项式的根域，r(x)表示接收码字多项式，i x 表示 i 在GF 2m 上的极小多项式）：a)计算伴随式S1 , S2 , , S2t ,Si = r i = bi i GF 2m .bi x = r x modi (x)。若 i 与 j 共轭，则i x = j (x), bi x = bj (x)。于是计算bj j 可以转化为计算bi j ，这样可以不用求bj (x)。b)求错误位置多项式 (x)。用 BM（伯列坎普梅

9、西）算法。初始化： = 1, d0 = S1 , 0 x = 1, d1 = 1, 1 x = 11)若 d 1 = 0, 则 x = 1 x2)若 d 1 0, 则找出 ，使 =k-b(k).length()+1;j-,l+)index(l)=j; d(k)=dat(s(index),b(k); if(d(k)=-1)elseb(k+1)=b(k);/l=k-1; l=0; for(j=0;jl-b(l).length()l=j;j=l;b(k+1)=pap(b(k),pmp(smp(mul(ni(d(j),d(k),base(k-j),b(j); 这段代码基本上按照第四节的译码算法步骤b)

10、中的三个子步骤来运行。但用粗体表示的两行代码代表着两种不同的算法：若采用代码l=0;，则相当于“找出 ，使 𝜇 1, d 0, l 最大且𝛒尽可能小”；若采用代码l=k-1;则相当于“找出 ，使 𝜇 1, d 0, l 最大且𝛒尽可能大”。这看上去是两种截然不同的算法，但却能得到相同的译码结果，可谓殊途同归。参考第四节的算法可知，只要满足 𝜇 1, d 0, l ，可选择任意的 值。因此以上两种代码实现方法应该得到相同的结果。这一点可以通过程序来验证。详细内容可参见第六节。 有关向量运算的函数如下所示：ivec s

11、mv(int a,ivec b)/标量与向量做乘法。int dat(ivec v1,ivec v2)/向量内积。 ivec vav(ivec a,ivec b)/向量加法。 完整的源代码清单可参见附录。6.仿真结果本次仿真中设置了有三个错误符号的错误向量0 0 0 7 0 0 3 0 0 0 0 0 4 0 0 因为本文设计的 RS 码的纠错能力就是纠三个错，因此上述错误应能够完全纠正。编译码结果如下图所示：图 1 编译码结果图从图中可见，接收端计算出来的错误向量与实际叠加在发送码字上的错误向量完全一 致，因此三个错误符号可以被完全纠正。在上一节中提到，按照不同规则选出的 值将影响中间结果，但

12、不改变最终的译码结果。可以通过在代码中的合适位置添加 cout 语句来观察各次迭代中 (x)的结果。 当使用代码 l=0 时，得到各次迭代的 (x)为 x = 1 x = 1 x = 1 + 12 x x = 1 + 3 x x = 1 + 3 x + 3 x2 x = 1 + 4 x + 12 x2 x = 1 + 4 x + 3 x2 + 13 x3 x = 1 + 7 x + 4 x2 + 6 x3当使用代码 l=k-1 时，得到各次迭代的 (x)为 x = 1 x = 1 x = 1 + 12 x x = 1 + 3 x x = 1 + 13 x + 5 x2 x = 1 + 4 x

13、+ 12 x2 x = 1 + 9x + 4 x3 x = 1 + 7 x + 4 x2 + 6 x3由此不难发现，以上两种情况只是中间结果不同，最终给出的结果是完全一致的。7.总结本文结合 IT+库提供的 API 进行编程，按照编译码的各个步骤依次完成了相应的软件 实现。程序运行结果表明，设计的编译码方案可靠有效，达到了预期的纠错能力。利用相同的程序，稍加改动后还观察到了不同的译码策略带来的影响。根据实验结果可知，在选择序 号 的问题上确实具有一定任意性。8.附录本附录的内容是程序代码清单，包括一个头文件和一个源文件。a)myhead.h 头文件的内容如下：1.#includeitbase.

14、h2.int xoz(bvec a);3.bvec zox(int x);4.int add(int x,int y);5.int mul(int x,int y);6.int dat(ivec v1,ivec v2);7.int ni(int x);8.ivec smp(int a,ivec b);9.ivec vav(ivec a,ivec b);10. ivec pmp(ivec p,ivec q);11. ivec pap(ivec p,ivec q);12. ivec base(int n);13. ivec brief(ivec a);14. ivec berlekamp(ivec

15、 s);15. ivec smv(int a,ivec b);16. ivec rsencoding(ivec in);17. int cimi(int x,int n);18. int rfa(ivec r,int x);19. ivec cs(ivec r);20. int pofx(ivec p,int x);21. ivec ed(int initial,int delta,int length);22. ivec error(ivec sigma,ivec s);b)testRSCode.cpp 源文件内容如下：1.#includemyhead.h2.3.void main()4.5

16、.ivec data=3 -1 6 -1 -1 8 -1 14 -1;6.coutendlendlTransmitterendlinformation symbles=endldataendl;7.ivec code=rsencoding(data);8.coutcoded symbles=endlcodeendl;9.ivec te=-1 -1 -1 7 -1 -1 3 -1 -1 -1 -1 -1 4 -1 -1;10.couterror vector=endlteendl;11.ivec r=vav(code,te);12.cout*endl Receiverendl;13.coutre

17、ceived vector=endlrendl;14.ivec s=cs(r);15.ivec sigma=berlekamp(s);16.ivec e=error(sigma,s);17.coutcalculated error vector=endleendl;18.ivec result=vav(r,e);19.coutcorrected symbles=endlresultendl;20.ivec decode_bits=result(6,14);21.coutdecoded result=endldecode_bitsendl;22. 23. ivec error(ivec sigm

18、a,ivec s)/接收找错位多项式和校验子，输出错误多项式。24. 25.int i,j;26.ivec t;27.ivec b(sigma.length();28.for(i=0,j=1;i15;i+)29.30.if(pofx(sigma,i)=-1)31.32.b(j)=ni(i);33.j+;34.35.36.ivec z(sigma.length();37.z(0)=0;38.for(i=1;iz.length();i+)39.40.z(i)=dat(s(ed(i,-1,i+1),sigma(0,i);41.42.ivec temp(2);43.ivec e(sigma.lengt

19、h();44.for(i=1;ie.length();i+)45.46.t=0;47.for(j=1;jsigma.length();j+)48.if(j!=i)49.50.temp(0)=0;51.temp(1)=b(j);52.t=pmp(t,temp);53.54.e(i)=mul(pofx(z,ni(b(i),ni(pofx(t,ni(b(i);55.56.ivec result(15);57.result.zeros();58.result-=1;59.for(i=1;ib.length();i+)60.result(b(i)=e(i);61.return result;62. 63

20、.64. ivec ed(int initial,int delta,int length)/输出等差数列，输入初始值、步长和数列长度。65. 66.ivec result(length);67.int n;68.for(n=0;nlength;n+)69.result(n)=initial+n*delta;70.return result;71. 72. int pofx(ivec p,int x)/求多项式p(X)在点X=x的值p(x)。73. 74.ivec q=p;75.int i;76.if(q.length()=1)77.return q(0);78.else79.80.for(i

21、=1;iq.length();i+)81.82.q(i)=mul(q(i),cimi(x,i);83.q(0)=add(q(0),q(i);84.85.return q(0);86.87. 88. ivec cs(ivec r)/输出校验子，输入接收多项式。89. 90.ivec re(7);91.int x;92.for(x=1;x7;x+)93.re(x)=rfa(r,x);94.re(0)=0;95.return re;96. 97. int rfa(ivec r,int x)/计算r(x)的值，可用于计算接收多项式对应的校验子。98. 99.ivec t(15);100.int m;1

22、01.for(m=0;m15;m+)102.t(m)=cimi(x,m);103.m=dat(t,r);104.return m;105. 106. int cimi(int x,int n)/计算x的n次幂。107. 108.if(n=0)109.return 0;110.else if(n=1)111.return x;112.else113.114.int y,k;115.y=x;116.for(k=1;kn;k+)117.y=mul(x,y);118.return y;119.120. 121. ivec rsencoding(ivec in)/完成RS编码。122. 123.if(i

23、n.length()!=9)124.125.coutrsencoding error!-1;k-)135.136.c(0)=-1;137.c.set_subvector(1,a.get(0,4);138.a=vav(smv(add(a(5),in(k),b),c);139.140.b.set_size(15);141.b.set_subvector(0,a);142.b.set_subvector(6,in);143.return b;144.145. 146.147.148. ivec base(int n)/产生单项式x的n次方。149. 150.ivec a(n+1);151.a.zer

24、os();152.a-=1;153.a.shift_left(0);154.return a;155. 156.157. ivec berlekamp(ivec s)/用BM算法求“找错位多项式”。158. 159.Array b(s.length()+1);160.ivec d(s.length();161.int k,j,l;ivec index;162.b(0)=0;163.b(1)=b(0);164.d(0)=0;165.for(k=1;k=k-b(k).length()+1;j-,l+)169.index(l)=j;170.d(k)=dat(s(index),b(k);171.if(

25、d(k)=-1)172.173.b(k+1)=b(k);174.175.else176.177.l=k-1;178./l=0;179.for(j=0;jl-b(l).length()183.l=j;184.j=l;185.b(k+1)=pap(b(k),pmp(smp(mul(ni(d(j),d(k),base(k-j),b(j);186.187.188.return b(b.length()-1);189.190. 191. ivec brief(ivec a)/紧凑化多项式向量。192. 193.int i=a.length()-1;194.while(i!=0&a(i)=-1)195.1

26、96.i-;197.198.ivec b=a.get(0,i);199.return b;200. 201. ivec pap(ivec p,ivec q)/多项式加法。202. 203.ivec result(p.length()q.length()?p.length():q.length();204.ivec temp;205.if(p.length()=q.length()206.207.result=p;208.temp=vav(q,result.get(0,q.length()-1);209.result.set_subvector(0,temp);210.211.else212.2

27、13.result=q;214.temp=vav(p,result.get(0,p.length()-1);215.result.set_subvector(0,temp);216.217.result=brief(result);218.return result;219. 220. ivec pmp(ivec p,ivec q)/多项式乘法。221. 222.ivec result(p.length()+q.length()-1);223.result.zeros();224.result-=1;225.int k;226.ivec temp;227.for(k=0;kp.length()

28、;k+)228.229.temp=vav(smp(p(k),q),result.get(k,k+q.length()-1);230.result.set_subvector(k,temp);231.232.result=brief(result);233.return result;234. 235. ivec vav(ivec a,ivec b)/向量加法。236. 237.if(a.length()!=b.length()238.coutvav failed!endl;exit(0);239.ivec result(a.length();240.int i;241.for(i=0;ia.l

29、ength();i+)242.result(i)=add(a(i),b(i);243.return result;244. 245.246. ivec smp(int a,ivec b)/标量与多项式做乘法。247. 248.ivec result(b.length();249.int i;250.for(i=0;ib.length();i+)251.result(i)=mul(a,b(i);252.return result;253.254. 255.256. ivec smv(int a,ivec b)/标量与向量做乘法。257. 258.ivec result(b.length();25

30、9.int i;260.for(i=0;ib.length();i+)261.result(i)=mul(a,b(i);262.return result;263. 264.265. int ni(int x)/求一个有限域元素的倒数。266. 267.if(x=-1)268.coutni failed!endl;269.exit(0);270.271.int result=x*(-1);272.result=mod(result,15);273.return result;274. 275.276. int dat(ivec v1,ivec v2)/向量内积。277. 278.int i,j

31、,result;279.j=v1.length();280.ivec c(j);281.for(i=0;ij;i+)282.c(i)=mul(v1(i),v2(i);283.result=-1;284.for(i=0;i14|x14|y-1)300.coutmul failed!endl;301.exit(0);302.303.int result;304.if(x=-1|y=-1)305.result=-1;306.else307.x+=y;result=mod(x,15);308.return result;309. 310.311. int xoz(bvec a)/比特序列转换成指数式。312. int result;313. if(a=0 0 0 0)314. result=-1;315. else if(a=0 0 0 1)316. result=0;317. else if(a=0 0 1 0)318. result=1;319. else if(a=0 1 0 0)320. result=2;321. else if(a=1 0 0 0)322. result=3;323. else if(a=0 0 1 1)324. result=4;325. else if(a=0 1 1 0)326. result=5;327. else if(a=1 1 0 0)3