◄ WORLD V · SONNY 5DART 117 · a helldive at the net

GOLOMB CODING the optimal code for things that repeat

For data where small values dominate — run lengths, gaps, quiet audio samples — Golomb coding is the optimal prefix code: split each number by a parameter M into a quotient in unary and a remainder in near-binary. It is the entropy stage of FLAC, JPEG-LS, and Rice-coded telemetry. Simple, tunable, and exactly matched to geometric data.

THE TECHNIQUE unary quotient, truncated-binary remainder

Choose a parameter M. For a value n, write the quotient q = ⌊n/M⌋ in unary (q ones then a zero) and the remainder r = n mod M in truncated binary (most remainders in ⌊log₂M⌋ bits, a few in one more). Small numbers get short codes. Encode some values and watch the bit-lengths. live demo

HISTORY & CREDIT the eponym is right; the proof and the subset are not his

“Golomb proved his code optimal for geometric data” — he proved invented it; the optimality proof is someone else’s. cited

1966 · Solomon W. Golomb — “Run-length encodings” (IEEE Trans. IT-12) introduces Golomb codes. Genuinely his; not a naming accident.
1971 · Robert Rice (with Plaunt) — Rice coding is the special case M = 2k (remainder is pure bits, no division) — a subset, not a separate invention of the general idea.
1975 · Gallager & van Voorhis prove Golomb codes are optimal among prefix codes for a geometric source — the optimality is theirs, not Golomb’s.
in the wild · FLAC, JPEG-LS (LOCO-I), Rice-coded deep-space telemetry — the entropy stage that beats Huffman (dart 006) on skewed data.

Golomb also gave us Golomb rulers and shift-register theory — a coder with an unusually deep bench. Golomb 1966

RECOMMEND FOR I-13 integer div/mod and bit-writes

Encode is a quotient/remainder split plus bit output; decode is the mirror — and the codes come out exact:

$ i13 run golomb.i13 # M=5 n=0 ->3 bits n=3 ->4 n=7 ->4 n=12 ->5 Rice M=4: n=9 -> 5 bits
Recommend: nothing new — encode is q = n/M, r = n mod M (integer div/mod, dart 001), then q one-bits + a zero and the truncated-binary remainder via a compare-and-branch (bitwise, dart 029); decode is the mirror (verified code lengths 3, 4, 4, 5 for M=5). Rice (M = 2k) needs no division at all — pure shifts.
Note: it ties Huffman (006) as the entropy family — Huffman is optimal for arbitrary alphabets, Golomb the closed-form optimum for geometric ones, no tree stored.