基于FPGA的crc编码器的毕业设计文件综述

1、毕业设计（论文）文 献 综 述浙江工业大学之江学院毕业设计（论文） 文献综述 基于FPGA的CRC编码器的建模和设计1 前言人们对于信息的认识和利用，可以追溯到古代的通讯实践。中国古代的“烽隧相望”和古罗马地中海诸城市的“悬灯为号”，可以说是传递信息的原始方式。随着社会生产的发展，科学技术的进步，人们对传递信息的要求急剧增加。到了20世纪20年代，如何提高传递信息的能力和可靠性己成为普遍重视的课题。1948年香农(Shannon)在他的开创性论文“通信的数学理论”中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠错码的基石。目前，利用纠错码降低各类数

2、字通信系统以及计算机存储和运算系统中的误码率，提高通信质量，延长计算机无故障运行时间等，在美国等西方国家中已作为一门标准技术而广泛采用，而且纠错码技术还用于超大规模集成电路设计中，以提高集成电路芯片的成品率，降低芯片的成本。不仅如此，纠错码技术已开始渗透到很多领域。利用纠错码中的许多编译码原理和方法，与通信系统中的其它有关技术相结合，得到令人惊喜的结果。分组码和卷积码是两类较重要的纠错码。分组码是对信源待发的信息序列进行分组(每组K位)编码，它的校验位仅同本组的信息位有关。分组码在数字通信和数据存储系统中已被广泛应用。卷积码不对信息序列进行分组编码，它的校验元不仅与当前的信息元有关，而且同以前

3、有限时间段上的信息元有关。卷积码在编码方法上尚未找到像分组码那样有效的数学工具和系统的理论。但在译码方面，不论在理论上还是实用上都超过了分组码，因而在差错控制和数据压缩系统中得到广泛应用。纠错码之所以有纠错功能，是因为里面含有冗余信息，因此纠错码比检错码要长很多。通常情况下只采用检错码检错，数据的可靠性采用重传的方式来完成。只有在信道质量比较差的情况下，重传次数很多，重传开销非常大，这个时候采用纠错码，信道质量 越差，采用的纠错码汉明间距应该越大，冗余信息也就越多，编码长度相应变长。廖海红在通信系统中的CRC算法的研究和工程实现1中指出在通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使

4、得每个数据码元所占的时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息的可靠性下降。若是要求可靠，则使得传送消息的速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统的关键问题之一。为保证传输过程的正确性，需要对通信过程进行差错控制.差错控制最常用的方法是自动请求重发方式(ARQ)、向前纠错方式(FEC)和混合纠错(HEC)。在传输过程误码率比较低时，用FEC方式比较理想。在传输过程误码率较高时，采用FEC容易出现“乱纠”现象。HEC方式则是ARQ和FEC的结合。在许多数字通信中，广泛采用ARQ方式，此时的差错控制只需要检错功能。实现检错功能的

5、差错控制方法很多，传统的有:奇偶校验、校验和检测等厂这些方法都是增加数据的冗余量，将校验码和数据一起发送到接收端。接收端对接收到的数据进行相同校验，再将得到的校验码和接收到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。循环冗余校验CRC(Cyclic Redundancy Check)码是由分组线性码的分支而来，其简称为循环冗余码，其主要应用是二元码字。编码简单且误判概率很低，在通信系统中得到了广泛的应用。循环冗余校验码的检错能力很强，偶重的循环冗余校验码的检错能力如下：能100%检测出奇数个差错；能100%检测出长度小于等于2的两个突发差错；能100%

6、检测出小于等于生成多项式码重dmin-1 的随机差错；能100%检测出长度小于等于校验位长w的单个突发差错;能以的概率检出长度为的单个突发差错；能以的概率检出长度大于的单个突发差错。2 CRC编码器的建模和设计 2.1 CRC 基本原理一个由若干个“0”或“1”组成n 位二进制数可以表示成为( n -1)阶的多项式的各项系数，也就是说，一个n 位二进制数可以用( n -1)阶多项式表示。一个8位二进制数可以用一个7阶二进制码多项式表示2。CRC码共由两部分构成： k 位有效信息数据和r位CRC校验码。其中r 位CRC校验码是信息数据移位所得序列被一个事先选择的r + 1位“生成多项式”相除后得

7、到，r 位余数即为CRC码的校验码，此处的除法就是“模2”除运算,即不考虑进借位3。李晓珍，苏建峰在循环冗余校验CRC 算法分析及实现4中指出，CRC 校验码的基本思想是利用线性编码理论，在发送端根据要传送的k 位二进制码序列，以一定的规则产生一个校验用的监督码(既CRC码) r 位，并附在信息后边，构成一个新的二进制码序列数共位，最后发送出去。在接收端，则根据信息码和CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。CRC 码是基于模2 除法运算而建立编码规律的校验码。步骤如下：(1) 用除数对被除数最高几位作模2 减，没有借位。(2) 除数右移一位,若余数最高位为1 ，商为1 ，并

8、对余数作模2 减。若余数最高位为0 ，商为0，除数继续右移一位。(3) 一直做到余数的位数小于除数时，该余数就是最终余数。接收方将接收到的二进制序列数(包括信息码和CRC码) 除以多项式，如果余数为0 ，则说明传输中无错误发生，否则说明传输有误。用软件计算CRC 码时，接收方可以将接收到的信息码求CRC 码，比较结果和接收到的CRC 码是否相同。伍方辉，方安安在CRC的FPGA设计与实现5中指出16位的CRC码产生的规则是先将要发送的二进制序列数左移16位后在除以一个多项式,最后所得到的余数就是CRC码。如式1所示,B(X)表示二进制列数,G(X)为多项式,Q(X)为整数,R(X)是余数,也就

9、是CRC码。 (1)以CRC-CCITT为例,数据由低位开始串行输入,逐位移入移位寄存器,并进行相应的模2加法运算(异或运算),如图1所示。当所有的数据移位完成后,留在寄存器中的16位数就是最终的CRC码。 杨宏在基于DSP的CRC算法的实现6中指出循环冗余校验的过程可简单描述为:在发送端,根据要传送的k位二进制码序列,以一定的规则产生一个校验用的r位监督码(CRC码),附在原始信息后边,构成一个新的二进制码序,CRC码的格式如图1所示,共位,然后发送出去;在接收端,根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。这种码的编码和解码设备都不太复杂,且检错的能力较强。在除法运

10、算中,如果用被除数除以除数后所得的余数不为零,那么从被除数中减去余数后,所得结果可被除数除尽,循环冗余校验正是基于这一思想。唐晓辉,杨双,李云在一种基于FPGA 的快速CRC算法及实现7指出循环码的编码方法即是由信息码元和监督码元一起构成循环码,首先把信息序列分为等长的k 位序列段,每一个信息段附加r 位监督码元,构成长度为的循环码。循环码用表示。这样新组成的二进制序列要由原序列经过运算后得到。表征CRC 循环的多项式叫生成多项式,原k 位二进制码加上r 位校验后,信息位要向左移位( 位) ,这相当于乘上。 被生成多项式除,得整式多项式加上余数多项式,即，移项得 令 信息多项式 和余数多项式可

11、以合并成一个新得多项式,称为循环多项式,则该多项式是生成多项式得的整数倍,即能被生成多项式整除。根据这一原理,在发送端用信息码多项式乘上 除以生成多项式所得的余数多项式就是所要加的监督位。在接收端将接收到的循环码多项式除以生成多项式 ,若能整除,则说明接收的是正确的信息,否则说明出现错误。CRC 被广泛使用,并且CRC 多项式有多项标准。如CRC - 12 、CRC - 16 、CRC - CCITT、CRC - 32 等, 其中CRC - 16 和CRC - CCITT 产生16 位的CRC 冗余码,而CRC - 32 则产生的是32 位的CRC 冗余码,多项式G(x) 的正确选择对应不同的

12、通信环境和应用非常关键。2.2 CRC 算法分析2.2.1 直接计算法 直接计算法又可以分为并行计算法和串行计算法,这两种方法里面又可以用3 种设计思想即矩阵法、代入法和流水线法来设计。并行算法对于高速的通信实时性要求非常强;同时对于长帧结构,采用并行算法有利于减少算法时间,但需要严格的数学算法模型。2.2.2 查表法 对于查表法生成CRC 校验码,预先计算好所要的全部有效信息位,存放信息位表中,接着按信息位的顺序计算好所有校验位,并存放于表中,待要使用时查表使用。其原理图如图2.17所示。图2.1CRC 查表法原理图唐晓辉，杨双，李云在一种基于FPGA 的快速CRC 算法及实现7指出，和计算

13、法相反,查表法生成CRC 校验码的优点是运算量小、速度快;缺点是需要大量地存储空间,灵活性不高。但这几种算法需要的逻辑资源较多,且需要多级组合逻辑的反馈及各种数学运算,较为复杂,不易实际应用。本设计拟采用模拟人的思维方式进行串行设计,同时减少串行设计所要的时间。其中,，模2 算法后得的余数,判断余数高位为0 ,则从 依次后补位位数,直到余数高位为1 ,接着再进行模2 算法,循环处理。最后所得余数,如示例中余数为110 共3 位,得新的信息序列1001100110 。本设计就是利用此算法,可以得出512 比特串行CRC- 32 算法的程序建模,比特型算法是逐位进行运算,效率比并行低,若算法是在C

14、PU 处理器中执行,循环一次运算就要若干个指令时钟,则不适用于高速通信的场合。数字通信系统(各种通信标准) 一般是对一帧数据进行CRC 校验,而比特是帧的基本单位。本设计比特串行CRC - 32 算法不在FPGA 嵌入的CPU NIOS 中处理,而是利用FPGA的硬件资源来实现,用硬件构成多项式除法电路,除法电路的主体由一组移位寄存器和模2 加法器(异或单元) 组成,有效地解决了效率的问题,硬件算法并符合于10M 以太网接入系统的设计。CRC - 32 算法公式如下: 图2.27为运算仿真输出的32 位余数。为方便表示仿真信息位取288bit ,随机取值为16 进制数92628CDE8 (后接

15、63 个0) ,余数为16 进制数5818EF44 (即图中二进制值) 。同时经过多次信息位位数变化的仿真,只要更改循环的次数j 就可以,满足要求,移植性强,也符合以太网数据帧中数据位不断变化的要求。一帧的时钟可以根据所用不同速度等级的器件调节为几十个ns 数量级,运算速度快,并且算法经优化,优于其他算法。图2.2CRC 余数仿真波形由上述的信息位和产生的余数构成的新序列进行解码仿真,仿真波形如图2.37所示。图2.3 余数为零 当有错时,余数不为零。假设最后一位为错,则余数为1 ,仿真波形如图2.47所示。 图2.4 余数不为零3 CRC编解码系统的设计及实现 范绿蓉，栗广云，吴淑君在基于V

16、HDL 语言的CRC 信道编解码电路设计与实现8中指出，CRC编译码系统包含发端电路和收端电路两部份。发端有信码发生器模块、编码器模块，收端有模拟错码发生器模块、错码位置计算模块、纠错单元模块。其中错码位置计算单元和纠错单元合在一起构成译码器。，其框图如图3.18所示。图3.1 循环码编解码系统 4、总结 基于FPGA 的CRC 实现方法完全用数字电路实现,具有很高的速度和可靠性,而且可以很方便地与其他功能模块融合,嵌入到应用系统中,实现片上系统设计,优化了电路系统的设计;同时采用模拟人类的思维方式,创建快速、移植性强的串行循环移位异或运算方式来实现CRC 编解码的算法,运算速度快,同时简化了

17、设计的资源,增加了可读性。参考文献1 廖海红。通信系统中的CRC算法的研究和工程实现M 。北京:北京邮电大学,2006.2 冯玉珉，张树京.通信系统原理M.北京:清华大学出版社,2003.3 王忠，李延社，游智胜. CRC 算法设计与程序实现J。电子测量技术,2007,32(12)：26-28.4 李晓珍，苏建峰.循环冗余校验CRC 算法分析及实现J.中国科技信息,2010,(13)，100-101.5 伍方辉,方安安.CRC的FPGA设计与实现M .南京:南昌大学，2008.6 杨宏.基于DSP的CRC算法的实现J .西安邮电学院伍方辉,方安安.CRC的FPGA设计与实现M.南京：南昌大学，

18、2008,(12)：34-38.7 唐晓辉,杨双,李云.一种基于FPGA的快速CRC算法及实现J .桂林航天工业高等专科学校学报,2009（01）：37-39.8 范绿蓉，栗广云，吴淑君.基于VHDL语言的CRC信道编解码电路设计与实现J .湖北华中师范大学,2008：23-26.9 曹志刚.现代通信原理M .北京:清华大学出版社,2006.10 韩进, 程勇, 齐现英.VHDL在数字集成电路设计中的应用J.山东科技大学学报(自然科学版), 2003,(04):34-37.11 沈世锰,陈鲁生.信息论与编码理论M.北京:科学出版社，2003.12 张平安。16 位循环冗余校验码CRC 的原理和性能分析J.山西科技,2005 ,(5):180-190.13 邹久朋,林瑶瑶,周建.CRC 校验编程和硬件快速校验探讨J.单片机与嵌入式系统运用,2009 ,(4)，76-78.14 文谧.CRC校验的软件实现J.广东工业大学华立学院.2008(27):330-331.15 薛瑞.适用于51 单片机的CRC 算法研究J .北华航天工业学院学报,2007, (1) :12 - 14.16 刘科峰,张沙清,田丰.EDA技术在电子设计中的应用J.广西物理,2004,(02):59-89.17 程学敏,叶兵,孙宁.可纠正单个错误的并行CRC解码器