作者 / 賈先韜 張旭 劉澤曦 山東大學 物理學院(山東 濟南 250100)

*大學生集成電路創新創業大賽全國總決賽三等獎

摘要：傳統的硬件實現哈夫曼編碼的方法主要有：預先構造哈夫曼編碼表，編碼器通過查表的方法輸出哈夫曼編碼^[1];編碼器動態生成哈夫曼樹，通過遍歷節點方式獲取哈夫曼編碼^[2-3]。第一種方法從平均碼長角度看，在很多情況下非最優;第二種方法需要生成完整的哈夫曼樹，會產生大量的節點，且需遍歷哈夫曼樹獲取哈夫曼編碼，資源占用多，實現較為麻煩。本文基于軟件實現^[4]時，使用哈夫曼樹，會提出一種適用于硬件并行實現的新數據結構——字符池，通過對字符池的頻數屬性比較和排序來決定各個字符節點在字符池中的歸屬。配置字符池的同時逐步生成哈夫曼編碼，可以提高硬件利用率，并且無需額外操作來提取哈夫曼編碼。

引言

　　哈夫曼(Huffman)編碼對出現頻率較高的字符采用較短的編碼，對出現頻率較低的字符采用較長的編碼，它可以保證平均碼長最短，具有較高的編碼效率。因而哈夫曼編碼被廣泛應用于數據壓縮領域。已有的硬件實現方法包括預先構造哈夫曼編碼表和模仿軟件實時生成完整哈夫曼樹兩種。前一種方法在大多數情況下不是最優編碼，后一種方法不僅需要生成大量節點，而且需要額外硬件模塊實現遍歷節點操作。針對這些問題，本文提出一種新的適用于硬件實現的數據結構——字符池來對輸入數據實時生成哈夫曼編碼。

1 哈夫曼編碼的原理

　　哈夫曼編碼是一種不等長編碼，根據每個字符出現頻率進行編碼，每個字符的編碼不能是其他字符編碼的前綴，所有字符編碼總長度相比原碼而言將會降低。

2 哈夫曼編碼硬件總體實現方案

　　本文采用自頂而下的設計方式。總體框架由一個頂層模塊、接收模塊、計算模塊、輸出模塊和FIFO模塊構成。頂層模塊由其余4個模塊連接而成，系統總體結構如圖1所示。

　　接收模塊：接收數據源并分類統計各字符出現的頻數，數據接收完成后，接收模塊向計算模塊發送開始計算信號。計算模塊進行計算，生成各字符對應的編碼值，做成編碼表，結束后向輸出模塊發送輸出信號。最后輸出模塊通過查表方式輸出各字符的編碼值以及哈夫曼編碼結果。FIFO模塊用于接收原始數據和向輸出模塊提供數據源。

3 實現流程

　　本文使用verilog語言在vivado平臺上進行哈夫曼編碼硬件模塊的實現，選用器件為xc7a100tcsq324-1。

3.1 FIFO模塊

　　本文的FIFO模塊使用vivado的IP核生成，設計時選擇好相應參數配置，生成verilog文件后即可直接調用。

3.2 輸入模塊

　　使用多個計數器對輸入各字符頻數以及輸入字符總量進行計數，頻數被存放在寄存器中，當字符輸入結束(例如輸入字符總量達到了約定值)時，輸入模塊向計算模塊輸出計算開始信號，同時頻數寄存器中的數據被并行輸出至計算模塊。

3.3 計算模塊

3.3.1 新數據結構及對應的硬件實現

　　本文基于哈夫曼樹的思想構建了新的數據結構——字符池用于硬件實現哈夫曼編碼。根據n種字符構建n個字符池和n個字符節點。每個字符池包含一個屬性：包含的所有字符的頻數之和。每個字符節點包含以下屬性：所屬字符池序號、自身編碼值和自身編碼長度。因此，定義n個寄存器記錄字符節點對應的字符池序號、n個寄存器記錄編碼值、n個寄存器記錄編碼長度以及n個寄存器記錄字符池的頻數。

3.3.2 哈夫曼編碼計算流程

　　進行哈夫曼編碼計算時，計算模塊通過執行循環操作完成各字符編碼的生成以及字符在字符池中的移動。以圖2中的實例描述計算流程。

　　圖2中共有5種字符，各自頻數為：“0”：5，“1”：10，“2”：20，“3”：30，“4”：35。

　　圖2(a)為初始化效果，此時每個字符池包含一個字符，每個字符池的頻數恰為那個字符的頻數;每個字符的編碼值和編碼長度清零。圖2(a)到圖2(d)共經過4次循環操作，最終可以從圖2(d)中讀取出每個字符的編碼值和編碼長度，“0”編碼值為0011，“1”編碼值為1011，“2”編碼值為111，“3”編碼值為01，“4”編碼值為0。

　　每次循環操作包含排序、挑選、最小值和次小值求和、頻數更新、字符移動、編碼值更新及編碼長度更新8步。其中前4步按順序完成，然后同時完成后4步。總循環次數由字符種類數控制。

　　排序操作功能是將每個節點池的頻數從小到大進行排序，本文借鑒了參考文獻[5]中的方法，硬件實現時通過構建比較器陣列將每兩個數兩兩比較，再通過加法器對每個字符頻數的比較結果求和。對一個字符頻數，若它小于另一個字符的頻數，則相應結果為0，否則為1。那么通過指定字符頻數與其他字符頻數的比較結果之和可以得知它的頻數在所有頻數中的位置。

　　挑選操作是將排序操作中比較結果為0和1對應的字符頻數選出，它們代表最小頻數和次小頻數，挑選操作同時挑選出這兩個頻數對應的字符池ID。硬件實現時構建多個比較器，將比較結果之和與0和1比較，再通過多路復用器從多個頻數和字符池ID中準確挑選出所需的值。例如在圖2(b)中，挑選出的兩個頻數為15和20，它們對應字符池ID為1和2。

　　接下來的最小值和次小值求和操作就是將挑選操作挑選出的最小頻數和次小頻數求和，然后輸出。此步驟硬件實現時需要一個多位加法器。例如在圖2(b)中，求和值為15+20=35。

　　頻數更新操作指根據挑選操作挑選出的結果進行字符池頻數的更新。按照本文約定方法，將最小頻數對應字符池的頻數更新成無效值，無效值應大于所有可能的頻數，它的目的是避免此字符池的頻數被接下來的循環挑選操作挑選出。本文將次小頻數對應字符池的頻數以求和操作的加法結果替代。例如圖2(c)中1號字符池頻數變成100，2號字符池頻數變成35。

　　字符移動操作指將特定字符從一個字符池移動到另一個字符池中。按照本文約定方法，將最小頻數對應字符池的所有字符移動到次小頻數對應字符池中。例如將圖2(c)和圖2(b)對比可發現1號字符池的字符“0”和“1”被移動到了2號字符池中。

　　編碼值、編碼長度更新操作中，按本文約定方法，將最小頻數對應字符池的所有字符編碼值左移1位并在最后一位補0，長度加1。將次小頻數對應字符池的所有字符編碼值左移1位并在最后一位補1，長度加1。將圖2(c)和圖2(b)對比可看出，字符“0”的編碼值從0變成00，“1”編碼值從1變成10，“2”編碼值從無變成1。

　　所有循環結束后編碼表已生成，計算模塊向輸出模塊發送計算結束信號。

3.4 輸出模塊

　　輸出模塊負責從FIFO中讀取出原始數據、從編碼表中獲取編碼值，再通過并串轉換以一位數據口首先輸出各字符編碼值，再輸出字符串編碼結果。

4 仿真和調試

　　本文使用vivado對頂層模塊進行綜合實現，通過實現后仿真驗證 結果正確性。

　　圖3展示了模塊輸入時序。本文測試時以huf_in_start高電平脈沖標志數據輸入開始，實際數據以4為并口輸入，測試字符范圍為“0”至“9”。

　　圖4展示了模塊輸出時序。通過huf_out_start高電平脈沖表明輸出開始。首先輸出各字符編碼序列，包含4bit編碼長度和實際編碼值，然后輸出原始字符串的編碼值。huf_out_end高電平脈沖表明輸出結束。

　　圖5為vivado控制臺輸出，它展示了各字符編碼值以及原始字符和testbench進行的解碼字符比較，說明模塊正常運行。

5 結論

　　本文提出了一種新的在硬件上實現哈夫曼編碼的方法，利用本文的字符池數據結構，對每次輸入的數據實時生成哈夫曼編碼表，從平均碼長角度保證了編碼的最優，同時避免了生成完整的哈夫曼樹，減少了資源占用，并避免了遍歷哈夫曼樹所需的額外操作，實現方便快捷。

　　參考文獻：

　　[1]鄧麗娟,田金文,柳健,等.哈夫曼編碼器IP核的設計與實現[J].微電子學與計算機,2005(02):9-12.

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

　　[3]曾英,鄧曙光.基于FPGA的Huffman編碼器的設計[J].湖南城市學院學報(自然科學版), 2014(01):32-35.

　　[4]楊蘭.基于C語言的哈夫曼編碼的實現[J].軟件導刊,2012(09):40-42.

　　[5]師廷偉,金長江.基于FPGA的并行全比較排序算法[J].數字技術與應用,2013(10):126-127.

　　本文來源于《電子產品世界》2017年第12期第40頁，歡迎您寫論文時引用，并注明出處。