无损压缩算法在存储测试系统中的应用

　　存储测试系统是为完成特殊环境下测试而设计的电子物理系统,它可在高温、高压、强冲击振动、高过载等恶劣环境下自动完成被测信息的实时采集与存储记忆[1]。在某些星载、弹载测试系统中，测试环境恶劣、测试时间长，所需记录的数据量较大。但测试装置受到体积的限制,要在现有存储容量基础上获取更多的信息,就需要进行相关的数据处理。数据压缩是减少数据量的有效手段之一。数据压缩通常分为有损压缩和无损压缩两大类。为准确恢复出原始数据并结合测试数据的特点，本文选用游程（RLE）和LZW两种无损压缩算法对数据进行组合压缩。
　　
　　1、数据压缩理论
　　
　　存储测试系统作为一种信息采集系统，目的是向使用者传递信息。由于A/D转换的位数是有限的，所以信息采集系统只能产生有限的数据，可以把数据采集系统看作是一种离散信源。根据香农信息论[2]，某离散消息xi所携带的信息量：　　
　　平均信息量也称为信息熵，是在采用无损压缩时所能达到的压缩的zui小极限。
　　
　　实际上，消息序列的符号间往往还存在着一定的统计相关性[3]，这将使得消息序列携带的信息量减少。例如，对一个标准余弦函数进行数据采集，不论采样的数据量有多大，只需要知道这个函数的幅度、频率和起始相位就可以地表示这一数据。这在具体数据中就表现为重复出现的数据串，消除这些重复串，降低数据中的统计相关性，也是数据压缩算法一般遵循的准则。实际的压缩器在设计上往往不是单独采用统计式或字典式压缩法，一般将几种算法结合起来，以达到率的压缩比。
　　
　　2、算法设计
　　
　　2.1算法选择
　　
　　在对多组实测的数据进行分析后，可以看出测试数据有一些典型的特征。图1是一典型的石油井下压力测试数据，由图可以看出,测试数据一般都具有以下特征:
　　
　　（1）测试数据幅值比较连续,相邻数据差值较小,具有很强的统计相关性。
　　
　　（2）大部分数据波动不大,只有少部分数据变化辐度较大。　　
　　针对上述的测试数据（12bit的AD转换器）大部分波动很小（高4位数据基本保持不变）,这样的大量重复数据非常适合游程压缩。对于低8bit数据,虽然相邻时刻的值不可能*相同,但其值会在测试过程中多次出现。无损数据压缩中,LZW是基于字典模型的一种压缩算法,具有自适应的特点,非常适合这种数据的压缩。表1是两种算法组合与单独使用LZW算法的对比。从表1中可以看出，采用这两种算法结合的方式对数据进行组合压缩可以获得较好的压缩效果。　　
　　2.2游程压缩算法
　　
　　游程编码（RLE）是一种相对比较简单的数据压缩技术，容易以硬件实现压缩。实现游程编码分为定长游程编码和变长游程编码两种。本文采用8bit定长游程编码，编码流程如下：
　　
　　（1）初始化计数器cnt=1，输入首字节P；
　　
　　（2）判断文件是否结束。若结束，输出P和cnt，压缩完成；若没有结束，输入次字节C，如果P=C且cnt<255，cnt=cnt+1,则重复步骤（2）；如果P≠C，则输出P和cnt，重复步骤（1）。直到压缩完成。
　　
　　2.3LZW压缩算法
　　
　　LZW算法是一种面向通用数据的即时、、简单,易于实现的一种无损数据压缩算法,不依赖于任何数据格式,具有很大的应用范围,且是基于字典模型的算法实现的关键在于字典的建立和查找。LZW算法的粗略描述如下[4]：
　　
　　InitializeTable
　　
　　STRING=getinputcharacter
　　
　　WHILEtherearestillinputcharactersDO
　　
　　CHARACTER=getinputcharacter
　　
　　IFSTRING+CHARACTERisinthestringtablethen
　　
　　STRING=STRING+character
　　
　　ELSE
　　
　　OutputthecodeforSTRING
　　
　　AddSTRING+CHARACTERtothestringtable
　　
　　STRING=CHARACTER
　　
　　ENDofIF
　　
　　ENDofWHILE
　　
　　OutputthecodeforSTRING
　　
　　OutputEnd_flag
　　
　　由算法描述可见，LZW算法逻辑过程简单，能够得到较快的压缩速度，易于硬件压缩。
　　
　　3、硬件实现
　　
　　3.1系统整体设计
　　
　　CycloneII是Altera公司推出的新一代低成本系列FPGA器件[5]，本设计选用CycloneII系列的EP2C5T144I8芯片来实现数据的组合压缩。EP2C5T144I8芯片具有4608个LE（逻辑单元）、26个M4K的RAM、13个嵌入式乘法器、2个PLL（锁相环）和158个用户I/O引脚。系统的整体框图如图2所示。传感器采集到信号后，经过模拟适配电路进行滤波、放大后进入AD转换器,由AD转换器转换输出12bit的数据流输入到FPGA进行压缩。高4bit数据进行游程压缩，低8bit数据进行LZW压缩，zui后将压缩后的输出数据流存储到外部存储器中。采集完成后，通过USB接口电路将压缩后的数据从外部存储器中读入计算机保存下来，然后用软件对压缩后的数据进行解压，还原出原始采集到的数据以便进一步进行分析处理。　　
　　3.2算法的FPGA实现
　　
　　系统的设计核心是压缩算法实现。由于游程压缩实现简单，下面重点讨论LZW算法的实现。用FPGA实现LZW算法要解决以下几个问题[6]:
　　
　　（1）压缩过程中字典的缓存。因为所有数据处理和传输工作都是由FPGA完成,字典的缓存必须使用FPGA内部有限RAM资源。（2）字典的建立与更新。字典的建立使用FPGA片内资源来完成,大容量字典虽然会提高压缩比，但必须考虑到FPGA内部的资源量。因此选用9bit的定长编码方式对数据进行处理。（3）压缩后输出数据流的传输和存储。由于压缩后是9bit的数据流，不利于数据的存储。因此需将9bit的数据流转换成8bit的数据流进行传输和存储。FPGA设计过程中模块划分非常重要,好的模块划分能够大大减少逻辑所消耗的面积和优化功能的时序关键路径。LZW算法实现划分了8个模块，各个模块相互之间的连接如图3所示。整个压缩过程都是在状态机控制模块（U5）下进行的。　　
　　3.3结果与分析
　　
　　本文对所实现压缩算法进行了综合与仿真验证,使用开发工具为Altera公司的QuartusII7.2,使用ModelsimSE6.1f仿真工具,用图4所示的字符串作为输入码流进行测试。图中datain表示输入数据,dataout表示压缩输出码流，以16进制表示，用于验证压缩的正确性。仿真结果与通过计算机软件压缩的结果*一致。如图4所示，本设计*可行。
　　
　　经过综合,算法的实现使用了20个引脚，占用了13%的逻辑单元,使用了33%的内部RAM存储容量，综合所得zui高时钟工作频率为80MHz，实时压缩速度达到8MB。表2是一组实测数据的压缩效果。
　　
　　本文介绍的在以FPGA为核心的存储测试系统,实现了数据的无损组合压缩。通过相关仿真和综合验证,压缩*，大大减少了对存储空间的要求，实现了压缩性能与压缩速度的统一。算法主体结构用VHDL语言编写,具有可移植性，可广泛地应用于各种基于FPGA的数据压缩系统中，有很大的应用价值。
　　
　　参考文献
　　
　　[1]张文栋.存储测试系统的设计理论及其应用[M].北京:高等教育出版社,2002.
　　
　　[2]吴家安.数据压缩技术及应用[M].北京:科学出版社,2009.
　　
　　[3]朱琳,罗家融,田一海.核聚变实验数据采集系统中数据压缩算法的研究[J].计算机工程,2003，2（29）:11-12.
　　
　　[4]MARKN.LZWdatacompression[EB/OL].1989.http:marknelson.us/lzw-data-compression/.1989-10-01.
　　
　　[5]AlteraCorporation.CycloneIIdevicehandbook,volume1.2007.
　　
　　[6]陈晋敏,黄春明,周军.激光雷达数据无损压缩的FPGA实现[J].计算机测量与控制,2007,15（1）:100-102.