一种基于LZW算法的数据无损压缩硬件实现*

作者：刘洪庆1，王新才2，沈海斌1，缪志宏1 日期：2008-08-18/span> 浏览：3532 查看PDF文档

一种基于LZW算法的数据无损压缩硬件实现*

刘洪庆1，王新才2，沈海斌1，缪志宏1
（1.浙江大学 超大规模集成电路设计研究所，浙江 杭州 310027; 2.数源科技股份有限公司，浙江 杭州 310012）

摘要：针对软件实现的压缩、解压方案存在消耗资源过多、速度慢的特点，介绍了一种基于LZW算法的硬件实现的无损压缩器，并根据算法的特点提出了其体系结构。该结构采用了一种并行的字典搜索策略，极大地提高了字串的搜索速度。在压缩器的设计中控制部分和数据处理部分明确分工，有利于功能的扩展。仿真结果显示，该设计的压缩器可以正确实现压缩，资源占用情况可以接受;工作频率达到210 MHz，总的数据处理能力达到750 Mbps，处理性能比软件实现的处理能力快20多倍。
关键词：无损压缩；超大规模集成电路；硬件；字典压缩;LZW算法
中图分类号：TP301.6文献标识码：A文章编号：1001-4551(2008)08-0001-04

A hardware implementation of lossless data compression based on LZW algorithm
LIU Hong-qing1, WANG Xin-cai2, SHEN Hai-bin1, MIAO Zhi-hong1
(1.Institute of VLSI Design， Zhejiang University， Hangzhou 310027， China; 2.SOYEA Technology Co. Ltd., Hangzhou 310012, China)
Abstract: Aiming at the disadvantages of excess consumption of resource and low speed existing in gormpression and decompresscon scheme readlioed by software, an implementation of lossless data compression in hardware based on LZW algorithm was introduced. The architecture used a parallel dictionary searching strategy to speed up the string search in dictionary. These configurable registers made the control subsystem and data processing subsystem apart and also was helpful for the function extension. The simulation result reveals that the compression core can compress data correctly and the resource is acceptable; the maximum frequency is 210 MHz, so the total data processing ability reaches 750 Mbps, which is twenty times larger than software implementation.
Key words: lossless compression; very large scale integration(VLSI); hardware; dictionary compression; lempel ziv welch encoding(LZW) algorithm
参考文献(Reference):
［1］HALLBACH T H. 264 Video Compression Standard［C］// Proceedings of 6th Nordic Signal Processing Symposium, Bergen, Norway,2003：1-10.
［2］LE G D. MPEG: A Video Compression Standard for Multimedia Applications［C］//Comm. ACM,1991:46-58.
［3］JOCH A, KOSSENTINI F, NASIOPOULOS P. A Performance Analysis of the ITU-T Draft H.264 Video Coding Standard［C］. Proc. 12th Int. Packetvideo Workshop, Pittsburgh, PA,2002.
［4］ZIV J, LEMPEL A. A universal algorithm for sequential data compression ［J］. IEEE Transactions on Information. Theory,1977,23(3):337-343.
［5］BASSIOUNI M, MUKHERJEE A, RANGANATHAN N. Enhancing arithmetic and tree-based coding ［J］. Inform. Processing Manage,1989,25(3):293-305.
［6］HO S, LAW P. Efficient hardware-decoding method for modified Huffman code［J］. Electronics Letters,1991,27(10):855-856.
［7］HUFFMAN A. A method for the construction of minimum redundancy codes［J］. Proceedings of the Institute of Radio Engineers,1952,40(9):1098-1101.
［8］NELSON MARK. LZW Data Compression ［EB/OL］.[1989-10-01]. http://marknelson.us/1989/10/01/lzw-data-compression/.
［9］HENRIQUES S, RANGANATHAN N. A Parallel Architecture for Data Compression［C］. Proc. 2nd IEEE Symp. Parall. Distrib. Process., 1990.
［10］SU Chau-chin, YEN Chenq-fan, YO Jang-chuang. Hareware Efficient Updating Technique for LZW CODEC Design ［C］. 1997 IEEE International Symposium on Circuit and Systems, Hong Kong, 1991.
［11］LIN Ming-bo, LEE Jang-feng, JAN GE. A lossless data compression and decompression algorithm and its hardware architecture［J］. IEEE Transactions on Very Large Scale Integration(VLSI) Systems,2006,14(9):925-936.