資源描述：
《試論一種基于fpga的deflate壓縮算法研究與實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、桂林理工大學(xué)碩士學(xué)位論文一種基于FPGA的Deflate壓縮算法研究與實現(xiàn)姓名：孫圣申請學(xué)位級別：碩士專業(yè)：計算機應(yīng)用技術(shù)指導(dǎo)教師：程小輝20100401摘要FPGA技術(shù)已經(jīng)取得了巨大進步，F(xiàn)PGA芯片在容量和速度上都達到了較高的水平，現(xiàn)在已經(jīng)有許多學(xué)者研究如何使用FPGA完成對應(yīng)用程序的加速。Deflate算法是無專利保護的可以自由使用的無損壓縮算法，一方面用歷史數(shù)據(jù)的指針來代替輸入數(shù)據(jù)，另一方面通過哈夫曼編碼對替換后的數(shù)據(jù)再次壓縮。Deflate壓縮由Deflate編碼和哈夫曼編碼兩部分組成。哈夫曼編碼是經(jīng)典的信息編碼算法之一，可以應(yīng)用
2、到各種領(lǐng)域中，目前已經(jīng)有許多的研究哈夫曼編碼的硬件實現(xiàn)。而Deflate編碼方面，雖然也存在許多研究，但是字典窗口大小都比較小，這極大地影響了硬件實現(xiàn)的壓縮性能。本文對FPGA及壓縮算法做簡要介紹，對Deflate的原理及性能進行分析。在分析的基礎(chǔ)上，采用脈動陣列方法，在芯片110TFPGA上實現(xiàn)Deflate壓縮算法的硬件加速，主要工作如下：1、本文研究了不同的分塊壓縮、以及字典采用的窗口大小對編碼性能的影響。研究發(fā)現(xiàn)，為了進一步發(fā)揮硬件的并行性，硬件系統(tǒng)可以同時實現(xiàn)多路編碼模塊，對同一個文件進行分塊壓縮或同時壓縮不同的文件。其中，前者可
3、以加速單個文件的壓縮過程，后者可以提高系統(tǒng)的整體吞吐率。在使用分塊壓縮時，本塊無法使用其它塊的歷史信息，所以當(dāng)字典窗口大小小于32K的時，壓縮效果降低嚴(yán)重。因此本文提出一種基于FPGA的窗口大小為32K的Deflate壓縮算法的硬件系統(tǒng)設(shè)計。2、本文研究了不同的最大匹配長度對編碼性能的影響。Deflate編碼階段是整個壓縮過程的核心部分，研究發(fā)現(xiàn)最大匹配長度在16時，能較好地完成對測試集的壓縮。因此為了節(jié)約開銷，在不過分損失性能的前提下，本文最終確定采用最大匹配長度為16的硬件實現(xiàn)方案。3、由于Deflate壓縮算法是一種結(jié)合哈希表的壓縮算
4、法，會產(chǎn)生一定程度的哈希表膨脹的問題。為了解決該問題，提出一種了基于改進后的循環(huán)存儲的哈希表實現(xiàn)方法，避免了窗口的移動。該方法能在不移動窗口內(nèi)數(shù)據(jù)的前提下，實現(xiàn)對哈希表的截斷。通過對上述設(shè)計進行的性能分析可以得出，該設(shè)計具備兼顧單個文件的壓縮速度和系統(tǒng)整體吞吐率等優(yōu)勢。同時，該方案所實現(xiàn)的系統(tǒng)在使用110TFPGA芯片時可以工作在200MHz，相對于3GHz的Xeon處理器有2．4倍的加速比。關(guān)鍵詞：FPGA；Deflate；壓縮算法；哈希表AbstractAbstractFPGAtechnologyhasmadetremendouspro
5、gress，thecapacityandspeedofFPGAchipshavereachedahigherlevel，andalargenumberofscholarsarestudyingtheapplicationaccelerationcapabilityofFPGA．Deflateisanopatentprotectionlosslesscompressionalgorithmthatcanbefreetouse，anditcompressdatabymeansofontheonehandwiththeinputdatarepla
6、cedbyapointertothehistoricaldata，ontheotherbyHuffmanencodingofthedataafterthereplacement．DeflatealgorithmismadedupwithDeflateencodingandHuffmanencoding．HuffmanencodingisoneoftheclassicinformationencodingalgorithmswhichCallbeappliedtoavarietyoffields，andtherearealreadyaloto
7、fresearchonthehardwareHuffmanencoding．AlthoughtherearealotofresearchonhardwareimplementationofDeflateencoding，buttheirdictionarywindowsizeisrelativelysmall，whichwouldbeakillerofthethroughputofthehardwareimplementation．ThispaperintroducesFPGAandCompressionAlgorithmbriefly，a
8、ndanalyzestheprincipleandtheperformancesoftheDeflatealgorithm．BythewayofSystolicarrayappr
