Tight Upper Bounds on the Redundancy of Huffman Codes

Abstract

Bounds on the redundancy of Huffman codes, in terms of the probability p1, of the most likely source letter, are provided. In particular, upper bounds are presented that are sharper than the recent bounds given by Gallager and by Capocelli et al., for an interval 2/(2l+1 +1) < p1 < 1/(2l -1), l ≥ 2. It is also shown that the new bounds are the tightest possible for these intervals. © 1989 IEEE