CaltechAUTHORS
  A Caltech Library Service

Existence, Uniqueness, and Optimality of Sibling-Property Codes for Infinite Sources

Klimesh, Matthew and McEliece, Robert J. (2006) Existence, Uniqueness, and Optimality of Sibling-Property Codes for Infinite Sources. In: 2006 IEEE International Symposium on Information Theory. IEEE , Piscataway, NJ, pp. 2536-2540. ISBN 1-4244-0505-X. https://resolver.caltech.edu/CaltechAUTHORS:20170509-170830648

[img] PDF - Published Version
See Usage Policy.

155Kb

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

Abstract

By definition Huffman codes only exist for finite sources, since the Huffman algorithm cannot be applied to an infinite source. On the other hand, Gallager's sibling property, which was introduced as a characterization of Huffman codes, extends naturally to (countably) infinite sources. Thus we define a Huffman-Gallager code as any code that has the sibling property, and we present some basic facts about such codes. (1) For any source, a Huffman-Gallager code exists and its list of node probabilities is unique. (2) A Huffman-Gallager code is optimal, and given an optimal code, there exists a Huffman-Gallager code with the same codeword lengths. (3) For sources with infinite entropy, the existence and uniqueness results continue to hold, and the optimality results hold for a natural extended form of optimality.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ISIT.2006.262089DOIArticle
http://ieeexplore.ieee.org/document/4036429/PublisherArticle
Additional Information:© 2006 IEEE.
Record Number:CaltechAUTHORS:20170509-170830648
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170509-170830648
Official Citation:M. Klimesh and R. J. McEliece, "Existence, Uniqueness, and Optimality of Sibling-Property Codes for Infinite Sources," 2006 IEEE International Symposium on Information Theory, Seattle, WA, 2006, pp. 2536-2540. doi: 10.1109/ISIT.2006.262089
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:77320
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:16 May 2017 20:56
Last Modified:03 Oct 2019 17:56

Repository Staff Only: item control page