基于CAM字典的LZW算法的实现.pdfVIP

学兔兔 总第47卷 第535期 电测与仪表 Vo】．47 No．535 2010年 第07期 Eleetrical Measurement Instrumentation Ju1．2010 基于CAM字典的LZW算法的实现 朱宝峰，景海涛，王立欣 (哈尔滨工业大学 电气工程系，哈尔滨150001) 摘要：在进行LZW压缩算法的过程中，需要一个可以存储数据的字典。本文介绍了一种构建CAM压缩字典的方 法，基于寄存器加比较器的结构构建了字典，并且用流水线技术对字典进行了优化，字典内的查找可以在三个 时钟周期内完成。最后，使用该字典实现了LZw压缩算法与解压缩算法。 关键词：FPGA；CAM；流水线技术；LZw 中图分类号：TP30 文献标识码：B 文章编号：1001—1390(2010)07—0069—05 The Realization of LZW Algorithm Based on CAM Dictionary ZHU Bao—feng，JING Hai—tao，WANG Li-xin (Harbin Institute of Technology，Harbin 1 5000 1，China) Abstract：In the process of LZW algorithm．we need a dictionary for storing data．This paper presents an approach to build a CAM dictionary；it used registers and eomparators on FPGA．Furthermore，it optimized this CAM dictionary by pipeline technology．It can complete the search within three clock cycles．At the end of this paper，it realized IZW compression and decompression algorithms by this CAM dictionary． Key words：FPGA，CAM，pipeline，IZW 0 引 言 1．1 CAM字典基本单元的结构 LZw压缩算法是一种通用的无损压缩方法，该压 本设计的CAM字典基于寄存器+比较器结构，寄 缩算法是根据其发明人Lempel、Zif、Welch名字的首字 存器用来存储数据，输人数据与寄存器中存储的数据 母命名的。其不同于费诺编码、霍夫曼编码和算术编 通过比较器进行比较，将匹配结果输出。 码，使用时不需要对信源进行概率统计；也不同于游 图l是用典型的门电路实现了的该结构。datatag 程编码，它既可以对重复字符编码，也可以对不同但 与寄存器中的数据data进行比较，通过与门和或门组 重复出现的字符串进行编码…。内容可寻址存储器 成的两级逻辑电路将比较结果高电平送出到match (CAM)是一种新型的存储器，它的高速、并行、易扩展 端。 和实现的灵活性使它一出现就得到人们的重视。CAM 在高速数据采集过程中，基于对速度的要求，往 基于内容寻址，通过硬件电路实现快速匹配[21。 往需要提高设计芯片稳定运行时所能达到的最高时 在实现LZw压缩与解压缩算法的时候，需要构建