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

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

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

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

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