一种基于八叉树的Huffman解码方法及其在MPEG-4中的应用
doi: 10.3724/SP.J.1146.2007.00066
An Octonary Huffman Decoding Method and Its Application to MPEG-4
-
摘要: 传统的二值Huffman解码方法的解码效率较低。为了提高解码速度，该文提出了一种基于八叉树的Huffman解码方法。该方法将Huffman码表示为八叉树结构，并根据各个节点在树中的位置将码表重建为一维数组。解码时，每次从码流中读取3 bit码元，并使用数值计算代替判断和跳转操作，从而提高了解码效率。将本文方法应用于MPEG-4 VLC和RVLC解码的实验结果表明，该方法在内存增加不大的情况下能大幅度提高Huffman解码效率，其性能优于其它方法。Abstract: The efficiency of traditional binary Huffman decoding method is very low. A new decoding method based on octonary Huffman trees is presented in this paper to improve the decoding speed. Huffman codes are represented as an octonary tree and reconstructed as a single dimensional array according to the position of each node in the tree. When decoding, three bit code elements are read from the bitstream each time, and direct numerical computation may be used to replace judge and jump operations, which improve decoding efficiency. The proposed method is also applied to VLC and RVLC decoding algorithms of MPEG-4. Experiment results demonstrate that the proposed method can greatly improve decoding efficiency without increasing memory consumption much, and it exhibits better performance than other decoding methods.
-
Huffman D A. A method for the construction of minimumredundancy codes[J].Proceedings of IRE.1952, 40(10):1098-1101[2]Jain A K. Image data compression: An overview[J].Proc. IEEE.1981, 69(3):349-389[3]Bell T C, Cleary J G, and Witten I H. Text Compression.New Jersey: Prentice-Hall, 1990: 102-108.[4]Schwartz E S and Kallick B. Generating a canonical prefixencoding[J].Communications of the ACM.1964, 7(3):166-169[5]Chung K L and Wu J G. Level-compressed Huffman decoding[J].IEEE Trans. on Communications.1999, 47(10):1455-1457[6]Tanka H. Data structure of Huffman codes and itsapplication to efficient encoding and decoding[J].IEEETransactions on Information Theory.1987, 33(1):154-156[7]Ho S and Law P. Efficient hardware decoding method formodified huffman code[J].Electronics Letters.1991, 27(10):855-856[8]Nekritch Y. Decoding of canonical Huffman codes withlook-up tables. Proceedings of Data Compression Conference,Snowbird, UT, USA, 2000: 566-567.[9]Hashemian R. Condensed table of Huffman coding, a newapproach to efficient decoding[J].IEEE Trans. onCommunications.2004, 52(1):6-8[10]Lee J S, Jeong J H, and Chang T G. An efficient method ofHuffman decoding for MPEG-2 AAC and its performanceanalysis[J].IEEE Trans. on Speech and Audio Processing.2005,13(6):1206-1209[11]Hashemian R. Design and hardware implementation of amemory efficient Huffman decoding[J].IEEE Trans. onConsumer Electronics.1994, 40(3):345-352[12]Hashemian R. Memory efficient and high speed searchHuffman coding[J].IEEE Trans. on Communications.1995,43(10):2576-2581[13]Aggarwal M and Narayan A. Efficient Huffman decoding.International Conference on Image Processing, Vancouver,BC, 2000: 936-939.[14]International Standard ISO/IEC 14496-2 (MPEG-4).Information Technology-Coding of Audio-Visual Objects-Part 2: Visual. 2002.[15]ISO/IEC JTC1/SC29/WG11 N4668. Overview of MPEG-4Standard. 2002.[16]Texas Instrument. TMS320C6000 CPU and Instruction SetReference Guide. 1999. -
计量
- 文章访问数: 2942
- HTML全文浏览量: 74
- PDF下载量: 1357
- 被引次数: 0
下载:
