一种易于硬件实现的LZW算法的应用

0 引言

传统的ARC算法虽然已经在遥测数据上实现了无损压缩，但其运算极其复杂，而且ARC算法特别依赖信源统计的模型，更重要的是要预先知道信源的概率分布必须通过大量的测试与分析，因此ARC算法用硬件实现起来仍然比较困难[1]。相对而言，LZW编码简单，压缩/解压速度快，压缩效果比较好，适用广、易于软硬件实现，适合实时压缩。

为了使LZW算法易于在遥测硬件压缩系统上实现，利用MATLAB仿真找出传统LZW压缩算法的不足与优化方向，从LZW压缩算法的字典空间设置、查表方式设计、字典更新方法等方面改进算法的压缩性能。尤其使用了多次散列的查表方法，并通过MATLAB仿真确定了最终采用的散列次数，极大地提高了压缩算法的执行速率。同时，根据字典使用的特点，简化了字典的结构，节省了硬件资源。最后，通过采用删除后续出现次数较少词条的字典更新方法，提高了数据压缩比。对压缩后输出的数据流进行汉明码校验，提高了系统可靠性。

1 LZW算法的选择

1.1 遥测数据压缩的可行性

遥测数据中模拟量参数根据参数的频带范围可分为缓变参数和速变参数，缓变参数的频带范围为0～10 Hz，速变参数频带范围为10～8 000 Hz。通常情况下速变参数的采样率远大于缓变参数，而且速变参数采集量也远大于缓变参数的量。实测表明，速变参数传输通道约占系统通道总量的10%，但采集的数据却占总数据量的80%左右。对速变参数的实测结果表明，速变参数具有“短期活跃，长期稳定”的特点，其活跃期占飞行过程不到20%，并分散在整个飞行过程中，这说明遥测数据中的速变参量存在较大的压缩空间[2-3]。

图1为一组遥测数据的波形及相应波形的概率分布。图1(a)为随机抽取的4 500个字节经MATLAB绘制出的波形图，图1(b)为与波形图相对应的概率分布图。从图中可以看出，这组随机抽取的遥测数据在100～150之间出现的概率最大且为非等概率分布，具有一定的压缩空间。

1.2 3种压缩算法的比较

在采集遥测数据的压缩系统工作条件下，衡量是否适合遥测硬件系统压缩编码应根据以下3点：

(1)压损比，压缩比与采用的算法有直接关系，而遥测数据属于非等概率分布相似度小，故不适合算术编码。压缩比定义如式(1)，m表示变量个数，L表示编码的平均长度，CR表示数据压缩比：

从式(1)中可以看出，变量个数越多，压缩比相对也会越大，但霍夫曼压缩编码不适合处理大批量的数据压缩[4]。

(2)信源，遥测数据不仅包含图像数据，还包含各种工况信息，例如：工作电压参数、冲击量、环境温度等，而行程编码适合图像数据的有损压缩，不适合遥测数据的无损压缩[5]。

(3)复杂度，ARC算术编码运算非常复杂，这额外增加了硬件的成本开销[6]。

综上3点所述，LZW不仅适合处理大批量数据，而且无需知道信源的数据模型，运算简单，适合实时压缩。因此从硬件上考虑，选择LZW压缩算法作为遥测硬件压缩系统的核心算法是最好的选择。

2 LZW算法的优化设计

为了使LZW算法更适用于遥测硬件上，通过对遥测数据的科学分析及软件仿真分别从字典大小、查找方式、字典更新方法三个方面对LZW算法进行优化设计。

2.1 字典大小的优化设计

本设计采用的FPGA为XC3S1400AN，其内部可使用的RAM为72K×8bit=576 Kbit，为了缩小硬件系统的尺寸，通过FPGA内部给字典分配的空间，考虑到整个系统的工作量，可为字典分配的空间为2K，4K，6K，8K，16K，32K。通过软件实验分析结果绘制的曲线图如图2所示，从图中可以看出，分配空间为2K～4K时压缩比有明显的变化，而超过4K后压缩比变化较平缓。采用母节点、目录、字符结构的字典方案，4K的字典所需的空间为2×4K×12 bit+4K×8 bit=128 Kbit。综合考虑，给字典分配的空间为4K。

2.2 查找方式的优化设计

LZW算法的关键在于字典的检索，这一步骤关系到整个压缩算法的执行速率和压缩效果，目前较为有效的检索方法是构建散列表。合适的散列函数可使散列值均匀分布，通过散列值可快速查找记录，从而缩小检索时间。

查找字典的方式对数据压缩的速率影响很大。字典空间长度为4K，若只采用顺序查表，在最坏的情况下处理4 KB的数据需查找4 096×4 097/2=8 390 656的数据长度。遥测系统晶振以100 MHz为例，查找一个词条一般需4个系统时钟周期，字典填满后若清空，则还需要(4 096-256)×4个时钟周期，所以极端情况下处理4K数据用时约为：[4 096×4 097/2+(4 096-256)×4]×10 ns≈335.78 ms，转换成速率约为11.91 KB/s，而压缩系统要求对遥测信号的采样率192 KB/s远高于该速率，显然只采用顺序查表的查字典方式的压缩算法不能满足遥测硬件实时压缩的需求。

只采用顺序查表的方法已经不能满足要求，而采用一次散列很难找到合适的散列函数使散列值非常发散。为了加快查字典的速度，保证压缩速度，考虑采用多次散列法。利用MATAB软件对采用不同次数散列的压缩算法进行测试，结果统计绘制的曲线图如图3所示。为了测试结果更准确，每种查表方式都经过多次测试后取平均压缩时间。为了更客观地分析测试结果，在相同条件下加入了随机数据压缩结果作为参考标准，图中虚线表示随机数据压缩时间与散列次数的关系，实线表示实测遥测数据压缩时间与散列次数的关系。从图中客观的分析可知，散列次数在15次以上时，压缩时间大幅度缩短;散列次数在15～40之间时，压缩时间虽稍有缩短，但有波动。总之，散列次数并不是越多越好。根据遥测数据压缩曲线图，本设计选择散列次数为25次。

仿真时钟周期为10 ns(100 MHz时钟)时，通过仿真可计算出硬件程序压缩64 KB遥测数据理论用时24.785 ms，平均处理速率约为2 582 KB/s，压缩64 KB的随机数据用时83.624 ms，平均处理速率约为765 KB/s。由于这两个速率都远大于对遥测数据的采集速率192 KB/s，所以25次散列完全可以满足压缩系统的硬件要求。

2.3 字典更新方式的优化设计

为了调试出易于硬件设计的字典更新方式，利用MATLAB绘制出了当字典首次填满时各词条的使用情况，结果如图4所示。经统计分析可知，除去字典前256个位置引用次数为0的词条数为2 529，占总词条数(4 096)的61.74%。因此可从引用次数为0的词条进行优化设计：每次字典写满后，保留被引用次数大于0而删除被引用次数为0或引用次数最少的词条，然后继续添加新的词条直到再次填满字典空间，以此进行循环更新。

通过软件仿真将3种传统的字典更新方式与优化后的字典更新方式进行压缩效果对比，得到表1的数据结果。从表中数据不难看出，优化后的设计压缩时间明显增加很多，但数据的压缩比同样得到明显的提高。

为了验证优化后的设计易于硬件压缩系统的实现，将优化后的设计应用在FPGA的压缩模块中，系统时钟为100 MHz，经软件仿真得出压缩64 KB遥测数据用时77.159 ms，平均压缩速率约为830 KB/s;压缩64 KB随机数据的时间为152.580 ms，平均压缩速率约为419 KB/s。因这两个压缩速率远大于遥测数据的输入速率192 KB/s，所以优化后的方法可以应用于遥测压缩系统的硬件设计中。

3 逻辑功能的实现

本设计的LZW压缩算法的数据结构由传统的三部分构成：母节点(parent)、目录(index)和字符(symbol)。首先，根据FPGA并行执行的特点，配置3个RAM块分别存储字典的三个部分，并用统一的地址进行读/写操作，顶层图如图5所示。

用硬件逻辑语言实现优化后的LZW算法，具体的流程图如图6所示。I表示经过压缩处理的数据串，X表示采集到的数据，P表示检索指针。优化后的LZW算法压缩过程为：

(1)逐一输入数据累积成I;

(2)取下一个数据x;

(3)在字典中检索数据串Ix。若数据串Ix在字典中，则检索成功，置I为检索地址并输入下一个要压缩的数据x;如果数据串Ix不在字典中，则检索失败，输出I在字典中的存储指针，然后在字典中存储Ix，设字典指针为p，最后置I=x并输入下一个要压缩的数据x;

(4)判断字典是否已满，满了即将字典清空。

4 结果分析

结合shannon信息论可知，信源各符号间若相互独立，则信源为等概率分布时其熵值最大，冗余度为零，因此无损压缩的本质可以理解为：使信源趋于等概率分布，降低信源的冗余度。由此理论分析，从概率上来看数据压缩后与压缩前相比概率分布图应更为平稳、均匀。为保持结论的客观性，将优化后的LZW压缩算法应用在硬件系统中，将前文随机抽取的遥测数据进行压缩对比，同样利用MATLAB软件画出压缩后的波形图与概率分布图，结果如图7所示。经对比可知，经压缩后的遥测数据概率分布呈现出明显的平滑曲线，同时表明，数据的冗余度明显降低，可压缩空间更是接近于极限。最终压缩比为1.832:1。

本设计没有从优化LZW压缩算法的数据结构入手，而且最终优化的结果仅适用于遥测硬件数据压缩系统，因此该设计存在局限性，仍然有很大的提升空间。

参考文献

[1] 凌伟.基于ARC算法的数据压缩技术与实现[J].电子技术应用，2013(8)：84-87.

[2] 刘文怡.遥测速变数据无损压缩时空性能优化设计及应用[D].太原：中北大学，2009.

[3] 刘鑫.基于遥测数据的压缩算法设计与实现[J].电子技术应用，2008，34(11)：79-81.

[4] 叶芝慧，沈克勤.信息论与编码[M].北京：电子工业出版社，2011.

[5] 陈昌主.数据压缩算法研究与设计[D].长沙：中南大学，2010.

[6] 曾尚春.SAR数据压缩算法研究[D].南京：南京航空航天大学，2007.