0 引言
遥测数据种类繁多、数量庞大，给遥测系统带来了巨大的处理压力，而遥测数据的冗余度也很大，统计表明标准遥测系统中传输的数据冗余度达到90%以上[1]。为了降低信号空间，缓解数据处理压力，在遥测系统中采用数据压缩技术成为必然，而选择一个好的数据压缩算法，会起到事半功倍的效果。LZW压缩算法以其编码简单、适用广、易于软硬件实现等特点成为数据压缩算法的首选。但遥测数据数据量大，通用的LZW算法并不能取得良好的压缩效果，其缺点在于传统字典的更新方式和字典的查找方式影响数据的压缩效果。针对存在的这些问题，本文提出了LZW算法的优化方法，并对优化算法进行验证分析。实验结果表明，该优化方法提高了系统的压缩速率和压缩比，达到遥测数据压缩系统的指标要求。
1 LZW算法基础理论
LZW是一种基于字典编码的算法。字典编码就是把先输入的“前文”编为字典，用来指代后输入的重复的“下文”，减少重复性的输出，从而达到数据压缩的目的[4]。LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个字典，然后用字典中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。但应该注意到，这里的字典不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的字典[5]。其压缩过程为编码器逐个输入字符并累积成一个字符串I，每个输入字符x首先串接在I后面，然后在字典中重新查找字符串I，找到I则继续取下一个字符串接在I后面继续查找过程；否则将其存入字典，输出指向I的指针，预置I为x，取下一个字符……。算法流程如图1所示。
2 传统LZW算法压缩方法的分析
假设母节点、索引、字符的长度都为 10 位，即检索地址指针数据长度为 10 位，则字典节点的个数为 210，称这个字典的大小为 1 K。相对于压缩数据量而言，字典的空间往往小得多，因为受硬件条件、算法复杂度和实现速度等因素的限制。通常由于压缩数据任务较大，几K大小的字典也很快会填满，传统LZW算法中当字典填满时常采用以下处理方式：(1)停止更新字典。(2)将字典清空，用来重新更新。(3)引用次数少的删除。
而这三种方式会带来如下影响：停止更新字典会使字典对之后的输入数据失去适应性，从而导致压缩效果差；由于字典由空至满是字典慢慢适应输入数据的过程，将字典清空，重新填写会延长字典对被压缩数据的适应时间，影响压缩效果；删除被引用次数为0或后续出现频率较少的词条，保留被引用次数大于0或后续出现频率较高的词条。虽然会提高压缩比，但复杂的字典管理对硬件资源的占用和压缩时间的消耗是得不偿失的。
传统LZW算法中的查找字典的方式为顺序查表。当需要处理的数据任务量大时，会导致生成的字典项较多，严重降低查找字典的速率。
若只采用顺序查表，取字典大小为4 K，则处理4 KB的数据的最大查找长度约为4 096×4 097/2=8 390 656。假设FPGA查找一个词条需要4个系统时钟周期，则最坏情况处理4 KB数据需要查找8 390 656×4=33 562 624个时钟周期；字典填满后若清空，以4个时钟周期的单位清零为例，则还需要（4 096-256）×4个时钟周期，总共用时33 577 984个时钟周期。以100 MHz的时钟为例，则系统处理4 KB数据的最大时间为335.78 ms，处理速率约为11.91 KB/s。查找单个词条的最大时间为（4 096-256）×4个时钟周期，为153.6 ?滋s。而FPGA对遥测信号的采样率为32 kHz，量化精度为8 bit，采样通道数为6，则压缩系统的输入数据速率为192 KB/s。显然采样这样的查字典方式的压缩算法速度过慢，不能满足实时压缩需求。
3 LZW算法的优化设计
3.1 字典大小的设计
字典的大小对算法的执行速度和压缩比有影响。过小的字典很快会被填满，且由于存储的字符串少，数据匹配效果差，影响压缩比。过大的字典可能会增加查字典的时间，影响了压缩速度，重要的是大容量字典耗费的存储空间也大，要充分考虑FPGA芯片内部块RAM资源。
在计算机上通过软件算法试验找出合适的字典大小，再考虑算法的硬件实现速度。软件实验设计的字典大小必须在硬件的可接受范围。取128 KB的遥测数据作为压缩数据源，分别设2 K、4 K、6 K、8 K、16 K、32 K的字典空间大小，实验结果如表1。随着字典的增大，压缩比都有一定的增大，对表1进行压缩比-字典绘图如图2所示。字典大小为2 K～4 K时压缩比增长率较大，字典大小为4 K～16 K区间字典增长率放缓。
从图中可以看到4 K字典或8 K字典才是合理的选择。由于FPGA还要完成其他工作，考虑到整个系统工作量，将其设置为4 K字典。
3.2 查找字典的方式优化
查找字典的方式对压缩和解压的速度有很大的影响。为了加快查找字典的速度，保证压缩速率，对查找字典的方式进行优化，采用多次散列法作为查找字典的方式。根据散列表思想，通过建立散列函数index=f(K)，在字典的存储位置index和它的关键字K之间建立一个确定的关系，使这些关键字与字典中相应的存储位置一一对应。图3为采用散列表结构的字典检索过程示意图。
压缩时采用的散列函数为：
其中：currentchar为当前输入数据，prechar为前一个编码数据，offset为偏移量，tab_size为散列表长，即字典地址为当前输入数据左移一位再与前一个编码数据相异或的值。当散列表中地址产生冲突时，字典地址用式(3)计算，如果该式中字典地址小于0,则用式(4)计算字典地址。
利用MATLAB软件对采用不同次数散列的压缩算法进行测试，结果如图4所示。为了测试结果更准确，每种查表方式都经过多次测试取平均压缩时间。
从图可看出，在散列次数达到15次以上时，压缩速度有较大的提高；散列次数从15～40时，压缩速度并不总是提高，而是稍有波动。原因如下:
(1)与信号源的特性及散列函数有关。
(2)由于程序设计为多次散列后出现“冲突”则采用顺序方法查表，散列方法查过的位置都有可能被重复查找，散列次数越多，可能出现的重复查找次数就越多，这就增加了一定的压缩时间。
由此可见，散列次数并不是越多越好，由试验结果来看可以选择25~40次之间。从纵向角度来看，在同等条件下，遥测数据比随机数据压缩要快。这是因为随机信号源的各个字符的出现概率几乎相等，字符间相互独立，冗余度极小，这就会使程序更频繁地在查字典和写词条，平均处理一个字符的时间较长。由此可以把对随机数据的压缩时间估算为实际压缩的最大时间。
3.3 字典更新方式的设计
下面通过软件仿真比较几种不同的字典更新方式的压缩效果，从表2中可以看到不能在提高压缩比的情况下同时提高压缩速率，意味着压缩比满足情况下，压缩速率受到制约。所以将这几种字典更新方式的优点综合起来，即当字典没有填满时就将字典全部清除，重新建立字典，这样可以同时提高压缩比和压缩率，并有效地避免了散列地址的冲突。
4 实验结果分析
根据上述优化设计方法对FPGA的LZW压缩算法进行改进，设计查字典散列次数最大为25次，利用Modelsim软件仿真程序，结果如图5所示。从图5可以看出，改进后的压缩算法没有出现长时间的查表时间，程序压缩字符的时间较为均匀。仿真结果表明，当仿真周期为10 ns(100 MHz时钟)时，硬件程序压缩64 KB遥测数据用时24.785 ms，平均处理速率约为2 582.2 KB/s；压缩64 KB的随机数据用时83.624 ms，平均处理速率约为765.3 KB/s。这两个速度都远大于遥测数据输入流速率192 KB/s。
通过对LZW算法的分析，总结了算法优化：字典大小设计、表方式设计和字典分别针对这两个优化点，以MATLAB软件为主、Modelsim软件为辅做仿真实验，为程序优化、提高系统压缩性能提供依据。