HP Labs Technical Reports

On Adaptive Strategies for an Extended Family of Golomb-Type Codes

Seroussi, Gadiel; Weinberger, Marcelo J.

HPL-97-08

Keyword(s): lossless compression; image compression; Golomb codes; Huffman codes; geometric distribution; adaptive coding; low complexity

Abstract: Off-centered, two-sided geometric distributions of the integers are often encountered in lossless image compression applications, as probabilistic models for prediction residuals. Based on a recent characterization of the family of optimal prefix codes for these distributions, which is an extension of the Golomb codes, we investigate adaptive strategies for their symbol-by-symbol prefix coding, as opposed to arithmetic coding. Our adaptive strategies allow for coding of prediction residuals at very low complexity. They provide a theoretical framework for the heuristic approximations frequently used when modifying the Golomb code, originally designed for one-sided geometric distributions of non- negative integers, so as to apply to the encoding of any integer.

Back to Index