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

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

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

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

　　1 系統(tǒng)設(shè)計(jì)方案

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

　　基于以上兩點(diǎn)，本文提出以下的改進(jìn)方案，操作步驟如下：

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

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

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

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

　　圖1 系統(tǒng)框圖

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

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

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

　　2.1 排序模塊

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

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

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

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

　　2.2二叉樹(shù)及編碼生成模塊

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

　　圖3 二叉樹(shù)生成及編碼

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

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

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

　　圖4 仿真時(shí)序圖

　　3 硬件實(shí)現(xiàn)

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

　　參考文獻(xiàn)：

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

　　[2]吳晨暉,王映輝.一種基于自頂向下的哈夫曼編碼方法[J].計(jì)算機(jī)技術(shù)與發(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]謝娜.哈夫曼樹(shù)算法的改進(jìn)[J].電腦知識(shí)與技術(shù),2010(29):8224-8226.

　　[5] ThomasH.Cormen.算法導(dǎo)論[M].機(jī)械工業(yè)出版社,2007.