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

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

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

3、和 md5 编码。通过对前两种编码各个模块进行设计，完整阐述了对前两种 编码软件部分的设计；又通过测试，完善，修改，最终完成了各自独立的编码程序。 基于 vhdl 硬件描述语言，利用 fpga 器件开发的差错控制编码系统，采用了自顶向下 的设计方法用 vhdl 语言进行设计，选用当前应用最广泛的 eda 软件 xilinx ise 作为 开发平台及配套的 multisim 仿真工具，所有程序全部通过了该平台的编译和功能仿真 测试，得出了实际的仿真波形，最后，对设计调试过程中出现的问题进行了分析、研 究、解决。我还对上述这些各种编码的异同点进行了总结，对 md5 编码进行了算法分 析，既而对这些

4、编码进行研究。 关键词：fpga，vhdl，汉明码，循环冗余码，md5 码 iii the design and implementation of error control coding based on fpga abstract this paper mainly introduced the main characteristics, current situation and prospects and significance of eda technology, and puts some elaboration in related to topic research dir

5、ections; and further discussed the development 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

6、coding each module design, complete elaborated 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

7、proposed, using the top-down design methods 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 conclude

8、d that the actual simulation waveform, finally, 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,

9、crc code, md5 iv 目 录 摘 要.iii abstract.iv 第一章 绪论.1 1.1 课题的来源 .1 1.1.1 eda 技术综述 .1 1.1.2 差错控制编码技术介绍 .3 1.2 课题的意义 .5 1.3 差错控制编码发展现状 .6 1.4 课题研究的主要内容 .6 第二章 基于 fpga 的实现差错控制编码技术.8 2.1 差错控制编码的总体设计方案 .8 2.2（8，4）增余汉明码的差错控制编码译码设计.8 2.2.1 汉明码编码译码原理 .8 2.2.2（8，4）增余汉明码的算法与实现.8 2.2.3（8，4）汉明码编码波形仿真图：.10 2.2.4（8，4

10、）汉明码译码算法实现.10 2.2.5（8，4）汉明码编码波形仿真图：.12 2.2.6（8，4）汉明码编码译码综合模块.12 2.2.7（8，4）汉明码编码译码综合波形仿真图.13 2.3 循环冗余差错控制校验码的设计.13 2.3.1 crc 循环校验码编码校验原理 .13 2.3.2 crc 循环码编码规则 .14 2.3.3 crc 循环码算法分析 .14 2.3.4 crc 校验生成模块的设计实现.15 2.3.5 crc 校验生成模块仿真波形图 .17 2.3.6 crc 校验接收模块的设计实现.18 2.3.7 crc 校验接收模块仿真波形图 .19 2.4 md5 码的算法分析

11、 .19 2.5.1 md5 的引言 .19 2.5.2 md5 的原理 .20 2.5.3 md5 算法的安全性考虑 .21 2.5.4 md5 的应用 .22 第三章 基于 fpga 的实现差错控制编码技术开发体会.23 v 3.1 算法的重要.23 3.2 硬件对软件的制约影响.23 3.3 调试的重要性.23 第四章 结束语.24 致谢.26 附录.27 嘉兴学院本科生毕业设计 0 第一章 绪论 1.1 课题的来源 1.1.1 eda 技术综述 由于大规模集成电路开发技术的应用和发展以及电子产品市场运作的进一步加快， 涉及诸如通信、智能仪表、医药设备、军事、民用电器等领域的现代电子科学

12、技术与 应用已进入了一个崭新的阶段，电子设计自动化已成为当今电子设计领域的主流。 电子设计自动化技术是在电子计算机辅助设计技术基础上发展起来的计算机软件 系统，是指以计算机为工作平台，整合了应用电子技术、计算机技术、信息处理等最 新成果，进行电子产品的自动设计。 利用电子设计自动化工具，电子设计师可以将大量工作通过计算机完成，并可以 将电子产品从电路设计、性能分析到设计出 ic 版图或 pcb 版图的整个过程的计算机上 自动处理完成。 上世纪的最后 10 年以来，微电子技术以惊人的速度发展，其工艺水平达到了深亚 微米级，在一个芯片上可集成数百万乃至上千万只晶体管，工作速度已经可达到 ghz 的

13、时钟频率，这为制造出更大规模的，更快速度和更大信息容量的芯片系统提供了有 利条件，于此同时也对 eda 系统提出了更高的要求。此阶段主要出现了以高级硬件语 言描述、计算机系统仿真和综合技术为特征的第三代 eda 技术，不仅大大地提高了系 统的设计效率，而且使设计人员摆脱了大量基础性验证测试工作，将精力主要集中在 创造性的方案与概念的构思上，下面简单介绍这个阶段 eda 技术的主要特征： （1） 高层综合的理论与方法取得较大进展，将 eda 设计层次提高到行为级，并 划分为逻辑综合和测试综合。 （2） 采用硬件描述语言 hdl 来描述 10 万门以上的设计，并形成了 vhdl 和 verilog

14、 hdl 两种 ieee 标准硬件描述语言。它们均支持不同层次的描述，使得复杂 ic 的描述规范化，便于重复使用。它们多应用于 fpga 及其他可编程逻辑器件的设计中。 （3）可测性综合设计。随着 asic 的规模与复杂性的增加，测试难度与费用急剧 基于 fpga 的差错控制编码的设计与实现 1 增加，因此产生了将可测性电路结构制造在 asic 芯片上的想法，于是开发了扫描插入、 内建自测试、边界扫描等可测性设计（dft）工具，并已集成到 eda 系统中。 （4）建立并行设计工程 ce 框架结构的 ide，以适应当今 asic 器件的一些特点。 随着百万门规模的复杂的可编程逻辑器件的推出及应用

15、，eda 技术在仿真、时序分析、 集成电路自动测试、高速印刷电路板设计及操作平台的扩展等方面都面临着新的问题， 这些问题实际上也是新一代 eda 技术的未来发展趋势。 用 vhdl 语言开发 fpga 的设计流程如图 1-1 所示： 确定功能要求 进行设计 源代码模拟 综合优化和布局布 线 布局布线后的设计 模拟 符合要求？ 符合要求？ 是 是 否 否 接受设计任 务 器件变成配置 图 1-1 可编程逻辑器件开发设计流程图 接受任务：进行系统设计之前，先要由总体设计部门给出设计的任务和设计的一 些要求。 嘉兴学院本科生毕业设计 2 确定功能：对给出的设计任务和设计的一些要求进行分析，确定出具体

16、的功能及 要求。 进行分析：决定设计中所要采用的设计方法。 源代码模拟：在设计中，采用 vhdl 硬件描述语言模拟器进行源代码模拟可以在早 期开发中发现设计上的缺陷和错误，并及时进行改正，既而节省大量的设计时间，缩 短开发周期。 综合、优化和布局布线：综合是将较高层次的抽象描述转化到较低级描述的一种 方法，即将设计的 vhdl 源描述转化成底层电路表示。优化是指将设计的时延缩小到最 小和有效利用资源。布局布线就是把通过综合和优化所得到的逻辑，安放到一个逻辑 器件中的过程，一个较好的布局布线过程就是将电路的相关部分放置在一起，以消除 布线延迟。 布局布线后的设计模拟：布局布线后的设计模拟与源代码

17、模拟不同，源代码模拟 只是对设计的逻辑功能进行模拟，而布局布线后的设计模拟不仅可以对逻辑功能进行 验证，而且还能对设计时序功能进行验证。 器件编程和配置：器件编程就是将 vhdl 设计描述经过模拟、综合、优化和布局布 线的结果，经过一定映射转化成一个器件编程所用的数据文件格式。器件配置就是在 功能仿真和时序仿真正确的前提下，将综合后的文件下载到具体的芯片中进行电路验 证。 1.1.2 差错控制编码技术介绍 差错控制在数据通信过程中能发现或纠正差错，把差错限制在尽可能小的允许范 围内的技术和方法。在数字通信中常利用编码方法对传输中产生的差错进行控制，以 提高数字消息传输的准确性。差错控制系统的组

18、成及其作用原理如图。 信源信道编码器信道信道译码器信宿 重传控制反向信道重传控制 基于 fpga 的差错控制编码的设计与实现 3 图1-2 差错控制系统原理图 图中虚线内的部分就是数字通信中的差错控制系统10。当没有差错控制时，信源输 出的数字序列将直接送住信道。由于信道中存在干扰，信道的输出将发生差错。数字 在传输中发生差错的概率是传输准确性的一个主要指标。在数字通信中信道给定以后， 如果误码率不能满足要求,就要采取差错控制。按具体实现方法的不同,差错控制可以 分为前向纠错法、反馈重传法和混合法三种类型10。 （1）前向纠错法 差错控制系统只包含信道编码器和译码器。从信源输出的数字序列在信道

19、编码器 中被编码,然后送往信道。由于信道编码器使用的是纠错码，译码器可以纠正传输中带 来的大部分差错而使信宿得到比较正确的序列。 （2）反馈重传法 只利用检错码以发现传输中带来的差错，同时在发现差错以后通过反向信道通知 发信端重新传输相应的一组数字，以此来提高传输的准确性。根据重传控制方法的不 同，反馈重传法还可以分成若干种实现方式。其中最简单的一种称为等待重传方式。 采用这种方式时发信端每送出一组数字就停下来等待收信端的回答。这时信道译码器 如未发现差错便通过收信端重传控制器和反向信道向发信端发出表示正确的回答。发 信端收到后通过发信端重传控制器控制信源传输下一组数字，否则信源会重新传输原

20、先那组数字。 上述两种方法的主要差别是：前向纠错不需要反向信道，而反馈重传必须有反 向信道。前向纠错利用纠错码，而反馈重传利用检错码。一般来讲，纠错码的实现 比较复杂，可纠正的差错少，而检错码的实现比较容易，可发现的差错也多。前向 纠错带来的消息延迟是固定的，传输消息的速率也是固定的，而反馈重传中的消息延 迟和消息的传输速率都会随重传频度的变化而变化。前向纠错不要求对信源控制， 而反馈重传要求信源可控。经前向纠错的被传消息的准确性仍然会随着信道干扰的 变化而发生很大变化，而经反馈重传的被传消息的准确性比较稳定，一般不随干扰的 变化而变化。因此，两者的适用场合很不相同。 （3）混合法 在信道干扰

21、较大时，单用反馈重传会因不断重传而使消息的传输速率下降过多，而仅 嘉兴学院本科生毕业设计 4 用前向纠错又不能保证足够的准确性，这时两者兼用比较有利，这就是混合法。此法 所用的信道编码是一种既能纠正部分差错又能发现大部分差错的码。信道译码器首先 纠正那些可以纠正的差错，只对那些不能纠正但能发现的差错才要求重传，这会大大 降低重传的次数。同时，由于码的检错能力很强，最后得到的数字消息的准确性是比 较高的10-11。 差错控制编码又可分为检错码和纠错码11。检错码只能检查出传输中出现的差 错，发送方只有重传数据才能纠正差错；而纠错码不仅能检查出差错而且能自动纠正 差错，避免了重传。 1.2 课题的

22、意义 如今各种数字通信系统已广泛用于我们的生产生活中。然而数字信号在传输过程 中，由于受到干扰的影响，码元波形将变坏。接收端收到后可能发生错误判决。由乘 性干扰引起的码间串扰，可以采用均衡的办法纠正。而加性干扰的影响则需要用其它 办法解决。在设计数字通信系统时，应该首先从合理选择调制制度、解调方法以及发 送功率等方面考虑，使加性干扰不足以影响达到误码率的要求。在仍不能满足要求时， 就要考虑差错控制措施了，这就是我们研究差错控制技术的意义所在。 现代电子产品面临高功能、设计周期短、上市快的要求，其复杂度日益加深，一 个电子系统可能由数万个中小规模的集成电路构成，这就带来了体积大、功耗大、可 靠性

23、差的问题，解决这一问题的有效方法就是来用可编程逻辑器件（pld）进行设计。 可编程逻辑器件，尤其是 fpga 器件，即现场可编程门阵列，它是在 pal、gal、cpld 等可编程器件的基础上进一步发展的产物。它是作为专用集成电路领域中的一种半定 制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限 的缺点，具有集成度高、运行速度快、可靠性强、设计方式灵活、快速等特点，现已 成为现代高层次电子设计方法的实现载体。本课题研究了 eda 技术发展对电路设计方 法的影响，深入探讨了用 vhdl 语言和可编程逻辑器件 fpga 开发的基本方法，为开发 专用集成电路提供了基本的设计步

24、骤。作为应用对象，进一步开发差错控制编码技术。 开发这一系统的目的并不是为了实际的应用或应用到市场中去，只是通过一个简 基于 fpga 的差错控制编码的设计与实现 5 单系统的整体设计完成过程，深入体会 fpga 技术优势性，了解这些编码的特性及其应 用，使这几类编码得到更广泛的应用。在数字系统过程中，为了减少误码率，使这些 编码技术很好的应用到相关的一些领域中去，我总结出这些编码的异同点，为以后选 择这些编码时在相关领域的应用奠定一定的基础。 1.3 差错控制编码发展现状 1948年 c.e.香农（shannon）1发表论文指出，只要采用适当的纠错码，就可在 多类信道上传输消息。宣告了纠错码

25、的诞生。自 shannon 之后，人们不断向逼近信道 容量努力，取得重大发展，如分组码，代数码，卷积码，网格码和 turbo 码。所能达 到的性能也越来越接近 shannon 限间的距离。现在利用 fpga 技术实现差错控制编码的 种类很多，而且这些具有很强的纠错、检错码，被广泛应用到密码学、通信、磁盘阵 列及光存储、卫星通信、移动通信、深空通信等众多领域。 1.4 课题研究的主要内容 汉明码是一种能纠一位错的线性分组码, 由于它的编译码简单,在数据通信和计算 机存储系统中广泛应用,如在蓝牙技术和硬盘阵列中。它的最小码距为,可以纠正一位 错误,但对于两位错不能检测,还可能会造成误纠。尽管发生一

26、位错的概率相对最高, 但在一些要求较高的应用中汉明码不能满足要求。常用的能检测两位错同时能纠正一 位错的纠错码有(8,4)扩展汉明码。 crc 即循环冗余校验码（cyclic redundancy check）：是数据通信领域中最常用 的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。crc 常用硬 件电路和软件编程的方法实现,采用 crc 串行算法,即一个时钟周期内有一位数据输入, k 位长度的信息元连续计算 k 次后得出校验码. 这种传统 crc 的产生和校验方法对于 现代实时高速的通信系统已经不能满足其对于信息处理高速化、并行化的要求。 因此,本 文提出一种新的并行 crc

27、 编码方法:用 vhdl 语言在 fpga 芯片上编程,实现在一个时钟 周期内完成一次并行 crc 码的计算及校验. 该方法可以对不同长度的数据进行差错控 制,而且大大缩短了 crc 码的校验周期,为实现循环冗余校验提供了一种新思路. md5 的全称是 message-digest algorithm 5，在 90 年代初由 mit 的计算机科学实 嘉兴学院本科生毕业设计 6 验室和 rsa data security inc 发明，经 md2、md3 和 md4 发展而来。message-digest 泛指字节串(message)的 hash 变换，就是把一个任意长度的字节串变换成一定长的大

28、 整数。md5 还广泛用于加密和解密技术上，在很多操作系统中，用户的密码是以 md5 值 （或类似的其它算法）的方式保存的。 对于差错控制编码技术的研究，我主要是研究(8,4)增余汉明码编译码、crc 循环 编码和 md5 编码，现在首先是分别研究这几种编码，对前两种分别应用 fpga 技术去实 现，用 vhdl 语言去编写代码，然后再进行编译，下载，仿真及其去了解这些编码；然 后是对 md5 码进行研究和算法分析；最后总结出它们的异同点，以适应在以后需要的 时候选择适当的编码应用到相应的领域中去。 基于 fpga 的差错控制编码的设计与实现 7 第二章 基于 fpga 的实现差错控制编码技术

29、 2.1 差错控制编码的总体设计方案 在具体设计过程中，采取自上而下的设计思路。首先根据整体的规划设计出模块 的外部输入输出引脚定义以及功能，也就是设计出这一个小芯片的外部特性；然后根 据设计的这一个芯片的外部特性以及功能设计实现芯片内部的实现细节。 2.2（8，4）增余汉明码的差错控制编码译码设计 2.2.1 汉明码编码译码原理 汉明码(hamming code)是由 richard hamming 于 1950 年提出的,它属于线性分组 编码方式,用以纠正单个错误的线性分组码,在软件无线电中应用广泛。 设原代码的码长为 k 比特, 附加纠错编码部分为 r 比特,当码字长度 n=2r-1,r

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

31、兴学院本科生毕业设计 8 1 2 3 4 5 6 7 8 01111000 10110100 0 11010010 11111111 x x x x x x x x 若用方程式来表示, 则上式可以写成: 从而形成 5234613471248123;,xxxxxxxxxxxxxxxx 全码这就是(8,4)增余汉明码的编码过程。 12345678x x x x x x x x （8,4）汉明码编码的顶层设计模块如图所示： 图2-1 汉明码编码模块图 可以看出，输入为四位并行输入，编码后为一个八位的并行输出。 （8,4）汉明码编码的底层设计模块如图所示： 基于 fpga 的差错控制编码的设计与实现

32、9 图2-2 汉明码编码模块底层关系图 底部的各个分模块为两位的输入模通过各种逻辑运算，并最终组合在一起形成一 个 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就比较复杂。而一个译码器的复杂性及其译码错误概率也是由

33、这一步决定的。 设接收方收到发送方传来的一个完整的全码为:x11,x22,x33,x44,x55,x66,x77,x88,根 据汉明码校验矩阵: 11111 22222 3 48888 01111000 10110100 .11010010. 11111111 sxx sxx sh s sxx s1 s2 s3 s4为(8 ,4) 增余汉明码的校验子。当 s1 s2 s3 s4 =0000 时,传送无误;当 s1 s2 s3 s4为偶数时,可判接收到的全码中有两位错误,但不能判断哪两位错,可要求发 送方重新发送全码;当 s1 s2 s3 s4为奇数时,可根据表 1 判断哪一位错,然后通过软件来

34、 嘉兴学院本科生毕业设计 10 纠错,完成译码过程。 表2-1 （8，4）汉明码校验参数 错位 s1s2s3s4 错位 s1s2s3s4 1011151001 2101160101 3110170011 4111180001 译码算法的流程图如图所示： s1s2s3s4=0 s1s2s3s4=奇 数 有一位错，纠错 没错，输出信息 位 两位错，重发 no yes 初始化 s1 s2 s3 s4 输出信息位 图2-4 汉明码译码流程图 根据上述流程图，用 vhdl 语言描述（8，4）汉明译码算法功能模块如图所示： 图2-5 汉明码译码顶层模块图 基于 fpga 的差错控制编码的设计与实现 11

35、hamin 为汉明 8 位数据输入，dataout 为汉明 4 位数据输出，sec、ded、ne 为诊断 输出。 2.2.5（8，4）汉明码编码波形仿真图： 图2-6 汉明码译码仿真图 可以看出，通过译码模块，8 位全码又重新译码成原输入数据。 2.2.6 （8，4）汉明码编码译码综合模块 通过原件例化，对编码、译码电路进行连接得到综合顶层模块如下： 图2-7 汉明码编码译码综合顶层模块图 对顶层模块进行细化，如图所示： 嘉兴学院本科生毕业设计 12 图2-8 汉明码编码译码综合底层模块图 2.2.7 （8，4）汉明码编码译码综合波形仿真图 图2-9 汉明码综合模块仿真图 2.3 循环冗余差错

36、控制校验码的设计 2.3.1 crc 循环校验码编码校验原理 crc 校验采用多项式编码方法。被处理的数据块可以看作是一个 n 阶的二进制多 项式，如一个 8 位二进制数 10110101 可以表示为：x7+x5+x4+x2+1。多项式乘除法运算 过程与普通代数多项式的乘除法相同。多项式的加减法运算以 2 为模，加减时不进位、 错位和逻辑异或运算一致。采用 crc 校验时，发送方和接收方用同一个生成多项式 g(x),并且 g（x）的首位和最后一位的系数必须为 1。crc 的处理方法是：发送方以 g（x）去除 t（x） ，得到余数作为 crc 校验码。校验时，以计算的校正结果是否为 0 为据，判

37、断数据帧是否出错。 crc 校验可以 100地检测出所有奇数个随机错误和长度小于等于 k（k 为 g（x） 的阶数）的突发错误。所以 crc 的生成多项式的阶数越高，那么误判的概率就越小。 基于 fpga 的差错控制编码的设计与实现 13 2.3.2 crc 循环码编码规则 crc 编码实际上是将代发送的 m 位二进制多项式 t（x）转换成了可以被 g（x）除 尽的 m+r 位二进制多项式 t(x)，所以解码时可以用接受到的数据去除 g（x） ，如果余 数位零，则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。 许多 crc 的硬件解码电路就是按这种方式进行检错的。同时 t(

38、x) 可以看做是由 t（x）和 crc 校验码的组合，所以解码时将接收到的二进制数据去掉尾部的 r 位数据， 得到的就是原始数据。 2.3.3 crc 循环码算法分析 crc 校验码的编码方法是用待发送的二进制数据 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）

39、 。此二进制多项式 y（x）就是 t（x）经过生成多项式 g（x）编码的 crc 校验码。 （3） 用 t(x) 以模 2 的方式减去 y（x） ，得到二进制多项式 t(x) 。t(x) 就是 包含了 crc 校验码的待发送字符串。 由于 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）

40、的末尾添加 4 个 0 构成 x4t(x)，数据块就成了 1001000111000000。然后用 g（x）去除 x4t(x)，不用管商是多 少，只需要求得余数 y（x） 。表 1 给出了除法过程。 表 2-1 求校验码的过程表 嘉兴学院本科生毕业设计 14 除数次数 被除数/ g（x）/ 结果 余数 1 001000111000000 1 0011 0 0 000100111000000 100111000000 1 00111000000 1 0011 1 0 00001000000 1000000 1 000000 1 0011 2 0 001100 1100 从表 2-1 中可以看出，

41、crc 编码实际上是一个循环移位的模 2 运算。对 crc-4，我 们假设有一个 5 bits 的寄存器，通过反复的移位和进行 crc 的除法，那么最终该寄存 器中的值去掉最高一位就是我们所要求的余数。 2.3.4crc 校验生成模块的设计实现 crc 校验生成模块是在 xilinx ise 平台编程实现，程序首先执行了 11 次异或运 算，流程图如 2-10 所示，然后在作一次异或运算，得到的记过就是 crc 校验码 基于 fpga 的差错控制编码的设计与实现 15 结束 crcvar30复制到变量 c 中 rdatacrc 高 5 位复制到变量 crcvar i=11 rcrcvar（4）

42、 =？ crcvar30与 g(x)系数的低 4 位异或结果放在变量 c 中 crcvar40=c反之,则以为信息发送错误,将 error 设置为“1” 。 crc 校验检错模块如图 x 所示,其端口数据说明如下: rdata :接收模块(检错模块) 接收的 12 位有效信息数据； datafini :数据接收校验完成； clk :时钟信号； datacrci :附加上 5 位 crc 校验码的 17 位 crc 码； error :误码警告信号； hrecv :与生成模块的握手信号。 图 2-13 crc 校验接收模块的设计实现 嘉兴学院本科生毕业设计 18 2.3.7 crc 校验接收模块

43、仿真波形图 图 2-14 crc 校验接收模块仿真波形图 2.4 md5 码的算法分析 md5 的全称是 message-digest algorithm 5，就是把一个任意长度的字节串变换 成一定长的大整数。即 md5 将任意长度的“字节串”变换成一个 128bit 的大整数，并 且它是一个不可逆的字符串变换算法，换句话说就是，即使你看到源程序和算法描述， 也无法将一个 md5 的值变换回原始的字符串，从数学原理上说，是因为原始的字符串 有无穷多个，这有点象不存在反函数的数学函数。 2.5.1 md5 的引言 md5 算法是通过数学运算,把不同长度的信息串转化到 128 位编码中,形成 ha

44、sh 值,通 基于 fpga 的差错控制编码的设计与实现 19 过比较这个数值是否正确,来确定通信双方的合法性。这也可以说是数字签名,在数据 传输后,可以通过比较 hash 值来判断信息途中是否被截获修改,是否由合法的发送人发 送或者合法的接收人接收等。用这种方法,可以防止密钥丢失的问题,因为它的加密部 分是随机生成的,如果没有正确的 hash 值根本就无法解开加密部分,而且它还具备了数 字签名的能力,可以证明发送方和接收方的合法身份,具有不可抵赖性,很适用于商业信 息的传递。md5 的典型应用是对一段信息(message)产生信息摘要(message-digest) , 以防止被篡改。它还被

45、广泛用于加密和解密技术上。md5(rfc1321)是于 90 年代由 ron rivest 在 mit 提出来的。我们现在来了解一下 md5 的原理。 2.5.2 md5 的原理 该算法输入任意长度的消息,输出 128 位消息摘要,处理以 512 位输入数据块为单 位。处理报文摘要的过程如下: 步骤 1:添加填充位(最高位为 1 和其余为 0)。在消息的最后添加适当的填充位使 得数据位的长度满足与 448 模 512 同余,即:length=448mod512。 步骤 2:添加长度。原始消息长度(二进制位的个数),用 64 位表示,并附加在步骤 1 的结果后。由这两个步骤得到长度为 512 整

46、数倍的报文。表示为 l 个 512 位的数据块: y0,y1 ,yl-1.其长度为 l512bits.令 n=l16,则长度为 n 个 32 位的字。令 m0n-1表示以字为单位的消息表示。 步骤 3:初始化 md 缓冲区。一个 128 位 md 缓冲区用以保存中间和最终散列函数的 结果.它可以表示为 4 个 32 位的寄存器(a,b,c,d)。寄存器初始化为以下的 16 进制值。 a=67452301 b=efcdab89 c=98badcfe d=10325476 寄存器内容 word a : 01 23 45 67 word b: 89 abcd ef 嘉兴学院本科生毕业设计 20 wo

47、rd c: fe dc ba 98 word d: 76 54 32 10 采用小数在前的格式存储,即将字的低字节放在低地址字节上 步骤 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

48、是弧度.于 abs(sin(i)是一个 0 到 1 之间的数,t 的每一个元素是一个可以表示成 32 位的整数。 t 表提供了随机化的 32 位模板,消除了在输入数据中的任何规律性的特征 t 表 t 1 = d76aa478 t 49 = f4292244 t 2 = e8c7b756 t 50 = 432aff97 t 3 = 242070db t 51 = ab9423a7 t 4 = c1bdceee t 52 = fc93a039 . . . . . . t 16 = 49b40821 t 64 = eb86d391 步骤 5:输出结果。所有 l 个 512 位数据块处理完毕后,最后的

49、结果就是 128 位消息 摘要。 2.5.3 md5 算法的安全性考虑 对强行攻击的安全性:使用强行技术,产生任何一个报文使其摘要等于给定保文摘 要的难度对 md5 是 2128 数量级的操作,产生相同报文摘要的两个报文的难度是 264 数 量级 对密码分析的安全性:对单循环的 md5,使用不同的密码分析可能在合理的时间内找 出能够产生相同摘要的两个报文,这个结果被证明对四个循环中的任意一循环也成立。 目前,md5 已被认为是易受攻击的。事实上,md5 算法已有被德国解密专家攻破的纪录, 据称,一个价值几百万美元的计算机系统可以在几周内寻找出已被暗码处理的原文。在 基于 fpga 的差错控制编

50、码的设计与实现 21 对安全要求很高的场合使用仍存在风险。 2.5.4 md5 的应用 md5 码主要是应用在加密和解密两个方面，使用的是非常的广泛，应用的领域也是 非常的多。在我们的解压缩文件中，有很多就是应用到了 md5 码，因为它的保密工作 具有一次性保密工作，不仅保留了一次性口令的优点,而且克服了序列密码一次性口令 系统中的小数攻击和 ip 地址欺骗攻击的漏洞,同时又避免了 rsa 算法中大整数质因数 分解的计算效率问题。 嘉兴学院本科生毕业设计 22 第三章 基于 fpga 的实现差错控制编码技术开发体会 3.1 算法的重要 在刚开始设计这个毕设的时候，我可以说的这个课题不甚了解，有

51、点无从下手的 感觉，通过上网查询和杨老师的教导，我的课题是一个研究性的课题，所以我就要搜 集好几种编码来分别进行研究，来找出它们的异同点，首先找到的是汉明码和 crc 码， 这两种广泛应用于数字通讯中的编码，但是我要用 fpga 去实现，这种用硬件实现起来 传输速度会很快，可是在这之中算法就是一个很难的问题，我只有理解了算法才能用 vhdl 的语言来做出来，包括我后来做的 md5 编码，算法也是相当的重要的，而且我觉 得很难，这些花费我很多的时间。 算法可以说是一种编码的灵魂，没有算法我是不可能实现我的研究课题的，这些 涉及到很多别的问题，不是很容易明白，我就要不断地去分析和查找书籍，找出这些

52、 原理的所在，为下面的工作做准备。 3.2 硬件对软件的制约影响 在毕业设计的过程中，尤其到了硬件调试的时候，还有一点感受比较深刻，那就 是硬件对软件设计的影响。由于试验台硬件和小组设计试验板硬件性能不完全相同， 致使软件系统从试验台到试验板的过程中遇到了很多意想不到的问题，最终还是通过 修改软件来适应硬件的标准。 3.3 调试的重要性 程序写出来之后，需要进行大量的硬件调试工作，否则的话，一旦出现问题，就 搞不清楚问题究竟是软件设计的错误还是硬件电路板的错误，所以首先解决硬件调试 是必须的。在调试的过程中，需要有清晰的逻辑思维作基础，对硬件知识有熟练的掌 握和灵活的应用。 基于 fpga 的差错控制编码的设计与实现