Title :
Tight Bounds on the Redundancy of Huffman Codes
Author :
Mohajer, Soheil ; Pakzad, Payam ; Kakhbod, Ali
Author_Institution :
School of Computer and Communication Sciences, Ecole Polytechnique Fédérale de Lausanne, Switzerland, Email: soheil.mohajer@epfl.ch
Abstract :
In this paper we derive tight upper and lower bounds on the redundancy of the Huffman code on a source, for which the probability of one of the symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound, and we use a simple argument to derive the lower bounds. Several other previously known bounds with different constraints follow immediately from our results.
Keywords :
Binary codes; Darmstadtium; Encoding; Entropy; Probability distribution; Upper bound;
Conference_Titel :
Information Theory Workshop, 2006. ITW '06 Punta del Este. IEEE
Conference_Location :
Punta del Este, Uruguay
Print_ISBN :
1-4244-0035-X
Electronic_ISBN :
1-4244-0036-8
DOI :
10.1109/ITW.2006.1633796
