Design And Implementation Of FPGA-based Lossless Data Compression Using PPMd Algorithm

With the rapid increase of Internet and the exponential growth of data, limited network bandwidth and the scarcity of storage resources become the bottleneck of data processing. Data compression is a meaningful technology, by which redundant information can be eliminated without loss of useful information, reducing storage space, improving the efficiency of signal transmission, storage and processing. However, the existing compression algorithms adopt the software architecture, and process sequentially in the CPU(Central Processing Unit, CPU), without considering the power consumption and parallel. FPGA, a high-performance hardware platform with strong logicality, high speed,little power consumption and strong flexibility, provides the new operation environment for compression algorithm, reduces the dependence on computer resources and broadens the application scope of the algorithm.This paper focuses on the implementation of PPMd compression algorithm on FPGA platform. In the PPMd algorithm, the frequency and 4-order context information of compressed data stream can be recorded by establishing a context statistical model. The probability of appearance of individual characters in the data stream to be compressed can be predicted based on the stored information, and the final predicted probability is encoded using interval encoder. The update process of context index tree is too complicated and occupies large memory space. It is suitable for the algorithm with the high degree of parallelization to run on the FPGA platform. Hence the software architecture should be adjusted in parallel and it is required to improve the operation efficiency of the algorithm on the FPGA platform.This paper optimizes the algorithm in parallel from the two aspects of querying and updating the context index tree. The query operation of different layers have little mutual relations, so the five-layer query operation can be performed on FPGA platform in parallel. Including node and symbol information update, update operations is done after finishing query. These two update operations can be performed in parallel at some layers by changing the architecture of the algorithm. The escape module of the algorithm is modified and the probability of escape character is predicted in advance.The module clock delay is shielded according to rollback process of the matching result. Finally, the struct of context tree node is modified and the character and frequency information are separated with pointer information. With this change, the volume of reading and writingDDR decreases nearly by half, significantly improving the access efficiency of the DDR,and eventually reducing the delay of the query module.Finally, the complete compression algorithm IP core is realized, including input and output module, query and update module, coding module, and main control module.Through a variety of acceleration parallel execution plans, the final throughput ratio of the single core of PPMd algorithm running on Atlys Spartan-6FPGA platform is 23 Mb/s. Running PPMd compression algorithm on FPGA platform can reduce the dependence on the resources of computer such as CPU, widen the range of engineering application, and enhance the practicality of compression algrothm.