The Research and Design on Data Compression Algorithm

The applications of lossless data compression spread widely in communication, spaceflight, medical treatment and some other fields. Now the compression implementation realized by VLSI technology is getting more and more sights due to its more powerful processing ability. And the research on VLSI compression technology is becoming hot. This thesis mainly deals with the design and implementation of a lossless data compression core in hardware. The compression core is based on LZW algorithm. The thesis raises a special architecture of the lossless data compression core according to characteristic of the LZW algorithm. This architecture uses a parallel dictionary searching strategy which speeds up the string searching in dictionary quitely. Meanwhile, a big dictionary is split into 8 dictionaries with different size, which saves the memory space and reduces the chip area. A simulation model, which is used to prove the correctness of the function, is designed with C++ based on the architecture. Then the compression core is divided to module level and every module is described with RTL language (Verilog). In the design of the dictionary module, it use a hierarchical design methodology which make the dictionary design quite clear and save much coding effort. The configurable control register module is designed to control various function of the compression core. These configurable registers make the control subsystem and data processing subsystem apart and also is helpful for the extension of the function. The design of the compression core reflects the DFT thinking. It designs a logic BIST structure which based on the CRC16 checker. This logic BIST can help the function test at full speed. After the design of the compress core is finished, the simulation environment, which is based on the VCS simulator, is established. The design of the compression core is simulated in the simulation environment. The simulation result reveals that the compression core can compress data correctly according to the LZW algorithm. The Synplify tool is used to synthesis the RTL code of the compression core, Xilinx Virtex4 FPGA as the target FPGA. The synthesis result reveals that the resource is acceptable, the maximum frequency is 210MHz. So the total data processing ability reaches to 750Mbps, which is twenty times larger than software implementation and can compare to the other hardware compression core in market.

Alternate abstract:

数据的无损压缩在通信、航天、医疗等各个方面获得了普遍的应用。基于VLSI实现的压缩器由于其速度快、处理能力强而获得人们的重视，成为一个热门的研究领域。 本文提出了一种基于LZW算法的硬件实现的无损压缩器。根据LZW算法的特点提出了无损压缩器的体系结构。该体系结构采用了一种并行的字典搜索策略，极大的提高了字串的搜索速度。同时字典被拆分，字典宽度变长，从而节省了存储空间，减少了芯片面积。在此体系结构的基础上用C++实现了一个仿真模型，以此模型证明了功能的正确性。然后压缩器被细分到模块级，并用RTL（Verilog）描述了各个模块。其中层次化的字典模块设计策略使得字典结构清晰合理，并大大减少了代码量。在压缩器的设计中采用了可配置的寄存器来控制压缩器的功能，使得控制部分和数据处理部分明确分工，并且有利于功能的扩展。同时该压缩器体现了DFT的设计思想，提出了一种基于CRC16比较的logic BIST设计策略，有利于功能的全速测试。 在设计完成后以VCS基础建立仿真环境，将本压缩器的Verilog 代码进行了仿真。仿真结果显示，该设计的压缩器可以正确地以LZW算法实现数据的压缩。用Synplify以Xilinx的Virtex4为目标器件综合了本设计的RTL代码，证明资源占用情况是可以接受的。并且压缩器工作频率达到了210MHz，总的数据处理能力达到750Mbps。处理性能比软件实现的处理能力快了20多倍，可以同市面上主流的硬件压缩器相媲美。