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 an 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. This makes it extremely efficient for use on computers, since the division operation becomes a bitshift operation and the remainder operation becomes a bitmask operation.
Applications
The FLAC audio codec uses Rice coding to represent linear prediction residues.
Apple's ALAC audio codec uses bastardized Rice coding after its Adaptive FIR filter.
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.de:Golomb Code