Tight Bounds on the Redundancy of Huffman Codes

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.


Published in:
Ieee Transactions On Information Theory, 58, 11, 6737-6746
Year:
2012
Publisher:
Piscataway, Ieee-Inst Electrical Electronics Engineers Inc
ISSN:
0018-9448
Keywords:
Laboratories:




 Record created 2013-02-27, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)