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

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

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

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

引言

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

1 哈夫曼編碼的原理

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

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

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

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

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

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

3.1 FIFO模塊

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

3.2 輸入模塊

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

3.3 計(jì)算模塊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 輸出模塊

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

4 仿真和調(diào)試

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

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

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

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

5 結(jié)論

　　本文提出了一種新的在硬件上實(shí)現(xiàn)哈夫曼編碼的方法，利用本文的字符池?cái)?shù)據(jù)結(jié)構(gòu)，對(duì)每次輸入的數(shù)據(jù)實(shí)時(shí)生成哈夫曼編碼表，從平均碼長(zhǎng)角度保證了編碼的最優(yōu)，同時(shí)避免了生成完整的哈夫曼樹，減少了資源占用，并避免了遍歷哈夫曼樹所需的額外操作，實(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)及高速存儲(chǔ)系統(tǒng)設(shè)計(jì)[D].長(zhǎng)安大學(xué),2015.

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

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

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

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