魯云飛，何明華

（1.福州大學電氣工程與自動化學院，福建福州350108；2.福州大學物理與信息工程學院，福建福州350108）

基于四叉樹的嵌入式平臺Huffman解碼優(yōu)化

魯云飛1，何明華2

（1.福州大學電氣工程與自動化學院，福建福州350108；2.福州大學物理與信息工程學院，福建福州350108）

考慮到嵌入式設備資源的有限性，提出一種基于四叉樹的Huffman解碼優(yōu)化算法.解碼過程中，先將Huffman碼表表示成四叉樹結構，據(jù)此重建為一維數(shù)組，并充分利用數(shù)值計算代替判斷與跳轉操作.為測試本算法解碼性能，將其應用于嵌入式MP3實時解碼中，結果表明本算法內(nèi)存損耗小，解碼速率快，算法復雜度低，相比于其他優(yōu)化算法，更適合應用于嵌入式設備中.

嵌入式；四叉樹；Huffman解碼；解碼優(yōu)化；MP3音頻

Huffman編碼是一種高效的無失真信源熵編碼，作為無損信源壓縮的重要方法，該編碼算法在文本、音頻、圖像、視頻等多種多媒體數(shù)據(jù)壓縮中得到廣泛應用［1－2］.Huffman解碼的實現(xiàn)分硬件實現(xiàn)和軟件實現(xiàn).其中，硬件實現(xiàn)需采用專用集成電路或芯片，解碼效率雖高，但解碼成本也高，系統(tǒng)硬件依賴性強，解碼靈活度小；而軟件實現(xiàn)則依靠處理器采用軟件編程為手段，雖效率較前者稍低，但系統(tǒng)開發(fā)成本小，靈活度大.傳統(tǒng)的Huffman解碼軟件實現(xiàn)算法主要有順序搜索法、二值樹法、查表法等［1－5］.但這些算法分別存在搜索時間長、解碼速率低及內(nèi)存損耗大等問題，因此，不少學者以此為基礎，提出了一系列的改進算法.Hashemian及董培良等（以下簡稱Hashemian等算法）提出每次從碼流中讀取r比特碼元，減少了解碼效率對碼長的依賴［2－4］；Aggarwal等［5］基于特征分類方法提出解碼思想，解決了解碼效率對碼長的依賴問題；Lee等［6］提出了改進二值解碼算法（以下簡稱Lee算法），用數(shù)值計算代替每步解碼時的判斷與跳轉操作，其解碼效率在一定程度上得到提高.然而，隨著生活質(zhì)量的提高與生活節(jié)奏的加快，人們對娛樂設備的要求也越來越高，即要求設備便攜的同時還能提供高質(zhì)量與多功能的服務［6－8］.這就需要在不影響功能效果的前提下盡量減小單個功能模塊的內(nèi)存損耗，充分利用嵌入式設備的有限存儲空間和能源供給.基于此，本文結合Hashemian等算法中的多位操作及Lee算法中的數(shù)值計算等優(yōu)點，提出了基于四叉樹的Huffman解碼優(yōu)化算法.

1 基于四叉樹的Huffman解碼算法

1.1 Huffman碼表四叉樹形結構的建立

常規(guī)的多媒體數(shù)據(jù)解碼時，其Huffman碼多采用二值Huffman樹表示.圖1為二值Huffman樹，即將表1中的Huffman碼字用二值樹表示時的樹形圖.為方便算法闡述，表1所示的碼表來源于MPEG1音頻數(shù)據(jù)layer 3的部分標準Huffman碼表［9］.如圖1所示，從根節(jié)點出發(fā)，每次從碼流中讀取1 bit的碼元，根據(jù)這個數(shù)據(jù)的數(shù)值進行跳轉，若為1則跳轉到右節(jié)點，反之則跳轉到左節(jié)點；以此類推，直到跳轉至二叉樹的葉節(jié)點，即可得到碼字所代表的字符［10］.

從圖1可看到：二值Huffman樹對碼流一位一位進行操作，其碼字的搜索次數(shù)多，搜索深度廣，因而解碼效率低.為提高Huffman解碼過程中對碼字的搜索速度，采用Hashemian等算法中的多位操作思想，以縮短解碼過程中對碼字的搜素深度.然而，由于Huffman碼為單義碼，且為前綴碼，碼中無任何碼字為其他碼字的前綴，所以會出現(xiàn)相同前綴的碼字解出相同結果的情況.為盡量減小這種情況所帶來的大量內(nèi)存冗余，提高嵌入式設備內(nèi)存使用效率，本算法一次性對碼流的2位碼元進行操作，將標準Huffman碼表重建成四叉樹結構，如圖2所示.圖2中：根節(jié)點表示Huffman樹的開始；葉子節(jié)點表示某個碼字的結束，其處存儲著該碼字所代表的字符；中間節(jié)點對應碼字的碼元；空節(jié)點表示該節(jié)點為無意義節(jié)點.

表1 MP3部分標準Huffman碼表Tab.1 Part of the MP3 Huffman code table

圖1 二值Huffman樹Fig.1 Binary Huffman tree

從圖2可看出：該四叉碼樹同樣由父節(jié)點及子節(jié)點組成，每個節(jié)點對應2個碼元，且每個節(jié)點下面最多有4個子節(jié)點，從左到右分別代表讀入的碼字為“00”～“11”的搜索路徑.因而解碼時，每經(jīng)過四叉Huffman樹一個節(jié)點，相當于從碼流中讀取2個比特碼元進行Huffman碼字匹配，故理論上對每個Huffman碼字解碼的搜索深度及搜索時間最多可減少為原二叉樹的1／2.

由于一次性只對碼流的2位碼元進行操作，當碼長為2的整數(shù)倍時，最后一組剩余的碼元個數(shù)為2，因而該組碼元即與四叉樹中節(jié)點是一一對應關系，如圖2中的S2～S5；當碼長不是2的整數(shù)倍時，最后一組剩余的碼元個數(shù)為1，此時該組碼元對應兩個具有相同前綴的節(jié)點，即如待解的Huffman碼字長度為L，M＝L mod N（N為單次處理碼元的位數(shù)），則需要填補（2M－1）個節(jié)點，各節(jié)點數(shù)值大小從左到右，從上到下依次遞增“01”，如圖2中的S1，S6及S7.從圖2可知：本四叉Huffman樹的冗余度較小.

1.2 四叉Huffman碼樹信息的存儲

四叉Huffman樹重建完后，還需根據(jù)其結構將所帶數(shù)據(jù)信息存儲起來.為進一步提高解碼速度，減少二值Huffman解碼算法中大量“比較跳轉”操作所消耗的時間，可采用Lee等數(shù)值運算的方法，將圖2所示的四叉樹信息存儲成一維數(shù)組形式以供解碼時使用，所建一維數(shù)組Array［］如表2所示.

圖2 四叉Huffman樹Fig.2 Quad Huffman tree

表2 所建一維數(shù)組Tab.2 Single dimensional array constructed

在重建數(shù)組時，將四叉樹中的節(jié)點按照從上到下、從左到右的順序排列后，依次分配給數(shù)組中的元素，因而，數(shù)組元素的索引值index隨著節(jié)點數(shù)目的增加而增加.除此之外，數(shù)組Array［］中的每個節(jié)點包含3個變量：F，el，rv.其中：F用以表示該節(jié)點是否為葉節(jié)點，若F為0，則該節(jié)點為中間節(jié)點，否則為葉子節(jié)點；el用于表示中間節(jié)點中的有效碼元個數(shù)，且el的取值為1～2；rv用于表示中間節(jié)點到其子節(jié)點0的偏移距離.如表2所示，數(shù)組中的每個元素代表1個節(jié)點，且第1行的數(shù)據(jù)表明了節(jié)點在四叉樹中所屬的層數(shù)，表中前4個元素對應樹的第1層節(jié)點，后5個對應樹的第2層，最后4個則對應樹的第3層.以四叉樹中第2層左起第3個節(jié)點為例，其對應表2中索引Index值為6的元素，且其為中間元素，有效碼元個數(shù)為2，到其0子節(jié)點的偏移距離為6，即索引值為12處的元素.

1.3 碼流的Huffman解碼

利用重建好的Huffman碼四叉樹型結構及其對應的一維數(shù)組，對讀入的碼流進行相應Huffman解碼，其流程如圖3所示.具體解碼過程如下：

1）先初始化查找表的基地址；

2）從輸入的碼流中讀取2 bit碼元，并將新讀入碼元值new＿2digit與初始基地址（即初始索引值Index）之和作為新索引地址值Index，從而得到當前查找節(jié)點的地址；

3）從數(shù)組中該節(jié)點的F值判斷該節(jié)點是否為葉子節(jié)點，若是，則終止本次搜索，并將該節(jié)點數(shù)組中存儲的碼字Array［］.rv讀取出來；否則，將該節(jié)點數(shù)組中存儲的偏移值rv讀出來，并與過程2）所得新索引值Index相加，再轉到步驟2）繼續(xù)搜索，直至遇到葉子節(jié)點，則該分支碼字搜索結束；

4）依次遞推搜索直至將輸入碼流解碼完畢；

5）將搜索出來的碼字依次排列起來，即為輸入Huffman碼流所對應解碼后的碼字.

當對一輸入Huffman碼流解碼連續(xù)出現(xiàn)多個中間節(jié)點時，可將圖3所示流程中計算下一分支地址索引值的過程直觀地歸納為：index∶＝index＋Array［index］.rv＋new＿2digit.以防止索引值多次疊加時出錯，以輸入Huffman碼流“010100101”解碼為例，其解碼結果為“S3S7”，在碼字“S7”所對應的碼元解碼時就連續(xù)出現(xiàn)對3個中間節(jié)點操作的情況.

圖3 基于四叉樹結構的Huffman解碼流程Fig.3 Huffman decode flow base on quad－tree

2 實驗結果及算法性能分析

根據(jù)以上四叉樹Huffman解碼優(yōu)化算法原理，以軟件編程方式實現(xiàn)其解碼過程，并將其應用到嵌入式MP3解碼中，以測試該算法解碼性能.為便于各算法性能的比較，分別以W1，W2，W3表示Lee算法（改進二值法）、Hashemian等算法（以一次性操作3位即八叉樹來代替）和本文提出的基于四叉樹的Huffman解碼算法.以5個不同碼率的MP3文件作為測試文件，測試表明算法W1，W2，W3消耗的內(nèi)存分別為0.62，1.23，0.75 KB，而所需解碼時間以及解碼指令數(shù)情況如表3所示.

由測試結果可知：若以W1算法的Huffman解碼算法為基準，W3算法內(nèi)存損耗增加少，約為W1算法的21%，而W2算法所耗內(nèi)存增量大，約為W1算法的98%，換而言之，W2算法帶來了很大的內(nèi)存冗余.根據(jù)表3數(shù)據(jù)可知：當對不同碼率的文件進行測試時，所需的Huffman解碼時間及指令數(shù)都各有不同.就解碼時間而言，相比于W1算法，W3算法節(jié)省了約為47.5%，而W2算法節(jié)省的略多于W3算法，即約為W1算法的62.6%，也即W2算法的解碼速度略快于W3算法；就解碼所需指令數(shù)而言，相比于W1算法，W3算法總指令數(shù)約為W1算法的57%，而W2算法約為W1算法的44%，即W3算法的指令數(shù)略多于W2算法.

表3 3種Huffman解碼算法解碼時間及算法指令數(shù)Tab.3 Three different Huffman decode algorithm decoding time and instruction number

3 結論

Lee的改進二值法雖內(nèi)存損耗小，但解碼所耗時間長，算法復雜度高，因而算法的解碼實時性較差，不適合應用于嵌入式設備多媒體應用程序開發(fā)當中.Hashemian等算法的Huffman解碼效率較好，實時性較高，但其內(nèi)存損耗大，因而對于內(nèi)存有限的嵌入式開發(fā)并不合適.所提出的基于四叉樹的Huffman解碼算法綜合了以上兩類算法的優(yōu)點.相比于Lee的改進二值法，在內(nèi)存損耗增加不明顯的情況下，顯著提高了Huffman的解碼性能；相比于Hashemian等算法，其解碼性能雖有所降低，但卻能明顯改善系統(tǒng)的內(nèi)存冗余，提高內(nèi)存的利用率，符合嵌入式開發(fā)的實時性與內(nèi)存低損耗性要求.因此，可更靈活地移植到嵌入式環(huán)境下多種多媒體數(shù)據(jù)解碼中，具有一定的普適性.

［1］ 倪昕，王維東，劉鵬，等.媒體處理器視頻哈夫曼解碼快速算法［J］.浙江大學學報：工學版，2007，41（12）：2036－2039.

［2］ 董培良，俞日龍，廖天康，等.一種快速霍夫曼解碼算法及其軟硬件實現(xiàn)［J］.復旦學報：自然科學版，2002，41（2）：165－169.

［3］ HASHEMIAN R.Memory efficient and high speed search Huffman coding［J］.IEEE Trans on Communications，1995，43（10）：2576－2581.

［4］ HASHEMIAN R.Condensed table of Huffman coding，a new approach to efficient decoding［J］.IEEE Transactions on Communications，2004，52（1）：6－8.

［5］ AGGARWAL M，NARAYAN A.Efficient huffman decoding［C］∥International Conference on Image Processing.Vancouver：［s.n.］，2000：936－939.

［6］ LEE J S，JEONG J H，CHANG T G.An efficient method of Huffman decoding for MPEG－2 AAC and its performance analysis［J］.IEEE Trans on Speech and Audio Processing，2005，13（6）：1206－1209.

［7］ WANG Sung－wen，WU Ja－ling，CHUANG Shang－chih.Memory efficient hierarchical lookup tables for mass arbitrary－side growing huffman trees decoding［J］.IEEE Trans on Circuits and Systems for Video Technology，2008，18（10）：1335－1346.

［8］ PHAM H A，BUI V H，DINH－DUC A V.An adaptive huffman decoding algorithm for MP3 decoder［C］∥Fifth IEEE International Symposium on Electronic Design，Test ＆Applications.Washington D C：IEEE Computer Society，2010：153－157.

［9］ ISO／IEC.ISO／IEC 11172－3－1994 Information technology：Coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit／s：Part 3：Audio［S］.Geneva：ISO／IEC，1994.

［10］ 朱坤旺，傅文淵，凌朝東.低功耗H.264 Baseline解碼IP核設計［J］.華僑大學學報：自然科學版，2011，32（3）：280－283.

Embedded Platform Huffman Optimization Decoding Algorithm Base on Quad－Tree

LU Yun－fei1，HE Ming－h(huán)ua2
（1.College of Electric Engineering and Automation，F(xiàn)uzhou University，F(xiàn)uzhou 350108，China；2.College of Physics and Telecommunication Engineering，F(xiàn)uzhou University，F(xiàn)uzhou 350108，China）

Considering the limitation of embedded system resources，a Huffman decoding optimization algorithm based on the quad tree is proposed in this paper.In this process，the Huffman code table is expressed as quad tree structure at first，and according to which a one－dimensional array is reconstructed，then make full use of numerical calculation instead of judgment and jump operation.In order to test the decoding performance，the method is applied to the embedded realtime MP3 decoding.The results show that the algorithm memory loss is small，decoding speed is rapid and its complexity is low，compared to other optimization algorithms，this algorithm is more suitable for application in embedded devices.

embedded；quad－tree；Huffman decoding；decoding optimization；MP3 audio

TP 391

A

（責任編輯：黃曉楠 英文審校：吳逢鐵）

1000－5013（2012）05－0499－04

2012－01－22

何明華（1971－），男，教授，博士生導師，主要從事嵌入式系統(tǒng)與系統(tǒng)級芯片設計的研究.E－mail：mhhe＠fzu.edu.cn.

福建省科技重大專項（2009HZ0007 1）