Search the Kids Internet
Encyclopedia > Golomb coding
Article Content
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:
All Wikipedia text is available under the terms of the GNU Free Documentation License
|
Search Encyclopedia
|