Title :
Tight bounds on the redundancy of Huffman codes
Author :
Manstetten, Dietrich
Author_Institution :
Lehrstuhl fuer Angewandte Math. Insbesondere Inf., RWTH Aachen, Germany
fDate :
1/1/1992 12:00:00 AM
Abstract :
A method for deriving optimal upper bounds on the redundancy of binary Huffman codes in terms of the probability p1 of the most likely source letter is presented. This method will be used to compute bounds for all p1⩾1/127, which were previously known only for a few special cases. Furthermore, the known optimal lower bound for binary Huffman codes is generalized to arbitrary code alphabets and some upper bounds for D-ary Huffman codes, 2⩽D<∞, are given, which are the tightest possible for all p1⩾1/2
Keywords :
codes; redundancy; D-ary codes; Huffman codes; arbitrary code alphabets; binary codes; most likely source letter probability; optimal lower bound; optimal upper bounds; redundancy; tight bounds; Codes; Entropy; Probability distribution; Upper bound;
Journal_Title :
Information Theory, IEEE Transactions on
