《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 可編程邏輯 > 設(shè)計(jì)應(yīng)用 > Huffman并行解碼算法的改進(jìn)與實(shí)現(xiàn)
Huffman并行解碼算法的改進(jìn)與實(shí)現(xiàn)
來(lái)源:微型機(jī)與應(yīng)用2013年第11期
周艷娥1,,葛海波1,,林 界2,,柯奎雄3
(1.西安郵電大學(xué) 電子工程學(xué)院,,陜西 西安 710061,; 2.西安郵電大學(xué) 通信與信息工程學(xué)院,,
摘要: 為了提高Huffman解碼的效率和實(shí)時(shí)性,采用并行處理技術(shù)和改進(jìn)的Huffman并行解碼算法,,設(shè)計(jì)基于現(xiàn)場(chǎng)可編程門(mén)陣列FPGA的Huffman并行解碼器,。在不考慮Huffman編碼長(zhǎng)度的情況下,解碼器通過(guò)插入流水線結(jié)構(gòu)的方法將Huffman碼流的碼流頭和信息碼流分開(kāi),,同時(shí)進(jìn)行解碼,。硬件仿真結(jié)果表明,在一個(gè)時(shí)鐘節(jié)拍內(nèi)解碼器處理的數(shù)據(jù)位數(shù)與解碼效率成正比,,位數(shù)越多,,實(shí)時(shí)性越好,。
Abstract:
Key words :

摘  要: 為了提高Huffman解碼的效率和實(shí)時(shí)性,,采用并行處理技術(shù)和改進(jìn)的Huffman并行解碼算法,設(shè)計(jì)基于現(xiàn)場(chǎng)可編程門(mén)陣列FPGA的Huffman并行解碼器。在不考慮Huffman編碼長(zhǎng)度的情況下,,解碼器通過(guò)插入流水線結(jié)構(gòu)的方法將Huffman碼流的碼流頭和信息碼流分開(kāi),,同時(shí)進(jìn)行解碼。硬件仿真結(jié)果表明,,在一個(gè)時(shí)鐘節(jié)拍內(nèi)解碼器處理的數(shù)據(jù)位數(shù)與解碼效率成正比,,位數(shù)越多,實(shí)時(shí)性越好,。
關(guān)鍵詞: Huffman解碼,;并行解碼器;碼流頭,;流水線結(jié)構(gòu)

 在靜止圖像和運(yùn)動(dòng)視頻的壓縮方法中,,由于信息量大、速率快,,使得編解碼效率的提高迫在眉睫,。最常用的編解碼方式是基于可變長(zhǎng)編碼VLC(Variable-Length Code)的Huffman編解碼[1]。與編碼相比,,并行Huffman解碼較復(fù)雜,。其實(shí)時(shí)性不僅要提高時(shí)鐘頻率,還需要從算法,、硬件優(yōu)化的角度提高,。
通過(guò)改進(jìn)文獻(xiàn)的Huffman解碼算法[2-3],在原有基礎(chǔ)的解碼中加入流水線結(jié)構(gòu),。針對(duì)參考文獻(xiàn)[4]中Huffman編碼方式設(shè)計(jì)并實(shí)現(xiàn)了一種能夠節(jié)省碼字存儲(chǔ)空間的,、可以提高解碼速度的并行Huffman解碼方式。
1 Huffman并行解碼算法改進(jìn)
 Huffman并行解碼方式可以彌補(bǔ)查找表過(guò)大引起硬件開(kāi)銷(xiāo)大的不足,。與并行解碼算法相比[5-7],,本算法在解碼結(jié)構(gòu)中插入流水線,在并行解碼方式中,,當(dāng)頭碼流分析結(jié)束時(shí),,輸入到解碼器中的信息碼采用并行多路檢測(cè),得到地址偏移量和最小編碼的長(zhǎng)度,。在每個(gè)時(shí)鐘周期內(nèi),,都會(huì)輸出一個(gè)解碼信息碼。Huffman并行解碼器總的處理過(guò)程如圖1所示,。

2 JPEG中的Huffman并行解碼設(shè)計(jì)
 在碼流分析中可以得到Huffman編碼時(shí)的相關(guān)信息,,即相同長(zhǎng)度的最小編碼、最小編碼的個(gè)數(shù)和Huffman編碼相關(guān)值,,并分別存入對(duì)應(yīng)的存儲(chǔ)器中,,再把相應(yīng)的地址存入16×8存儲(chǔ)器里,編碼相關(guān)值則存入256×8的寄存器中。還需設(shè)定Huffman解碼的重啟間隔,,這由JPEG的DC差值編碼決定,。為了防止解碼中造成較大的誤差,每解碼m比特就需對(duì)DC進(jìn)行清零,,其中m為重啟間隔度量值,。Huffman并行解碼復(fù)位控制如圖2所示。

 在碼流分析中,,確定Huffman并行解碼的相關(guān)信息后進(jìn)行解碼,。對(duì)JPEG來(lái)說(shuō),最終要找到AC=0的個(gè)數(shù)Run,、AC的位數(shù)Size和幅度Amplitude,,以及DC的Size和Amplitude。在JPEG中,,AC和DC分別是交流系數(shù)和直流系數(shù),,其中AC和DC各自又包含色度和亮度。進(jìn)行一次Huffman并行解碼處理流程是整個(gè)Huffman并行解碼器的關(guān)鍵流程之一,,處理流程如圖3所示,。

 輸入碼流的關(guān)鍵處理是在輸入并行多路檢測(cè)上,它可以同時(shí)處理當(dāng)前對(duì)應(yīng)的最小編碼長(zhǎng)度,、最小編碼的解碼及其地址偏移量,。通過(guò)對(duì)輸入碼流的處理,最終得到Huffman并行解碼所需要最小編碼的Run,、Size,、Amplitude信息,其并行多路實(shí)現(xiàn)方式如圖4所示,。獲得當(dāng)前編碼的寬度提供給當(dāng)前解碼器使用,。在當(dāng)前編碼進(jìn)行對(duì)應(yīng)的最小編碼的處理時(shí),同時(shí)與在碼流分析中得到的存入存儲(chǔ)器的最小編碼進(jìn)行比較,,確定當(dāng)前碼流解碼需要的間隔,。其具體過(guò)程如圖5所示,其中DC,、AC就是從碼流分析中存入存儲(chǔ)器的,。解碼獲得Run、Size及Amplitude的實(shí)現(xiàn)流程方式如圖6,、7所示,。但是要注意DC中Huffman并行解碼只能得到相應(yīng)最小編碼的Size和Amplitude。而在AC中Huffman并行解碼可以得到相應(yīng)最小編碼的Run,、Size及Amplitude,。

 關(guān)于解碼DC中獲得R/S,,采用相對(duì)地址和絕對(duì)地址尋址,即當(dāng)前最小編碼的地址=基本最小編碼地址+相對(duì)地址(差值),。對(duì)不同的4種碼表,,第一個(gè)編碼的基本地址都是固定的,,由于DC中個(gè)數(shù)最大值為126,,而AC中個(gè)數(shù)最大值為162。因此將第一個(gè)亮度DC地址設(shè)為0,,第一個(gè)亮度AC地址的設(shè)為12,;第一個(gè)色度DC地址設(shè)為114,第一個(gè)色度AC地址為156,。對(duì)于不同長(zhǎng)度編碼同一分量的最小地址,,直接采用該分量第一個(gè)編碼地址與小于該長(zhǎng)度編碼個(gè)數(shù)的和。從待解碼數(shù)據(jù)流的輸入到確定R/S,、Amplitude,,都采用并行多路檢測(cè)的方法。與串行解碼方式相比大大提高了碼流的解碼速度,。
 在并行Huffman解碼結(jié)構(gòu)中,,處理了幾位編碼后,補(bǔ)上相應(yīng)個(gè)數(shù)的新的待解編碼,,補(bǔ)充的位數(shù)是由Size和Amplitude值決定的,。由于每次解碼碼長(zhǎng)的不確定性,本文采用桶型移位寄存器,,但是會(huì)占有一定的面積資源,。因?yàn)槊看我莆坏奈粩?shù)也是不確定的,所以必須要考慮移位溢出的情況,。設(shè)計(jì)中選用32位移位寄存器和16位桶型移位寄存器,,前者相當(dāng)于一個(gè)緩存器,其[15:0]的后半段寄存器進(jìn)行解碼操作,,[31:16]后半段寄存器存入桶型移位寄存器中,。當(dāng)最小編碼等于16時(shí),Amplitude值從桶型寄存器中移出,;若操作編碼流長(zhǎng)度大于16,,需要由32位寄存器對(duì)它進(jìn)行移位補(bǔ)位,[15:0]和[31:16]共同移位,。當(dāng)移位位數(shù)超過(guò)48時(shí),,設(shè)計(jì)一個(gè)累加器向外輸出碼流輸入允許信號(hào),繼續(xù)輸入碼流到32位寄存器中,。此外,,輸入解碼器數(shù)據(jù)位寬在0~32范圍內(nèi)變化,,實(shí)際輸入的待解碼數(shù)據(jù)位寬將取決于該編碼數(shù)據(jù)在Huffman編碼樹(shù)中的位置。
3 Huffman并行解碼的實(shí)現(xiàn)
 將Run,、Size及Amplitude值存入相應(yīng)的寄存器后,,為JPEG后續(xù)的解碼做準(zhǔn)備。同時(shí)也就完成了一次Huffman并行解碼,,所有的解碼處理過(guò)程都是同步進(jìn)行的,。經(jīng)過(guò)驗(yàn)證,Huffman并行解碼處理過(guò)程是在一個(gè)時(shí)鐘周期內(nèi)實(shí)現(xiàn)解一個(gè)編碼,。由于FPGA實(shí)現(xiàn),,需采用很多組合邏輯,因此關(guān)鍵路徑的延時(shí)必須考慮在內(nèi)[8-9],。同時(shí)該硬件實(shí)現(xiàn)中也用到了許多存儲(chǔ)器,,所以會(huì)占有一定FPGA的面積資源,與串行解碼相比,,在速度上和輸出的穩(wěn)定性上有一定的優(yōu)勢(shì),。其中具體環(huán)節(jié)的硬件實(shí)現(xiàn)框架如圖8所示。

 圖8中各模塊的性能為:
?。?)16位最小碼存儲(chǔ)器,。存放的是DC和AC的最小編碼。
?。?)16位最小碼解碼模塊,。輸入的16位待解碼流與最小編碼進(jìn)行比較,找到相同長(zhǎng)度的最小編碼,,輸出Huffman最小編碼到R/S存儲(chǔ)器,,輸出與相應(yīng)最小編碼同等長(zhǎng)度的實(shí)際碼子到數(shù)選器[10]。
?。?)16:1數(shù)選器,。差值=實(shí)際編碼長(zhǎng)度-最小編碼長(zhǎng)度。
?。?)16位最小碼存儲(chǔ)器,。預(yù)存的最小編碼地址,16×8的寄存器,。
?。?)8位加法器。最小編碼的地址+差值=實(shí)際編碼的地址,。
?。?)最小碼R/S存儲(chǔ)器。預(yù)存R/S和所有與Huffman相對(duì)應(yīng)的值在256×8的寄存器中,,最終解碼解出相應(yīng)的R/S,。
?。?)16:4數(shù)選器。把16位編碼的長(zhǎng)度換成4位表示,。
?。?)4位加法器。最小編碼的長(zhǎng)度+差值Size=解碼時(shí)一共處理的位數(shù),,即需要補(bǔ)入數(shù)據(jù)流的位數(shù),。
 (9)運(yùn)算器,。累加器是將移位的總位數(shù)進(jìn)行相加,,并向移位器提供當(dāng)前移位位數(shù),。當(dāng)總數(shù)≥16時(shí),,輸出輸入數(shù)據(jù)允許信號(hào),請(qǐng)求前置模塊輸入數(shù)據(jù),,在輸入允許信號(hào)有效時(shí),,刷新運(yùn)算器的值;當(dāng)總數(shù)≥32時(shí),,輸入允許信號(hào)仍未有效,,則終止后續(xù)的操作。
?。?0)32移位寄存器,。對(duì)輸入數(shù)據(jù)進(jìn)行存儲(chǔ)和移位。
?。?1)16移位寄存器,。移出幅度的值,選用桶型移位寄存器的原因是當(dāng)移出位數(shù)>16時(shí)也可以處理,。
與串行解碼相比,,Huffman并行解碼算法的優(yōu)點(diǎn)是在一個(gè)時(shí)鐘周期內(nèi),無(wú)論Huffman編碼的長(zhǎng)度是多少,,都可以正確解出編碼信息,。數(shù)據(jù)處理速度的提高,顯然會(huì)伴隨硬件FPGA設(shè)計(jì)的復(fù)雜度的增加,。本文采用并行處理技術(shù)給出了Huffman解碼算法,,實(shí)現(xiàn)了Huffman并行解碼器的設(shè)計(jì)。不但能夠在一個(gè)時(shí)鐘節(jié)拍內(nèi)處理多比特?cái)?shù)據(jù),,而且節(jié)省了存儲(chǔ)空間,,克服了Huffman串行解碼實(shí)時(shí)性差的不足。顯然,,本算法的實(shí)現(xiàn)是在提高處理數(shù)據(jù)速度的同時(shí),,增加了FPGA硬件的面積資源,。
參考文獻(xiàn)
[1] 宋奇剛,魏小義.霍夫曼解碼器的設(shè)計(jì)及在MP3解碼中的應(yīng)用[J].今日電子,,2005(3):10-12.
[2] 李曉飛.Huffman編解碼及其快速算法研究[J].現(xiàn)在電子技術(shù),,2009(21):102-108.
[3] 陳亞光,陳少平,,朱翠濤,,等.并行Huffman解碼器算法分析[J].計(jì)算機(jī)測(cè)量與控制,2002,,10(6):418-420.
[4] 雒莎,,葛海波.基于查找表的自適應(yīng)Huffman編碼算法[J].西安郵電學(xué)院報(bào),2011,,16(5):76-79.
[5] 楊浪花,,張濤,于鳳萍,,等.MP3/AAC解碼器中Huffman硬件加速器設(shè)計(jì)與實(shí)現(xiàn)[J].電聲技術(shù),,2010(6):55-59.
[6] 陳佳昕,林濤.一種優(yōu)化了的并行Huffman解碼器[J].有線電視技術(shù),,2007(8):47-50.
[7] 方嬋嬋,,葉兵,吳彪,,等.Huffman并行解碼結(jié)構(gòu)及硬件實(shí)現(xiàn)[J].合肥工業(yè)大學(xué)學(xué)報(bào),,2007,30(7):855-857.
[8] 傅祖蕓.信息論基礎(chǔ)理論與應(yīng)用[M].北京:電子工業(yè)出版社,,2001.
[9] 馬建國(guó),,孟憲元.FPGA現(xiàn)代數(shù)字系統(tǒng)設(shè)計(jì)(第1版)[M].北京:清華大學(xué)出版社,2010.
[10] PALNITKAR S.Verilog HDL數(shù)字設(shè)計(jì)與綜合(第2版)[M].夏宇聞,,胡燕祥,,刁嵐松,等譯.北京:電子工業(yè)出版社,,2009.

此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載。