基于FPGA的差错控制编码的设计与实现

《基于FPGA的差错控制编码的设计与实现》由会员分享，可在线阅读，更多相关《基于FPGA的差错控制编码的设计与实现（35页珍藏版）》请在装配图网上搜索。

1、 （ （2007 届）届）毕业设计毕业设计题目：基于 FPGA 的差错控制编码的设计与实现 学院：机电工程学院专业：电子信息工程班级：电信学号：1 姓名：指导教师：教务处制 年月日诚诚 信信 声声 明明我声明，所呈交的论文是本人在老师指导下进行的研究工作及取得的研究成果。据我查证，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得或其他教育机构的学位或证书而使用过的材料。我承诺，论文中的所有内容均真实、可信。 论文作者签名： 签名日期： 年 月 日I授授 权权 声声 明明 学校有权保留送论文交的原件，允许论文被查阅和借阅，学校可以公布论文的全部或部

2、分内容，可以影印、缩印或其他复制手段保存论文，学校必须严格按照授权对论文进行处理，不得超越授权对论文进行任意处置。论文作者签名： 签名日期： 年 月 日II基于 FPGA 的差错控制编码的设计与实现摘 要本文主要介绍了电子设计自动化（EDA）技术的主要特点、现状、前景及意义，并就课题的研究方向做了相关的论述；且进一步论述了 EDA 技术的发展对电路设计应用的影响，探讨了通过 VHDL 语言和可编程门阵列（FPGA）进行电路设计开发的流程，以其作为应用对象，进一步编程开发了(8,4)增余汉明码的编码、译码，循环冗余差错校验编码(CRC)和 MD5 编码。通过对前两种编码各个模块进行设计，完整阐述

3、了对前两种编码软件部分的设计；又通过测试，完善，修改，最终完成了各自独立的编码程序。基于 VHDL 硬件描述语言，利用 FPGA 器件开发的差错控制编码系统，采用了自顶向下的设计方法用 VHDL 语言进行设计，选用当前应用最广泛的 EDA 软件 XILINX ISE 作为开发平台及配套的 MULTISIM 仿真工具，所有程序全部通过了该平台的编译和功能仿真测试，得出了实际的仿真波形，最后，对设计调试过程中出现的问题进行了分析、研究、解决。我还对上述这些各种编码的异同点进行了总结，对 MD5 编码进行了算法分析，既而对这些编码进行研究。关键词：FPGA，VHDL，汉明码，循环冗余码，MD5 码I

4、IIThe Design and Implementation of error control coding based on FPGAAbstractThis paper mainly introduced the main characteristics, current situation and prospects and significance of EDA technology, and puts some elaboration in related to topic research directions; And further discussed the develop

5、ment of EDA technology to the influence of CAD, explored the VHDL language and FPGA for circuit design development process, with its as applied objects, further developed the coding and decoding Hamming code, CRC coding and MD5 coding. Through the first two coding each module design, complete elabor

6、ated on the first two coding software part of the design; And through the test, perfect, modify, eventually completed the independent encoding process. Based on VHDL hardware description language, using the FPGA device development error-controlling codes is proposed, using the top-down design method

7、s with VHDL language design, selection of the most widely used as ISE XILINX EDA software development platform and related MULTISIM simulation tools, all the procedures of the platform are all through the compiler and function simulation test, it is concluded that the actual simulation waveform, fin

8、ally, to design the debugging process problems were analyzed, research, solved. I also turned to these various coding differences and similarities are summarized, the algorithm of MD5 coding for these codes, then analyzed.Keywords: FPGA，VHDL, Hamming code, CRC code, MD5 IV目 录摘 要.IIIAbstract.IV第一章 绪论

9、.11.1 课题的来源 .11.1.1 EDA 技术综述 .11.1.2 差错控制编码技术介绍 .31.2 课题的意义 .51.3 差错控制编码发展现状 .61.4 课题研究的主要内容 .6第二章 基于 FPGA 的实现差错控制编码技术.82.1 差错控制编码的总体设计方案 .82.2（8，4）增余汉明码的差错控制编码译码设计.82.2.1 汉明码编码译码原理 .82.2.2（8，4）增余汉明码的算法与实现.82.2.3（8，4）汉明码编码波形仿真图：.102.2.4（8，4）汉明码译码算法实现.102.2.5（8，4）汉明码编码波形仿真图：.122.2.6（8，4）汉明码编码译码综合模块.1

10、22.2.7（8，4）汉明码编码译码综合波形仿真图.132.3 循环冗余差错控制校验码的设计.132.3.1 CRC 循环校验码编码校验原理 .132.3.2 CRC 循环码编码规则 .142.3.3 CRC 循环码算法分析 .142.3.4 CRC 校验生成模块的设计实现.152.3.5 CRC 校验生成模块仿真波形图 .172.3.6 CRC 校验接收模块的设计实现.182.3.7 CRC 校验接收模块仿真波形图 .192.4 MD5 码的算法分析 .192.5.1 MD5 的引言 .192.5.2 MD5 的原理 .202.5.3 MD5 算法的安全性考虑 .212.5.4 MD5 的应

11、用 .22第三章 基于 FPGA 的实现差错控制编码技术开发体会.23V3.1 算法的重要.233.2 硬件对软件的制约影响.233.3 调试的重要性.23第四章 结束语.24致谢.26附录.27嘉兴学院本科生毕业设计0第一章 绪论1.1 课题的来源1.1.1 EDA 技术综述由于大规模集成电路开发技术的应用和发展以及电子产品市场运作的进一步加快，涉及诸如通信、智能仪表、医药设备、军事、民用电器等领域的现代电子科学技术与应用已进入了一个崭新的阶段，电子设计自动化已成为当今电子设计领域的主流。电子设计自动化技术是在电子计算机辅助设计技术基础上发展起来的计算机软件系统，是指以计算机为工作平台，整合

12、了应用电子技术、计算机技术、信息处理等最新成果，进行电子产品的自动设计。利用电子设计自动化工具，电子设计师可以将大量工作通过计算机完成，并可以将电子产品从电路设计、性能分析到设计出 IC 版图或 PCB 版图的整个过程的计算机上自动处理完成。上世纪的最后 10 年以来，微电子技术以惊人的速度发展，其工艺水平达到了深亚微米级，在一个芯片上可集成数百万乃至上千万只晶体管，工作速度已经可达到 GHz的时钟频率，这为制造出更大规模的，更快速度和更大信息容量的芯片系统提供了有利条件，于此同时也对 EDA 系统提出了更高的要求。此阶段主要出现了以高级硬件语言描述、计算机系统仿真和综合技术为特征的第三代 E

13、DA 技术，不仅大大地提高了系统的设计效率，而且使设计人员摆脱了大量基础性验证测试工作，将精力主要集中在创造性的方案与概念的构思上，下面简单介绍这个阶段 EDA 技术的主要特征：（1） 高层综合的理论与方法取得较大进展，将 EDA 设计层次提高到行为级，并划分为逻辑综合和测试综合。（2） 采用硬件描述语言 HDL 来描述 10 万门以上的设计，并形成了 VHDL 和Verilog HDL 两种 IEEE 标准硬件描述语言。它们均支持不同层次的描述，使得复杂 IC的描述规范化，便于重复使用。它们多应用于 FPGA 及其他可编程逻辑器件的设计中。（3）可测性综合设计。随着 ASIC 的规模与复杂性

14、的增加，测试难度与费用急剧基于 FPGA 的差错控制编码的设计与实现1增加，因此产生了将可测性电路结构制造在 ASIC 芯片上的想法，于是开发了扫描插入、内建自测试、边界扫描等可测性设计（DFT）工具，并已集成到 EDA 系统中。（4）建立并行设计工程 CE 框架结构的 IDE，以适应当今 ASIC 器件的一些特点。随着百万门规模的复杂的可编程逻辑器件的推出及应用，EDA 技术在仿真、时序分析、集成电路自动测试、高速印刷电路板设计及操作平台的扩展等方面都面临着新的问题，这些问题实际上也是新一代 EDA 技术的未来发展趋势。用 VHDL 语言开发 FPGA 的设计流程如图 1-1 所示：确定功能

15、要求进行设计源代码模拟综合优化和布局布线布局布线后的设计模拟符合要求？符合要求？是是否否接受设计任务器件变成配置图 1-1 可编程逻辑器件开发设计流程图接受任务：进行系统设计之前，先要由总体设计部门给出设计的任务和设计的一些要求。嘉兴学院本科生毕业设计2确定功能：对给出的设计任务和设计的一些要求进行分析，确定出具体的功能及要求。进行分析：决定设计中所要采用的设计方法。源代码模拟：在设计中，采用 VHDL 硬件描述语言模拟器进行源代码模拟可以在早期开发中发现设计上的缺陷和错误，并及时进行改正，既而节省大量的设计时间，缩短开发周期。综合、优化和布局布线：综合是将较高层次的抽象描述转化到较低级描述的

16、一种方法，即将设计的 VHDL 源描述转化成底层电路表示。优化是指将设计的时延缩小到最小和有效利用资源。布局布线就是把通过综合和优化所得到的逻辑，安放到一个逻辑器件中的过程，一个较好的布局布线过程就是将电路的相关部分放置在一起，以消除布线延迟。布局布线后的设计模拟：布局布线后的设计模拟与源代码模拟不同，源代码模拟只是对设计的逻辑功能进行模拟，而布局布线后的设计模拟不仅可以对逻辑功能进行验证，而且还能对设计时序功能进行验证。器件编程和配置：器件编程就是将 VHDL 设计描述经过模拟、综合、优化和布局布线的结果，经过一定映射转化成一个器件编程所用的数据文件格式。器件配置就是在功能仿真和时序仿真正确

17、的前提下，将综合后的文件下载到具体的芯片中进行电路验证。1.1.2 差错控制编码技术介绍差错控制在数据通信过程中能发现或纠正差错，把差错限制在尽可能小的允许范围内的技术和方法。在数字通信中常利用编码方法对传输中产生的差错进行控制，以提高数字消息传输的准确性。差错控制系统的组成及其作用原理如图。信源信道编码器信道信道译码器信宿重传控制反向信道重传控制基于 FPGA 的差错控制编码的设计与实现3图1-2 差错控制系统原理图图中虚线内的部分就是数字通信中的差错控制系统10。当没有差错控制时，信源输出的数字序列将直接送住信道。由于信道中存在干扰，信道的输出将发生差错。数字在传输中发生差错的概率是传输准

18、确性的一个主要指标。在数字通信中信道给定以后，如果误码率不能满足要求,就要采取差错控制。按具体实现方法的不同,差错控制可以分为前向纠错法、反馈重传法和混合法三种类型10。（1）前向纠错法差错控制系统只包含信道编码器和译码器。从信源输出的数字序列在信道编码器中被编码,然后送往信道。由于信道编码器使用的是纠错码，译码器可以纠正传输中带来的大部分差错而使信宿得到比较正确的序列。（2）反馈重传法只利用检错码以发现传输中带来的差错，同时在发现差错以后通过反向信道通知发信端重新传输相应的一组数字，以此来提高传输的准确性。根据重传控制方法的不同，反馈重传法还可以分成若干种实现方式。其中最简单的一种称为等待重

19、传方式。采用这种方式时发信端每送出一组数字就停下来等待收信端的回答。这时信道译码器如未发现差错便通过收信端重传控制器和反向信道向发信端发出表示正确的回答。发信端收到后通过发信端重传控制器控制信源传输下一组数字，否则信源会重新传输原先那组数字。 上述两种方法的主要差别是：前向纠错不需要反向信道，而反馈重传必须有反向信道。前向纠错利用纠错码，而反馈重传利用检错码。一般来讲，纠错码的实现比较复杂，可纠正的差错少，而检错码的实现比较容易，可发现的差错也多。前向纠错带来的消息延迟是固定的，传输消息的速率也是固定的，而反馈重传中的消息延迟和消息的传输速率都会随重传频度的变化而变化。前向纠错不要求对信源控制

20、，而反馈重传要求信源可控。经前向纠错的被传消息的准确性仍然会随着信道干扰的变化而发生很大变化，而经反馈重传的被传消息的准确性比较稳定，一般不随干扰的变化而变化。因此，两者的适用场合很不相同。（3）混合法 在信道干扰较大时，单用反馈重传会因不断重传而使消息的传输速率下降过多，而仅嘉兴学院本科生毕业设计4用前向纠错又不能保证足够的准确性，这时两者兼用比较有利，这就是混合法。此法所用的信道编码是一种既能纠正部分差错又能发现大部分差错的码。信道译码器首先纠正那些可以纠正的差错，只对那些不能纠正但能发现的差错才要求重传，这会大大降低重传的次数。同时，由于码的检错能力很强，最后得到的数字消息的准确性是比较

21、高的10-11。差错控制编码又可分为检错码和纠错码11。检错码只能检查出传输中出现的差错，发送方只有重传数据才能纠正差错；而纠错码不仅能检查出差错而且能自动纠正差错，避免了重传。 1.2 课题的意义如今各种数字通信系统已广泛用于我们的生产生活中。然而数字信号在传输过程中，由于受到干扰的影响，码元波形将变坏。接收端收到后可能发生错误判决。由乘性干扰引起的码间串扰，可以采用均衡的办法纠正。而加性干扰的影响则需要用其它办法解决。在设计数字通信系统时，应该首先从合理选择调制制度、解调方法以及发送功率等方面考虑，使加性干扰不足以影响达到误码率的要求。在仍不能满足要求时，就要考虑差错控制措施了，这就是我们

22、研究差错控制技术的意义所在。现代电子产品面临高功能、设计周期短、上市快的要求，其复杂度日益加深，一个电子系统可能由数万个中小规模的集成电路构成，这就带来了体积大、功耗大、可靠性差的问题，解决这一问题的有效方法就是来用可编程逻辑器件（PLD）进行设计。可编程逻辑器件，尤其是 FPGA 器件，即现场可编程门阵列，它是在 PAL、GAL、CPLD等可编程器件的基础上进一步发展的产物。它是作为专用集成电路领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点，具有集成度高、运行速度快、可靠性强、设计方式灵活、快速等特点，现已成为现代高层次电子设计方法的实现载体

23、。本课题研究了 EDA 技术发展对电路设计方法的影响，深入探讨了用 VHDL 语言和可编程逻辑器件 FPGA 开发的基本方法，为开发专用集成电路提供了基本的设计步骤。作为应用对象，进一步开发差错控制编码技术。开发这一系统的目的并不是为了实际的应用或应用到市场中去，只是通过一个简基于 FPGA 的差错控制编码的设计与实现5单系统的整体设计完成过程，深入体会 FPGA 技术优势性，了解这些编码的特性及其应用，使这几类编码得到更广泛的应用。在数字系统过程中，为了减少误码率，使这些编码技术很好的应用到相关的一些领域中去，我总结出这些编码的异同点，为以后选择这些编码时在相关领域的应用奠定一定的基础。1.

24、3 差错控制编码发展现状1948年 C.E.香农（Shannon）1发表论文指出，只要采用适当的纠错码，就可在多类信道上传输消息。宣告了纠错码的诞生。自 Shannon 之后，人们不断向逼近信道容量努力，取得重大发展，如分组码，代数码，卷积码，网格码和 Turbo 码。所能达到的性能也越来越接近 Shannon 限间的距离。现在利用 FPGA 技术实现差错控制编码的种类很多，而且这些具有很强的纠错、检错码，被广泛应用到密码学、通信、磁盘阵列及光存储、卫星通信、移动通信、深空通信等众多领域。1.4 课题研究的主要内容汉明码是一种能纠一位错的线性分组码, 由于它的编译码简单,在数据通信和计算机存储

25、系统中广泛应用,如在蓝牙技术和硬盘阵列中。它的最小码距为,可以纠正一位错误,但对于两位错不能检测,还可能会造成误纠。尽管发生一位错的概率相对最高, 但在一些要求较高的应用中汉明码不能满足要求。常用的能检测两位错同时能纠正一位错的纠错码有(8,4)扩展汉明码。CRC 即循环冗余校验码（Cyclic Redundancy Check）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。CRC 常用硬件电路和软件编程的方法实现,采用 CRC 串行算法,即一个时钟周期内有一位数据输入, k 位长度的信息元连续计算 k 次后得出校验码. 这种传统 CRC 的产生和校验

26、方法对于现代实时高速的通信系统已经不能满足其对于信息处理高速化、并行化的要求。 因此,本文提出一种新的并行 CRC 编码方法:用 VHDL 语言在 FPGA 芯片上编程,实现在一个时钟周期内完成一次并行 CRC 码的计算及校验. 该方法可以对不同长度的数据进行差错控制,而且大大缩短了 CRC 码的校验周期,为实现循环冗余校验提供了一种新思路.MD5 的全称是 Message-Digest Algorithm 5，在 90 年代初由 MIT 的计算机科学实嘉兴学院本科生毕业设计6验室和 RSA Data Security Inc 发明，经 MD2、MD3 和 MD4 发展而来。Message-D

27、igest泛指字节串(Message)的 Hash 变换，就是把一个任意长度的字节串变换成一定长的大整数。MD5 还广泛用于加密和解密技术上，在很多操作系统中，用户的密码是以 MD5 值（或类似的其它算法）的方式保存的。对于差错控制编码技术的研究，我主要是研究(8,4)增余汉明码编译码、CRC 循环编码和 MD5 编码，现在首先是分别研究这几种编码，对前两种分别应用 FPGA 技术去实现，用 VHDL 语言去编写代码，然后再进行编译，下载，仿真及其去了解这些编码；然后是对 MD5 码进行研究和算法分析；最后总结出它们的异同点，以适应在以后需要的时候选择适当的编码应用到相应的领域中去。基于 FP

28、GA 的差错控制编码的设计与实现7第二章 基于 FPGA 的实现差错控制编码技术2.1 差错控制编码的总体设计方案在具体设计过程中，采取自上而下的设计思路。首先根据整体的规划设计出模块的外部输入输出引脚定义以及功能，也就是设计出这一个小芯片的外部特性；然后根据设计的这一个芯片的外部特性以及功能设计实现芯片内部的实现细节。2.2（8，4）增余汉明码的差错控制编码译码设计 2.2.1 汉明码编码译码原理汉明码(Hamming Code)是由 Richard Hamming 于 1950 年提出的,它属于线性分组编码方式,用以纠正单个错误的线性分组码,在软件无线电中应用广泛。设原代码的码长为 k 比

29、特, 附加纠错编码部分为 r 比特,当码字长度 n=2r-1,r=n-k，r=1，2时就称这种线性分组码为汉明码。其基本原理是,将信息码元与监督码元通过线性方程式联系起来,每一个监督位被编在传输码字的特定比特位置上。系统对于错误的数位无论是原有信息位中的,还是附加监督位中的都能把它分离出来。由汉明码的性质可知,(8,4) 增余汉明码能纠 1 位错,检 2 位错。 2.2.2 （8，4）增余汉明码的算法与实现(8,4)增余汉明码全码码元数 n=8,其中信息码元数 k=4 ,监督码元数 d=4,其监督矩阵为:01111000101101001101001011111111H对于任何给定的信息码组,

30、都可以由下式求出相应的监督码元,即:嘉兴学院本科生毕业设计812345678011110001011010001101001011111111XXXXXXXX若用方程式来表示, 则上式可以写成: 从而形成5234613471248123;,XXXXXXXXXXXXXXXX全码这就是(8,4)增余汉明码的编码过程。12345678X X X X X X X X（8,4）汉明码编码的顶层设计模块如图所示：图2-1 汉明码编码模块图可以看出，输入为四位并行输入，编码后为一个八位的并行输出。（8,4）汉明码编码的底层设计模块如图所示：基于 FPGA 的差错控制编码的设计与实现9图2-2 汉明码编码模块

31、底层关系图底部的各个分模块为两位的输入模通过各种逻辑运算，并最终组合在一起形成一个 8 位的最终编码输出。2.2.3 （8，4）汉明码编码波形仿真图：图 2-3 汉明码编码仿真图2.2.4 （8，4）汉明码译码算法实现n,k,d分组码的译码步骤可归结为以下三步:1) 由接收到的 R,计算伴随式 S=RHT；2) 若 S=0,则认为接收无误。若 S0,则由找出错误图样 E；3) 由 E和 R 找出 C=R-E。汉明码的译码较简单,它可由 S 直接得到错误图样 E ,其他分组码如何由 S 求得E就比较复杂。而一个译码器的复杂性及其译码错误概率也是由这一步决定的。设接收方收到发送方传来的一个完整的全

32、码为:X11,X22,X33,X44,X55,X66,X77,X88,根据汉明码校验矩阵: 11111222223488880111100010110100.11010010.11111111SXXSXXSHSSXXS1 S2 S3 S4为(8 ,4) 增余汉明码的校验子。当 S1 S2 S3 S4 =0000 时,传送无误;当S1 S2 S3 S4为偶数时,可判接收到的全码中有两位错误,但不能判断哪两位错,可要求发送方重新发送全码;当 S1 S2 S3 S4为奇数时,可根据表 1 判断哪一位错,然后通过软件来嘉兴学院本科生毕业设计10纠错,完成译码过程。表2-1 （8，4）汉明码校验参数错位

33、S1S2S3S4错位S1S2S3S41011151001210116010131101700114111180001译码算法的流程图如图所示：S1S2S3S4=0S1S2S3S4=奇数有一位错，纠错没错，输出信息位两位错，重发NOYES初始化 S1 S2 S3 S4输出信息位图2-4 汉明码译码流程图根据上述流程图，用 VHDL 语言描述（8，4）汉明译码算法功能模块如图所示：图2-5 汉明码译码顶层模块图基于 FPGA 的差错控制编码的设计与实现11Hamin 为汉明 8 位数据输入，dataout 为汉明 4 位数据输出，sec、ded、ne 为诊断输出。2.2.5（8，4）汉明码编码波形

34、仿真图：图2-6 汉明码译码仿真图可以看出，通过译码模块，8 位全码又重新译码成原输入数据。2.2.6 （8，4）汉明码编码译码综合模块通过原件例化，对编码、译码电路进行连接得到综合顶层模块如下：图2-7 汉明码编码译码综合顶层模块图对顶层模块进行细化，如图所示：嘉兴学院本科生毕业设计12图2-8 汉明码编码译码综合底层模块图2.2.7 （8，4）汉明码编码译码综合波形仿真图图2-9 汉明码综合模块仿真图2.3 循环冗余差错控制校验码的设计2.3.1 CRC 循环校验码编码校验原理CRC 校验采用多项式编码方法。被处理的数据块可以看作是一个 n 阶的二进制多项式，如一个 8 位二进制数 101

35、10101 可以表示为：x7+x5+x4+x2+1。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以 2 为模，加减时不进位、错位和逻辑异或运算一致。采用 CRC 校验时，发送方和接收方用同一个生成多项式g(x),并且 g（x）的首位和最后一位的系数必须为 1。CRC 的处理方法是：发送方以g（x）去除 t（x） ，得到余数作为 CRC 校验码。校验时，以计算的校正结果是否为 0为据，判断数据帧是否出错。CRC 校验可以 100地检测出所有奇数个随机错误和长度小于等于 k（k 为 g（x）的阶数）的突发错误。所以 CRC 的生成多项式的阶数越高，那么误判的概率就越小。基于

36、 FPGA 的差错控制编码的设计与实现132.3.2 CRC 循环码编码规则CRC 编码实际上是将代发送的 m 位二进制多项式 t（x）转换成了可以被 g（x）除尽的 m+r 位二进制多项式 t(x)，所以解码时可以用接受到的数据去除 g（x） ，如果余数位零，则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多 CRC 的硬件解码电路就是按这种方式进行检错的。同时 t(x) 可以看做是由t（x）和 CRC 校验码的组合，所以解码时将接收到的二进制数据去掉尾部的 r 位数据，得到的就是原始数据。2.3.3 CRC 循环码算法分析CRC 校验码的编码方法是用待发送的二进制数据

37、 t（x）除以生成多项式 g（x） ，将最后的余数作为 CRC 校验码。其实现步骤如下：（1）设待发送的数据块是 m 位的二进制多项式 t（x） ，生成多项式为 r 阶的g（x） 。在数据块的末尾添加 r 个 0，数据块的长度增加到 m+r 位，对应的二进制多项式为 t(x)。（2） 用生成多项式 g（x）去除 t(x) ，求得余数为阶数为 r-1 的二进制多项式y（x） 。此二进制多项式 y（x）就是 t（x）经过生成多项式 g（x）编码的 CRC 校验码。（3） 用 t(x) 以模 2 的方式减去 y（x） ，得到二进制多项式 t(x) 。t(x) 就是包含了 CRC 校验码的待发送字符串

38、。由于 CRC-32、CRC-16、CCITT 和 CRC-4 的编码过程基本一致，只有位数和生成多项式不一样。为了叙述简单，用一个 CRC-4 编码的例子来说明 CRC 的编码过程。设待发送的数据 t（x）为 12 位的二进制数据 100100011100；CRC-4 的生成多项式为 g（x）=x4+x+1，阶数 r 为 4，即 10011。首先在 t（x）的末尾添加 4 个 0 构成x4t(x)，数据块就成了 1001000111000000。然后用 g（x）去除 x4t(x)，不用管商是多少，只需要求得余数 y（x） 。表 1 给出了除法过程。表 2-1 求校验码的过程表嘉兴学院本科生毕

39、业设计14 除数次数 被除数/ g（x）/结果 余数1 0010001110000001 001100 0001001110000001001110000001 001110000001 001110 0000100000010000001 0000001 001120 0011001100从表 2-1 中可以看出，CRC 编码实际上是一个循环移位的模 2 运算。对 CRC-4，我们假设有一个 5 bits 的寄存器，通过反复的移位和进行 CRC 的除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。2.3.4CRC 校验生成模块的设计实现CRC 校验生成模块是在 XILINX IS

40、E 平台编程实现，程序首先执行了 11 次异或运算，流程图如 2-10 所示，然后在作一次异或运算，得到的记过就是 crc 校验码基于 FPGA 的差错控制编码的设计与实现15结束Crcvar30复制到变量C 中Rdatacrc 高 5 位复制到变量 crcvari=11Rcrcvar（4）=？Crcvar30与 G(x)系数的低 4位异或结果放在变量 C 中Crcvar40=c&rdatacrci-1i=i-1i=0?YESNOYESNO12 位信息左移 4 位后放到 rdatacrc图 2-10 CRC 校验生成模块流程图CRC 校验生成模块如图 X 所示. 其中 sdata 是 12 位

41、待发送信息,datald 是sdata 的装载信号,clk 是时钟信号,datacrco 是附加上 4 位 CRC 校验码的 16 位 CRC 码,hsend 是与检错模块的握手信号。嘉兴学院本科生毕业设计16图2-11 CRC校验生成模块2.3.5 CRC 校验生成模块仿真波形图图2-12 CRC校验生成模块仿真波形图基于 FPGA 的差错控制编码的设计与实现172.3.6 CRC 校验接收模块的设计实现CRC 校验检错模块编程思想与生成模块类似. 从接收到的 CRC 码中提取出信息码,将信息码与生成多项式进行异或运算,最后判断得到的余数与 CRC 生成模块中得到的校验码是否相同,如果相同则

42、认为信息发送正确,将输出的误码警告信号 error 设置为“0”;反之,则以为信息发送错误,将 error 设置为“1” 。CRC 校验检错模块如图 X 所示,其端口数据说明如下:rdata :接收模块(检错模块) 接收的 12 位有效信息数据；datafini :数据接收校验完成；clk :时钟信号；datacrci :附加上 5 位 CRC 校验码的 17 位 CRC 码；error :误码警告信号；hrecv :与生成模块的握手信号。图 2-13 CRC 校验接收模块的设计实现嘉兴学院本科生毕业设计182.3.7 CRC 校验接收模块仿真波形图图 2-14 CRC 校验接收模块仿真波形图

43、2.4 MD5 码的算法分析MD5 的全称是 Message-Digest Algorithm 5，就是把一个任意长度的字节串变换成一定长的大整数。即 MD5 将任意长度的“字节串”变换成一个 128bit 的大整数，并且它是一个不可逆的字符串变换算法，换句话说就是，即使你看到源程序和算法描述，也无法将一个 MD5 的值变换回原始的字符串，从数学原理上说，是因为原始的字符串有无穷多个，这有点象不存在反函数的数学函数。2.5.1 MD5 的引言 MD5 算法是通过数学运算,把不同长度的信息串转化到 128 位编码中,形成 Hash 值,通基于 FPGA 的差错控制编码的设计与实现19过比较这个数

44、值是否正确,来确定通信双方的合法性。这也可以说是数字签名,在数据传输后,可以通过比较 Hash 值来判断信息途中是否被截获修改,是否由合法的发送人发送或者合法的接收人接收等。用这种方法,可以防止密钥丢失的问题,因为它的加密部分是随机生成的,如果没有正确的 Hash 值根本就无法解开加密部分,而且它还具备了数字签名的能力,可以证明发送方和接收方的合法身份,具有不可抵赖性,很适用于商业信息的传递。MD5 的典型应用是对一段信息(Message)产生信息摘要(Message-Digest) ,以防止被篡改。它还被广泛用于加密和解密技术上。MD5(RFC1321)是于 90 年代由 Ron Rives

45、t 在 MIT 提出来的。我们现在来了解一下 MD5 的原理。2.5.2 MD5 的原理该算法输入任意长度的消息,输出 128 位消息摘要,处理以 512 位输入数据块为单位。处理报文摘要的过程如下:步骤 1:添加填充位(最高位为 1 和其余为 0)。在消息的最后添加适当的填充位使得数据位的长度满足与 448 模 512 同余,即:length=448mod512。步骤 2:添加长度。原始消息长度(二进制位的个数),用 64 位表示,并附加在步骤 1的结果后。由这两个步骤得到长度为 512 整数倍的报文。表示为 L 个 512 位的数据块:Y0,Y1 ,YL-1.其长度为 L512bits.令

46、 N=L16,则长度为 N 个 32 位的字。令M0N-1表示以字为单位的消息表示。步骤 3:初始化 MD 缓冲区。一个 128 位 MD 缓冲区用以保存中间和最终散列函数的结果.它可以表示为 4 个 32 位的寄存器(A,B,C,D)。寄存器初始化为以下的 16 进制值。A=67452301B=EFCDAB89C=98BADCFED=10325476寄存器内容Word A : 01 23 45 67Word B: 89 ABCD EF嘉兴学院本科生毕业设计20Word C: FE DC BA 98Word D: 76 54 32 10采用小数在前的格式存储,即将字的低字节放在低地址字节上步骤

47、 4:处理消息块(512 位=16 个 32 位字)。一个压缩函数是本算法的核心(HMD5),它包括 4 轮处理.轮处理具有相似的结构,但每次使用不同的基本逻辑函数,记为F,G,H,I.每一轮以当前的 512 位数据块(Yq)和 128 位缓冲值 ABCD 作为输入,并修改缓冲值的内容。每次使用 64 元素表 T164四分之一。该 T 表 sin 函数构造而成。T 的第 i 个元素表示为 Ti,其值等于 232abs(sin(i)的整数部分,其中 i 是弧度.于abs(sin(i)是一个 0 到 1 之间的数,T 的每一个元素是一个可以表示成 32 位的整数。T 表提供了随机化的 32 位模板

48、,消除了在输入数据中的任何规律性的特征T 表T 1 = D76AA478 T 49 = F4292244T 2 = E8C7B756 T 50 = 432AFF97T 3 = 242070DB T 51 = AB9423A7T 4 = C1BDCEEE T 52 = FC93A039. . . . . .T 16 = 49b40821 T 64 = EB86D391步骤 5:输出结果。所有 L 个 512 位数据块处理完毕后,最后的结果就是 128 位消息摘要。2.5.3 MD5 算法的安全性考虑 对强行攻击的安全性:使用强行技术,产生任何一个报文使其摘要等于给定保文摘要的难度对 MD5 是

49、2128 数量级的操作,产生相同报文摘要的两个报文的难度是 264 数量级对密码分析的安全性:对单循环的 MD5,使用不同的密码分析可能在合理的时间内找出能够产生相同摘要的两个报文,这个结果被证明对四个循环中的任意一循环也成立。目前,MD5 已被认为是易受攻击的。事实上,MD5 算法已有被德国解密专家攻破的纪录,据称,一个价值几百万美元的计算机系统可以在几周内寻找出已被暗码处理的原文。在基于 FPGA 的差错控制编码的设计与实现21对安全要求很高的场合使用仍存在风险。2.5.4 MD5 的应用MD5 码主要是应用在加密和解密两个方面，使用的是非常的广泛，应用的领域也是非常的多。在我们的解压缩文

50、件中，有很多就是应用到了 MD5 码，因为它的保密工作具有一次性保密工作，不仅保留了一次性口令的优点,而且克服了序列密码一次性口令系统中的小数攻击和 IP 地址欺骗攻击的漏洞,同时又避免了 RSA 算法中大整数质因数分解的计算效率问题。嘉兴学院本科生毕业设计22第三章 基于 FPGA 的实现差错控制编码技术开发体会3.1 算法的重要在刚开始设计这个毕设的时候，我可以说的这个课题不甚了解，有点无从下手的感觉，通过上网查询和杨老师的教导，我的课题是一个研究性的课题，所以我就要搜集好几种编码来分别进行研究，来找出它们的异同点，首先找到的是汉明码和 CRC 码，这两种广泛应用于数字通讯中的编码，但是我

51、要用 FPGA 去实现，这种用硬件实现起来传输速度会很快，可是在这之中算法就是一个很难的问题，我只有理解了算法才能用VHDL 的语言来做出来，包括我后来做的 MD5 编码，算法也是相当的重要的，而且我觉得很难，这些花费我很多的时间。 算法可以说是一种编码的灵魂，没有算法我是不可能实现我的研究课题的，这些涉及到很多别的问题，不是很容易明白，我就要不断地去分析和查找书籍，找出这些原理的所在，为下面的工作做准备。3.2 硬件对软件的制约影响在毕业设计的过程中，尤其到了硬件调试的时候，还有一点感受比较深刻，那就是硬件对软件设计的影响。由于试验台硬件和小组设计试验板硬件性能不完全相同，致使软件系统从试验

52、台到试验板的过程中遇到了很多意想不到的问题，最终还是通过修改软件来适应硬件的标准。3.3 调试的重要性程序写出来之后，需要进行大量的硬件调试工作，否则的话，一旦出现问题，就搞不清楚问题究竟是软件设计的错误还是硬件电路板的错误，所以首先解决硬件调试是必须的。在调试的过程中，需要有清晰的逻辑思维作基础，对硬件知识有熟练的掌握和灵活的应用。基于 FPGA 的差错控制编码的设计与实现23第四章 结束语本课题的研究设计至此基本完成。本文研究了 EDA 技术的发展对电路设计方法的影响，深入讨论了用 VHDL 语言和复杂系统可编程逻辑器件开发的基本方法，作为应用对象，进一步研制、开发了多功能电子钟系统。基于

53、 VHDL 语言、应用 FPGA 开发的差错控制编码技术，系统采用了“自顶向下”的设计方法，系统的顶层设计和底层设计采用原理图输入描述和 VHDL 语言进行描述，选用了当前最先进的 EDA 软件平台 XINLIX ISE 作为开发平台，所有程序全部通过了该平台的编译和功能仿真实验，在配有SPATANIII 芯片的实验台上通过了硬件测试。最后，把程序下载到一个独立的硬件系统，经过不断的调试和改进，终于完成了独立系统。通过上述工作，我对设计、调试过程中出现的问题进行了分析、研究、解决。通过对 EDA 技术的学习和对这些编码的初步尝试，对前三年的软硬件方面的知识有了进一步的了解和加深，进一步对软硬件

54、的结合有了初步的认识。通过这个课题的研究使我们已经开始掌握了复杂可编程逻辑器件的开发流程和步骤，并可以展开进一步的提高，比如开发更为复杂的系统。我们研究的这个系统完全可以移植到一个大的系统内部，作为其中的计时模块使用。回首毕业设计的整个过程，感受最深的并不是自己开发的这么一个简单时钟，而是一个系统设计从起步到终止整个过程的整体性，连贯性，开放性；在这个过程中，初步有了系统开发的概念和经验，为以后的学习工作打下了坚实的基础；通过这个题目的研究，对大学四年学习到的软硬件方面的知识有了更加系统深入的了解；通过整个学习新知识，运用新知识的过程，锻炼了自己独立自主学习，团队合作，分析解决问题等等方面的素

55、质总之一句话，通过毕业设计阶段的学习和锻炼，受益终身！嘉兴学院本科生毕业设计24参 考 文 献1王兴亮等，数字通信原理与技术，西安电子科技大学出版社，20002R. W. Hamming,Codingand InformationTheory,Prentice-Hall,Englewood Cliffs,New Jersey,1980.)3潘 松 黄继业 .EDA 技术与 VHDL . 清华大学出版社4黄智伟.FPGA 系统设计与实践M.北京:电子工业出版社,20055刘科峰, 张沙清, 田丰. EDA 技术在电子设计中的应用J. 广西物理, 2004,(02)6侯伯亨 顾 新 .VHDL 硬

56、件描述语言与数字逻辑电路设计. 西安电子科技大学出版社 7吴继华,王诚. Altera FPGA/ CPLD 设计M . 北京:人民邮电出版,2005.8刘佳,焦斌亮. FPGA 的发展趋势及其新应用J . 电子技术,2008 (4)9樊昌信, 等. 通信原理M . 北京:国防工业出版社, 2005. 10周贤伟. 差错控制编码与安全M . 北京: 国防工业出版社,2004.10辛英. 汉明码纠错检错能力分析与应用J . 盐城工学院报:自然科学版,2008 ,21 (1) :34.11 王新梅、肖国镇，纠错码-原理与方法，西安电子科技大学出版社，199112Error Control Codi

57、ng:Fundamentals and Applications, 2nd EditionBy Shu Lin,Daniel J.Costello13基于 FPGA 的循环冗余校验模块设计,郭瑛,俞宗佐14浅析差错控制技术的主要思想及其实现,程中东, 卢琼玲15Tsfasman M A. Moduar curves, Shimura curves and Goppa codes, bet ter than V arshamov2Gilbert bound J . Math N ach r,1982, 104: 13 28基于 FPGA 的差错控制编码的设计与实现25致 谢时光飞逝,转眼大学四年学习即将结束。回首大学学习期间的校园学习生活，在知识的海洋里汲取营养和体味获取知识的充实与喜悦，不禁感慨万千。嘉兴学院本科生毕业设计26附 录