Simpler Adaptive Selection of Golomb Power-of-Two Codes

The selected code-parameter value is within 1 of the optimum value.

An alternative method of adaptive selection of Golomb power-of-two (GPO2) codes has been devised for use in efficient, lossless encoding of sequences of non-negative integers from discrete sources. The method is intended especially for use in compression of digital image data. This method is somewhat suboptimal, but offers the advantage in that it involves significantly less computation than does a prior method of adaptive selection of optimum codes through “brute force” application of all code options to every block of samples.

A rather lengthy discussion of background is necessary to give meaning to a brief summary of this innovation. For positive integer, m, the mth Golomb code defines a reversible, prefix-free mapping of non-negative integers to variable-length binary code words. Golomb codes are optimum for geometrically distributed sources (a model that frequently arises in image compression): In the case of a geometrically distributed random variable, δ, the appropriately selected Golomb code minimizes the expected code-word length over all possible lossless binary codes for δ.

In a GPO2 code, m = 2^k, where k is a non-negative integer. Such a code makes the coding process particularly simple: The code word for the integer δ consists of the unary representation of ⎣δ/2^k⎦ (that is, ⎣δ/2^k⎦ zeros followed by a one) concatenated with the k least significant bits of the binary representation of δ. More specifically, the code is called a GPO2 code of parameter k.