Tight bounds on the redundancy of Huffman codes

Soheil Mohajer, Payam Pakzad, Ali Kakhbod

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

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.

Original languageEnglish (US)
Title of host publication2006 IEEE Information Theory Workshop, ITW 2006
Pages131-135
Number of pages5
StatePublished - Nov 21 2006
Event2006 IEEE Information Theory Workshop, ITW 2006 - Punta del Este, Uruguay
Duration: Mar 13 2006Mar 17 2006

Publication series

Name2006 IEEE Information Theory Workshop, ITW 2006

Other

Other2006 IEEE Information Theory Workshop, ITW 2006
Country/TerritoryUruguay
CityPunta del Este
Period3/13/063/17/06

Fingerprint

Dive into the research topics of 'Tight bounds on the redundancy of Huffman codes'. Together they form a unique fingerprint.

Cite this