LZMA压缩算法FPGA硬件实现

李冰; 张林; 刘勇

doi:10.13700/j.bh.1001-5965.2014.0169

LZMA压缩算法FPGA硬件实现

doi: 10.13700/j.bh.1001-5965.2014.0169

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

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

基金项目: “十二五”国家科技支撑计划课题(2013BAJ05B03)

详细信息

通讯作者:
李冰(1968—),男,江苏南京人,教授,bernie_seu@seu.edu.cn,主要研究方向为大数据云计算.

中图分类号: TP391.1;TN492
计量
- 文章访问数: 2922
- HTML全文浏览量: 175
- PDF下载量: 26991
- 被引次数: 0
出版历程
- 收稿日期: 2014-03-31
- 网络出版日期: 2015-03-20

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

摘要

摘要: 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.
- Lempel Ziv Markov-chain algorithm (LZMA) /
- compression /
- hardware /
- acceleration /
- file format

HTML全文

参考文献(15)

[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.