Tight bounds on the redundancy of Huffman codes

Soheil Mohajer, Payam Pakzad, Ali Kakhbod

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

In this paper, we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.

Original languageEnglish (US)
Article number6239594
Pages (from-to)6737-6746
Number of pages10
JournalIEEE Transactions on Information Theory
Volume58
Issue number11
DOIs
StatePublished - Nov 1 2012

Keywords

  • Huffman code
  • Redundancy
  • Tight bounds

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

Cite this