基于FPGA的快速哈夫曼編碼設計

作者　陸哲敏 易慶陽(yáng) 楊一凡 蔣劍飛　　上海交通大學(xué)(上海 200240)

　　*“第一屆(2016-2017)全國大學(xué)生集成電路創(chuàng )新創(chuàng )業(yè)大賽全國總決賽“FPGA設計方向三等獎

摘要：針對不同的應用場(chǎng)景，給出兩種方案，一種用碼表實(shí)現，另一種用靜態(tài)編碼實(shí)現。碼表方式將題目與實(shí)際應用結合起來(lái)，針對不同場(chǎng)景給出不同的碼表快速編碼;不過(guò)考慮到無(wú)規律信號的編碼，所以通過(guò)靜態(tài)編碼使我們的作品更加具有普適性，我們還采用三位范式編碼的方式，縮短輸出周期;同時(shí)在數據輸入結束之前開(kāi)始排序，減少編碼實(shí)際占用的時(shí)間。

0 引言

　　哈夫曼編碼是基于帶權路徑最小的最優(yōu)二叉樹(shù)——哈夫曼樹(shù)的一種平均碼長(cháng)最短的編碼方式。哈夫曼編碼常用于數據的無(wú)損壓縮，尤其在衛星探測、醫學(xué)圖像處理、雷達測試系統等領(lǐng)域有著(zhù)廣泛應用^[1]。

　　以對一段長(cháng)度為256的0~9的數據進(jìn)行編碼為例，如果采用定長(cháng)編碼，則需要4位表示一個(gè)0~9的數字，一共需要4*256 = 1024位實(shí)現編碼，而如果采用哈夫曼編碼可以大大降低需要的位數。

1 算法設計

　　在開(kāi)始設計前，我們先對目前主流哈夫曼方案作簡(jiǎn)單分析：

　　1.靜態(tài)編碼：編碼速度與資源占用方面都在合理范圍內，雖然編碼速度比碼表慢，但是通用性要比碼表好;

　　2.動(dòng)態(tài)編碼：動(dòng)態(tài)編碼依據的是一棵動(dòng)態(tài)變化的哈夫曼樹(shù)，每個(gè)數據的編碼都是由它前面所有數據組成的哈夫曼樹(shù)決定的，雖然可以同步輸出編碼序列，但是對資源占用較大;

　　3.碼表方案：碼表只針對特定分布的數據可以獲得良好壓縮率，但是有著(zhù)其極小的資源占用和無(wú)需復雜運算的優(yōu)點(diǎn)。

　　經(jīng)過(guò)以上分析，我們選擇碼表和靜態(tài)編碼相結合的方式進(jìn)行編碼。在輸入完成前，對輸入序列的分布進(jìn)行判斷，如果符合碼表的分布要求，則直接由碼表編碼，加快編碼的速度，如果不符合，則進(jìn)行靜態(tài)編碼，以實(shí)現編碼速度和壓縮率的平衡。

　　為實(shí)現哈夫曼編碼，我們將整個(gè)系統分為5個(gè)模塊：統計、排序、編碼、碼表和輸出。

　　數據由數據源輸入之后，首先對其統計與排序。在整個(gè)過(guò)程中，排序進(jìn)行兩次，第一次在第251個(gè)周期，用于判斷使用碼表還是靜態(tài)編碼;第二次則根據編碼方式的不同而改變：如果使用碼表編碼，則在第256個(gè)周期開(kāi)始排序;如果使用靜態(tài)編碼，則在第254個(gè)周期排序，這是由于最后兩個(gè)權值對壓縮率影響極小，所以通過(guò)丟棄最后兩個(gè)權值信息加快編碼速度。

　　為了進(jìn)一步減小資源占用與輸出周期，編碼和碼表模塊輸出的碼長(cháng)均由3位構成，這樣設計比起4位輸出時(shí)要節省10個(gè)周期。理論支撐是出現碼長(cháng)為9的情況時(shí)，數據頻率需要滿(mǎn)足第i個(gè)數的碼長(cháng)大于前i-2個(gè)數的碼長(cháng)之和，這種情況的概率是極小的;而且即使出現碼長(cháng)為9的情況時(shí)，最大的4個(gè)碼長(cháng)——9、9、8、7也可以用8、8、8、8來(lái)近似，由于最大碼長(cháng)對應的數據的頻率很小，壓縮率的損失也很小。故碼長(cháng)為9的情況可以舍棄，所以認為碼長(cháng)在1~8之間，用3位二進(jìn)制來(lái)表示。

1.1 統計模塊

　　統計模塊的功能是對輸入的數據統計出現的頻數。設計的思想是給0到9每個(gè)數字構造一個(gè)計數器，先初始化計數器值為0，每次輸入一個(gè)數字之后其相應的計數器加1，這樣，在數據全部輸入完成后即可得到0到9這10個(gè)數字的權重。

1.2 排序模塊

　　排序模塊的功能是對已經(jīng)統計好的數據進(jìn)行排序。設計的思想是：將每個(gè)權值都兩兩比較一次，由比較結果就可以快速確定它在一個(gè)降序排列的存儲器seq中的位置。由于這些比較都是并行的組合邏輯，所以只需要讀一次比較結果，一個(gè)周期即可完成排序。

1.3 碼表模塊

　　排序模塊的排序結果作為碼表模塊選擇何種編碼方式的判斷依據，當序列接近于等概率分布時(shí)，哈夫曼編碼基本等效于等長(cháng)編碼，此時(shí)進(jìn)行靜態(tài)編碼效率較低，所以通過(guò)碼表1直接編碼;除此之外，當序列分布范圍極廣，即分布十分不均勻的時(shí)候，用靜態(tài)編碼效率也比較低，此時(shí)采用碼表2進(jìn)行編碼。兩張碼表如表1、表2所示。

1.4 編碼模塊

　　如果碼表模塊無(wú)法對輸入數據進(jìn)行編碼，則必須通過(guò)編碼模塊完成靜態(tài)編碼。

　　編碼過(guò)程是由構建哈夫曼樹(shù)和分配碼長(cháng)兩個(gè)過(guò)程組成的[4]，此模塊中我們使用到3個(gè)存儲器，一個(gè)是上文提到的seq，記錄排序好的十個(gè)數據以及各自權值;另一個(gè)存儲器是node，是由哈夫曼樹(shù)中的非葉節點(diǎn)構成的;而最后一個(gè)存儲器為result，保存整棵哈夫曼樹(shù)。

　　10個(gè)葉結點(diǎn)組成的哈夫曼樹(shù)應有19個(gè)結點(diǎn)，但是根結點(diǎn)不參與編碼，所以result只保存18個(gè)結點(diǎn)，同樣，node結點(diǎn)也只保存8個(gè)內部結點(diǎn)。

　　為了提高編碼效率，構建node存儲器和構建result存儲器是同步進(jìn)行的，而構建哈夫曼樹(shù)和分配碼長(cháng)的操作均為兩個(gè)結點(diǎn)同時(shí)操作，編碼過(guò)程也沒(méi)有選擇常規的自底向上的編碼，而是選擇了自頂向下的編碼方式，避免重復讀取內部結點(diǎn)[5]，如此下來(lái)，構造result的過(guò)程耗時(shí)10個(gè)周期，編碼過(guò)程最快只需耗時(shí)8個(gè)周期。

　　具體過(guò)程如下：

　　假設已有：降序排列的權值序列seq = {seq0, seq1, seq2, seq3, seq4, seq5, seq6, seq7, seq8. seq9}，初始化好的存儲器為node={FFH,FFH……,FFH}。

　　1)第1個(gè)周期開(kāi)始構造內部結點(diǎn)node存儲器：

　　a)依次從seqn、seqn-1、nodek和nodek+1中尋找最小的兩個(gè)值(如果權值相同，認為排前面的權值小);

　　b)將最小的兩個(gè)權值相加后放入node中;

　　c)將n、k作相應移動(dòng);

　　d重復a。

　　2)第2個(gè)周期開(kāi)始同步進(jìn)行哈夫曼樹(shù)result存儲器的構造：

　　a)依次從seqn、seqn-1、nodek和nodek+1中尋找最小的兩個(gè)值(如果權值相同，認為排前面的權重小);

　　b)將兩個(gè)最小權值依次放入result中;

　　c)將n、k作相應移動(dòng);

　　d)重復a。

　　3)第11個(gè)周期開(kāi)始編碼：

　　a)初始碼長(cháng)result[17]=result[16]=1;

　　b)根據標記位，可以知道某一個(gè)結點(diǎn)是否有子結點(diǎn)：

　　i.如果有子結點(diǎn)，給子結點(diǎn)分配碼長(cháng);如果子節點(diǎn)已經(jīng)是樹(shù)尾，則編碼結束;

　　ii.如果沒(méi)有子結點(diǎn)，排查下一個(gè)結點(diǎn)。

　　4)輸出碼長(cháng)數據，即按0~9順序輸出編碼結果。

　　1.5 輸出模塊

　　輸出模塊主要有三個(gè)工作：存儲輸入數據、求范式哈夫曼編碼、對輸入數據編碼并輸出。具體介紹求范式哈夫曼編碼[6]工作：

　　編碼模塊工作完成后，輸出模塊開(kāi)始接收碼長(cháng)信息(code_length)，同時(shí)記錄每個(gè)碼長(cháng)出現的次數(size_of_len)和順序(code_order)，然后根據這些信息求出每個(gè)符號的范式哈夫曼編碼。

　　如表3所示，第一行表示code的位，第一列表示碼長(cháng)。把碼長(cháng)1出現的次數二進(jìn)制值對齊第8位，把碼長(cháng)2出現的次數二進(jìn)制值對齊第7位，以此類(lèi)推，最后將表格按行相加，即得到數i的編碼。

2 驗證分析與FPGA實(shí)現

　　根據前述的算法設計，最終得到如圖1所示的模塊連接圖。

　　為了驗證編碼的準確性，首先采用C++編寫(xiě)常規的靜態(tài)哈夫曼編碼算法，同時(shí)在Testbench中，采用讀寫(xiě)文件的方式將輸出結果就保存到文件中，最后再驗證兩者輸出的一致性。

　　對于題目提出的Totalcycles參數，它主要包含了輸入數據的256個(gè)周期，編碼用時(shí)以及輸出用時(shí)。我們的輸出用時(shí)包含2個(gè)部分：一是輸出范式編碼表，總計30個(gè)周期;二是輸出編碼序列。所以Totalcycles = 256 + 編碼用時(shí) + 30 + 編碼序列長(cháng)度。根據測量結果，Totalcycles最優(yōu)為碼表2的547個(gè)周期，最差為碼表1的1159個(gè)周期。

　　對于壓縮算法的另一個(gè)重要指標壓縮率，這里定義為編碼后的數據長(cháng)度與編碼前的數據長(cháng)度之比^[7]，根據測量結果，最優(yōu)壓縮率為25.20%，最差為85.06%，同樣分別發(fā)生在表1和表2。

　　在目標器件XC7A100T-1CSG324C 上綜合實(shí)現后，可以得到我們的設計一共使用了1819個(gè)查找表和785個(gè)寄存器;同時(shí)調用了Block Ram的IP核用于存儲輸入的256個(gè)序列。在將扇出約束為50的情況下，由時(shí)序報告可知8.600ns的時(shí)鐘下還有0.025ns的余量，經(jīng)計算此時(shí)的工作頻率為116.28MHz^[8]，關(guān)鍵路徑位于編碼模塊的哈夫曼樹(shù)構造過(guò)程。

　　在FPGA上，運用Vivado Logic Analyzer驗證后，得到的波形與預期結果完全一致。

3 結論

　　哈夫曼編碼從被提出開(kāi)始，就一直被關(guān)注和研究。經(jīng)過(guò)60多年的發(fā)展，它已經(jīng)被廣泛應用于數據壓縮的各個(gè)領(lǐng)域。

　　我們的設計的主要有以下特點(diǎn)：

　　1)與實(shí)際應用場(chǎng)景結合起來(lái)，提供了兩個(gè)碼表和一種靜態(tài)編碼的方案。在輸入數據符合碼表條件時(shí)，自動(dòng)調用碼表加快編碼速度。

　　2)采用范式編碼的方式輸出，易于解碼，并使輸出哈夫曼編碼表的過(guò)程縮短4~24個(gè)周期。

　　3)采用3位碼長(cháng)輸出，在幾乎不損失壓縮率的情況下，將輸出碼表的體積減小25%。

　　4)采用預先編碼方案，進(jìn)一步縮短編碼耗時(shí)。

　　最初的方案中，靜態(tài)編碼耗時(shí)共需要70多個(gè)周期，后來(lái)幾經(jīng)優(yōu)化，利用FPGA同步處理的優(yōu)勢，最終降到19個(gè)周期，加上預先編碼方案，實(shí)際占用為17個(gè)周期。

　　在判斷使用表1、表2或使用靜態(tài)編碼的時(shí)候，設計采用了數據頻度的極差作為條件，但是在實(shí)際測試中我們發(fā)現極差并不是特別準確，真正的碼表選擇和數據分布有著(zhù)極為復雜的關(guān)系，最終我們只能通過(guò)收緊判斷條件，更多的采用靜態(tài)編碼以避免加速失效。所以碼表和碼表的選擇條件，還需要更多的實(shí)驗檢驗和數學(xué)證明。

　　參考文獻：

　　[1]Latha Pillai, “Huffman Coding” EXILINX, Virtex Series, XAPP616 (v1.0) Apr 22, 2003.

　　[2]方敏,秦曉新.動(dòng)態(tài)哈夫曼編碼的數據壓縮方法[J].計算機世界,1994(7):29-33.

　　[3]Matai, Janarbek, J. Y. Kim, and R. Kastner. "Energy efficient canonical huffman encoding." IEEE, International Conference on Application-Specific Systems, Architectures and Processors IEEE, 2014:202-209.

　　[4]李偉生,李域,王濤.一種不用建造Huffman樹(shù)的高效Huffman編碼算法[J].中國圖像圖形學(xué)報,2005,10(3):382-387.

　　[5]林建英,伍勇,李建華,等.一種易于硬件實(shí)現的快速自適應哈夫曼編碼算法[J].大連理工大學(xué)學(xué)報,2008,48(3):436-440.

　　[6]張全伙,于洪斌,林榆.優(yōu)化哈夫曼編碼數據壓縮技術(shù)及程序實(shí)現[J].華僑大學(xué)學(xué)報(自然科學(xué)版),1995,16(3):344-348.

　　[7]張穎超.基于FPGA的Huffman編碼并行實(shí)現及高速存儲系統設計[D].長(cháng)安大學(xué),2015.

　　[8]Latha Pillai, “Huffman Coding” EXILINX, Virtex Series, XAPP616 (v1.0) Apr 22, 2003.

　　本文來(lái)源于《電子產(chǎn)品世界》2018年第3期第54頁(yè)，歡迎您寫(xiě)論文時(shí)引用，并注明出處。