基于CPLD的BCH码编-译码器的设计与实现

1、基于CPLD的BCH码编-译码器的设计与实现2010年9月西安邮电学院Sept.2010第15卷第5期JOURNALOFXIANUNIVERSITYOFIKISANDTELECi)MMUNICATIONSVo1.15No.5基于CPLD的BCH码编/译码器的设计与实现张高记,罗朝霞2(1.西安邮电学院通信与信息工程学院,陕西西安710121;2.西安邮电学院电子工程学院,陕西西安710121)摘要:为提高BCH编僻码器系统性能,使硬件设计更具灵活性,提出了一种基于CPLD的BCH编/译码器实现方法.通过设计BCH(57,44,6)编/译码器,对BCH码的构造方法,BCH编僭码器进行了研究.论述

2、了一种基于复杂可编程逻辑器件,采用模块化设计思想,利用VHDL硬件描述语言实现BCH编僻码器的方法;在QuartusII软件环境下给出了BCH(57,44,6)编/译码器的仿真结果,并在CPLD器件上验证实现.仿真和实验都证明了这种方法的可行性和正确性.关键词:CPLD;VHDL;BCH码;编码器;Meggitt译码器中图分类号:TN919.3文献标识码:A文章编号:10073264(2010)050030040引言BCH(BoseChaudhuriHocquenghem)码是一类特别适用于随机差错校正的循环校验码,也是最重要且最有效的线性分组码之一,由Bose,Chaudhuri和Hocqu

3、enghem在1950年1960年问提出l1J.BCH码具有严格的代数结构,能灵活地选择码参数,如分组长度和码率,所以是到目前为止研究得最为详尽,应用最为广泛的一类码【2J.BCH编/泽码器可通过硬件或软件实现.软件实现方法特另lI适合计算机通信网等场合,可以直接利用网中的计算机进行编码和译码,不需要另加专用设备,但软件实现速度较慢;硬件实现方法速度较高,比软件实现可快几个数量级,适合于对实时性要求较高的语音,视频等数字通信系统J.传统硬件实现方法,主要采用传统数字逻辑电路设计来实现,即通过大规模集成电路来实现,这种设计方法存在结构复杂,体积大,集成度低,稳定性不高等缺点,而基于CPLD的硬件

4、设计方法,正好可以克服这些缺点,使电路设计更具灵活性和便捷性,便于实现系统的小型化,集成化.文中以BCH(57,44,6)码为例研究了基于CPLD的BCH编/泽码器的设计方法,选用Altera公司的可编程逻辑器件EP1CAQ240C8,在Quartus开发环境下,实现BCH编/译码器.BCH编码器原理及实现1.1BCH(57,44,6)编码器的原理BCH码的结构完全建立在有限域的基础上,可以用近世代数的方法精确描述【.(57,44,6)BCH码是一个系统循环码,其产生的具体步骤为:(1)将信息多项式inf(z)预乘Xn;(2)将inf(z)除以g(z),得余式r(x);(3)系统循环码的码多项

5、式为c(z):inf(1z)z一+r(z)的形式【5l.由上述(57,44,6)BCH码的产生过程可以看出:构造一个(57,44,6)BCH码的关键是要找出该码的生成多项式g(z).当码长及纠错能力给定后可以这样来构造生成多项式:因为(57,44,6)BCH代码是以二元扩域GF(2)N-元域GF(2)的变换为基础的,故首先应找到一个6次的本原多项式P(z):+z十1,产生一个GF(2)扩域;然后在GF(2)上找一个本原元,利用本原多项式P(z)的根计算2个连续幂次根a,a,a=口所对应的GF(2)域上的最小多项式ml(z)=,27+1,m2(z)=.+,27+1,m2(z)z.+z+./7+z

6、十1,这收稿日期:201007一l5作者简介:张高记(1968一),男,陕西礼泉人,西安邮电学院通信与信息工程学院工程师.第5期张高记,等:基于CPLD的BCH码编/译码器的设计与实现?31?里t为BCH代码能纠正差错的个数,(57,44,6)BCH码可纠两个错误,即t=2;最后计算这些最小多项式的最小公倍式LCM(LeastCommonMultiple),得到生成多项式g(.z):g(z)=LCM771(z),2(),2(z)=z134-.;1712+lzll+X10+z9+8+3;6+z3+z+1利用该生成多项式,就可构造(57,44,6)BCH循环码编码器.(57,44,6)BCH循环码

7、编码器的电路结构如图116所示.当开关A和B闭合,C打开时,编码器接收输入信息位,并且直接将其变换成编码输出码元,同时将输入信息位送给递归移位寄存器组用来计算余式r(X);当信息位数据都被处理完之后,开关A和B打开,C闭合,余数依次移位输出,形成编码器输出.图1(57.44.6)BCH码的编码器电路结构图1.2(57,44,6)BCH码编码器的CPLD实现采用模块化的设计思想,BCH编码器电路包括除法电路,控制电路和输出电路等三个模块组成,每一模块对应一部分VHDL的设计文件,这样利于程序的编写和调试,从而降低了整个程序的调试难度,提高了软件的可维护性和可读性【.BCH(57,44,6)编码器

8、电路框图如图2所示.图2【57,44,6)BCH码编码器电路框图(57,44,6)BCH码编码器时序仿真结果如图3所示.下面举例说明该编码器的编码过程,假定输入消息序列为:din=(111011011100101l101O1001l000011101l001010l00),因为(57,44,6)BCH码是系统码,故控制电路在输人数据din的前44拍时发控制信号给输出电路使编码器输出码元clout等于din;44拍结束时,除法电路的内容就是余式,在接下来的13拍,输出电路在控制电路的控制下依次输出余数1100111010011,至此57拍对一个输入数据的编码完成.(57,44,6)B编码器的完整

9、编码输出序列为:dout=11101101110010111010100110000111011001010l001100111010011图3(57.44,6)BCH码编码器时序仿真结果2BCH译码器原理及实现BCH码的译码分为频域译码和时域译码.频域译码是把码字看作一个时域数字序列,对其执行有限域的离散傅立叶变换(DFT)将它变换到频域,然后利用其频域特点译码.而时域译码是把码字看成时间轴上的信号序列,利用码的代数结构进行译码l8j.到目前为止,BCH码在时域和频域内有很多种有效地译码器,Meggitt译码器就是其中之一.Meggitt译码器不仅可以用在时域译码,而且也可以用于频域译码.这

10、里仅介绍Meggitt译码器在时域的译码.2.1Meggitt译码器的原理Meggitt译码器是利用循环码的循环特征设计出来的一类译码算法,它的思路主要有两条:(1)S(-z)和E(z)模g(z)相等并不能断言两式全等,但是如果能使E(z)的次数低于g(z)的次数,zte,那么两者模g()相等等效于两者全等.为此,可利用循环特性把差错多项式E(-z)的次数循环得低于nle次,以达到E(:)与S()的一一对应5l.(2)接收码R(z)的循环对应于差错E(X)的循环,部分高位的差错(E(x)次数大于,z一是),可以通过循环变为低位差错(次数低于一是).这样识别一个重量小于等于t且次数小于一是的可纠

11、正图案,就等效于识别循环前的一类差错5l.根据Meggitt译码器的算法思路,Meggitt译码器的译码过程可分成以下三步进行,如图4【】所示.)计算电路(除法电路)n位移位寄存器图4(57.44.6)Meggitt译码器C()?32?西安邮电学院2010年9月(1)由接收码尺()计算伴随式S(x)(用g(x)除法电路);(2)由伴随式s(z)计算差错图案估值E(z)(用各种译码,差错识别电路);(3)由差错图案估值E(X)求译出码字C(z)(用关系式C(x)=R(z)一E(z)J.2.2(57.44,6)BCH码的Meggitt译码器伴随式的计算Meggitt译码器利用了BCH码的循环性质,

12、使得该译码器对于仅有少数差错需要校验的代码是非常有效的.由于只校验最高位位置的差错,然后计算循环移位,所以实际上所有被破坏的位都要通过MSB位置,并且得到校正J.(57,44,6)BCH码具有校正两个差错的能力,如果仅有MSB位置的差错需要校正,那么由于伴随式和错误图样之间的映射单元必须能识别出所有单个和两个错误,故需存储总数为1+(56/1)=57个不同的错误图样,合理设计电路,采用VHDL硬件设计语言进行描述,通过Quartus软件仿真,可以计算这57个伴随式.表1中简要列出了可能的差错图样及相应地伴随式.表1可能的差错图样及伴随式表错误图样E伴随式S10010110o1001101010

13、10100o00101001111000011111001000101000O00l10001l11001011100001011000001101101111011001100111001O0110001l10010011011111001001l01002.3(57.44,6)BCH码的Meggitt译码器电路组成及仿真实现译码电路通常比编码电路复杂得多.一个好的译码方法不仅应使纠错能力达到理论极限,而且应能高速度,低成本地实现J.选用CPLD器件设计译码器电路即可达到这一要求.根据(57,44,6)BCH码的Meggitt译码器原理,采用自顶向下的模块化设计方法,用VHDL硬件描述语言设

14、计的(57,44,6)BCH码译码器电路框图如图5所示.整个电路包括除法电路,错误图样识别电路,57级缓存电路和输出电路等四个模块.输入数据din57级缓存电路图5(57,44,6)BCH码Meggitt译码器电路框图该Meggitt译码器具有两个级.第一阶段(57拍),通过除法电路计算伴随式S(X);第二阶段(57拍)通过查询差错图样伴随式表,进行实际的差错校正.图6为(57,44,6)BCH码Meggitt译码器的时序仿真结果.图6中的(a)所示,假设译码器输入序列为:din=1110110111001011101010011000011101100101O100l100111010011

15、(图3中编码器输出序列)无差错,译码器输出dout等于din,差错告警输出为全0,表示无差错;图6中的(b)所示,假设译码器输入序列为:din=ll0011O11100lO11l010100l1OOO011101l0010101O011001l10l0011(第3位有1个差错),dout=11101101110010111010100110000111011001010100l1001110100l1(等于图3中编码器的输出序列),差错告警第3位输出一个脉冲,表示有1个差错,输出结果进行了纠错;图6中的(c)所示,假设译码器输入序列为:din=1100110111001011101010011

16、00O01110110010101001100111010001(第3,56位共2个差错),00OOO0l0叭l2345678一第5期张高记,等:基于CPLD的BCH码编/译码器的设计与实现?33?dout=11101101110010111010100110000111011001010l00110011101o011(等于图3中编码器输出序列),差错告警第3,56位各输出一个脉冲,表示有2个差错,输出结果进行了纠错.fa1无差错时的仿真结果舔懒P;.L一一Jn00u0.0t0uLi0-一一一一一一一一一一一一一一一一(b)有一个差错时的仿真结果rc1有二个差错时的仿真结果图6(57.44,

17、6)tH码Meggitt译码器时序仿真结果从仿真结果可以看出,该Meggitt译码器符合设计要求.3结论Meggitt译码器作为一种通用循环码译码器.从原理上说,它可以用于任何循环码或缩短循环码的译码.但实际上,该译码器的复杂度随纠错能力的增加而飞速增长,因此,当t3时,或突发差错超过每码字一次时,一般不用此种译码器.汉明码的t=1,所用差错图样可归人同一类,特别适合用Meggitt译码.设计中采用自顶向下的设计方法,利用VHDL硬件描述语言对BCH编/译码器进行设计,在Quartus11集成开发平台上进行仿真,综合,并下载到EP1C6Q240C8可编程逻辑器件中得以验证.实验证明用该方法进行

18、设计可缩短设计周期,提高系统集成度及性能,使电路设计更具灵活性.本设计还具有一定的通用性,它的逻辑大部分只涉及到编/译码器本身,而与外部的接口十分简单,并且对其它的设计是十分独立的.另外,由于选用器件资源比较丰富,故对其进行功能添加十分方便,只需添加电路设计而不必对原有电路进行修改.参考文献1吴湛击.现代纠错编码与调制理论及应用M.北京:人民邮电出版社,2008.2JunhoCho.EfficientSoftware-BasedEncodingandDecodingofBCHCodesJ.IEEETRANSACTIONSONC0M_PUTERS,2009,58(7):878889.3宁楠.一种

19、基于FPGA的纠错编译码器的设计与实现J.通信技术,2008(8):5661.4卢开澄.编码理论与通信安全M.北京:清华大学出版社,2006.5张宗橙.纠错编码原理和应用M.北京:电子工业出版社,2003.6刘凌.数字信号处理的FPGA实现M.北京:清华大学出版社,2003,7罗朝霞.CDMA系统中反向链路卷积编码器的CPLD实现J.西安邮电学院,2005,10(1):5861.8李雄飞.缩短BCH码(16,8,5)编译码算法及其实现J.空间电子技术,2009,6(2):8489.9王进宏.BCH(15,7,5)纠错译码的MATLAB实现J.华东理工学院,2006,29(1):97102.ImplementationofBCHcoder/decoderbasedonCPLDZHANGGao-ji,LUOZhao-xia2(1.SchoolCommunicationandInformationEngineering,XianUniversityofPostsandTelecommunications,Xian710121,China;2.SchoolofElec