Existence, Uniqueness, and Optimality of Sibling-Property Codes for Infinite Sources
- Creators
- Klimesh, Matthew
- McEliece, Robert J.
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.
Additional Information
© 2006 IEEE.Attached Files
Published - 04036429.pdf
Files
Name | Size | Download all |
---|---|---|
md5:1978f7ed1f25b57ba2e5ce01afb80b33
|
159.7 kB | Preview Download |
Additional details
- Eprint ID
- 77320
- Resolver ID
- CaltechAUTHORS:20170509-170830648
- Created
-
2017-05-16Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field