LZMA压缩算法FPGA硬件实现

《LZMA压缩算法FPGA硬件实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2015年3月第41卷第3期北京航空航天大学学报JournalofBeijingUniversityofAeronauticsandAstronauticsMarch2015V01．41No．3http：／／bhxb．buaa．edu．cnjbuaa@buaa．edu．cnDOI：10．13700／j．bh．1001—5965．2014．0169LZMA压缩算法FPGA硬件实现李冰刈”，张林1，刘勇1(1．东南大学集成电路学院，南京210018；2．东南大学成贤学院，南京210018)摘要：LZMA(LempelZivMarkov．cha

2、inAlgorithm)无损压缩算法在进行数据压缩时速度慢且占用大量的CPU(CentralProcessingUnit)资源，不能满足实时系统的要求．在改进算法的基础上，采用FPGA(FieldProgrammableGateArray)设计了一个LZMA压缩算法硬件加速电路．该电路由LZ77压缩控制器、区间编码控制器和数据读出控制器组成，采用数据乒乓结构、高性能并行匹配结构和流水线处理结构等多种方法提高了LZMA压缩算法的速度，在支持标准LZMA压缩文件格式的同时，将压缩速度提升到近125Mb／s，相比基于软件的LZMA算法加速10倍

3、，每个时钟处理的相对数据加速近200倍．最后通过基于Virtex-6FPGA的ML605开发平台验证了硬件加速电路的正确性和可行性．关键词：LZMA；压缩；硬件；加速；文件格式中图分类号：TP391．1；TN492文献标识码：A文章编号：1001—5965(2015)03-0375-08随着信息和通信技术的迅猛发展，庞大的数据必须进行有效的压缩，才能减少数据交换量，最大限度地利用有限的数据传输带宽．无损压缩要求对压缩的数据进行重构(解压缩)后原来的数据完全相同，具有高保真性的无损压缩被大量应用到服务器和工作站等大数据处理系统中，IBM和百

4、度等公司均对其做过积极研究．LZMA压缩算法是LZ77压缩算法的一个改进版本，由Pavlov于1998年发明，目前在7zip压缩算法中被作为默认的压缩算法¨。。．虽然LZMA能够提供较高的压缩率，但处理过程中需要大量的随机访问存储器(RAM，Ran—domAccessMemory)，并且会耗费较多CPU资源．对海量数据进行处理时，长时间占用大量CPU资源，使得在执行LZMA数据压缩的同时进行其他操作变成了难题．目前一个高性能FPGA中包含了上千个独立的双端口RAM块，一个或多个的内嵌处理器以及海量的可配置资源．尽管这些资源相比CPU的工作

5、频率要慢很多，但却可以提供高性能的并行运算，从而使得加速LZMA压缩算法成为了可能．虽然国内外已有众多的关于数据无损压缩加速的电路实现方案，但却不能在支持高压缩带宽的同时，提供很好的压缩比．本文主要针对LZMA算法的FPGA硬件实现进行了研究，在高速压缩的同时提供更好的压缩比例．1LZMA算法LZMA压缩算法的结构与Deflate算法极其相似⋯1，只是将其中的Huffman编码替代成了区间编码，值得注意的是区间编码是一种基于整数运算的概率编码，其压缩效果十分接近数据的熵值．收稿日期：2014-03-31；录用日期：2014-06—25；网

6、络出版时间：2014-09—1815：15网络出版地址：WWW．cnki．net／kcms／doi／lO．13700／j．bh．10016965．2014．0169．html基金项目：“十二五”国家科技支撑计划课题(2013BAJ05803)}通讯作者：李冰(1968一)，男，江苏南京人，教授，bernie—seu@seu．edu．en，主要研究方向为大数据云计算引用格式：李冰，张林，刘勇．LZMA压缩算法FPGA硬件实现fJJ．北京航空航天大学学报，2015，41(3)：375—382．LiB．ZhangL．LiuY．FPGAhardw

7、areimplementationoftheLzMAcompressiona190rithm【j]．JournalofBeijingUniversityofAeronauticsandAstronautics，2015，41(3)：375—382(inChinese)．376北京航空航天大学学报在LZMA算法中，首先由LZ77压缩算法在搜索缓存(searchbuffer)中寻找与前向缓存(100k—aheadbuffer)中匹配最长的字符串，然后输出一个关于(DIS，LEN，LIT)的标识．其中，DIS代表了look—aheadbuffe

8、r中与searchbuffer中相匹配的两组数据首个字节之间的距离，最大的值取决于searchbuffer的大小；LEN代表了最大的匹配长度，通常是一个较小的数值；LIT代表下一个字符，通常是