Golomb-Rice Coding

Every time you rip a CD with FLAC, sequence a genome, or download satellite imagery, a tiny algorithm works behind the scenes: it takes a list of small non-negative integers and squeezes them into as few bits as possible. That algorithm is Golomb-Rice coding, and its key property is remarkable — it is provably optimal for a precise family of distributions.

The key insight is that not all integers are equally likely. When you record the silence between musical notes, the differences between consecutive audio samples cluster near zero. When a sequencing machine counts short DNA runs, most runs are short. Nature keeps handing us numbers where small values dominate and large values are rare — a pattern captured precisely by the geometric distribution.

A fixed-width code wastes this structure entirely: it assigns the same 8 bits to the number 0 as to the number 200. Variable-length codes exploit the skew: frequent small numbers get short codes; rare large numbers get long ones. Golomb coding — invented by Solomon Golomb in 1966 and refined by Robert Rice in the 1970s — is the unique family of codes that achieves the Shannon entropy lower bound for geometric distributions, meaning no lossless code can compress them further.

The mathematical proof is elegant: if you know only that your numbers come from a geometric distribution with some parameter p, the optimal code length for the number n is ⌊n $\log_{2}((1-p)$/p)⌋ + 1 bits. Golomb coding achieves this exactly, without knowing p in advance — just by choosing the right divisor m.

Type a sequence of non-negative integers separated by spaces and watch Golomb-Rice encode each one. Adjust the divisor m (a power of two gives Rice coding) and see how the bit counts change.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{lbl_numbers}} <input id="nums" type="text" value="0 1 0 2 1 0 3 0 1 0 2 5 0 1" /></label>
  <label>{{lbl_divisor}} <input id="mval" type="number" min="1" max="64" value="4" /></label>
  <button id="encode" type="button">{{btn_encode}}</button>
  <button id="preset1" type="button" class="ghost">{{btn_preset1}}</button>
  <button id="preset2" type="button" class="ghost">{{btn_preset2}}</button>
</div>
<div id="output"></div>
<div id="summary"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.4; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin-bottom: .8rem; }
label { display: flex; align-items: center; gap: .3rem; font-size: .85rem; }
input[type=text] { width: 200px; padding: .3rem .5rem; border: 1px solid #bbb; border-radius: 6px; font-size: .85rem; }
input[type=number] { width: 60px; padding: .3rem .5rem; border: 1px solid #bbb; border-radius: 6px; font-size: .85rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
table { border-collapse: collapse; width: 100%; margin: .5rem 0; font-size: .82rem; }
th { background: #e8eef3; color: #1d3557; text-align: left; padding: .35rem .5rem; border-bottom: 2px solid #b0c4d8; }
td { padding: .28rem .5rem; border-bottom: 1px solid #e0e8f0; font-family: ui-monospace, monospace; vertical-align: middle; }
tr:hover td { background: #f3f7fb; }
.bits-g { color: #0a6ea0; font-weight: 600; }
.bits-f { color: #888; }
.bar-wrap { display: flex; align-items: center; gap: 3px; }
.bar { height: 9px; border-radius: 2px; display: inline-block; min-width: 2px; }
.bar-g { background: #0a6ea0; }
.bar-f { background: #ccc; }
#summary { margin-top: .6rem; padding: .55rem .8rem; background: #e8f4ec; border-radius: 8px; font-size: .88rem; line-height: 1.5; }
#summary strong { color: #0a7d33; }
#summary.worse { background: #fde8e8; }
#summary.worse strong { color: #c92f3c; }
.err { color: #c92f3c; font-size: .9rem; }

// Code not found

Notice the asymmetry: small numbers near zero cost only 1–2 bits; large numbers cost proportionally more. With fixed-width 8-bit codes the total is always 8 × count bits. The savings only appear when your data is concentrated near zero — exactly the geometric-distribution assumption Golomb proved to be tight.

Golomb coding is a solved problem in information theory — the optimality proof was established by Solomon Golomb in 1966 and independently by Robert Rice in his 1979 NASA technical report.

The proof in three steps:

1. Shannon's source coding theorem tells us the minimum average bits needed to encode a symbol with probability p is −$\log_{2}(p)$. For the geometric distribution with parameter p, the number n has probability $p(1-p)^{n}$, so the optimal code length is $-\log_{2}(p(1-p)^{n}) = -\log_{2}(p) - n\cdot\log_{2}(1-p)$.

2. Golomb's construction splits n into quotient q = ⌊n/m⌋ and remainder r = n mod m. It encodes q in unary (q ones followed by a zero) and r in a near-optimal binary code. For the right choice of m, the total length matches the Shannon lower bound to within one bit per symbol.

3. The right m: if your geometric parameter is p, the optimal Golomb divisor is m = ⌈−1/$\log_{2}(1-p)$⌉. Remarkably, even rough estimates of p produce near-optimal codes — which is why FLAC adaptively resets m every 4096 samples and still wins.

Rice coding is the special case where m is a power of two. The remainder then uses exactly $\log_{2}(m)$ bits with no rounding, and encoding/decoding simplify to bit shifts and masks — which is why every hardware audio codec and CPU instruction set includes Rice as a primitive.

The complexity cost is tiny: encoding a number n with divisor m takes $O(n/m + \log m)$ time — proportional to the output length. Decoding is equally fast. There is no catch: Golomb-Rice is optimal, simple, and efficient.

Contrast this with the general compression problem. Kolmogorov complexity — the theoretically shortest description of any string — is uncomputable. Golomb-Rice sidesteps this entirely by knowing the distribution in advance and exploiting it to the mathematical limit. It is a rare case where theory and practice converge perfectly.

Whenever data follows a geometric-like distribution, Golomb-Rice coding appears:

• Lossless audio (FLAC, Apple Lossless): consecutive audio samples differ by small amounts. FLAC computes these residuals, models their distribution, and encodes them with Rice coding — achieving 30–60% compression of CD-quality audio at near-real-time speed on a microcontroller.
• DNA sequencing (CRAM format): reference-based compression of sequencing reads produces short integer offsets (base differences, quality score deltas). CRAM uses Golomb-Rice to shrink these to near the information-theoretic limit, reducing storage by 60% versus raw BAM files.
• Image compression (JPEG-LS, PNG): prediction residuals in lossless image formats cluster near zero. JPEG-LS uses Rice coding internally; PNG's filter stage produces residuals that ZIP (DEFLATE) then encodes, partly via Huffman — but specialized lossless image codecs use Rice directly.
• Astronomical data (FITS lossless extension): the NASA Flexible Image Transport System includes a lossless Rice-coded extension specifically for integer sky maps, used by missions from Chandra to Fermi.
• Error-correcting codes: Golomb sequences (a different but related construct) arise in combinatorics and ruler theory, showing that Golomb's name attaches to several distinct but elegant structures in discrete mathematics.

The unifying thread: any time you can predict the scale of your integers but not their exact values — audio deltas, genomic offsets, pixel differences — Golomb-Rice is the theoretically tight answer. Compare with sorting lower bounds: both results use information-theoretic arguments to establish that no algorithm can do better; the difference is that Golomb-Rice has a matching achiever while the sorting bound only rules out comparison-based algorithms.

Golomb-Rice coding is one of the cleanest results in applied information theory: a precise mathematical problem (compress geometrically distributed integers), a provably optimal solution (Solomon Golomb, 1966), and a practical implementation so simple it fits in a dozen lines of code.

The deeper lesson is about knowing your distribution. General-purpose compressors like ZIP must learn the structure of your data from scratch. Golomb-Rice starts with a proven model — the geometric distribution — and reaches the theoretical minimum. Every time FLAC saves you disk space or CRAM shrinks a genome file, that 1966 optimality proof is doing real work.

The next time a streaming service delivers lossless audio to your headphones, or a bioinformatics pipeline stores a sequenced genome, remember: the bits are as few as mathematics allows. Not approximately — exactly as few. That is what "provably optimal" means in practice.