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

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

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

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

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

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

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