基于FPGA的PPMd無損數(shù)據(jù)壓縮算法設計與實現(xiàn).pdf

1、隨著互聯(lián)網(wǎng)的快速發(fā)展，數(shù)據(jù)呈現(xiàn)指數(shù)級增長，有限的網(wǎng)絡帶寬和匱乏的存儲資源成為數(shù)據(jù)處理的瓶頸。數(shù)據(jù)壓縮是在不丟失有效信息的前提下，縮減數(shù)據(jù)量以減少存儲空間、提高數(shù)據(jù)傳輸和處理效率的技術方法。然而，現(xiàn)有文本壓縮算法多采用軟件架構實現(xiàn)，并順序執(zhí)行于中央控制單元（Central Processing Unit，CPU），未考慮壓縮算法的功耗和并行化。FPGA作為一種邏輯性強、速度高、功耗小以及靈活性強的高性能硬件平臺，為壓縮算法提供了新的運行環(huán)

2、境，減少其對計算機資源的依賴，拓寬壓縮算法的應用范圍。
　　本文重點討論部分匹配預測模型d方法（Prediction by Partial Matching method d，PPMd）在FPGA平臺上的實現(xiàn)。PPMd算法通過建立上下文統(tǒng)計模型，記錄已壓縮數(shù)據(jù)流4階上下文字符信息和頻度信息，根據(jù)存儲信息預測待壓縮數(shù)據(jù)流中出現(xiàn)各個字符的概率，最后將預測概率值運用區(qū)間編碼器編碼。算法實現(xiàn)的上下文索引樹更新過程過于復雜，占用內(nèi)存空間大，

3、不利于并行，而FPGA平臺適合并行度高的算法運行。因此需要調(diào)整算法架構以適應并行化，提高算法在FPGA平臺上的執(zhí)行效率。
　　本文主要從查詢和更新上下文索引樹兩個方面做了并行架構設計。各階層查詢操作不存在串行執(zhí)行的聯(lián)系，在FPGA內(nèi)部實現(xiàn)5個階層并行查詢；上下文更新操作包括節(jié)點信息的更新和后繼字符信息的更新，將各階層更新操作分離，獨立執(zhí)行，實現(xiàn)部分階層更新操作并行執(zhí)行；修改逃逸字符概率預測模塊，將逃逸字符概率預測和更新過程提前，根

4、據(jù)匹配結(jié)果回退更新操作的機制，降低了逃逸字符概率預測模塊的時鐘延遲；增加字符對應節(jié)點已建立的標志位，減少讀寫DDR的次數(shù)；最后修改了上下文索引樹的存儲結(jié)構，將字符和字符的頻度信息與指向下一階層節(jié)點的指針信息分離存儲，每次字符匹配查詢時，讀寫DDR的數(shù)據(jù)量減少為原來一半。
　　本設計最終實現(xiàn)了完整的壓縮算法IP核，包括輸入輸出模塊、預測更新模塊、編碼模塊以及主控制模塊，各個模塊之間實現(xiàn)了較高的并行度。本文在Atlys Spartan