Bounds on the redundancy of Huffman codes (Corresp.)
Renato M. Capocelli, Raffaele Giancarlo, Inder Jeet Taneja · IEEE Transactions on Information Theory · 1986
New upper bounds on the redundancy of Huffman codes are provided. A bound that for2/9 \leq P_{1} \leq 0.4is sharper than the bound of Gallager, when the probability of the most likely source letterP_{1}is the only known probability is presented. The improved bound is the tightest possible for1/3 \leq P_{1} \leq 0.4. Upper bounds are presented on the redundancy of Huffman codes when the extreme probabilitiesP_{1}andP_{N}are known.