Tight Bounds on the Redundancy of Huffman Codes

Details Tight Bounds on the Redundancy of Huffman Codes Tight Bounds on the Redundancy of Huffman Codes

2005-08-04

arxiv.org/abs/cs/0508039v2

Computer Science

Information Theory

12 pages, 7 figures, submitted to IT workshop 2006

Scientific paper

In this paper we have obtained tight upper and lower bounds on the redundancy of the Huffman code for a source, for which the probability of one of the symbols is known. Our upper bound proves a conjecture of Ye and Yeung, and our lower bound extends and completes several arlier partial results. We have further discussed the explicit form of the distributions that achieve each of these bounds. Our arguments can be extended to the case of the $D$-ary Huffman codes, and some of these extensions are included in this paper.

Affiliated with

Also associated with

No associations

Rating

Tight Bounds on the Redundancy of Huffman Codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight Bounds on the Redundancy of Huffman Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight Bounds on the Redundancy of Huffman Codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-614159