1、 编号 南京航空航天大学毕 业 设 计题 目 无损数据压缩算法的 FPGA实现学生姓名 梅发强学 号 041220318学 院 电子信息工程学院专 业 信息工程班 级 0412206指导教师 刘伟强 副教授二一六年五月南京航空航天大学本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：无损数据压缩算法的 FPGA 实现）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。作者签名： 年 月 日 （学号）：毕业设计（论文）报告纸i无损数据压缩算法的 F
2、PGA 实现摘 要随着信息技术的快速发展，数据量呈现爆炸性增长，因此数据压缩越来越受到人们的重视。目前，无损压缩算法大多数都是基于软件方式的实现，但是这在很多场合下已经不能满足高速数字系统的要求，所以基于硬件方式的实现成为了新的研究热点。目前已有LZ77、LZ78 及 LZW 等算法的硬件实现，但是都存在搜索窗口较小，压缩率较低，速度较慢等缺陷。本文出于硬件实现的考虑，对 LZ4 算法进行了适当的修改，基于 FPGA 进行实现，经实测发现其压缩率和速度都得到了显著提升。关键词：无损压缩， LZ4， Verilog， FPGA毕业设计（论文）报告纸iiFPGA Implementation of
3、 Lossless Data CompressionAbstractWith the rapid development of information technology, the amount of data presents explosive growth. Therefore, more and more attention has been paid to the data compression. Up to date, most of lossless compression algorithms are realized in software. However, softw
4、are implementation in many occasions cannot meet the real time requirements of high-speed system. The hardware implementation of data compression algorithms is becoming a research hotspot. Nowadays, there are hardware implementations of the lossless data compression algorithms such as LZ77, LZ78, LZ
5、W etc. But they have defects including small search window, low compression rate, and slow processing speed. In this thesis, for the consideration of the hardware implementation, the LZ4 algorithm is appropriately modified to be implemented on Xilinx FPGA KC 705 evaluation board, which offers higher
6、 compression rate and speed.Key Words：Lossless compression; LZ4; Verilog; FPGA毕业设计（论文）报告纸iii目 录摘 要 .iAbstract .ii第一章 引 言 .11.1 课题研究背景及意义 .11.2 本文研究内容和结构安排 .2第二章 基本原理和常用算法 .32.1 数据信息量、熵和冗余度介绍 .32.2 LZ 系列算法概述 .32.3 LZ4 算法简介 .4第三章 LZ4 无损压缩算法原理 .53.1 数据流格式 .53.2 官方 LZ4 格式 .53.3 修改后的 LZ4 格式 .73.4 算法流程 .7
7、3.4.1 hash 表 .73.4.2 匹配算法 .83.4.3 流操作 .83.5 解压 .93.5.1 官方 LZ4 格式解压流程 .93.5.2 修改后的 LZ4 格式解压流程 .9第四章 LZ4 无损压缩算法硬件实现方案 .114.1 方案一 .114.1.1 硬件框图 .114.1.2 算法流程 .124.1.3 硬件调试时序图 .134.1.4 压缩速度计算 .144.2 方案二 .14毕业设计（论文）报告纸iv4.2.1 硬件框图 .144.2.2 算法流程 .144.2.3 硬件调试时序图 .164.2.4 压缩速度计算 .164.3 方案三 .164.3.1 硬件框图 .1
8、64.3.2 算法流程 .174.3.3 硬件调试时序图 .184.3.4 压缩速度计算 .184.4 各方案优缺点分析 .194.4.1 资源消耗比较 .194.4.2 压缩速度比较 .194.4.3 最佳方案选择 .19第五章 LZ4 无损压缩算法硬件实现 .215.1 LZ4 核总体框架 .215.2 LZ4 压缩验证结构图 .225.3 LZ4 核内部模块功能说明 .225.4 LZ4 核性能 .27第六章 LZ4 无损压缩算法硬件实现功能测试 .296.1 测试框架图 .296.2 数据测试表格 .296.3 与已有的 LZ 系列的实现对比 .30第七章 LZ4 解压缩算法硬件实现
9、.317.1 LZ4 解压核总体框架 .317.2 LZ4 解压验证结构图 .317.3 LZ4 解压核内部模块功能说明 .327.3.1 输入模拟 FIFO .327.3.2 数据解压控制模块 .337.3.3 输出控制模块 .34毕业设计（论文）报告纸v7.3.4 输出 RAM 模块 .347.4 LZ4 解压核输出速度计算 .34第八章 总结 .36参 考 文 献 .37致 谢 .38毕业设计（论文）报告纸- 1 -第一章 引 言1.1 课题研究背景及意义随着信息时代的到来，人们对数据越来越依赖，数据交换量日益增大，海量数据带来的大规模数据处理也变得更加复杂。将数据进行有效的压缩能够减少
10、存储所需的空间以及最大限度地利用有限的通信带宽。而且，经过压缩的数据在一定程度上是对原始数据的加密，从而更加地提高数据的安全性 1。数据压缩通常分为无损压缩和有损压缩。图像、视频、音频等不是十分注重细节的数据大多数都采用有损压缩技术，用于此类应用场景的有 MPEG，H.263 ，H.264 等当今流行的压缩技术 23。但是像程序、电子档案等类似的需要完全可以复原的重要信息，就必须采用无损压缩技术，用于这种要求解压缩后的数据与原始数据完全一致的场合的常见算法有LZ77、LZSS、GZIP、BZIP2、RAR 等。人们对无损压缩技术的研究已经有很长的一段时间，其中 LZ 系列的压缩算法和最小冗余度
11、构造算法 Huffman 算法属于最重要的无损压缩技术。现在流行的压缩技术基本上都是由这些算法衍生而来 45。但是，当今很多压缩解压方案都是基于软件方式的实现。采用软件方式的压缩解压存在一个致命的弱点，那就是过多地消耗宝贵的 CPU 资源而且速度慢。特别是当压缩解压大量数据时，占有的 CPU 资源是非常大的，而且由于 CPU 采用的指令工作方式使得速度很慢，另外系统非常不稳定，很难满足一些特殊环境下的应用要求。所以，如何有效提高压缩算法的效率，减少庞大数据量压缩解压给 CPU 和内存带来的压力成为了现在压缩解压技术的主要发展方向。现代 VLSI 技术的发展使得采用硬件方式来实现压缩解压成为可能
12、。用专用硬件提供压缩解压可以解决上述软件压缩解压所存在的缺点。即它可以：l、提高了压缩解压的速度，有利于实时性处理；2、节省了宝贵的 CPU 资源。因为硬件方式相比软件方式实现的速度快很多，依靠电路实现不需要循环的指令计算，而且能够采取并行的实现方式，这样降低了资源和能源的消耗。如今已经有不少采用硬件方式的压缩解压方案在信息产业的各个环节被应毕业设计（论文）报告纸- 2 -用，具有长远的发展前景 67。1.2 本文研究内容和结构安排本文主要研究LZ4算法流程、硬件实现、以及算法优化。通过对现有的LZ4文献以及官方的C 程序，了解并掌握LZ4算法的压缩和解压原理。在对LZ4算法足够了解后，将算法
13、细分成几个步骤得出算法流程图。通过算法流程图，将整个算法细分成许多子模块，每个子模块实现一个简单的功能，通过流程控制将每个模块关联起来，最后实现每个子模块都处于同时工作状态，提高压缩速度，实现并行处理功能。本文章节内容安排如下：第一章主要介绍 LZ4 算法的 FPGA 高速实现的研究背景，介绍了数据压缩的历史与现状，并明确了本文的研究内容；第二章分析了数据压缩原理，表明了什么样的数据才能压缩，并对 LZ 系列算法做了一个大概的介绍。第三章对 LZ4 无损压缩算法原理进行了详细的介绍，包括 LZ4 数据格式以及 LZ4 算法流程。第四章提供了三个 LZ4 无损压缩算法的硬件实现方案，并详细介绍了
14、每个方案的实现流程以及每个方案的优缺点，同时对其性能做出了详细的比较。第五章介绍了 LZ4 无损压缩算法硬件实现程序的结构以及每个模块的功能，同时给出了在 kintex7 kc705 开发板上运行的到的一些资源消耗信息。第六章是对 LZ4 无损压缩算法的硬件实现做的一些数据测试，计算了其压缩率，并将它的压缩速度与市场上的一些产品做比较。第七章是根据压缩算法而做的解压算法的 FPGA 实现，其中详细介绍了解压流程以及解压程序中每个模块的功能。第八章是对整个论文的总结。毕业设计（论文）报告纸- 3 -第二章 基本原理和常用算法数据压缩的前提是数据可以被压缩。从信息论中可以知道什么样的数据压缩后会变
15、小，什么样的数据压缩后占据空间反而会变大。根据数据的信息量、熵和冗余度可以计算出压缩后的最小体积，但是由于算法原理、数据格式不同会导致始终达不到理论值。不过可以通过理论来知道为何数据可以被压缩，也可以通过这些理论来指导数据压缩的实现。2.1 数据信息量、熵和冗余度介绍信息量是指一个随机事件的不确定性，通常用熵来表示。信息论量度信息的基本出发点，是把获得的信息看作用以消除不确定性的东西，因此信息数量的大小，可以用被消除的不确定性的多少来表示。一个消息的可能性越小，其信息就越多；消息的可能性越大，其信息就越少。信息论中把一个事件（如字符）所携带的信息量定义为 8：（2.1）其中 P（X i）为实践发生（字符 Xi）的概率。将信息所有可能事件的信息量进行平均，就得到信息的熵。信源 X 的信息熵(Entropy) H(x)定义为 8：（2.2）信源经常由于事件相关或概率分布不均匀等原因，而使实际的熵小于其最大熵，这样就产生了信息的冗余。冗余度 R 定义为：（2.3）2.2 LZ 系列算法概述LZ 系列算法起源于两位以色列研究者 J.Ziv 和 A.Lempel 在 1977 年发布的 LZ77 数据压缩的通用算法，该算法与 Huffman 及算术编码更加有效，通过不断的发展演变最后提出了很
