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 September 1988 | Published
Journal Article Open

The Rényi Redundancy of Generalized Huffman Codes

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.

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.

Attached Files

Published - BLUieeetit88.pdf

Files

BLUieeetit88.pdf
Files (496.8 kB)
Name Size Download all
md5:b14c4c0a9e3ff15221aec6f81eac1d6c
496.8 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 17, 2023