Golomb coding
Golomb coding represents a nonnegative integer using a unary quotient and a truncated-binary remainder for a chosen positive divisor.
Mechanism: Divide x by m into quotient q and remainder r. Encode q in unary, then r with a balanced code over m values. With m = 1, no remainder bits are needed. Rice coding restricts m to a power of two. [1]
Worked bits: For m = 3, remainders 0, 1 and 2 use 0, 10 and 11. With a zero-run unary prefix terminated by 1, values 0 through 5 become 10, 110, 111, 010, 0110 and 0111. The divisor and unary convention must be shared by the decoder. [3]
Bounded values: A code designed for an unbounded geometric distribution allocates codewords to values above a known maximum. That can waste space for short bounded lists. Finite-universe coding adapts the tail; its practical heuristic is not optimal for every parameter pair. [1]
Relations
Citations
- N. Jesper Larsson: Run-Length Encoding in a Finite Universe, SPIRE 2019, arXiv:1909.06794v2, sections 1-5
- Hesela: exact Golomb/Rice bit-cost examples and partition accounting
Further reading
- S. W. Golomb: Run-Length Encodings, IEEE Transactions on Information Theory 12(3), 1966, pp. 399-401
Sources & caveats
- The 1966 paper is the historical reference; the modern quotient/remainder description and bounded-universe distinction follow Larsson's full paper.
- Exact educational bit strings use the FLAC-style unary polarity, not a claim of identical wire syntax across all Golomb formats.
- Executable controls: https://hesela.dev/research/golomb-rice.test.mjs. No native codec or finite-universe benchmark is reproduced.