LCS Publication Details
Publication Title: On the Redundancy Achieved by Huffman Codes
Publication Author: De Prisco, Roberto
Additional Authors: De Santis, Alfredo
LCS Document Number: MIT-LCS-TM-536
Publication Date: 9-1-1995
LCS Group: Theory of Computation
Additional URL: No URL Given
It has been recently proved that the redundancy r of any discrete memoryless source satisfies r < 1 -H(pn), where pn is the least likely source letter probability. This bound is achieved only by sources consisting of two letters. We prove a sharper bound if the number of source letters is greater than two. Also provided is a new upper bound on r, as function of the two least likely source letter probabilities which improve on previous results.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.