The Optimization Of LZ4 Lossless Compression Algorithm Based On FPGA

With the development of cloud computing and big data industry,there are more and more requirements in the aspect of storage space and transmitting speed of computer systems.Because of the compression speed is more than 100MBps,the new LZ4 algorithm is widely used in high speed compression applications.Concurrency and instantaneity of hardware can be used in specific application compression circuits to provide high compression speed or ratio performance without using CPU resource.In addition,hardware compression circuits are more flexible in the balance between compression ratio and compression speed.The disadvantage of LZ4 lossless compression algorithm is the lower compression ratio performance.Base on the principles of LZ4 lossless compression algorithm,this thesis present a method of compression ratio optimization and architecture of compression circuit on FPGA(Field Programmable Gate Array).The LZ4 comression circuit is consist of dictionary buffer,parallel match circuit,string partition circuit,parallel encoder,verify circuit,and pipeline controller.In order to optimize compression ratio performance,a second stage of compression base on semi-static Huffman encode algorithm is presented.It is implemented via designing pipeline circuits include statistics,sorting,tree building,code length optimizing functions.Furthermore,the cascade compression circuit provide compatible mode and optimized mode,which eliminate the conflict between compression ratio and compatible of LZ4 compression circuit.The optimized LZ4 lossless compression circuit has been tested on Xilinx KC705 development platform with 125MHz frequency.The test source files are from Calgary and Canterbury corpus.The test data has indicated that the average compression ratio(52.76%and 49.95%)and compression speed(213.09MBps and 217.93MBps)of circuit in compatible mode has reached LZ4 software level.In optimized mode,statistic length is setted to 16Kilo Bytes(KB).The circuit compression speed is 185.72MBps and 172.66MBps,and compression ratio(44.89%and 42.60%)is 14%better than LZ4 software.Compression ratio performance is improved effectively without large damage of compression speed.It indicate the flexibility of LZ4 compression circuit which balance the compression ratio and compression speed.