LZMA压缩算法FPGA硬件实现

doi:10.13700/j.bh.1001-5965.2014.0169

北京航空航天大学学报 ›› 2015, Vol. 41 ›› Issue (3): 375-382.doi: 10.13700/j.bh.1001-5965.2014.0169

LZMA压缩算法FPGA硬件实现

李冰^1,2, 张林¹, 刘勇¹

1. 东南大学集成电路学院, 南京 210018;
2. 东南大学成贤学院, 南京 210018

收稿日期:2014-03-31 出版日期:2015-03-20 发布日期:2015-04-02
通讯作者: 李冰(1968—),男,江苏南京人,教授,bernie_seu@seu.edu.cn,主要研究方向为大数据云计算. E-mail:bernie_seu@seu.edu.cn
基金资助:
“十二五”国家科技支撑计划课题(2013BAJ05B03)

FPGA hardware implementation of the LZMA compression algorithm

LI Bing^1,2, ZHANG Lin¹, LIU Yong¹

1. College of Integrated Circuits, Southeast University, Nanjing 210018, China;
2. Chengxian College, Southeast University, Nanjing 210018, China

Received:2014-03-31 Online:2015-03-20 Published:2015-04-02

摘要/Abstract

摘要： LZMA(Lempel Ziv Markov-chain Algorithm)无损压缩算法在进行数据压缩时速度慢且占用大量的CPU(Central Processing Unit)资源,不能满足实时系统的要求.在改进算法的基础上,采用FPGA(Field Programmable Gate Array)设计了一个LZMA压缩算法硬件加速电路.该电路由LZ77压缩控制器、区间编码控制器和数据读出控制器组成,采用数据乒乓结构、高性能并行匹配结构和流水线处理结构等多种方法提高了LZMA压缩算法的速度,在支持标准LZMA压缩文件格式的同时,将压缩速度提升到近125 Mb/s,相比基于软件的LZMA算法加速10倍,每个时钟处理的相对数据加速近200倍.最后通过基于Virtex-6 FPGA的ML605开发平台验证了硬件加速电路的正确性和可行性.

关键词: LZMA, 压缩, 硬件, 加速, 文件格式

Abstract: Software-based LZMA (Lempel Ziv Markov-chain algorithm) nondestructive compression algorithm is very slow and consumes too much CPU (central processing unit) resources during the data compression process, as a result it can not meet the requirements of real-time systems. On the basis of the improved algorithm, a hardware accelerator for LZMA was designed with FPGA (field programmable gate array) implementation. The hardware accelerator is composed of LZ77 compressor, range encoder and send out controller. Ping-pong operation, parallel matching method with high performance, pipeline processing structure and other acceleration techniques were used to speed up LZMA compression algorithm. While at the same time, data compressed by the circuit is still compatible with standard LZMA file format. The compression rate of the circuit is speeded up to 125 Mb/s, nearly 10 times faster than that of the software based LZMA. The processing relative data of each clock is speeded up nearly 200 times. Results from the experiments on ML605 basing on a Virtex-6 FPGA development kit, show the accelerator is correct and feasible.

Key words: Lempel Ziv Markov-chain algorithm (LZMA), compression, hardware, acceleration, file format

中图分类号:

李冰, 张林, 刘勇. LZMA压缩算法FPGA硬件实现[J]. 北京航空航天大学学报, 2015, 41(3): 375-382.

LI Bing, ZHANG Lin, LIU Yong. FPGA hardware implementation of the LZMA compression algorithm[J]. , 2015, 41(3): 375-382.

参考文献

[1] Salomon D. Data compression:the complete reference[M].4th ed.London:Springer,2007:241-246.
[2] Pavlov I. 7z format[EB/OL].US:Igor Pavlov,2013[2014-03-10].http://www.7-zip.org/7z.html.
[3] Klausman. Gzip,Bzip2 and LZMA compared[EB/OL].US:CEST,2008[2014-03-10].http://blog.i-no.de/archives/2008/05/08/.
[4] Rigler S, Bishop W,Kennings A.FPGA-based lossless data compression using Huffman and LZ77 algorithms[C]//Electrical and Computer Engineering.Canada:CCECE,2007:1235-1238.
[5] Ziv J,Lempel A. Universal algorithm for sequential data compression[J].IEEE Transactions on Information Theory,1977,IT-23(3):337-343.
[6] Ranganathan N, Henriques S.High-speed VLSI designs for Lempel-Ziv-based data compression[J].IEEE Transactions on Circuits and Systems II:Analog and Digital Signal Processing,1993,40(2):96-106.
[7] Shcherbakov I, Weis C,Wehn N.A high-performance FPGA-based implementation of the LZSS compression algorithm[C]//Data Compression Conference(DCC).Washington,DC:IEEE,2012:449-453.
[8] Martin G N N. Range encoding:an algorithm for removing redundancy from a digitized message[C]//IERE Conference Proceedings.London:IERE,1979,43:187-197.
[9] Pavlov I. LZMA SDK[EB/OL].US:Igor Pavlov,2013[2014-03-10].http://www.7zip.org/sdk.html.
[10] 孙圣. 一种基于FPGA的Defalte压缩算法研究与实现[D].桂林:桂林理工大学,2010. Sun S.A research and implementation of Deflate compression algorithm on FPGA[D].Guilin:Guilin University of Technology,2010(in Chinese).
[11] Shcherbakov I, Weis C,When N.A parallel adaptive range coding compressor:algorithm,FPGA prototype,evaluation[C]//Data Compression Conference(DCC).Piscataway,NJ:IEEE,2012,119-128.
[12] Xilinx. Xilinx FPGA[EB/OL].US:Xilinx,2011[2014-03-10].http://www.xilinx.com/products/silicon-devices/fpga/index.htm.
[13] Xilinx. ML605 Hardware User Guide[EB/OL].US:Xilinx,2011[2014-03-10].http://www.xilinx.com/support/documentation/boards_and_kits/ug534.pdf
[14] Leavline E J, Singh D A A G.Hardware implementation of LZMA data compression algorithm[J].International Journal of Applied Information Systems (IJAIS),2013,5(4):449-453.
[15] Calgary Corpus. Calgary corpus database[EB/OL].US:Calgary Corpus,1987[2014-03-10].http://en.wikipedia.org/wiki/Calgary_Corpus.

LZMA压缩算法FPGA硬件实现

FPGA hardware implementation of the LZMA compression algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	雷玉兰, 韩光超, 盛超杰, 张召臣. 10 kN超声辅助塑性成形压力机设计与试验[J]. 北京航空航天大学学报, 2019, 45(8): 1622-1629.
[2]	胡守信, 李兴虎. 中国CNG/汽油两用燃料汽车全生命周期评价[J]. 北京航空航天大学学报, 2019, 45(7): 1481-1488.
[3]	邱棚, 李鸣谦, 姚旭日, 翟光杰, 王雪艳. LPV模型的动态压缩测量辨识算法[J]. 北京航空航天大学学报, 2019, 45(5): 961-969.
[4]	姜晓明, 刘强. 基于FPGA的低复杂度快速SIFT特征提取[J]. 北京航空航天大学学报, 2019, 45(4): 804-810.
[5]	刘岩, 孙安强. 颈动脉内血流动力学特征受向前加速度影响的数值模拟[J]. 北京航空航天大学学报, 2019, 45(3): 493-498.
[6]	王鹏, 曹云峰, 许蕾, 丁萌, 张洲宇, 曲金秋. 一种图像缩放算法的SoC协同加速设计方法[J]. 北京航空航天大学学报, 2019, 45(2): 333-339.
[7]	吴玲达, 张喜涛, 孟祥利. 基于社团结构节点重要性的网络可视化压缩布局[J]. 北京航空航天大学学报, 2019, 45(12): 2423-2430.
[8]	上官士鹏, 朱翔, 陈睿, 马英起, 李赛, 韩建伟. 0.13 μm部分耗尽SOI工艺反相器链SET脉宽传播[J]. 北京航空航天大学学报, 2019, 45(11): 2193-2198.
[9]	李彦苏, 张坤, 何承军, 阎超. 低速修正的可压缩求解器对湍流模拟精度的影响[J]. 北京航空航天大学学报, 2019, 45(11): 2199-2206.
[10]	盖炳良, 滕克难, 王浩伟, 王文双, 陈健, 宦婧. 基于随机相关的电子部件二元加速退化可靠性评估[J]. 北京航空航天大学学报, 2019, 45(11): 2237-2246.
[11]	薛倩, 刘婧, 马敏, 王化祥. 基于原始对偶内点法的EST图像重建[J]. 北京航空航天大学学报, 2019, 45(10): 1973-1981.
[12]	高爽, 张若愚. 基于自适应遗传算法的MEMS加速度计快速标定方法[J]. 北京航空航天大学学报, 2019, 45(10): 1982-1989.
[13]	吴靖, 蔡国飙, 贺碧蛟. 氢氧发动机真空羽流干扰试验研究[J]. 北京航空航天大学学报, 2019, 45(1): 44-49.
[14]	肖沈阳, 金志刚, 苏毅珊, 武晋. 压缩感知OFDM稀疏信道估计导频设计[J]. 北京航空航天大学学报, 2018, 44(7): 1447-1453.
[15]	李欣, 王春阳, 原慧, 金珊珊. 基于干扰重构和峭度最大化的SMSP干扰抑制方法[J]. 北京航空航天大学学报, 2018, 44(6): 1176-1184.