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

陸哲敏 易慶陽 楊一凡 蔣劍飛

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

關鍵詞：哈夫曼編碼；靜態編碼；碼表；范式；應用

0 引言

哈夫曼編碼是基于帶權路徑最小的最優二叉樹啥夫曼樹的一種平均碼長最短的編碼方式。哈夫曼編碼常用于數據的無損壓縮，尤其在衛星探測、醫學圖像處理、雷達測試系統等領域有著廣泛應用[1]。

以對一段長度為256的0-9的數據進行編碼為例，如果采用定長編碼，則需要4位表示一個0-9的數字，一共需要4*256=1024位實現編碼，而如果采用哈夫曼編碼可以大大降低需要的位數。

1算法設計

在開始設計前，我們先對目前主流啥夫曼方案作簡單分析：

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

2.動態編碼：動態編碼依據的是一棵動態變化的哈夫曼樹，每個數據的編碼都是由它前面所有數據組成的哈夫曼樹決定的，雖然可以同步輸出編碼序列，但是對資源占用較大；

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

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

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

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

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

1.1 統計模塊

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

1.2 排序模塊

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

1.3 碼表模塊

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

1.4編碼模塊

如果碼表模塊無法對輸入數據進行編碼，則必須通過編碼模塊完成靜態編碼。

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

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

為了提高編碼效率，構建node存儲器和構建result存儲器是同步進行的，而構建哈夫曼樹和分配碼長的操作均為兩個結點同時操作，編碼過程也沒有選擇常規的自底向上的編碼，而是選擇了自頂向下的編碼方式，避免重復讀取內部結點[5]，如此下來，構造result的過程耗時10個周期，編碼過程最快只需耗時8個周期。

具體過程如下：

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

1）第1個周期開始構造內部結點node存儲器：

a）依次從seqn、seqn-l、nodek和nodek+l中尋找最小的兩個值（如果權值相同，認為排前面的權值小）；

b）將最小的兩個權值相加后放入node中；

c）將n、k作相應移動；

d重復a。

2）第2個周期開始同步進行哈夫曼樹result存儲器的構造：

a）依次從seqn、seqn-l、nodek和nodek+l中尋找最小的兩個值（如果權值相同，認為排前面的權重小）：

b）將兩個最小權值依次放入result中；

c）將n、k作相應移動：

d）重復a。

3）第11個周期開始編碼：

a）初始碼長result[17]=result[16]=1；

b）根據標記位，可以知道某一個結點是否有子結點；

i.如果有子結點，給子結點分配碼長：如果子節點已經是樹尾，則編碼結束：

ii如果沒有子結點，排查下一個結點。

4）輸出碼長數據，即按O～9順序輸出編碼結果。

1.5 輸出模塊

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

編碼模塊工作完成后，輸出模塊開始接收碼長信息（code_length），同時記錄每個碼長出現的次數（size_of_len）相順序（code_order），然后根據這些信息求出每個符號的范式哈夫曼編碼。

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

2 驗證分析與FPGA實現

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

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

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

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

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

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

3 結論

哈夫曼編碼從被提出開始，就一直被關注和研究。經過60多年的發展，它已經被廣泛應用于數據壓縮的各個領域。

我們的設計的主要有以下特點：

1）與實際應用場景結合起來，提供了兩個碼表和一種靜態編碼的方案。在輸入數據符合碼表條件時，自動調用碼表加快編碼速度。

2）采用范式編碼的方式輸出，易于解碼，并使輸出哈夫曼編碼表的過程縮短4～24個周期。

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

4）采用預先編碼方案，進一步縮短編碼耗時。

最初的方案中，靜態編碼耗時共需要70多個周期，后來幾經優化，利用FPGA同步處理的優勢，最終降到19個周期，加上預先編碼方案，實際占用為17個周期。

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

參考文獻：

[1]Latha Pillai，“Huffman Coding”EXILINX， Virtex Series， XAPP616 （vl.0） Apr 22， 2003

[2]方敏，泰曉新動態哈夫曼編碼的數據壓縮方法[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 ProcessorslEEE， 2014：202-209

[4]李偉生，李域，王濤一種不用建造Huffman樹的高效Huffman編碼算法[J].中國圖像圖形學報，2005，10（3）：382-387

[5]林建英，伍勇，李建華，等一種易于硬件實現的快速自適應哈夫曼編碼算法[J]大連理工大學學報.2008，48（3）：436-440

[6]張全伙，于洪斌，林榆優化哈夫曼編碼數據壓縮技術及程序實現[J]華僑大學學報（自然科學版）.1995，16（3）：344-348

[7]張穎超基于FPGA的Huffman編碼并行實現及高速存儲系統設計[D]長安大學，2015

[8]Latha Pillai，“Huffman Coding”EXILIN×， Virtex Series， XAPP616 （vl.0） Apr 22， 2003