CaltechAUTHORS
  A Caltech Library Service

Maximal codeword lengths in Huffman codes

Abu-Mostafa, Y. S. and McEliece, R. J. (2000) Maximal codeword lengths in Huffman codes. Computers and Mathematics with Applications, 39 (11). pp. 129-134. ISSN 0898-1221. https://resolver.caltech.edu/CaltechAUTHORS:20190710-133740050

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190710-133740050

Abstract

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1016/S0898-1221(00)00119-XDOIArticle
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.
Funders:
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)F49620-92-J-0398
NASA/JPL/CaltechUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)91-0037
Subject Keywords:Data compression; Huffman codes; Fibonacci numbers
Issue or Number:11
Record Number:CaltechAUTHORS:20190710-133740050
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190710-133740050
Official Citation:Y.S. Abu-Mostafa, R.J. McEliece, Maximal codeword lengths in Huffman codes, Computers & Mathematics with Applications, Volume 39, Issue 11, 2000, Pages 129-134, ISSN 0898-1221, https://doi.org/10.1016/S0898-1221(00)00119-X. (http://www.sciencedirect.com/science/article/pii/S089812210000119X)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97033
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:10 Jul 2019 20:50
Last Modified:03 Oct 2019 21:27

Repository Staff Only: item control page