Title :
A new upper bound on the data expansion of Huffman codes
Author :
Shen, Jia-Pei ; Gill, John
Author_Institution :
Inf. Syst. Lab., Stanford Univ., CA, USA
Abstract :
We prove that the maximum data expansion of Huffman coding is at most 0.83485 bits per symbol, improving on the previous best known bound of 1.268 bits per symbol. The bound is very close to the 0.8 bits per symbol conjectured by Cheng et al. (1995)
Keywords :
Huffman codes; source coding; Huffman codes; maximum data expansion; upper bound; Huffman coding; Information systems; Laboratories; Probability distribution; Size measurement; Tree data structures; Upper bound;
Conference_Titel :
Information Theory, 2000. Proceedings. IEEE International Symposium on
Conference_Location :
Sorrento
Print_ISBN :
0-7803-5857-0
DOI :
10.1109/ISIT.2000.866670
