靜態(tài)哈夫曼編碼的快速硬件實現(xiàn)

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

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

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

　　1 系統(tǒng)設計方案

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

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

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

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

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

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

　　圖1 系統(tǒng)框圖

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

　　2 系統(tǒng)實現(xiàn)

　　本節(jié)將分模塊介紹整個系統(tǒng)的實現(xiàn)方案，由于統(tǒng)計模塊和輸出模塊的可優(yōu)化性不強，只重點介紹排序模塊和二叉樹及編碼生成模塊所采用的算法。

　　2.1 排序模塊

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

　　圖2 奇偶排序網(wǎng)絡

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

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

　　2.2二叉樹及編碼生成模塊

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

　　圖3 二叉樹生成及編碼

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

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

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

　　圖4 仿真時序圖

　　3 硬件實現(xiàn)

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

　　參考文獻：

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

　　[2]吳晨暉,王映輝.一種基于自頂向下的哈夫曼編碼方法[J].計算機技術與發(fā)展,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].機械工業(yè)出版社,2007.