<meter id="pryje"><nav id="pryje"><delect id="pryje"></delect></nav></meter>
          <label id="pryje"></label>

          新聞中心

          EEPW首頁(yè) > 設(shè)計(jì)應(yīng)用 > 基于verilog實(shí)現(xiàn)哈夫曼編碼的新方法

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

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

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

          本文引用地址:http://www.ex-cimer.com/article/201711/372158.htm

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

          摘要:傳統(tǒng)的硬件實(shí)現(xiàn)的方法主要有:預(yù)先構(gòu)造表,編碼器通過(guò)查表的方法輸出[1];編碼器動(dòng)態(tài)生成哈夫曼樹(shù),通過(guò)遍歷節(jié)點(diǎn)方式獲取哈夫曼編碼[2-3]。第一種方法從平均碼長(zhǎng)角度看,在很多情況下非最優(yōu);第二種方法需要生成完整的哈夫曼樹(shù),會(huì)產(chǎn)生大量的節(jié)點(diǎn),且需遍歷哈夫曼樹(shù)獲取哈夫曼編碼,資源占用多,實(shí)現(xiàn)較為麻煩。本文基于軟件實(shí)現(xiàn)[4]時(shí),使用哈夫曼樹(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ù)兩種。前一種方法在大多數(shù)情況下不是最優(yōu)編碼,后一種方法不僅需要生成大量節(jié)點(diǎn),而且需要額外硬件模塊實(shí)現(xiàn)遍歷節(jié)點(diǎn)操作。針對(duì)這些問(wèn)題,本文提出一種新的適用于硬件實(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ā)送開(kāi)始計(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)流程

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

          3.1 FIFO模塊

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

          3.2 輸入模塊

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

          3.3 計(jì)算模塊

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

            本文基于哈夫曼樹(shù)的思想構(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ù)輸入開(kāi)始,實(shí)際數(shù)據(jù)以4為并口輸入,測(cè)試字符范圍為“0”至“9”。

            圖4展示了模塊輸出時(shí)序。通過(guò)huf_out_start高電平脈沖表明輸出開(kāi)始。首先輸出各字符編碼序列,包含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ù),減少了資源占用,并避免了遍歷哈夫曼樹(shù)所需的額外操作,實(shí)現(xiàn)方便快捷。

            參考文獻(xiàn):

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

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

            [3]曾英,鄧曙光.基于的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)江.基于的并行全比較排序算法[J].數(shù)字技術(shù)與應(yīng)用,2013(10):126-127.

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



          評(píng)論


          相關(guān)推薦

          技術(shù)專區(qū)

          關(guān)閉
          看屁屁www成人影院,亚洲人妻成人图片,亚洲精品成人午夜在线,日韩在线 欧美成人 (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();