Golomb coding

Golomb coding is a form of entropy coding invented by Solomon W. Golomb[?] that is optimal for alphabets following Geometric distributions. That is, when small values are vastly more common than large values.

It uses a tunable parameter b to divide a input value into two parts: the result of a division by b, and the remainder. The quotient is sent in unary coding, followed by the remainder in truncated binary encoding.

The parameter b is a function of the corresponding geometric distribution, which is parameterized by p = P(X = 0). b and p are related by these inequalities:

<MATH>(1-p)^b + (1-p)^{b+1} \leq 1 < (1-p)^{b-1} + (1-p)^b</MATH>

Rice coding is a special case of Golomb coding first described by Robert Rice. It is equivalent to Golomb coding where the tunable parameter is a power of two.

References:

• Golomb, S.W. (1966). Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401
• R. F. Rice, "Some Practical Universal Noiseless Coding Techniques, " Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79--22, Mar. 1979.

External links:

• http://www.iro.umontreal.ca/~pigeon/science/vlc/golomb.html