靜態哈夫曼編碼的快速硬件實現

作者/王朝馳 李成澤 史傲凱 李靖 電子科技大學(四川 成都 610054)

第一屆(2016-2017)全國大學生集成電路創新創業大賽全國總決賽FPGA設計方向二等獎

本文所提出的方案的主要功能是連續接收256個0~9之間的任意數值，針對這256個數據完成輸入數據元素的哈夫曼編碼，最后先輸出0~9元素對應的編碼，再按照輸入數據順序輸出各數據對應的哈夫曼編碼。

　　1 系統設計方案

　　哈夫曼編碼的基本思想是將出現概率較大的數據用較短的編碼表示，而將出現概率較小的數據用較長的編碼表示。通常的做法是先根據輸入數據的頻次構造一棵哈夫曼樹，再通過遍歷樹中的每一個節點來生成葉子節點即輸入數據的哈夫曼編碼。但是傳統的方法存在兩個比較大的缺陷：一是在構造哈夫曼樹時，每次生成一個父節點都會進行一次排序操作，這樣的多次排序操作不僅會花費大量的時間，也會耗費大量的硬件資源;二是編碼操作是在哈夫曼二叉樹生成之后進行，其實每次當一個父節點生成的時候，該父節點包含的葉子節點的哈夫曼編碼的一個比特就已經確定了，所以如果采用傳統的方法，就必須要保存整棵二叉樹，并且沒有有效利用生成二叉樹的這段時間，這樣做也浪費了更多的資源和更多的時間。

　　基于以上兩點，本文提出以下的改進方案，操作步驟如下：

　　(1)統計所有輸入數據元素的頻次，并將輸入數據依次保存到FIFO中。

　　(2)將所有的頻次數據進行一次排序操作，給出有序的頻次數據。

　　(3)根據有序的頻次數據生成哈夫曼二叉樹，每次生成一個父節點時，確定該父節點所包含的葉子節點的哈夫曼編碼的一個比特，當二叉樹構造完成，所有葉子節點的哈夫曼編碼也就生成了。

　　(4)根據生成的哈夫曼編碼先依次輸出0~9對應的編碼，再按照輸入數據順序輸出各數據對應的哈夫曼編碼。

　　圖1 系統框圖

　　本方案對應的系統框圖如圖1所示，圖中每個模塊對應上述的以一個操作步驟。

　　2 系統實現

　　本節將分模塊介紹整個系統的實現方案，由于統計模塊和輸出模塊的可優化性不強，只重點介紹排序模塊和二叉樹及編碼生成模塊所采用的算法。

　　2.1 排序模塊

　　排序模塊的主要功能是實現10個頻次數據的排序操作，常用的排序算法有冒泡排序、快速排序、歸并排序等，綜合考慮硬件可實現的難易程度，排序周期數，消耗的硬件資源，我們選擇了利用排序網絡進行排序。

　　圖2 奇偶排序網絡

　　排序網絡有很多種，本文主要使用的排序網絡為奇偶排序網絡，如圖2為四輸入的奇偶排序網絡，圖中共有四根橫向的線條，表示a1、a2、a3、a4四條網絡，網絡之間的豎向連接線表示一次比較操作，每次比較都把大的數交換到網絡上層，小的數交換到網絡下層。第一個時鐘周期，a1和a2，a3和a4同時進行比較排序，即偶排序，第二個時鐘周期，a2和a3進行比較排序，即奇排序，第三個時鐘周期，a1和a2，a3和a4同時進行比較排序，第四個時鐘周期，a2和a3進行比較排序。經過四個時鐘周期之后，四條網絡上的數據就變成由大到小排列。

　　同理當利用排序網絡對十個數據進行排序操作時，總共需要10條網絡，共消耗10個時鐘周期，偶排序和奇排序交替進行5次，其中偶排序同時進行5次比較操作，奇排序同時進行4次比較操作，所以，排序網絡充分利用了硬件并行性的特點，這有利于縮短排序周期。并且，每次偶排序和奇排序進行的比較操作都是相同的，所以可以復用偶排序模塊和奇排序模塊，這有利于減小硬件資源的消耗，整個排序模塊僅消耗了9個比較器。

　　2.2二叉樹及編碼生成模塊

　　排序操作完成后，為了更快的完成輸入數據元素的哈夫曼編碼，本文提出了二叉樹生成和編碼同時進行的方案，下面將結合實例給出本方案的具體實施過程。

　　圖3 二叉樹生成及編碼

　　本方案的實例如圖3所示。圖中共有五組寄存器：(1)葉子節點寄存器a0~a4，按頻次從小到大存放元素0~4及其頻次，如a0中“4:2”表示元素4的頻次為2。(2)父節點寄存器b0~b2，按照父節點生成順序依次存放生成的父節點頻次，所以父節點的頻次也按照從小到大排列。為了避免影響用指針查找最小的兩個頻次，其初始值設置為一個較大的數，此處為255;(3)指針pta0、pta1、ptb0、ptb1，指向待比較的四個數，通過比較這四個數，就能找到所有頻次中最小的兩個頻次，并生成一個父節點，通過反證法可以證明，最小的兩個頻次值一定在這四個指針指向的數據中。比較的方法為pta0與ptb1指向的數比較，同時pta1與ptb0指向的數比較，根據比較結果就能確定最小的兩個頻次了。因為兩次比較是同時進行的，所以只花費了一次比較的時間就能確定最小的兩個頻次值，這樣做也避免了重新進行排序操作。每次比較完成后，會根據比較結果移動指針。(4)葉子節點編碼寄存器，如a0~a4下方的兩排數據所示，用于保存葉子節點的哈夫曼編碼以及編碼長度。(5)父節點包含的葉子節點寄存器，如圖中指針上方的數據所示，用于保存該父節點包含的葉子節點，如b0的第0bit為1，說明它包含的葉子節點為元素0。

　　初始狀態下，各寄存器的值如圖3中(a)所示，通過四個指針進行比較可以確定最小的兩個頻次為4和2，比較完成后指針發生移動到如圖(b)所示的位置，并且頻次4和2合并生成父節點6，存儲到第一個父節點寄存器b0中，對應的將該父節點的葉子節點寄存器修改為“11000”，表示該父節點包含3和4兩個葉子節點，最后對兩個葉子節點分別分配編碼1和0，寫入到對應的編碼寄存器并修改長度值。由此，得到圖3(b)中所示的第一次比較完成后的狀態。在該狀態下，同樣的，根據四個指針確定最小的兩個頻次值，移動指針，生成父節點，修改父節點寄存器和其對應的葉子節點寄存器，修改葉子節點對應的編碼寄存器。如此循環往復，直到最后只剩下兩個節點，對剩下的節點直接分配編碼，最后再修改對應的編碼寄存器，即可得到各數據元素對應的哈夫曼編碼，如圖3(c)所示，圖中，節點a0對應的葉節點編碼為“00000”，對應長度為3，表示元素4的哈夫曼編碼為“000”。

　　從以上過程中可以看出，該方案的優點在于生成二叉樹的同時生成數據元素的編碼，所以生成編碼不需要額外的時間，有效的減小了編碼總周期數，并且生成二叉樹時不需要保存整棵二叉樹，和傳統方案相比，只需要保存父節點所包含的葉子節點，減少了寄存器的使用，進一步減小了硬件消耗。

　　圖4 仿真時序圖

　　3 硬件實現

　　基于以上的系統設計方案，本文利用Xilinx的Vivado軟件平臺進行了綜合實現，所用芯片型號為xc7a100tcsg324-1，根據仿真結果，本設計從數據輸入結束到編碼完成總共消耗32個時鐘周期，并且在最差情況下運行頻率達到了250MHz。仿真時序圖如圖4所示，data_in為輸入數據，output_data為編碼完成后的串行數據輸出，在start信號有效后，連續輸入256個數據，系統根據輸入數據完成編碼，最后通過output_start信號串行輸出哈夫曼編碼以及編碼后的數據序列，輸出結束后拉高ouput_done信號一個時鐘周期。

　　參考文獻：

　　[1]王防修,周康.基于二叉排序樹的哈夫曼編碼[J].武漢輕工大學學報,2011,30(4):45-48.

　　[2]吳晨暉,王映輝.一種基于自頂向下的哈夫曼編碼方法[J].計算機技術與發展,2009,19(10):51-53.

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

　　[4]謝娜.哈夫曼樹算法的改進[J].電腦知識與技術,2010(29):8224-8226.

　　[5] ThomasH.Cormen.算法導論[M].機械工業出版社,2007.