《机电工程》杂志,月刊( 详细... )

中国标准连续出版物号 ISSN 1001-4551 CN 33-1088/TH
主办单位浙江省机电集团有限公司
浙江大学
主编赵 群
副 主 编唐任仲、罗向阳(执行主编)
总 经 理罗向阳
出 版浙江《机电工程》杂志社有限公司
地 址杭州市上城区延安路95号浙江省机电集团大楼二楼211、212室
电话Tel+86-571-87041360、87239525
E-mailmeem_contribute@163.com
国外发行中国国际图书贸易总公司
订阅全国各地邮局   国外代号M3135
国内发行浙江省报刊发行局
邮发代号32-68
广告发布登记证:杭上市管广发G-001号

在线杂志

当前位置: 机电工程 >>在线杂志

Lempel-Ziv二叉树搜索算法的VLSI实现

作者:侯宁宁,沈海斌 日期:2007-08-31/span> 浏览:3499 查看PDF文档

                                               Lempel-Ziv二叉树搜索算法的VLSI实现*
                                                                侯宁宁,沈海斌
                                   (浙江大学 超大规模集成电路设计研究所,浙江 杭州 310027)

摘 要:Lempel-Ziv压缩算法的自分割机制是算法的核心思想,可以将其转换成二叉树搜索结构,以适于硬件实现。基于RAM字典设计出的Lempel-Ziv二叉树搜索算法VLSI实现方案,是把一个大的RAM作为二叉树节点的存储介质,通过一个周期内对RAM的局部访问完成对二叉树一个深度的搜索。此VLSI实现有较高的数据处理速率和较小的面积,并已经在一款数据处理芯片中得到应用。
关键词:Lempel-Ziv压缩算法;二叉树搜索;超大规模集成电路


                                   VLSI implementation of Lempel-Ziv binarytree search algorithm
                                                               HOU Ningning, SHEN Haibing
                                (Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China)

Abstract: Selfsegment is the basic idea of LempelZiv compression algorithm. The algorithm, can be converted into a dictionary that consists of binarytree searching structure. The VLSI implementation of LempelZiv binarytree search was based on a RAM dictionary that used a large RAM as a medium which can store the binarytree nodes, and implemented the tree search by accessing the word of RAM. The result shows that the implementation has a higher throughput and lower area. The module has been applied in a data process chip.
Key words: Lempel-Ziv compression algorithm; binarytree search; very large scale integration (VLSI)

参考文献(Reference):
[1]ZIV J, LEMPEL A. A universal algorithm for sequential data compression[J].Information Theory,1977,23(3):337-343.
[2]ZIV J, LEMPEL A. Compression of individual sequences via variablerate coding[J].Information Theory,1978,24(4):530-536.
[3]SCHNEIER B.应用密码学[M].北京:机械工业出版社,2001.
[4]RUKHIN A, SOTO J, NECHVATAL J, et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications[S]. NIST Special Publication 800-22(with revision dated December 2000).
[5]MUKHERJEE A, ACHARYA T. VLSI algorithms for compressed pattern search using tree based codes[C]//Application Specific Array Processor (ASAP). Strassbourg[s.n],1995:133-136.
[6]LAI Y K, CHEN K C. A novel VLSI architecture for LempelZiv based data compression[C]//The IEEE International Symposium on Circuits and Systems (ISCAS). Geneva [s.n] ,2000:617-620.



友情链接

浙江机械信息网