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

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

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

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

引言

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

1 哈夫曼編碼的原理

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

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

　　本文采用自頂而下的設計方式?？傮w框架由一個(gè)頂層模塊、接收模塊、計算模塊、輸出模塊和FIFO模塊構成。頂層模塊由其余4個(gè)模塊連接而成，系統總體結構如圖1所示。

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

3 實(shí)現流程

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

3.1 FIFO模塊

　　本文的FIFO模塊使用vivado的IP核生成，設計時(shí)選擇好相應參數配置，生成verilog文件后即可直接調用。

3.2 輸入模塊

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

3.3 計算模塊

3.3.1 新數據結構及對應的硬件實(shí)現

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

3.3.2 哈夫曼編碼計算流程

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

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

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

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

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

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

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

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

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

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

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

3.4 輸出模塊

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

4 仿真和調試

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

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

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

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

5 結論

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

　　參考文獻：

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

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

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

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

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

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