ExtendedSource checked

Golomb Coding

Encodes small nonnegative integers compactly when small values are common.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Compression
Difficulty: Intermediate
Family: Universal Coding
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 3
Code example: Not ready
Visualization: Ready
Aliases: Rice Coding

Overview

Golomb Coding splits a number into a quotient and remainder, making it useful for geometric-like distributions.

Core Concepts

integer key rangecodeword encodinguniversal codingsymbol representationlossless decodingstream encoding

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(1)

When to Use

Use Golomb Coding when you need to divide values by a chosen parameter.
Use it for compressing runs or gaps with inputs like nonnegative integers.
Use it when the data has repetition, predictable structure, or symbol frequency imbalance.
Use it when the Universal Coding tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when values are not bounded integers or cannot be mapped cleanly to integer keys.
Avoid it when small inputs or already compressed data would make metadata larger than the savings.
Avoid it when the required output is not variable-length bit codes.

What It Does

Divides values by a chosen parameter
Writes quotient and remainder codes

Use Cases

Compressing runs or gaps
Rice coding variants
Sparse integer data

Inputs

Nonnegative integers
Golomb parameter

Outputs

Variable-length bit codes

Key Formulas (1)

Quotient and remainder

q = ⌊value / m⌋; r = value mod m

q = floor(value / m); r = value mod m

Splits an integer into the unary-coded quotient and remainder.

Pseudocode

1.Choose a coding parameter
2.Divide each value into quotient and remainder
3.Encode the quotient in unary form
4.Encode the remainder in binary form
5.Concatenate the codes

Canonical Example

Input: text = 'AAAABBBCCDAA'
Output: compressed representation with repeated runs or shorter codes
Explanation: Golomb Coding: The algorithm replaces predictable or repeated structure with a more compact representation.

Implementation Notes

Keep the input contract explicit: Nonnegative integers; Golomb parameter.
Use this step as the implementation spine: Choose a coding parameter.
Then preserve the next state change: Divide each value into quotient and remainder.
Keep encoder and decoder tests paired so every compressed sample round-trips exactly.

Common Pitfalls

Rice coding is a common Golomb Coding variant where the parameter is a power of two.
Forgetting that the decoder needs the same model, dictionary, or metadata used by the encoder.
Returning variable-length bit codes without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show integers becoming quotient and remainder code parts.

Input:ABABABCABAB

Window:ABAB

Step 1 of 5: Choose a coding parameter

integer-codewords

Notes

Golomb Coding operates in O(n) time and O(1) space within the Universal Coding family. Key governing relation: q = floor(value / m); r = value mod m. Often compared with Delta Encoding and Run-Length Encoding.