基于verilog實(shí)現(xiàn)哈夫曼編碼的新方法

作者 / 賈先韜 張旭 劉澤曦 山東大學(xué) 物理學(xué)院(山東 濟(jì)南 250100)

*大學(xué)生集成電路創(chuàng)新創(chuàng)業(yè)大賽全國總決賽三等獎

摘要：傳統(tǒng)的硬件實(shí)現(xiàn)哈夫曼編碼的方法主要有：預(yù)先構(gòu)造哈夫曼編碼表，編碼器通過查表的方法輸出哈夫曼編碼^[1];編碼器動態(tài)生成哈夫曼樹，通過遍歷節(jié)點(diǎn)方式獲取哈夫曼編碼^[2-3]。第一種方法從平均碼長角度看，在很多情況下非最優(yōu);第二種方法需要生成完整的哈夫曼樹，會產(chǎn)生大量的節(jié)點(diǎn)，且需遍歷哈夫曼樹獲取哈夫曼編碼，資源占用多，實(shí)現(xiàn)較為麻煩。本文基于軟件實(shí)現(xiàn)^[4]時，使用哈夫曼樹，會提出一種適用于硬件并行實(shí)現(xiàn)的新數(shù)據(jù)結(jié)構(gòu)——字符池，通過對字符池的頻數(shù)屬性比較和排序來決定各個字符節(jié)點(diǎn)在字符池中的歸屬。配置字符池的同時逐步生成哈夫曼編碼，可以提高硬件利用率，并且無需額外操作來提取哈夫曼編碼。

引言

　　哈夫曼(Huffman)編碼對出現(xiàn)頻率較高的字符采用較短的編碼，對出現(xiàn)頻率較低的字符采用較長的編碼，它可以保證平均碼長最短，具有較高的編碼效率。因而哈夫曼編碼被廣泛應(yīng)用于數(shù)據(jù)壓縮領(lǐng)域。已有的硬件實(shí)現(xiàn)方法包括預(yù)先構(gòu)造哈夫曼編碼表和模仿軟件實(shí)時生成完整哈夫曼樹兩種。前一種方法在大多數(shù)情況下不是最優(yōu)編碼，后一種方法不僅需要生成大量節(jié)點(diǎn)，而且需要額外硬件模塊實(shí)現(xiàn)遍歷節(jié)點(diǎn)操作。針對這些問題，本文提出一種新的適用于硬件實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)——字符池來對輸入數(shù)據(jù)實(shí)時生成哈夫曼編碼。

1 哈夫曼編碼的原理

　　哈夫曼編碼是一種不等長編碼，根據(jù)每個字符出現(xiàn)頻率進(jìn)行編碼，每個字符的編碼不能是其他字符編碼的前綴，所有字符編碼總長度相比原碼而言將會降低。

2 哈夫曼編碼硬件總體實(shí)現(xiàn)方案

　　本文采用自頂而下的設(shè)計(jì)方式。總體框架由一個頂層模塊、接收模塊、計(jì)算模塊、輸出模塊和FIFO模塊構(gòu)成。頂層模塊由其余4個模塊連接而成，系統(tǒng)總體結(jié)構(gòu)如圖1所示。

　　接收模塊：接收數(shù)據(jù)源并分類統(tǒng)計(jì)各字符出現(xiàn)的頻數(shù)，數(shù)據(jù)接收完成后，接收模塊向計(jì)算模塊發(fā)送開始計(jì)算信號。計(jì)算模塊進(jìn)行計(jì)算，生成各字符對應(yīng)的編碼值，做成編碼表，結(jié)束后向輸出模塊發(fā)送輸出信號。最后輸出模塊通過查表方式輸出各字符的編碼值以及哈夫曼編碼結(jié)果。FIFO模塊用于接收原始數(shù)據(jù)和向輸出模塊提供數(shù)據(jù)源。

3 實(shí)現(xiàn)流程

　　本文使用verilog語言在vivado平臺上進(jìn)行哈夫曼編碼硬件模塊的實(shí)現(xiàn)，選用器件為xc7a100tcsq324-1。

3.1 FIFO模塊

　　本文的FIFO模塊使用vivado的IP核生成，設(shè)計(jì)時選擇好相應(yīng)參數(shù)配置，生成verilog文件后即可直接調(diào)用。

3.2 輸入模塊

　　使用多個計(jì)數(shù)器對輸入各字符頻數(shù)以及輸入字符總量進(jìn)行計(jì)數(shù)，頻數(shù)被存放在寄存器中，當(dāng)字符輸入結(jié)束(例如輸入字符總量達(dá)到了約定值)時，輸入模塊向計(jì)算模塊輸出計(jì)算開始信號，同時頻數(shù)寄存器中的數(shù)據(jù)被并行輸出至計(jì)算模塊。

3.3 計(jì)算模塊

3.3.1 新數(shù)據(jù)結(jié)構(gòu)及對應(yīng)的硬件實(shí)現(xiàn)

　　本文基于哈夫曼樹的思想構(gòu)建了新的數(shù)據(jù)結(jié)構(gòu)——字符池用于硬件實(shí)現(xiàn)哈夫曼編碼。根據(jù)n種字符構(gòu)建n個字符池和n個字符節(jié)點(diǎn)。每個字符池包含一個屬性：包含的所有字符的頻數(shù)之和。每個字符節(jié)點(diǎn)包含以下屬性：所屬字符池序號、自身編碼值和自身編碼長度。因此，定義n個寄存器記錄字符節(jié)點(diǎn)對應(yīng)的字符池序號、n個寄存器記錄編碼值、n個寄存器記錄編碼長度以及n個寄存器記錄字符池的頻數(shù)。

3.3.2 哈夫曼編碼計(jì)算流程

　　進(jìn)行哈夫曼編碼計(jì)算時，計(jì)算模塊通過執(zhí)行循環(huán)操作完成各字符編碼的生成以及字符在字符池中的移動。以圖2中的實(shí)例描述計(jì)算流程。

　　圖2中共有5種字符，各自頻數(shù)為：“0”：5，“1”：10，“2”：20，“3”：30，“4”：35。

　　圖2(a)為初始化效果，此時每個字符池包含一個字符，每個字符池的頻數(shù)恰為那個字符的頻數(shù);每個字符的編碼值和編碼長度清零。圖2(a)到圖2(d)共經(jīng)過4次循環(huán)操作，最終可以從圖2(d)中讀取出每個字符的編碼值和編碼長度，“0”編碼值為0011，“1”編碼值為1011，“2”編碼值為111，“3”編碼值為01，“4”編碼值為0。

　　每次循環(huán)操作包含排序、挑選、最小值和次小值求和、頻數(shù)更新、字符移動、編碼值更新及編碼長度更新8步。其中前4步按順序完成，然后同時完成后4步?？傃h(huán)次數(shù)由字符種類數(shù)控制。

　　排序操作功能是將每個節(jié)點(diǎn)池的頻數(shù)從小到大進(jìn)行排序，本文借鑒了參考文獻(xiàn)[5]中的方法，硬件實(shí)現(xiàn)時通過構(gòu)建比較器陣列將每兩個數(shù)兩兩比較，再通過加法器對每個字符頻數(shù)的比較結(jié)果求和。對一個字符頻數(shù)，若它小于另一個字符的頻數(shù)，則相應(yīng)結(jié)果為0，否則為1。那么通過指定字符頻數(shù)與其他字符頻數(shù)的比較結(jié)果之和可以得知它的頻數(shù)在所有頻數(shù)中的位置。

　　挑選操作是將排序操作中比較結(jié)果為0和1對應(yīng)的字符頻數(shù)選出，它們代表最小頻數(shù)和次小頻數(shù)，挑選操作同時挑選出這兩個頻數(shù)對應(yīng)的字符池ID。硬件實(shí)現(xiàn)時構(gòu)建多個比較器，將比較結(jié)果之和與0和1比較，再通過多路復(fù)用器從多個頻數(shù)和字符池ID中準(zhǔn)確挑選出所需的值。例如在圖2(b)中，挑選出的兩個頻數(shù)為15和20，它們對應(yīng)字符池ID為1和2。

　　接下來的最小值和次小值求和操作就是將挑選操作挑選出的最小頻數(shù)和次小頻數(shù)求和，然后輸出。此步驟硬件實(shí)現(xiàn)時需要一個多位加法器。例如在圖2(b)中，求和值為15+20=35。

　　頻數(shù)更新操作指根據(jù)挑選操作挑選出的結(jié)果進(jìn)行字符池頻數(shù)的更新。按照本文約定方法，將最小頻數(shù)對應(yīng)字符池的頻數(shù)更新成無效值，無效值應(yīng)大于所有可能的頻數(shù)，它的目的是避免此字符池的頻數(shù)被接下來的循環(huán)挑選操作挑選出。本文將次小頻數(shù)對應(yīng)字符池的頻數(shù)以求和操作的加法結(jié)果替代。例如圖2(c)中1號字符池頻數(shù)變成100，2號字符池頻數(shù)變成35。

　　字符移動操作指將特定字符從一個字符池移動到另一個字符池中。按照本文約定方法，將最小頻數(shù)對應(yīng)字符池的所有字符移動到次小頻數(shù)對應(yīng)字符池中。例如將圖2(c)和圖2(b)對比可發(fā)現(xiàn)1號字符池的字符“0”和“1”被移動到了2號字符池中。

　　編碼值、編碼長度更新操作中，按本文約定方法，將最小頻數(shù)對應(yīng)字符池的所有字符編碼值左移1位并在最后一位補(bǔ)0，長度加1。將次小頻數(shù)對應(yīng)字符池的所有字符編碼值左移1位并在最后一位補(bǔ)1，長度加1。將圖2(c)和圖2(b)對比可看出，字符“0”的編碼值從0變成00，“1”編碼值從1變成10，“2”編碼值從無變成1。

　　所有循環(huán)結(jié)束后編碼表已生成，計(jì)算模塊向輸出模塊發(fā)送計(jì)算結(jié)束信號。

3.4 輸出模塊

　　輸出模塊負(fù)責(zé)從FIFO中讀取出原始數(shù)據(jù)、從編碼表中獲取編碼值，再通過并串轉(zhuǎn)換以一位數(shù)據(jù)口首先輸出各字符編碼值，再輸出字符串編碼結(jié)果。

4 仿真和調(diào)試

　　本文使用vivado對頂層模塊進(jìn)行綜合實(shí)現(xiàn)，通過實(shí)現(xiàn)后仿真驗(yàn)證 結(jié)果正確性。

　　圖3展示了模塊輸入時序。本文測試時以huf_in_start高電平脈沖標(biāo)志數(shù)據(jù)輸入開始，實(shí)際數(shù)據(jù)以4為并口輸入，測試字符范圍為“0”至“9”。

　　圖4展示了模塊輸出時序。通過huf_out_start高電平脈沖表明輸出開始。首先輸出各字符編碼序列，包含4bit編碼長度和實(shí)際編碼值，然后輸出原始字符串的編碼值。huf_out_end高電平脈沖表明輸出結(jié)束。

　　圖5為vivado控制臺輸出，它展示了各字符編碼值以及原始字符和testbench進(jìn)行的解碼字符比較，說明模塊正常運(yùn)行。

5 結(jié)論

　　本文提出了一種新的在硬件上實(shí)現(xiàn)哈夫曼編碼的方法，利用本文的字符池?cái)?shù)據(jù)結(jié)構(gòu)，對每次輸入的數(shù)據(jù)實(shí)時生成哈夫曼編碼表，從平均碼長角度保證了編碼的最優(yōu)，同時避免了生成完整的哈夫曼樹，減少了資源占用，并避免了遍歷哈夫曼樹所需的額外操作，實(shí)現(xiàn)方便快捷。

　　參考文獻(xiàn)：

　　[1]鄧麗娟,田金文,柳健,等.哈夫曼編碼器IP核的設(shè)計(jì)與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī),2005(02):9-12.

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

　　[3]曾英,鄧曙光.基于FPGA的Huffman編碼器的設(shè)計(jì)[J].湖南城市學(xué)院學(xué)報(自然科學(xué)版), 2014(01):32-35.

　　[4]楊蘭.基于C語言的哈夫曼編碼的實(shí)現(xiàn)[J].軟件導(dǎo)刊,2012(09):40-42.

　　[5]師廷偉,金長江.基于FPGA的并行全比較排序算法[J].數(shù)字技術(shù)與應(yīng)用,2013(10):126-127.

　　本文來源于《電子產(chǎn)品世界》2017年第12期第40頁，歡迎您寫論文時引用，并注明出處。