A Note on D-ary Huffman Codes

Abstract

An upper bound on the redundancy of D-ary Huffman codes in terms of the probability p<inf>1</inf> of the most likely source letter is provided. For large values of p<inf>1</inf> the bound improves the one given by Gallager. Additionally, some results known for the binary case (D = 2) are extended to arbitrary D-ary Huffman codes. As a consequence, a tight lower bound that corrects a bound recently proposed by Golic and Obradovic is derived. © 1991 IEEE