golomb-coding · also Golomb code

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

related
Rice coding, Lossless compression, Variable-length integer

Citations

  1. N. Jesper Larsson: Run-Length Encoding in a Finite Universe, SPIRE 2019, arXiv:1909.06794v2, sections 1-5 (accessed 2026-11-17)
  2. Hesela: exact Golomb/Rice bit-cost examples and partition accounting (accessed 2026-11-17)

Further reading

  1. S. W. Golomb: Run-Length Encodings, IEEE Transactions on Information Theory 12(3), 1966, pp. 399-401 (accessed 2026-11-17)
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.

JSON: /data/terms/golomb-coding.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Golomb coding. Hesela. 2026-11-17. https://hesela.dev/terms/golomb-coding/