基于FPGA的快速哈夫曼編碼設(shè)計(jì)

陸哲敏 易慶陽(yáng) 楊一凡 蔣劍飛

摘要：針對(duì)不同的應(yīng)用場(chǎng)景，給出兩種方案，一種用碼表實(shí)現(xiàn)，另一種用靜態(tài)編碼實(shí)現(xiàn)。碼表方式將題目與實(shí)際應(yīng)用結(jié)合起來(lái)，針對(duì)不同場(chǎng)景給出不同的碼表快速編碼；不過(guò)考慮到無(wú)規(guī)律信號(hào)的編碼，所以通過(guò)靜態(tài)編碼使我們的作品更加具有普適性，我們還采用三位范式編碼的方式，縮短輸出周期；同時(shí)在數(shù)據(jù)輸入結(jié)束之前開(kāi)始排序，減少編碼實(shí)際占用的時(shí)間。

關(guān)鍵詞：哈夫曼編碼；靜態(tài)編碼；碼表；范式；應(yīng)用

0 引言

哈夫曼編碼是基于帶權(quán)路徑最小的最優(yōu)二叉樹(shù)啥夫曼樹(shù)的一種平均碼長(zhǎng)最短的編碼方式。哈夫曼編碼常用于數(shù)據(jù)的無(wú)損壓縮，尤其在衛(wèi)星探測(cè)、醫(yī)學(xué)圖像處理、雷達(dá)測(cè)試系統(tǒng)等領(lǐng)域有著廣泛應(yīng)用[1]。

以對(duì)一段長(zhǎng)度為256的0-9的數(shù)據(jù)進(jìn)行編碼為例，如果采用定長(zhǎng)編碼，則需要4位表示一個(gè)0-9的數(shù)字，一共需要4*256=1024位實(shí)現(xiàn)編碼，而如果采用哈夫曼編碼可以大大降低需要的位數(shù)。

1算法設(shè)計(jì)

在開(kāi)始設(shè)計(jì)前，我們先對(duì)目前主流啥夫曼方案作簡(jiǎn)單分析：

1.靜態(tài)編碼：編碼速度與資源占用方面都在合理范圍內(nèi)，雖然編碼速度比碼表慢，但是通用性要比碼表好：

2.動(dòng)態(tài)編碼：動(dòng)態(tài)編碼依據(jù)的是一棵動(dòng)態(tài)變化的哈夫曼樹(shù)，每個(gè)數(shù)據(jù)的編碼都是由它前面所有數(shù)據(jù)組成的哈夫曼樹(shù)決定的，雖然可以同步輸出編碼序列，但是對(duì)資源占用較大；

3.碼表方案：碼表只針對(duì)特定分布的數(shù)據(jù)可以獲得良好壓縮率，但是有著其極小的資源占用和無(wú)需復(fù)雜運(yùn)算的優(yōu)點(diǎn)。

經(jīng)過(guò)以上分析，我們選擇碼表和靜態(tài)編碼相結(jié)合的方式進(jìn)行編碼。在輸入完成前，對(duì)輸入序列的分布進(jìn)行判斷，如果符合碼表的分布要求，則直接由碼表編碼，加快編碼的速度，如果不符合，則進(jìn)行靜態(tài)編碼，以實(shí)現(xiàn)編碼速度和壓縮率的平衡。

為實(shí)現(xiàn)哈夫曼編碼，我們將整個(gè)系統(tǒng)分為5個(gè)模塊：統(tǒng)計(jì)、排序、編碼、碼表和輸出。

數(shù)據(jù)由數(shù)據(jù)源輸入之后，首先對(duì)其統(tǒng)計(jì)與排序。在整個(gè)過(guò)程中，排序進(jìn)行兩次，第一次在第251個(gè)周期，用于判斷使用碼表還是靜態(tài)編碼：第二次則根據(jù)編碼方式的不同而改變：如果使用碼表編碼，則在第256個(gè)周期開(kāi)始排序：如果使用靜態(tài)編碼，則在第254個(gè)周期排序，這是由于最后兩個(gè)權(quán)值對(duì)壓縮率影響極小，所以通過(guò)丟棄最后兩個(gè)權(quán)值信息加快編碼速度。

為了進(jìn)一步減小資源占用與輸出周期，編碼和碼表模塊輸出的碼長(zhǎng)均由3位構(gòu)成，這樣設(shè)計(jì)比起4位輸出時(shí)要節(jié)省10個(gè)周期。理論支撐是出現(xiàn)碼長(zhǎng)為9的情況時(shí)，數(shù)據(jù)頻率需要滿足第i個(gè)數(shù)的碼長(zhǎng)大于前i-2個(gè)數(shù)的碼長(zhǎng)之和，這種情況的概率是極小的：而且即使出現(xiàn)碼長(zhǎng)為9的情況時(shí)，最大的4個(gè)碼長(zhǎng)——9、9、8、7也可以用8、8、8、8來(lái)近似，由于最大碼長(zhǎng)對(duì)應(yīng)的數(shù)據(jù)的頻率很小，壓縮率的損失也很小。故碼長(zhǎng)為9的情況可以舍棄，所以認(rèn)為碼長(zhǎng)在1-8之間，用3位二進(jìn)制來(lái)表示。

1.1 統(tǒng)計(jì)模塊

統(tǒng)計(jì)模塊的功能是對(duì)輸入的數(shù)據(jù)統(tǒng)計(jì)出現(xiàn)的頻數(shù)。設(shè)計(jì)的思想是給0到9每個(gè)數(shù)字構(gòu)造一個(gè)計(jì)數(shù)器，先初始化計(jì)數(shù)器值為0，每次輸入一個(gè)數(shù)字之后其相應(yīng)的計(jì)數(shù)器加1，這樣，在數(shù)據(jù)全部輸入完成后即可得到0到9這10個(gè)數(shù)字的權(quán)重。

1.2 排序模塊

排序模塊的功能是對(duì)已經(jīng)統(tǒng)計(jì)好的數(shù)據(jù)進(jìn)行排序。設(shè)計(jì)的思想是：將每個(gè)權(quán)值都兩兩比較一次，由比較結(jié)果就可以快速確定它在一個(gè)降序排列的存儲(chǔ)器seq中的位置。由于這些比較都是并行的組合邏輯，所以只需要讀一次比較結(jié)果，一個(gè)周期即可完成排序。

1.3 碼表模塊

排序模塊的排序結(jié)果作為碼表模塊選擇何種編碼方式的判斷依據(jù)，當(dāng)序列接近于等概率分布時(shí)，哈夫曼編碼基本等效于等長(zhǎng)編碼，此時(shí)進(jìn)行靜態(tài)編碼效率較低，所以通過(guò)碼表1直接編碼；除此之外，當(dāng)序列分布范圍極廣，即分布十分不均勻的時(shí)候，用靜態(tài)編碼效率也比較低，此時(shí)采用碼表2進(jìn)行編碼。兩張碼表如表1、表2所示。

1.4編碼模塊

如果碼表模塊無(wú)法對(duì)輸入數(shù)據(jù)進(jìn)行編碼，則必須通過(guò)編碼模塊完成靜態(tài)編碼。

編碼過(guò)程是由構(gòu)建哈夫曼樹(shù)和分配碼長(zhǎng)兩個(gè)過(guò)程組成的[4]，此模塊中我們使用到3個(gè)存儲(chǔ)器，一個(gè)是上文提到的seq，記錄排序好的十個(gè)數(shù)據(jù)以及各自權(quán)值；另一個(gè)存儲(chǔ)器是node，是由哈夫曼樹(shù)中的非葉節(jié)點(diǎn)構(gòu)成的；而最后一個(gè)存儲(chǔ)器為result，保存整棵哈夫曼樹(shù)。

10個(gè)葉結(jié)點(diǎn)組成的哈夫曼樹(shù)應(yīng)有19個(gè)結(jié)點(diǎn)，但是根結(jié)點(diǎn)不參與編碼，所以result只保存18個(gè)結(jié)點(diǎn)，同樣，node結(jié)點(diǎn)也只保存8個(gè)內(nèi)部結(jié)點(diǎn)。

為了提高編碼效率，構(gòu)建node存儲(chǔ)器和構(gòu)建result存儲(chǔ)器是同步進(jìn)行的，而構(gòu)建哈夫曼樹(shù)和分配碼長(zhǎng)的操作均為兩個(gè)結(jié)點(diǎn)同時(shí)操作，編碼過(guò)程也沒(méi)有選擇常規(guī)的自底向上的編碼，而是選擇了自頂向下的編碼方式，避免重復(fù)讀取內(nèi)部結(jié)點(diǎn)[5]，如此下來(lái)，構(gòu)造result的過(guò)程耗時(shí)10個(gè)周期，編碼過(guò)程最快只需耗時(shí)8個(gè)周期。

具體過(guò)程如下：

假設(shè)已有：降序排列的權(quán)值序列seq= {seq0，seq1，seq2， seq3， seq4， seq5， seq6， seq7， seq8. seq9），初始化好的存儲(chǔ)器為node={FFH，F(xiàn)FH……，F(xiàn)FH）。

1）第1個(gè)周期開(kāi)始構(gòu)造內(nèi)部結(jié)點(diǎn)node存儲(chǔ)器：

a）依次從seqn、seqn-l、nodek和nodek+l中尋找最小的兩個(gè)值（如果權(quán)值相同，認(rèn)為排前面的權(quán)值?。?/p>

b）將最小的兩個(gè)權(quán)值相加后放入node中；

c）將n、k作相應(yīng)移動(dòng)；

d重復(fù)a。

2）第2個(gè)周期開(kāi)始同步進(jìn)行哈夫曼樹(shù)result存儲(chǔ)器的構(gòu)造：

a）依次從seqn、seqn-l、nodek和nodek+l中尋找最小的兩個(gè)值（如果權(quán)值相同，認(rèn)為排前面的權(quán)重小）：

b）將兩個(gè)最小權(quán)值依次放入result中；

c）將n、k作相應(yīng)移動(dòng)：

d）重復(fù)a。

3）第11個(gè)周期開(kāi)始編碼：

a）初始碼長(zhǎng)result[17]=result[16]=1；

b）根據(jù)標(biāo)記位，可以知道某一個(gè)結(jié)點(diǎn)是否有子結(jié)點(diǎn)；

i.如果有子結(jié)點(diǎn)，給子結(jié)點(diǎn)分配碼長(zhǎng)：如果子節(jié)點(diǎn)已經(jīng)是樹(shù)尾，則編碼結(jié)束：

ii如果沒(méi)有子結(jié)點(diǎn)，排查下一個(gè)結(jié)點(diǎn)。

4）輸出碼長(zhǎng)數(shù)據(jù)，即按O～9順序輸出編碼結(jié)果。

1.5 輸出模塊

輸出模塊主要有三個(gè)工作：存儲(chǔ)輸入數(shù)據(jù)、求范式哈夫曼編碼、對(duì)輸入數(shù)據(jù)編碼并輸出。具體介紹求范式哈夫曼編碼[6]工作：

編碼模塊工作完成后，輸出模塊開(kāi)始接收碼長(zhǎng)信息（code_length），同時(shí)記錄每個(gè)碼長(zhǎng)出現(xiàn)的次數(shù)（size_of_len）相順序（code_order），然后根據(jù)這些信息求出每個(gè)符號(hào)的范式哈夫曼編碼。

如表3所示，第一行表示code的位，第一列表示碼長(zhǎng)。把碼長(zhǎng)1出現(xiàn)的次數(shù)二進(jìn)制值對(duì)齊第8位，把碼長(zhǎng)2出現(xiàn)的次數(shù)二進(jìn)制值對(duì)齊第7位，以此類推，最后將表格按行相加，即得到數(shù)i的編碼。

2 驗(yàn)證分析與FPGA實(shí)現(xiàn)

根據(jù)前述的算法設(shè)計(jì)，最終得到如圖1所示的模塊連接圖。

為了驗(yàn)證編碼的準(zhǔn)確性，首先采用C++編寫(xiě)常規(guī)的靜態(tài)哈夫曼編碼算法，同時(shí)在TestbencH中，采用讀寫(xiě)文件的方式將輸出結(jié)果就保存到文件中，最后再驗(yàn)證兩者輸出的一致性。

對(duì)于題目提出的Totalcycles參數(shù)，它主要包含了輸入數(shù)據(jù)的256個(gè)周期，編碼用時(shí)以及輸出用時(shí)。我們的輸出用時(shí)包含2個(gè)部分：一是輸出范式編碼表，總計(jì)30個(gè)周期；二是輸出編碼序列。所以Totalcycles=256+編碼用時(shí)+ 30+編碼序列長(zhǎng)度。根據(jù)測(cè)量結(jié)果，Totalcycles最優(yōu)為碼表2的547個(gè)周期，最差為碼表1的1159個(gè)周期。

對(duì)于壓縮算法的另一個(gè)重要指標(biāo)壓縮率，這里定義為編碼后的數(shù)據(jù)長(zhǎng)度與編碼前的數(shù)據(jù)長(zhǎng)度之比[7]，根據(jù)測(cè)量結(jié)果，最優(yōu)壓縮率為25.20%，最差為85.06%，同樣分別發(fā)生在表1和表2。

在目標(biāo)器件XC7A100T-1CSG324C上綜合實(shí)現(xiàn)后，可以得到我們的設(shè)計(jì)一共使用了1819個(gè)查找表和785個(gè)寄存器：同時(shí)調(diào)用了Block Ram的lP核用于存儲(chǔ)輸入的256個(gè)序列。在將扇出約束為50的情況下，由時(shí)序報(bào)告可知8.600ns的時(shí)鐘下還有0.025ns的余量，經(jīng)計(jì)算此時(shí)的工作頻率為ll6.28MHz[8]，關(guān)鍵路徑位于編碼模塊的哈夫曼樹(shù)構(gòu)造過(guò)程。

在FPGA上，運(yùn)用Vivado Logic Analyzer驗(yàn)證后，得到的波形與預(yù)期結(jié)果完全一致。

3 結(jié)論

哈夫曼編碼從被提出開(kāi)始，就一直被關(guān)注和研究。經(jīng)過(guò)60多年的發(fā)展，它已經(jīng)被廣泛應(yīng)用于數(shù)據(jù)壓縮的各個(gè)領(lǐng)域。

我們的設(shè)計(jì)的主要有以下特點(diǎn)：

1）與實(shí)際應(yīng)用場(chǎng)景結(jié)合起來(lái)，提供了兩個(gè)碼表和一種靜態(tài)編碼的方案。在輸入數(shù)據(jù)符合碼表?xiàng)l件時(shí)，自動(dòng)調(diào)用碼表加快編碼速度。

2）采用范式編碼的方式輸出，易于解碼，并使輸出哈夫曼編碼表的過(guò)程縮短4～24個(gè)周期。

3）采用3位碼長(zhǎng)輸出，在幾乎不損失壓縮率的情況下，將輸出碼表的體積減小25%。

4）采用預(yù)先編碼方案，進(jìn)一步縮短編碼耗時(shí)。

最初的方案中，靜態(tài)編碼耗時(shí)共需要70多個(gè)周期，后來(lái)幾經(jīng)優(yōu)化，利用FPGA同步處理的優(yōu)勢(shì)，最終降到19個(gè)周期，加上預(yù)先編碼方案，實(shí)際占用為17個(gè)周期。

在判斷使用表1、表2或使用靜態(tài)編碼的時(shí)候，設(shè)計(jì)采用了數(shù)據(jù)頻度的極差作為條件，但是在實(shí)際測(cè)試中我們發(fā)現(xiàn)極差并不是特別準(zhǔn)確，真正的碼表選擇和數(shù)據(jù)分布有著極為復(fù)雜的關(guān)系，最終我們只能通過(guò)收緊判斷條件，更多的采用靜態(tài)編碼以避免加速失效。所以碼表和碼表的選擇條件，還需要更多的實(shí)驗(yàn)檢驗(yàn)和數(shù)學(xué)證明。

參考文獻(xiàn)：

[1]Latha Pillai，“Huffman Coding”EXILINX， Virtex Series， XAPP616 （vl.0） Apr 22， 2003

[2]方敏，泰曉新動(dòng)態(tài)哈夫曼編碼的數(shù)據(jù)壓縮方法[J]計(jì)算機(jī)世界，1994（7）：29-33

[3]Matai， Janarbek，J Y Kim， and R Kastner”Energy efficient canonical huffman encoding.”IEEE， International Conference On Application-Specific Systems， Architectures and ProcessorslEEE， 2014：202-209

[4]李偉生，李域，王濤一種不用建造Huffman樹(shù)的高效Huffman編碼算法[J].中國(guó)圖像圖形學(xué)報(bào)，2005，10（3）：382-387

[5]林建英，伍勇，李建華，等一種易于硬件實(shí)現(xiàn)的快速自適應(yīng)哈夫曼編碼算法[J]大連理工大學(xué)學(xué)報(bào).2008，48（3）：436-440

[6]張全伙，于洪斌，林榆優(yōu)化哈夫曼編碼數(shù)據(jù)壓縮技術(shù)及程序?qū)崿F(xiàn)[J]華僑大學(xué)學(xué)報(bào)（自然科學(xué)版）.1995，16（3）：344-348

[7]張穎超基于FPGA的Huffman編碼并行實(shí)現(xiàn)及高速存儲(chǔ)系統(tǒng)設(shè)計(jì)[D]長(zhǎng)安大學(xué)，2015

[8]Latha Pillai，“Huffman Coding”EXILIN×， Virtex Series， XAPP616 （vl.0） Apr 22， 2003