Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2000 | public
Journal Article

Maximal codeword lengths in Huffman codes


In this paper, we consider the following question about Huffman coding, which is an important technique for compressing data from a discrete source. If p is the smallest source probability, how long, in terms of p, can the longest Huffman codeword be? We show that if p is in the range 0 < p ≤12, and if K is the unique index such that 1F_(K+3)< p ≤1F_(K+2), where F_K denotes the Kth Fibonacci number, then the longest Huffman codeword for a source whose least probability is p is at most K, and no better bound is possible. Asymptotically, this implies the surprising fact that for small values of p, a Huffman code's longest codeword can be as much as 44% larger than that of the corresponding Shannon code.

Additional Information

© 2000 Published by Elsevier Ltd. Abu-Mostafa's contribution to this paper was supported by AFOSR Grant No. F49620-92-J-0398. McEliece's contribution was partly carried out at Caltech's Jet Propulsion Laboratory under contract with the National Aeronautics and Space Administration, and partly supported by AFOSR Grant No. 91-0037.

Additional details

August 21, 2023
October 20, 2023