CaltechAUTHORS
  A Caltech Library Service

The Rényi Redundancy of Generalized Huffman Codes

Blumer, Anselm C. and McEliece, Robert J. (1988) The Rényi Redundancy of Generalized Huffman Codes. IEEE Transactions on Information Theory, 34 (5). pp. 1242-1249. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20120531-153846714

[img]
Preview
PDF - Published Version
See Usage Policy.

485Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120531-153846714

Abstract

Huffman's algorithm gives optimal codes, as measured by average codeword length, and the redundancy can be measured as the difference between the average codeword length and Shannon's entropy. If the objective function is replaced by an exponentially weighted average, then a simple modification of Huffman's algorithm gives optimal codes. The redundancy can now be measured as the difference between this new average and A. Renyi's (1961) generalization of Shannon's entropy. By decreasing some of the codeword lengths in a Shannon code, the upper bound on the redundancy given in the standard proof of the noiseless source coding theorem is improved. The lower bound is improved by randomizing between codeword lengths, allowing linear programming techniques to be used on an integer programming problem. These bounds are shown to be asymptotically equal. The results are generalized to the Renyi case and are related to R.G. Gallager's (1978) bound on the redundancy of Huffman codes.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/18.21251DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=21251PublisherUNSPECIFIED
Additional Information:© 1988 IEEE. Manuscript received March 18, 1986. Date of Current Version: 06 August 2002. This work was supported in part by the Joint Services Electronics Program under Contract N00014-79-C-0424 with the University of Illinois, Urbana-Champaign, and in part by the National Science Foundation under Grant IST-8317918 to the University of Denver, CO. This work was partially presented at the IEEE International Symposia on Information Theory, Santa Monica, CA, January 1982, and Les Arcs, France, June 1982. It also formed part of a dissertation submitted to the Department of Mathematics, University of Illinois, Urbana-Champaign, in partial fulfillment of the requirements for the Ph.D. degree.
Funders:
Funding AgencyGrant Number
University of Illinois Joint Services Electronics ProgramN00014-79-C-0424
NSFIST-8317918
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number3375796
Record Number:CaltechAUTHORS:20120531-153846714
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20120531-153846714
Official Citation:Blumer, A.C.; McEliece, R.J.; , "The Renyi redundancy of generalized Huffman codes," Information Theory, IEEE Transactions on , vol.34, no.5, pp.1242-1249, Sep 1988 doi: 10.1109/18.21251 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=21251&isnumber=865
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:31759
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:01 Jun 2012 15:05
Last Modified:26 Dec 2012 15:17

Repository Staff Only: item control page