实时LZW压缩算法的FPGA实现-论文.pdf

《实时LZW压缩算法的FPGA实现-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析实时LZW压缩算法的FPGA实现耿赞薄保林(中国电子科技集团公司第五十四研究所河北石家庄050081)摘要：为降低数据传输的数据量提高传输速度，提出了一种用FPGA实现Lzw无损压缩算法的设计方案。字典存储形式~_LZW算法中的关键，用内容可寻址存储器构建字典可大大提高字典查询速度。仿真分析了字典容量与压缩率间的关系，使用较少的FPGA资源就能达到较好的压缩效果。关键词：无损压缩LZW算法内容可寻址存储器FPGA中图分类号：TN958．98文献标识码：A文章编号：1007—9416(2014)0

2、4—0135—02在某工程应用中需要将前端大量的采样数据传输到后端进行与压缩流程类似，区别在于解压缩查询字典时输出的不是匹配地址处理，为实现高效快速的数据传输，可利用数据压缩技术减少数据而是匹配字符或字符串，解压缩算法可从压缩数据中重构出与压缩量和传输时间。系统要求压缩数据必须能完全恢复为原始数据，且算法相同的字典，并且压缩与解压缩都不用存储字典，易于工程实处理时间不能过长，LZw压缩算法是一种常用的无损压缩算法，具现。LZW算法充分利用了数据的重复性，只需扫描一次数据就可以有较好的实时性，本文利用FP

3、GA的高速并行处理特点，提出了一完成压缩，能够实时处理数据。种实时LZW压缩算法的实现方案。2FPGA构建CAM字典1LzW算法LZW算法的关键在于构建字典和读写操作时间。传统的LZWLZW算法使用一种类似查字典的方式来进行压缩，通常针对算法实现中多使用RAM(随机存储器)来存储字典，查找词条时需逐计算机系统中的8位ASCII字符进行压缩。基本原理是将输入的字个查询从而造成压缩时间过长。建立字典地址与输入数据的哈希函符累积为字符串，把已出现的字符串作为词条存入字典，对重复出数可提高查询速度，但为解决地址

4、冲突问题还要增加额外的开销。现的字符串输出其在字典中的位置而不是字符串来达到压缩数据本文将CAM(内容可寻址存储器)用于存储字典，CAM的原理是将的目的。输人数据与存储的数据进行比较，给出是否匹配以及匹配地址，这LZW算法流程主要是字典的维护和查询，字典包含D项词条，与LZW算法的字典查询是相符的，利用CAM构建字典简化了对字每项词条由m位前缀和n位后缀组成，后缀位宽与输入数据位宽相典的读写操作。等，且满足D=2m。压缩算法流程如下：(1)字典的前256项初始化为本文使用Virtex系列FPGA基于BR

5、AM(块存储器)的实现方法8位ASCII字符集，(2)将第一个字符作为后缀与前缀0组成待查数据来构建CAM，这种方法读写时间都只需一个时钟周期，适合存储字进行查询，必与字典初始化项中的某一词条匹配，将前缀更新为匹典。CAM16x8表示可存储16项8bit数据，实现框图如图1所示。图中配地址；(3)将下一个输入字符作为后缀与前缀组成待查数据进行RAM_Dual为BRAM，将端lzlA配置成4096项lbit数据，端EIB配置查询，如果不匹配则将待查数据作为新词条写入到字典中，将前缀成256项16bit数据

6、，RAM_Erase由8个分布式RAM构成，存储CAM输出并更新前缀为后缀的匹配地址，如果匹配则将前缀更新为匹配中每个地址已存的内容。地址，(4)依次输入字符并按上步进行处理。LZW算法的解压缩流程CAM16x8的写操作分为擦除和写入两个步骤。擦除是从RAM—Erase模块中读出地址addri中已存的数据，作为RADualWriteReadPortAPortB模块端口A写地址addra的高8位，addra的低4位为addri，数据dia写0x4096)(16x256)0表示这一地址存储的数据已清零；下一

7、时钟周期再进行写操作，将dia【0】dobD5：D]datai与addri组合为addra，数据dia写1表示这一地址已存储数据，addm[11：O]addrb[7：0]同时更新RAM_EFase中地址addri存储的数据为datai。当查询数据图1CAM16x8实现框图datam在CAM中的地址时，将datam作为RAM_Dual模块端口B的表1字典容量与BRAM数量关系读地址，可读取数据dob，将dob进行按位或运算，如为1则表示匹配，为0则不匹配，并按照one—hot形式对d0b进行解码，获得实际

8、匹容量基本CAM单元BRAM数量1024x18bitCAM16x8+CAMl6xlO128配的地址addrm。one-hot是一种数据编码方式，例~N4bit十六进制2o48xl9bitCAM16x10+CAMl6xl0256数据0x7可表示为16bit_--进制数据0000000010000000，CAM就是利4096x2ObitCAM16x10+CAM16xl0512用这种方式实现的。8l92x2lbitCAMl6xll+CAM16x1