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₁ of the most likely source letter is presented. This method will be used to compute bounds for all p₁⩾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 p₁⩾1/2