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
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120531-153846714
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.|
|Other Numbering System:|
|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.|
|Deposited By:||Ruth Sustaita|
|Deposited On:||01 Jun 2012 15:05|
|Last Modified:||26 Dec 2012 15:17|
Repository Staff Only: item control page