Tight bounds on the redundancy of Huffman codes

A method for deriving optimal upper bounds on the redundancy of binary Huffman codes in terms of the probability p/sub 1/ of the most likely source letter is presented. This method will be used to compute bounds for all p/sub 1/>or=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<or=D< infinity , are given, which are the tightest possible for all p/sub 1/>or=1/2.<<ETX>>