An SGH-tree based efficient Huffman decoding

Author

Chuang, Yuh-he ; WU, JA-LING

Author_Institution

Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan

Volume

3

fYear

2003

fDate

15-18 Dec. 2003

Firstpage

1483

Abstract

Huffman code [D. A. Huffman, Sept. 1952] is the most well-known and widely used variable-length codes (VLCs) for compressing various kinds of data. Conventional table lookup and/or bit-serial decoding techniques for realizing VLCs are inefficient in memory usage and/or computation time. In this paper, we investigated some existing memory efficient VLC decoding methods [R. Hashemian, 1995], [K. L. Chung, 1997], [H. C. Chen, et al., 1999], [M. Aggarwal and A. Narayan, 2000] and gave some comments and comparisons among them. We also proposed an SGH-tree based data structure to implement Aggarwal´s approach [M. Aggarwal and A. Narayan, 2000] such that a symbol can be decoded in constant time; moreover, the required memory is much smaller than that of the original approach.

Keywords

Huffman codes; decoding; tree data structures; variable length codes; Huffman code; SGH-tree based data structure; bit-serial decoding techniques; table lookup; variable-length codes; Computer science; Costs; Data structures; Decoding; Huffman coding; Laboratories; Multimedia communication; Table lookup; Transform coding; Video coding;

fLanguage

English

Publisher

ieee

Conference_Titel

Information, Communications and Signal Processing, 2003 and Fourth Pacific Rim Conference on Multimedia. Proceedings of the 2003 Joint Conference of the Fourth International Conference on

Print_ISBN

0-7803-8185-8

Type

conf

DOI

10.1109/ICICS.2003.1292713

Filename

1292713