Golomb coding

related topics
{math, number, function}
{system, computer, user}
{food, make, wine}

Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the occurrence of small values in the input stream is significantly more likely than large values.

Rice coding (invented by Robert F. Rice) denotes using a subset of the family of Golomb codes to produce a simpler (but possibly suboptimal) prefix code; Rice used this in an adaptive coding scheme, although "Rice coding" can refer to either that scheme or merely using that subset of Golomb codes. Whereas a Golomb code has a tunable parameter that can be any positive value, Rice codes are those in which the tunable parameter is a power of two. This makes Rice codes convenient for use on a computer, since multiplication and division by 2 can be implemented more efficiently in binary arithmetic.

Rice coding is used as the entropy encoding stage in a number of lossless image compression and audio data compression methods.

Contents

Overview

Use with signed integers

Golomb's scheme was designed to encode sequences of non-negative numbers. However it is easily extended to accept sequences containing negative numbers using an overlap and interleave scheme, in which all values are re-assigned to some positive number in a unique and reversible way. The sequence begins: 0, -1, 1, -2, 2, -3, 3, -4, 4 ... The nth negative value (i.e., -n) is mapped to the nth odd number (2n-1), and the mth positive value is mapped to the mth even number (2m). This may be expressed mathematically as follows: a positive value x is mapped to (x^\prime=2|x|=2x, x\ge0), and a negative value y is mapped to (y^\prime=2|y|-1=-2y-1, y<0).

Construction of codes

Full article ▸

related documents
Constant of integration
Division algebra
Search algorithm
Symmetric group
Exact sequence
Mersenne prime
Separable space
Probability space
Euler's totient function
Kruskal's algorithm
Analytic geometry
Banach fixed point theorem
Inverse limit
Convex set
Mersenne twister
Linear equation
Local ring
Automated theorem proving
Controllability
Group representation
Carmichael number
Goodstein's theorem
Cardinality
Well-order
Diophantine set
Lebesgue measure
Tychonoff space
Topological group
Kolmogorov space
Separation axiom