Huffman Coding

It is well-known that Huffman encoding algorithm provides an optimal prefix-free code for a discrete memoryless source, in the sense that for a given source distribution no other code can have a shorter expected length than that of the Huffman code. The redundancy of a Huffman code is known to be non-negative and exceeding 1. These bounds can be improved if partial knowledge about the source distribution is available. 

Our focus in this work is on a class of sources, for which the frequency of only one of the symbols is know. We proved Ye and Yeung’s conjecture about the maximum redundancy of such Huffman codes, which yields in a tight upper bound. We also derived a tight lower bound for the redundancy. In consequence, we introduce a class of distributions that can achieve the derived lower bound, and investigate properties of the Huffman codes induced by such distributions.

huffman coding