Optimal prefix codes for sources with two-sided geometric distributions
- 1 January 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 46 (1) , 121-135
- https://doi.org/10.1109/18.817513
Abstract
A complete characterization of optimal prefix codes for off-centered, two-sided geometric distributions of the integers is presented. These distributions are often encountered in lossless image compression applications, as probabilistic models for image prediction residuals. The family of optimal codes described is an extension of the Golomb codes, which are optimal for one-sided geometric distributions. The new family of codes allows for encoding of prediction residuals at a complexity similar to that of Golomb codes, without recourse to the heuristic approximations frequently used when modifying a code designed for nonnegative integers so as to apply to the encoding of any integer. Optimal decision rules for choosing among a lower complexity subset of the optimal codes, given the distribution parameters, are also investigated, and the relative redundancy of the subset with respect to the full family of optimal codes is boundedKeywords
This publication has 17 references indexed in Scilit:
- Fast and efficient lossless image compressionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- LOCO-I: a low complexity, context-based, lossless image compression algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On adaptive strategies for an extended family of Golomb-type codesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Context-based, adaptive, lossless image codingIEEE Transactions on Communications, 1997
- Huffman coding with an infinite alphabetIEEE Transactions on Information Theory, 1996
- Huffman-type codes for infinite source distributionsJournal of the Franklin Institute, 1994
- Dynamic huffman codingJournal of Algorithms, 1985
- Optimal source coding for a class of integer alphabets (Corresp.)IEEE Transactions on Information Theory, 1978
- Optimal source codes for geometrically distributed integer alphabets (Corresp.)IEEE Transactions on Information Theory, 1975
- Run-length encodings (Corresp.)IEEE Transactions on Information Theory, 1966