基于FPGA的实时无损数据压缩系统设计

摘要：针对某些特殊的测试实验，既要求测试系统微体积、低功耗，还要求记录大量数据的问题，提出基于FPGA的数据压缩解决方案。介绍了LZW压缩算法的基本理论及其用FPGA硬件实现的方法。大量的实验表明，系统工作稳定，压缩速度快(8 MB／s以上)，对实测数据的压缩效果好(25％左右)、工作时电流小(37 mA)，实现了速度、性能、功耗三者的统一。
关键词：FPGA；数据压缩；LZW算法

引言
    在工业生产和科研中，通常要对信号进行长时间高速采样，会产生大量采样数据。在一些特殊环境下，受体积和功耗的限制，不能添加过多存储器，需要引入数据压缩技术来解决。软件压缩算法的运算量较大，需要很高的CPU运算速度和数据缓存空间，所以软件压缩一般应用
在对时间要求不高的非实时压缩场合。而对运行速度有特殊要求的情况下，对数据的实时压缩一般都要用硬件实现。有损压缩之后数据进行重构，与原来的数据有所不同。多数数据采集系统因被测对象的不确定性，需要采用无损数据压缩。由于LZW无损压缩算法具有自适应特性，在对信号统计特性不明确的情况下仍然有较好的压缩效果。结合FPGA的高集成度、低功耗、灵活性及并行运算的特性，该设计用FPGA硬件实现LZW算法，以提高系统的实时压缩能力。

1 LZW算法简介
    LZW算法是一种基于字典的压缩算法，由Lemple、Ziv、Welch三人共同创造。该算法在数据的压缩过程中会根据输入的数据动态地建立一个字典，后续输入的数据都会在这个字典中匹配查找，根据查找是否成功决定压缩编码的输出。该算法的巧妙之处在于，压缩过程中动态建立的字典不需要与压缩数据流一道进行传输和存储。在对数据进行解压时，也能够通过压缩数据流重新建立一个字典，来完成解压缩。算法粗略的描述如下：
   
   
    算法首先进行字典的初始化。然后输入第一个字符数据赋给变量String(S)。数据逐个输入压缩器中，并赋给变量Character(C)。s和C生成一个索引，与字典中的词条数据进行匹配：如果匹配成功，将S和C的编码值赋给S，继续进行下一轮的匹配；如果匹配失败，则将S输出，将S和C的编码值存入字典，并且将C的值赋给S，这一过程一直进行直到结束。最后输出S，输出结束标志。
    由算法描述可见，LZW算法过程并不是很复杂，能够得到较快的压缩速度。并且其在对数据特征并不了解情况下，也能有较好的压缩效果。同时，其对应的解压缩算法也不复杂，解压速度也优于其他一些算法。

2 LZW算法的FPGA实现
    CycloneII是Altera公司推出的新一代低成本系列FPGA器件，选用CycloneII系列的EP2C5T14418芯片来实现数据压缩。这款芯片有4 608个逻辑单元、26块M4K RAM块、13个嵌入式乘法器、2个锁相环，用户I／O引脚数目为89，完全能够满足设计对存储器容量以及逻辑功能的要求，并且有一定余量，便于功能扩展。设计采用Quartus II为FPGA器件软件开发平台，用VHDL+原理图的混合输入方式进行层次化描述。系统的整体框图如图1所示。采集到的数据经过压缩后存储到外部存储器，再读入计算机，用专用软件对压缩数据进行解压还原，对原始数据进一步分析处理。

    整个设计的核心是压缩算法的实现。FPGA设计过程中模块划分非常重要，好的模块划分能够大大减少逻辑所消耗的面积并优化功能的时序关键路径。具体到LZW算法的FPGA实现，划分了10个大模块，各个模块相互之间的连接如图2所示。图中名字相同的箭头，表示是连接在一起的。为了使框图看起来比较清晰，图中省略了一些控制信号的连接。状态机控制模块(M5)是整个压缩模块的时序控制中心，根据其他模块反馈给它的信号，判断压缩的运行状态，从而控制其他各个模块的运行。

    用FPGA实现LZW算法要解决以下几个问题：
    ①压缩过程中字典的缓存问题。因为所有数据处理和传输工作都是由FPGA完成，且考虑到实时压缩速度，字典的缓存使用FPGA内部的RAM资源。
    ②字典的建立与更新问题。字典的建立使用FPGA片内资源来完成，大容量字典虽然会提高压缩比，但必须考虑到FPGA内部的资源量。因此选用9位的定长编码方式对数据进行处理。
    ③压缩后输出数据流传输和存储问题。由于压缩后是9位的数据流，不利于数据的存储，因此将9位的数据转换成8位的数据流进行传输和存储。
3 系统测试及性能分析
    首先测试LZW算法模块能否正确无误地压缩数据。先由上位机发送数据给FPGA，FPGA压缩数据并写入SRAM存储器。压缩结束后，上位机读取SRAM中的数据并存为一个文件，最后再将这个文件与用软件压缩的结果作比较，来判断结果正确与否。图3是压缩原文件和解压后文件以十六进制形式对比后的结果，从图中下方框中的信息可知，两个文件的大小都是248 714字节，0字节差异，完全匹配。为了提高测试的全面性，避免出现因为偶然而造成的个别功能死角没被测到，利用格式各异的数据文件进行了大量的压缩结果对比实验，最终实验结果表明软硬件压缩的结果是一致的，并且解压后与源文件也是一样的，说明LZW数据压缩模块实现了功能上的要求。

    然后对压缩模块的压缩率进行测试。整个设计最初的定位是应用于微体积、微功耗的测试系统中，现选取了实验室里一些实测数据(图4～6)，对其分别用LZW与WinRAR进行压缩实验。WinRAR是一种商业的无损压缩软件，使用的是混合压缩算法，可根据需要向计算机申请内存作为哈希字典，字典大小可达4 MB。压缩后的最终结果如表1所列。表中的压缩率是按压缩后的数据量除以压缩前的数据量计算的，压缩率数值越小表明压缩效果越好。

    从表中可以粗略看出以下两点：
    ①同一压缩算法对同一类数据压缩效果相差不多，但同一压缩算法对不同类的数据压缩效果相差较大。
    ②LZW压缩算法的压缩性能低于商业软件WinRAR，并且这种压缩性能对不同类的数据的表现也不尽相同。
    从上表可以看出，所设计的算法对某些类型的数据的压缩效果还是非常显著的。虽然从压缩率上来说，LZW不如WinRAR出色，这是由于LZW算法要比使用混合算法的winRAR简单，同时还受到在FPGA器件中构造的哈希字典容量大小的限制。但LZW的优点也在于其算法简单，在对同一数据文件进行压缩时，速度上LZW比WinRAR要胜出一筹，这个速度特性在实时压缩时尤为重要。

结语
    介绍了一种用FPGA实现的数据压缩系统。通过大量测试验证，结果表明系统能够正确无误地工作，压缩时的最大数据吞吐量在8 MB／s以上，对实测数据压缩率最高可达13．70％，压缩效果显著，大大减少了对存储空间的要求，实现了压缩性能与压缩速度的统一。同时，当FPGA工作在主频为24 MHz，A／D采样频率在1 Msps时，整个电路的供电电流只有37 mA，满足了测试系统低功耗的要求。若用外部RAM存储器实现LZW字典，将能大幅度地扩大字典容量，显著改善数据的压缩效果。