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

1、目录摘要iabstractii引言11绪论21.1差错控制编解码21.2fpga技术简介32bch编译码42.1有限域42.2bch编码原理52.3bch译码原理63bch(57,44,6)编码器的设计与实现93.2vhdl实现及仿真结果104bch(57,44,6)译码器的设计与实现144.1bch(57,44,6)译码器设计144.1.1bch(57,44,6)译码器的原理144.1.2bch(57,44,6)译码器伴随式计算144.1.3bch(57,44,6)译码器电路组成154.2vhdl实现及仿真结果16结论21致谢22参考文献23摘要在现代数字通信中，常常受到信道噪声干扰而造成误

2、码，尤其在无线通信中，空中的突发或者随机干扰噪声会造成接收错误。信道作为通信系统的重要组成部分，其特性对通信系统的性能有很大影响。为了改善数字通信系统的传输质量，在信号进入信道传输之前要进行信道编码。采用差错控制的方法可以改善传输性能。为了提高传输的正确率, 往往采用一些校验方法, 进行检错和纠错。 通信中校验的方法很多, 其中bch编码有其独特的优点: 不仅可以检查和纠正突发性错误, 还能检查和纠正随机差错, 因此在通信系统中得到广泛应用。本论文采用循环码中的bch码进行编解码，设计出基于fpga的bch编码器和译码器。利用vhdl语言进行bch码编译码器的编写，在quartus 仿真平台上

3、对编译码器进行仿真。完成了各模块的调试，验证了编码器、译码器的合理性和准确性。本文对bch码的原理和bch编码器/译码器的实现进行了研究。把将信道编解码bch技术应用到编码和译码的过程中。关键字：bch；fpga；vhdl；编码器；译码器abstractin modern digital communications, often by the noise caused by channel errors, especially in wireless communications, air burst or random noise may cause interference to rec

4、eive errors. channel as an important component of communication systems, the characteristics of the communication system performance greatly. to improve the transmission quality of digital communication system, the signal transmitted into the channel before the channel coding. error control method u

5、sed to improve transmission performance. in order to improve the accuracy of information transfer, often using some calibration methods for error detection and correction. communication parity in many ways, including bch codes has its unique advantages: not only can check and correct the burst error

6、s, but also checking and correcting random errors, so the communication systems are widely used this paper by using cyclic code for decoding the bch code, the design gives appropriate encoder and decoder. use vhdl language bch code woven decoder, quartus tools in written on simulation of woven decod

7、er. completed each module is commissioning, verify the encoder and decoder rationality and accuracy. in this paper the principle of bch code and bch encoder/decoder realization is studied. put will channel decoding bch technology is applied to coding and decoding processkeywords: bch; fpga; vhdl; en

8、coder; decoder22基于fpga的bch码编/译码器的设计与实现引言由于信息在实际信道中传输时，信道特性的不理想、加性噪声和人为干扰等因素的影响，都会使系统接收到的信息不可避免地出现差错。为了提高通信的可靠性，我们可以通过信道编码技术对信道差错进行控制。纠错编码的实现方法是在信息位的尾部加上一些校验码元这些码元与信息码元通过一些线性关系或者其他某种关系相关联。通过校验码元与信息码元关系的变化来判断输出接收码元是否出错。循环码是线性分组码中最主要、最有用的一类，目前对它的研究和应用也最多。它是1957年由prange首先提出并进行研究的。循环码最引人注目的特点是：首先它可以用线性反馈

9、移位寄存器很容易地实现其编码和伴随式计算，其次由于循环码有许多固有的代数结构，从而可以找到各种简单实用的译码方法。由于循环码具有很多优良性质，所以它在理论和实践中很重要。在循环码中bch码是其中的最主要的一大类。bch码是最重要的循环码，能纠正多个随机错误，它具有纠错能力强，构造方便，编码简单，译码也较容易实现等一系列优点而被广泛采用。本人的主要工作如下：熟悉通信系统，重点理解差错控制编码中的bch编码技术。熟悉quartus 软件，通过bch(57,44,6)编码器和译码器的设计来实现对bch编译码器的理解和研究。最终通过硬件描述语言vhdl来实现bch编码器和译码器的软件设计，并在quar

10、tus 上进行运行调试。本论文主要章节介绍如下：绪论，简单介绍了差错控制编码和fpga技术。bch码，对bch码的原理，介绍其编码器与译码器的原理。bch(57,44,6)编码器的设计与实现。bch(57,44,6)译码器的设计与实现。总结。1绪论1.1差错控制编解码数字信号在传输过程中，由于受到干扰的影响，码元波形变坏。接收端收到后可能发生错误判决。从差错控制角度看，按照加性干扰引起的错码分布规律的不同，信道可以分为三类，即随机信道（random channel）、突发信道（burst channel）和混合信道（mixed channel）。在随机信道中，错码的出现是随机的，而且错码之间是

11、统计独立的。例如，由正态分布 白噪声引起的错码就具有这种性质。在突发信道中，错码是成串集中出现的，即在一些短促的时间段内会出现大量错码，而在这些短促的时间段之间存在较长的无错码区间。这种成串出现的错码称为突发错码。产生突发错码的主要原因之一是脉冲干扰，例如电火花产生的干扰。信道中的衰落现象也是产生突发错码的另一个主要原因。我们把既存在随机错码又存在突发错码，且每一种都不能忽略不计的信道称为混合信道。对于不同类型的信道，应该采用不同的差错控制技术。差错控制技术主要有以下四种。（1）检错(error detection)重发(retransmission)：在发送码元序列中加入差错控制码元，接收端

12、用这些码元检测到有错码时，利用反向信道通知发送端，要求发送端重发，直到正确接收为止。（2）前向纠错：前向纠错一般简称fec(forward error correction)。这时接收端用发送端在发送码元序列中加入的差错控制元码，不但能够发现错码，还能将错码恢复其正确取值。 （3）反馈(feedback)校验(checkout)：这时不需要在发送序列中加入差错控制码元。接收端将接收到的码元原封不动地转发回发送端。在发送端将它和原发送码元逐一比较。若发现有不同，就认为接收端接收到的序列中有错码，发送端则立即重发。（4）检错删除(deletion)：它和检错重发的区别在于，在接收端在发现错码后，立

13、即将其删除，不要求重发。1.2fpga技术简介fpga是英文field programmable gate array的缩写，即现场可编程门阵列，它是在pal、gal、epld等可编程器件的基础上进一步发展的产物。它是作为专用集成电路（asic）领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。fpga采用了逻辑单元阵列lca（logic cell array）这样一个新概念，内部包括可配置逻辑模块clb（configurable logic block）、输出输入模块iob（input output block）和内部连线（interconne

14、ct）三个部分。fpga的基本特点主要有：1）采用fpga设计asic电路，用户不需要投片生产，就能得到合用的芯片。 2）fpga可做其它全定制或半定制asic电路的中试样片。3）fpga内部有丰富的触发器和io引脚。4）fpga是asic电路中设计周期最短、开发费用最低、风险最小的器件一。5）fpga采用高速chmos工艺，功耗低，可以与cmos、ttl电平兼容。目前fpga的品种很多，有xilinx的xc系列、ti公司的tpc系列、alter公司的fiex系列等。fpga是由存放在片内ram中的程序来设置其工作状态的，因此，工作室需要对片内的ram进行编程。用户可以根据不同的配置模式，采用

15、不同的编程方式。加电时，fpga芯片将eprom中数据读入片内编程ram中，配置完成后，fpga进入工作状态。掉电后，fpga恢复成白片，内部逻辑关系消失，因此，fpga能够反复使用。fpga的编程无须专用的fpga编程器，只须用通用的eprom、prom编程器即可。当需要修改fpga功能时，只需换一片eprom即可。这样，同一片fpga，不同的编程数据，可以产生不同的电路功能。因此，fpga的使用非常灵活。fpga有多种配置模式：并行主模式为一片fpga加一片eprom的方式；主从模式可以支持一片prom编程多片fpga；串行模式可以采用串行prom编程fpga；外设模式可以将fpga作为微

16、处理器的外设，由微处理器对其编程。2bch编译码2.1有限域(1)群(group)对一个非空元素集合g及定义在g上的一种运算“*”，若满足以下四个条件： 封闭性: a*b=cg 结合律: a*b*c=a*b*c 存在唯一的单位元e ：a*e=e*a=a g中的每个元素存在唯一的逆元：a*a-1=e则称这样的代数系统为群，记为g, *。群中元素的个数称为群的阶。如满足a*b=b*a，群称作交换群。(2)域(field)设f是一组元素的集合，在其上定义了加法“+”和乘法“*两种运算。如果满足下列条件，则集合f与这两种运算一起称为域：在加法下f是一个交换群。f在非零元素的乘法下构成一个交换群。乘法对

17、加法满足分配率：a*b+c=a*b+a*c也就是说，域是一组元素的集合，在这个集合中进行加、减、乘、除后其结果仍在这个集合中。(3)伽罗华域(galois field)含有限元素的域称作有限域(finite field)。域中元素的个数称为域的阶。q个元素的有限域又称为伽罗华域，记gf(q)。可以将gf(q)延伸为一个含有qm个元素的域，这个域称作gf(q)的扩展域，表示为gf(q)，m是非零的正整数。扩展域gf(2m)中的符号用于构造rs码。gf(2m)中的2m个元素可以被看作由a的幂次和0构成的集合a0,a1,a2,a2m-1中的元素。其中agf(2m)，为本原多项式p(x)的根，称为域g

18、f(2m)的本原元，满足a2m-1=1=a。域中任何幂次大于等于m的元素都可以由幂次小于m的元素的线性组合表示。以px=1+x+x3的gf(23)域为例，域中元素的集合为a0,a1,a2,a3,a4,a5,a6,a7=1, a为px的根，即1+a+a3=0，那么有： a3=1+a a4=a*a3=a*1+a=a+a2 a5=a2*a3=a2*1+a=a2+a3=1+a+a2 a6=a*a5=a1+a+a2=1+a2+a3=1+a22.2bch编码原理bch码是由hocquenghem、bose和chaudhuri在1959年各自独立发现的二元线性循环码，人们用用他们三个人名字的字头bch命名b

19、ch码。bch码具有循环结构，是一类能够检测和纠正多个错误的循环码，可看成汉明码的推广。有限域是描述bch码的有效工具，可以从两种角度对本原bch码进行定义。1.从本原bch码生成的角度来定义：令a是有限域 gf(2m)中的本原元，若多项式g(x)是以a1,a2,a3,a2t为根的gf(2)上的最低次多项式，则由它生成的码长为2m-1，纠正t个错误的码称为本原bch码。2.从本原bch码的性能角度来定义对任何正整数m3,t2m-1，若存在循环码，其： 码长： n=2m-1 校验位数目： n-kmt 最小距离： dmin2t+1能纠正码字n=2m-1个码元中的t个或更少个错误的任意组合，称之为能

20、纠正t个错误的二元本原bch码。bch码是循环码的一类，因此，它具有分组码、循环码的一切性质。但它明确界定了码长，校验位数目，码的最小距离之间的关系。可以看出它的性能较好，在同样的编码效率下，纠错能力均较强，故可在无线通信系统中获得广泛应用。根据bch码的定义，若a是gf(2m)中的本原元，又码长为2m-1，能纠正t个错误的二元bch码的生成多项式g(x)是gf(2)上的次数最低的多项式，它以a1,a2,a3,a2t为根，即对于1i2t，有gai=0。根据gf(2m)域的性质，这些根的共轭元也是gx=0的根。令j(x)是aj的最小多项式，则必有gx=lcm1x2x3x, 2t(x) 式中lcm

21、表示最小公倍数。对于偶数的j，可以写成j=i*2s（其中i为奇数，i2t，s1），此时，因为aj=ai2s=(ai)as是ai的共轭元，所以aj和ai有相同的最小多项式jx=ix，从而可知bch码的生成多项式g(x)可写成gx=lcm1x3x5x, 2t-1(x) 因为每个最小多项式的次数为m，所以g(x)次数至多为mt，即码元的校验位数目为n-k，至多等于mt。由于a为本原元(它生成gf(2m)中所有非零元素)，也由于是由a和a的共轭元的最小多项式生成bch码的生成多项式，故称上述方法生成的bch码为本原bch码。2.3bch译码原理我们知道，bch码是一种特殊的循环码，所以，循环码和线性分

22、组码的译码方法对于bch码是完全适用的。但bch码在译码上也有特殊性，因为bch码有它的特殊结构，即生成多项式的根与校验矩阵h有很好的联系。设bch码的码字多项式为:vx=vn-1xn-1+vn-2xn-2+v2x2+v1x1+v0若aigf2m(1i2t)是生成多项式g(x)的根，由于生成多项式g(x)能除尽码字多项式v(x),则ai必然也是v(x)的根，故有：vn-1ai(n-1)+vn-2ai(n-2)+v2xi2+v1xi+v0=0 1i2t (3-1)写成矩阵形式为： 由式(3-1)和校验矩阵h的定义可得到：vht=0 (3-3)其中v=( v0 v1 v2 vn-1)是码字矢量，而

23、ht是校验矩阵h的转置矩阵。若aj是ai的共轭元，则当且仅当v(ai)=0时，也有v(aj)=0。即若v=( v0 v1 v2 vn-1)与校验矩阵h的第i行的内积为零，则它与h的第j行的内积也为零。因此，可以省去矩阵h的第i行的内积为零，则它与h的第j行的内积也为零。因此，可以省去矩阵h的第j行。对于bch码，可省去偶数项，校验矩阵h可写成如下形式：例如，对于(15,7)bch码的生成多项式gx=x8+x7+x6+x4+1 ，其根为a，a2，a3，a4，但只有a，a3是独立的，所以校验矩阵h为在对bch码进行译码时，如果发生t个错误，那么一般要找出这t个错误的位置，同时求出这些错误的值(即错

24、误大小)。在二进制中，不是“1”错成“0”，就是“0”错成 “1”，所以，错误值总是等于1.因此，只要求出错误位置就够了。可以从伴随方程来得到错误位置多项式。如，对于上述(15,7)bch码，若错误除在第i，j位，则伴随式为s=eht其中s有两个分量，即s1=ai+ajs3=a3i+a3j组合上面两式可得s1a2i+s12ai+s13+s3=0s1a2j+s12aj+s13+s3=0所以ai和aj都是 s1x2+s12x+s13+s3=0 (3-4)的根。式(3-4)被称为错误多项式。通过试探法可以解出根ai和aj。3bch(57,44,6)编码器的设计与实现3.1bch(57,44,6)编码

25、器设计bch码的结构完全建立在有限域的基础上，可以通过近世代数的方法来精确描述。bch(57,44,6)是一个系统循环码，可以通过如下步骤实现：用xn-k乘以消息多项式m(x)；用生成多项式g(x)除xn-km(x)得到余式b(x)(校验位多项式)；构成码字多项式 cx=xn-kmx+b(x)。实现bch(57,44,6)编码的关键是要找出改码的生成多项式g(x)。给定了码长和纠错能力可以通过如下方法来构造此码的生成多项式g(x):由于bch(57,44,6)代码是以二元扩域gf(26)到二元域gf2的变换为基础的，故首先找到一个6次本原多项式px=x6+x+1,产生一个gf(26)扩域；然后

26、在gf(26)上找到一个本原元，利用本原多项式p(x)的根 计算2t个连续幂次根a，a2，a2t=a4所对应的gf(2)域上的最小多项式m1x=x+1，m2x=x6+x+1，m2tx=x6+x4+x2+x+1，这里t为bch代码能纠正差错的个数，bch(57,44,6)码可以纠正两个错误，即t=2.从而：gx=lcmm1x,m2x,m2tx =x13+x12+x11+x10+x9+x8+x6+x3+x+1通过上式的生成多项式g(x)，就可以构成bch(57,44,6)编码器。通过g(x)可以获得该bch系统码编码电路图如下图所示：图3-1 bch(57,44,6)编码电路图上图中当门1闭合，门

27、2开时，编码器接收信息的输入，并且直接将信息作为编码信息输出。44次移位后信息位全部送入如上电路，完成出发作用，此时移位寄存器内保留了余式的系数，在二进制情况下就是校验元。此时，门1关，门2开，在经过13次移位后，把移位器中的校验码元全部输出，与原先44位信息元组成了一个长为57位的码字。从而完成bch编码器的输出。3.2vhdl实现及仿真结果下面举例说明（57,44,6）bch编码器的编码过程，假定输入消息序列为：data_in=(11101101110010111010100110000111011001010100),因为（57,44,6）bch码是系统码，故控制电路在输入数据din的前

28、44拍时发控制信号给输出电路使编码器输出码元 data_out 等于din；44拍结束时，除法电路的内容就是余式，在接下来的13拍，输出电路在控制电路的控制下依次输出余数1100111010011，至此57拍对一个输入数据的编码完成。（57，44，6）bch编码器的完整编码输出序列为：data_out=111011011100101110101001100001110110010101001100111010011其vhdl部分代码如下：process(clk)beginif(clkevent and clk=1) then if(count_state=56) then count_stat

29、e=1; register_state=divide; else count_state=count_state+1; if(count_state=44) then register_state register_shift(0) = data_in xor register_shift(12); register_shift(1) = data_in xor register_shift(12) xor register_shift(0); register_shift(2) = register_shift(1); register_shift(3) = data_in xor regi

30、ster_shift(12) xor register_shift(2); register_shift(4) = register_shift(3); register_shift(5) = register_shift(4); register_shift(6) = data_in xor register_shift(12) xor register_shift(5); register_shift(7) = register_shift(6); register_shift(8) = data_in xor register_shift(12) xor register_shift(7

31、); register_shift(9) = data_in xor register_shift(12) xor register_shift(8); register_shift(10)= data_in xor register_shift(12) xor register_shift(9); register_shift(11)= data_in xor register_shift(12) xor register_shift(10); register_shift(12)= data_in xor register_shift(12) xor register_shift(11);

32、 data_out register_shift(1)= register_shift(0); register_shift(2)= register_shift(1); register_shift(3)= register_shift(2); register_shift(4)= register_shift(3); register_shift(5)= register_shift(4); register_shift(6)= register_shift(5); register_shift(7)= register_shift(6); register_shift(8)= regis

33、ter_shift(7); register_shift(9)= register_shift(8); register_shift(10)= register_shift(9); register_shift(11)= register_shift(10); register_shift(12)= register_shift(11); data_out end case;end if;end process;（57,44,6）bch码编码器时序仿真结果如下图3-2所示：图3-2 (57,44,6)bch码编码器时序仿真结果4bch(57,44,6)译码器的设计与实现4.1bch(57,44

34、,6)译码器设计4.1.1bch(57,44,6)译码器的原理假设将编码器发送的码字记为多项式c(x),二元信道中的错误图样记为多项式e(x),把接收到的码元记为多项式y(x)，则有y(x)=c(x)+e(x)。如果信道没有发生错误，则y(x)能被生成多项式g(x)整除。如果g(x)不能被生成多项式g(x)整除，则可认定y(x)存在错误。从而y(x)除以g(x)所得的余式携带了信道中错误图样的信息。我们定义yx=yxmodg(x)为接收到y(x)后大伴随式，由0=cxmodg(x)，所以sx=exmodg(x) 即s(x)只和错误图样有关。bch循环码的译码可以以下3个步骤:将接收码字多项式y

35、(x)除以生成多项式g(x)，得到伴随多项式s(x)；由s(x)确定错误图样e(x)；将y(x)与e(x)进行模2加，纠正错误。基于错误图样识别的译码器称为梅吉特(miggitt)译码器,其原理如下图所示：伴随式计算电路 输入错误图样识别器 1 2 . . . n-kk级缓存器 纠错后的输出图3-3 miggitt译码器的原理4.1.2bch(57,44,6)译码器伴随式计算meggitt译码器利用了bch码的循环性质，使得该译码器对于仅有少数差错需要校验的代码是非常有效的。由于只校验最高位位置的差错，然后计算循环移位，所以实际上所有被破坏的位都要通过msb位置，并且得到校正。（57，44，6

36、）bch码具有校正两个差错的能力，如果仅有msb位置的差错需要校正，那么由于伴随式和错误图样之间的映射单元必须能识别出所有单个和两个错误，故需存储总数为1+(56/1)=57个不同的错误图样，合理设计电路，采用vhdl硬件设计语言进行描述，通过quartus软件仿真可以计算这57个伴随式。表1中简要列出了可能的差错图样及相应地伴随式。表3-1：可能的差错图样及伴随式表no.错误图样e伴随式s1100000000000000000000000000000000000000000000000000000000 11001001101012110000000000000000000000000000

37、000000000000000000000000000010100000101031010000000000000000000000000000000000000000000000000000000111100001111410010000000000000000000000000000000000000000000000000000010010001010005100010000000000000000000000000000000000000000000000000000000110001111061000010000000000000000000000000000000000000000

38、000000000000101110000101710000010000000000000000000000000000000000000000000000000010000011011018100000010000000000000000000000000000000000000000000000000111011001100155100000000000000000000000000000000000000000000000000000100110010011000156100000000000000000000000000000000000000000000000000000010110

39、01001101115710000000000000000000000000000000000000000000000000000000111001001101004.1.3bch(57,44,6)译码器电路组成译码电路通常比编码电路复杂得多。一个好的译码方法不仅应使纠错能力达到理论极限，而且应能高速度、低成本地实现。选用cpld器件设计译码器电路即可达到这一要求。 根据（57,44,6）bch码的meggitt译码器原理，采用自顶向下的模块化设计方法，用vhdl硬件描述语言设计的（57,44,6）bch码译码器电路框图如下图所示。整个电路包括除法电路、错误图样识别电路、57级缓存电路和输出电

40、路四部分。输出电路57级缓存电路错误图样识别电路除法电路输入数据 输出数据图 3-4（57,44,6）bch码译码器电路框图该meggitt译码器具有两个级。第一阶段（57拍），通过除法电路计算伴随式s(x)；第二阶段（57拍）通过查询差错图样伴随式表，进行实际的差错校正。4.2vhdl实现及仿真结果其vhdl部分代码如下：begin d(0)=din xor qq(12) xor memout; d(1)=qq(0) xor qq(12) xor din; d(2)=qq(1); d(3)=qq(2) xor qq(12) xor din; d(4)=qq(3); d(5)=qq(4) xo

41、r din; d(6)=qq(5) xor qq(12) xor din; d(7)=qq(6) xor din; d(8)=qq(7) xor qq(12); d(9)=qq(8) xor qq(12); d(10)=qq(9) xor qq(12) xor din; d(11)=qq(10) xor qq(12); d(12)=qq(11) xor qq(12); u0:dff port map(d(0),clk,clrn,prn,qq(0); u1:dff port map(d(1),clk,clrn,prn,qq(1); u2:dff port map(d(2),clk,clrn,pr

42、n,qq(2); u3:dff port map(d(3),clk,clrn,prn,qq(3); u4:dff port map(d(4),clk,clrn,prn,qq(4); u5:dff port map(d(5),clk,clrn,prn,qq(5); u6:dff port map(d(6),clk,clrn,prn,qq(6); u7:dff port map(d(7),clk,clrn,prn,qq(7); u8:dff port map(d(8),clk,clrn,prn,qq(8); u9:dff port map(d(9),clk,clrn,prn,qq(9); u10:dff port map(d(10),clk,clrn,prn,qq(10); u11:dff port map(d(11),clk,clrn,prn,qq(11); u12:dff port map(d(12),clk,clrn,prn,qq(12); q=qq; dout memout memout=0; end case; end process p1;图3-5中的（a）所示，假设译码器输入序列为：din=111011011100101110101001100001110110010101001100111010011(图3-1中编码器输