无损数据压缩算法的FPGA实现本科毕业论文.doc

编号 南京航空航天大学毕 业 设 计题 目 无损数据压缩算法的 FPGA实现学生姓名 梅发强学 号 041220318学 院 电子信息工程学院专 业 信息工程班 级 0412206指导教师 刘伟强 副教授二〇一六年五月南京航空航天大学本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：无损数据压缩算法的 FPGA 实现）是本人在导师的指导下独立进行研究所取得的成果尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品作者签名： 年 月 日 （学号）： 毕业设计（论文）报告纸i无损数据压缩算法的 FPGA 实现摘 要随着信息技术的快速发展，数据量呈现爆炸性增长，因此数据压缩越来越受到人们的重视目前，无损压缩算法大多数都是基于软件方式的实现，但是这在很多场合下已经不能满足高速数字系统的要求，所以基于硬件方式的实现成为了新的研究热点。

目前已有LZ77、LZ78 及 LZW 等算法的硬件实现，但是都存在搜索窗口较小，压缩率较低，速度较慢等缺陷本文出于硬件实现的考虑，对 LZ4 算法进行了适当的修改，基于 FPGA 进行实现，经实测发现其压缩率和速度都得到了显著提升关键词：无损压缩， LZ4， Verilog， FPGA 毕业设计（论文）报告纸iiFPGA Implementation of 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, software 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, LZW 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 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 算法流程 ..............................................................................................................................73.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 硬件调试时序图 ................................................................................................。