LZW改进压缩算法的FPGA实现

0 引言
    随着大规模集成电路的发展，在电子设备监控系统中，需要采集与处理的数据量也在急剧增加，从而数据压缩技术得到广泛应用。然而很多压缩、解压方案都是基于软件实现，其致命的弱点就是过多地消耗宝贵的CPU资源，速度慢。基于FPGA实现的压缩器因其速度快、处理能力强而获得人们的重视。现代FPGA的发展使得只用专用硬件的方式来实现压缩、解压成为可能，可以解决上述软件实现方式所存在的缺点。但在通用数据的压缩领域，基于FPGA的硬件压缩、解压方案还不多见，所以研究基于FPGA硬件实现的数据压缩技术具有很高的应用价值。
    当前数据压缩技术分为有损压缩和无损压缩，算术编码、游程编码、霍夫曼和LZW压缩是传统的数据压缩方法，属于无损数据压缩；而基于小波变换的数据压缩和基于神经网络的编码方式是近年来新发展起来的现代数据压缩方法，属于有损数据压缩。本研究主要探讨一种基于LZW算法的数据无损压缩硬件实现。

1 LZW算法及其改进算法
    LZW压缩算法在压缩的过程中自适应建立一个字典，以后的数据同字典中的数据相匹配，匹配上则输出字典的索引。由于表示字典的索引所用的比特数远小于字符的比特数，从而达到压缩的效果。这个生成的字典不需要随着压缩的数据一同传输，而是能够根据压缩的数据在解压时重新动态生成一模一样的字典。
    LZW编码原理如图1所示，在进行压缩时首先把字典中的前256(0～255)项初始为全部的256个8位字符，分别为十进制数0～255。当输入第一个字符时，总是在字典中可以找到，直到新的字符X不在字典词条中时，便将字符串IX加入到字典的第256项，以此类推。以字符串流5，6，7，8，9，5，5，6，6，7，8，9，5，…为例，表1给出了字典存储的物理结构和压缩过程中字典项的读写示意。压缩后编码输出为5，6，7，8，9，5，256，257，259，…。

    传统的LZW压缩算法采用8位数据输入，固定长度编码输出，随着字典内容的不断增多，输出编码的位数不断增加势必造成资源的浪费，也会损失压缩率。另外，由于字典的容量有限，随着压缩过程的进行，字典会被填满，若是简单的不再向字典中增加内容，那么后面的压缩率就会降低，而如果将字典全部清除重新建立字典，在字典建立初期压缩率也是很低的。针对以上不足，文献对LZW算法做以下改进：采用12位数据作为压缩输入，变长度的码字输出。
    压缩字典最多可容纳16 384个码，共分为三部分，其中0～4 095为12位输出，4 096～8 191为13位，8 192～16 383为14位。每当输出长度变化时，同时输出一个变长标识，便于解码器解码。

2 LZW算法FPGA实现
2．1 算法实现硬件结构
    LZW数据压缩算法的FPGA硬件实现，其内部功能模块划分如图2所示。

2．2 各功能模块说明
    输入／输出数据缓存模块完成FPGA所有数据传输工作，为了保证异步时钟域数据同步，使用FPGA片内的Block RAM构成一个FIFO对输入数据进行缓存。
    字典存储器模块需要存放字典项的三部分内容：字典项编码、前缀码、当前码。将存储器的容量设计为1K。采用FPGA内部宏单元lpm-ram-dp(单口RAM)设计字典存储器。
    算法实现模块要实现匹配串的查找、判断字典相应地址内容是否为空、比较字典地址相应内容是否匹配或冲突、冲突时重新生成地址、压缩编码输出控制、压缩结束控制等功能。
    外接闪存数据宽度为8位，所以压缩后输出数据位数需要转换。数据转换模块就是实现压缩后数据由13位向8位的转换。
    时钟处理与控制模块主要完成时钟的匹配与控制，对各个功能模块分配时钟，并初始化各使能端信号。
2．3 仿真结果
    清空字典存储器模块，初始化信号，将可能出现的单字符存入字典，压缩时新传续存地址为4096，新字符串输入时产生相应的哈希表地址与偏移量；然后读字典存储器相应地址的内容，如内容为空则输出输入的数据，并把相应内容存入字典，如内容匹配，则继续输入下一数据，否则(即发生冲突)产生新的哈希表地址，重新读取字典，进行判断、比较。仿真时序如图3所示。

    仿真结果：输入数据为5，6，7，8，9，5，6，7，8，9，5，6，7，…；输出数据为5，6，7，8，9，4 098，4 100，4 102，…。仿真结果与理论计算值一致。

3 结 论
    LZW算法逻辑简单，实现速度快，擅长于压缩重复出现的字符串；无需事先统计各字符的出现概率，一次扫描即可；相对于其他算法，更有利于硬件实现。本文利用FPGA实现了改进的LZW压缩算法，仿真证明其算法具有很高压缩率，适合工程的实际应用。