> golomb | optimal | compress <
// Golomb Coding - Optimal integer compression with flexible divisor
>> features
Flexible Divisor
Choose any M value for optimal compression efficiency.
Truncated Binary
Uses minimal bits for remainder encoding.
General Purpose
Works with any non-negative integer distribution.
>> technical info
How Golomb Coding Works
Golomb coding divides each integer n by divisor M to get quotient q and remainder r. The quotient is encoded in unary, and the remainder uses truncated binary coding - using minimal bits needed to represent M values. This creates an optimal code for geometric distributions with parameter p = 1/M.
Golomb Coding Example (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 bits for r<3) 1 → q=0, r=1 → 0|01 → 001 (2 bits for r<3) 2 → q=0, r=2 → 0|10 → 010 (2 bits for r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 bits for r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 bits for r≥3) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 Truncated binary: r<3 use 2 bits, r≥3 use 3 bits
Why Use Golomb Coding
- Optimal for geometric distributions
- Flexible M parameter
- Minimal bit usage
- Simple implementation
- Proven optimality
>> frequently asked questions
What is Golomb coding?
Golomb coding is an optimal prefix-free variable-length code for geometric distributions. It divides integers by a tunable parameter M, encoding the quotient in unary and the remainder in truncated binary, achieving optimal compression for data following P(n) = (1-p)^n × p.
How to choose the M parameter?
The optimal M depends on your data's geometric parameter p. For data with mean μ, optimal M ≈ μ + 1. For exponentially decreasing probabilities with parameter p, optimal M = ⌈-1/log₂(1-p)⌉. Use the analyze function to find the best M for your specific data.
What is truncated binary coding?
Truncated binary minimizes bits when encoding one of M possible values. If M is a power of 2, use standard binary. Otherwise, some values use ⌊log₂M⌋ bits and others use ⌈log₂M⌉ bits, ensuring unique decodability with minimal average length.
Where is Golomb coding used?
Golomb coding is used in JPEG-LS image compression, H.264 video coding (as Exp-Golomb), and lossless audio formats. It's ideal for run-length encoding, residual coding after prediction, and any data with geometric or exponential distributions.