一種基于FPGA的Deflate壓縮算法研究與實現(xiàn).pdf

1、FPGA技術已經(jīng)取得了巨大進步，F(xiàn)PGA芯片在容量和速度上都達到了較高的水平，現(xiàn)在已經(jīng)有許多學者研究如何使用FPGA完成對應用程序的加速。Deflate算法是無專利保護的可以自由使用的無損壓縮算法，一方面用歷史數(shù)據(jù)的指針來代替輸入數(shù)據(jù)，另一方面通過哈夫曼編碼對替換后的數(shù)據(jù)再次壓縮。Deflate壓縮由Deflate編碼和哈夫曼編碼兩部分組成。哈夫曼編碼是經(jīng)典的信息編碼算法之一，可以應用到各種領域中，目前已經(jīng)有許多的研究哈夫曼編碼的硬件實

2、現(xiàn)。而Deflate編碼方面，雖然也存在許多研究，但是字典窗口大小都比較小，這極大地影響了硬件實現(xiàn)的壓縮性能。
　　 本文對FPGA及壓縮算法做簡要介紹，對Deflate的原理及性能進行分析。在分析的基礎上，采用脈動陣列方法，在芯片110T FPGA上實現(xiàn)Deflate壓縮算法的硬件加速，主要工作如下：
　　 1、本文研究了不同的分塊壓縮、以及字典采用的窗口大小對編碼性能的影響。研究發(fā)現(xiàn)，為了進一步發(fā)揮硬件的并行性，硬件

3、系統(tǒng)可以同時實現(xiàn)多路編碼模塊，對同一個文件進行分塊壓縮或同時壓縮不同的文件。其中，前者可以加速單個文件的壓縮過程，后者可以提高系統(tǒng)的整體吞吐率。在使用分塊壓縮時，本塊無法使用其它塊的歷史信息，所以當字典窗口大小小于32K的時，壓縮效果降低嚴重。因此本文提出一種基于FPGA的窗口大小為32K的Deflate壓縮算法的硬件系統(tǒng)設計。
　　 2、本文研究了不同的最大匹配長度對編碼性能的影響。Deflate編碼階段是整個壓縮過程的核心部

4、分，研究發(fā)現(xiàn)最大匹配長度在16時，能較好地完成對測試集的壓縮。因此為了節(jié)約開銷，在不過分損失性能的前提下，本文最終確定采用最大匹配長度為16的硬件實現(xiàn)方案。
　　 3、由于Deflate壓縮算法是一種結合哈希表的壓縮算法，會產(chǎn)生一定程度的哈希表膨脹的問題。為了解決該問題，提出一種了基于改進后的循環(huán)存儲的哈希表實現(xiàn)方法，避免了窗口的移動。該方法能在不移動窗口內(nèi)數(shù)據(jù)的前提下，實現(xiàn)對哈希表的截斷。
　　 通過對上述設計進行的性