哈夫曼編碼的HDL實現

作者 / 黃傳 黃尚川 劉旭陽 北京航空航天大學 電子信息工程學院（北京 100191）

*第一屆（2016－2017）全國大學生集成電路創新創業大賽全國總決賽FPGA設計方向獲獎作品

　　Huffman編碼是一種可變字長的無損壓縮編碼。根據字符出現的概率得到的可變字長編碼表是Huffman編碼的核心。概率低的字符使用較短的編碼，概率高的字符使用的長的編碼。

　　Huffman編碼的具體方法是將序列中的信源符號先按出現的頻次排序，把兩個最小的頻次相加，作為新的頻次和剩余的頻次重新排序，再把最小的兩個頻次相加，再重新排序，直到最后變成序列的總長度。每次挑出的最小兩個頻次所對應的信源符號或信源符號集構成二叉樹的左右兩支，對這左右兩支賦予“0”和“1”的權重。符號的編碼從樹的根部開始一直到達符號所在的葉節點， 將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號的哈夫曼編碼。

　　編碼示例如表 1和圖1所示。

　　表1 編碼示例1

　　圖1哈夫曼編碼示例

　　2設計

　　2.1算法

　　算法核心思想就是利用哈夫曼編碼過程中需要合并頻次最小的兩個符號集并且每次合并符號集不相交的特點，先用“獨熱碼”對符號進行預編碼(信源符號“0”用0000000001編碼,信源符號“1”用0000000010編碼…)，在合并符號集時對兩符號集的編碼進行抑或，使新符號集的編碼能反映符號集中的元素。比如一個符號集的編碼是0000010011，按照之前的規定，這個符號集就含有“0”,“1”,“4”這三個信源符號。這樣做的好處就是能通過對檢測符號集編碼中“1”的位置得到符號集中元素，從而在對符號的哈夫曼編碼過程轉化為對一個個符號集整體編碼。

　　編碼示例如表2和圖2所示。

　　表2 編碼示例2

　　圖2 硬件編碼示例

　　注意到每個符號集被合并時都會將參與合并的兩個符號集的預編碼相異或，并將結果作為新符號集的預編碼。并行化處理就體現在這排序和編碼可以同時進行。

　　在每次參與合并的兩個符號集上都帶有其相應的預編碼，預編碼不為0的位體現了這個符號集包含的信源符號。在每次排序完成后，將0和1分別賦予這兩個符號集內包含的元素，便可以在排序完成后立即得到所有元素的碼字。

　　對于碼字長度最小方差問題，對幾個符號集頻次相同的情況，優先合并符號集中所包含符號數量少的兩個符號集。算法選擇的下圖中第二種算法，碼長方差最小。

　　圖3 兩種哈夫曼編碼

　　2.2硬件設計

　　圖4 頂層模塊

　　頂層模塊為Huffman Coding，其中包含五個子模塊，分別為：

　　1)Receiver：統計頻次信息，并控制shift register緩存這些信息，統計完成后輸出頻次信息;

　　2)Sorter：根據頻次信息進行9次排序，每次排序輸出相應的數據到code_gen;

　　3)Code gen：根據sorter數據生成編碼表，并輸出到encoder;

　　4)Shift register：256x4 bit的移位寄存器。(此模塊為Xilinx IP 核);

　　5)Encoder：控制移位寄存器輸出并根據編碼表輸出數據。

　　3實現

　3.1 接收模塊

　　圖5 接收模塊

　　功能：統計各個符號出現的頻次，并控制移位寄存器保存輸入序列，統計完成后，在輸出端口串行輸出信息。

　　頻次的統計使用簡單的寄存器操作即可完成，具體不贅述。在統計過程中，使能移位寄存器信號為高，統計完成后，valid信號產生高電平脈沖，示意排序器開始工作，同時在輸出端將各個符號出現的頻次按時鐘節拍依次送入排序器。

　　3.2 排序模塊

　　圖6 排序模塊

　　為了便于描述，我們將排序器的操作對象定義為“節點”。一個“節點”中包含有一組待編碼的符號，“節點”的頻次為這些符號的頻次之和。

　　該排序器的功能是輸出具有兩個最小頻次的節點信息。data_0表示最小頻次對應的節點信息，data_1表示次小頻次對應的節點信息。

　　初始時，每個節點中僅有一個符號。排序器每次將具有最小頻次的兩個節點的信息輸出(為data_0和data_1)，然后將這兩個節點合并成一個新的節點。如表3所示，對于5個節點進行排序的例子可以說明該排序器的工作原理。

　　表3 第一次排序之前

　　第一次輸出頻率最小的兩個符號的data，即A和E對應的data，分別為00001和10000;然后這兩組符號被合并為同一個節點，即有表4結果。

　　表4 第二次排序之前

　　類似上一次，第二次輸出分別為10001和00010，然后這兩組符號被合并，即有表5結果。

　　表5 第三次排序之前

　　類似上一步，第三次輸出分別為10011和01000，仍然將它們合并，即有表6結果。

　　表6 第四次排序之前

　　則第四次輸出為00100和11011。這也是最后一次輸出。所以輸出結果如表7所示。

　　表7 data輸出結果

　　類似地，對于此項目中10個符號的情況，只要用10位二進制數來表示相應的節點信息即可。

　　3.3 編碼生成模塊

　　圖7 產生編碼模塊

　　功能是根據排序器排序模塊輸出的數組生成編碼表。

　　在本工程中，根據設計需求，可以算出，每個字符的編碼位數最長可能為9位，最短為1位。所以存儲編碼表的寄存器應該至少有9位，每一位的可能狀態有三種：“0”，“1”，“-”，分別表示“該位編碼為0”、“該位編碼為1”和“該位沒有存儲編碼信息”。因此，我們使用兩個比特來表示一位編碼。

　　編碼是根據data_0和data_1生成的，初始時，所有位都被置為“-”，然后根據data_0和data_1進行操作。對于data_0中的每一個符號，為其增加一位編碼“0”;對于data_0中的每一個符號，為其增加一位編碼“1”。表8為圖1中的數據生成編碼的過程。

　　表8 生成編碼示例

　　3.4 移位寄存器

　　圖8 產生編碼表模塊

　　功能是一個移位寄存器，在CE為高時工作。

　　注：此模塊采用Xilinx IP核——RAM-based Shift Register。

　　3.5 編碼模塊

　　圖9 編碼模塊

　　功能是把編碼表和輸入序列的編碼串行輸出。

　　輸出格式：在output_start置高電平后、output_done置高電平前，output_data端為有效的輸出數據。這些數據包含了霍夫曼編碼表，以及對輸入數據進行編碼后的結果。

　　哈夫曼編碼表按順序存放了0～9的霍夫曼編碼。對于某特定的符號，其哈夫曼編碼表示為：該符號的的碼字長度(長度為4比特)，緊接著是該符號的碼字。

　　哈夫曼編碼表之后是輸入數據的編碼結果。具體的格式如下圖所示：

　　圖10 輸出序列示例

　　4結果

　　4.1電路功能

　　先通過MATLAB程序產生用來測試電路的256個數據，這些數據根據一個概率向量p來生成，再利用Vivado仿真工具加載數據到電路輸入端，并把電路輸出的有效數據輸出到文件中。

　　利用MATLAB對輸出數據進行解碼并和原始數據進行比對(編碼正確性測試)，還利用MATLAB內置的哈夫曼編碼函數計算平均碼長與電路得出的平均碼長進行對比(平均碼長測試)。下表是在不同概率向量p下得到的測試結果如表9所示。

　　表9 功能測試

　　根據測試結果，可以證明電路功能的正確性。

　　4.2電路性能

　　4.2.1消耗時鐘周期數

　　對于不同的輸入序列有不同的編碼長度，所以電路的Total Cycle是不確定的。但是從start到output_start的周期間隔是確定的，為272個時鐘周期，如下圖所示。

　　圖11 輸出波形示例

　　4.2.2資源占用

　　在選擇目標器件為xc7a100tcsg324-1進行綜合、布線之后，資源消耗情況如表10所示。

　　表10 資源占用

　　4.2.3最高時鐘頻率

　　經過時序約束后，在時鐘頻率為125M的情況，滿足約束條件。

　　參考文獻：

[1]David A. Huffman. A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE. 40(9): 1098–1101. doi:10.1109/JRPROC.1952.273898

[2]Sutherland, Stuart, Davidmann, Simon, Flake, Peter. SystemVerilog for Design Second Edition. Springer US: 2006

[3]Joshua Vasquez.(January 20,2016)“SORT FASTER WITH FPGAS”, http://hackaday.com/2016/01/20/a-linear-time-sorting-algorithm-for-fpgas/

[4]高亞軍.Vivado從此開始[M].北京;電子工業出版社，2017.　               [5]Donald E. Thomas, Philip R. Moorby. The Verilog? Hardware Description Language,Fifth Edition. Kluwer Academic Publishers; 2002.