What Is Golomb Coding: Unary and Binary Systems

Golomb coding is a lossless data compression method designed to efficiently encode non-negative integers, particularly when smaller values occur more frequently than larger ones. This article provides a clear overview of how Golomb coding works by splitting an input integer into two distinct components: a quotient and a remainder. It examines how the quotient is represented using unary encoding and how the remainder is represented using standard or truncated binary encoding, demonstrating how these two numerical representations merge into a compact, variable-length code.

What Is Golomb Coding?

Invented by Solomon W. Golomb in 1966, Golomb coding is an entropy encoding technique optimal for data that follows a geometric distribution. In such distributions, the probability of an integer decreases exponentially as its magnitude increases. Common applications include run-length encoding, audio compression (such as FLAC and Apple Lossless), and image compression algorithms like JPEG-LS.

The algorithm relies on an adjustable integer parameter, denoted as \(M\). The choice of \(M\) determines the boundary between the quotient and the remainder, directly influencing compression efficiency based on the distribution of the source data.

How Golomb Coding Splits Integers

To encode any non-negative integer \(N\) using a chosen parameter \(M\), the algorithm performs integer division:

1. Calculate the Quotient (\(q\)): \[q = \lfloor N / M \rfloor\]
2. Calculate the Remainder (\(r\)): \[r = N \pmod M\]

The final Golomb codeword is formed by concatenating the encoded quotient and the encoded remainder: \[\text{Codeword} = [\text{Encoded Quotient}] + [\text{Encoded Remainder}]\]

Representing the Quotient: Unary Encoding

Unary encoding is a base-1 numeral system where a number \(q\) is represented by a sequence of identical bits followed by a terminating bit.

In standard Golomb coding: * The integer \(q\) is written as \(q\) copies of 1, followed by a single 0 (or alternatively, \(q\) copies of 0 followed by a 1). * Examples: * \(q = 0 \rightarrow \texttt{0}\) * \(q = 1 \rightarrow \texttt{10}\) * \(q = 2 \rightarrow \texttt{110}\) * \(q = 3 \rightarrow \texttt{1110}\)

Because smaller values of \(N\) produce smaller quotients, the unary part remains short for frequent values, saving significant space.

Representing the Remainder: Binary Encoding

The remainder \(r\) can take any value from \(0\) to \(M - 1\). The method used to encode \(r\) depends on whether \(M\) is a power of two.

1. When \(M\) Is a Power of Two (Golomb-Rice Coding)

When \(M = 2^k\), the encoding simplifies to Rice coding. The remainder \(r\) is simply represented as a standard \(k\)-bit binary number.

• If \(M = 4\) (\(k = 2\)), the possible remainders (\(0, 1, 2, 3\)) are encoded as:
  • \(r = 0 \rightarrow \texttt{00}\)
  • \(r = 1 \rightarrow \texttt{01}\)
  • \(r = 2 \rightarrow \texttt{10}\)
  • \(r = 3 \rightarrow \texttt{11}\)

2. When \(M\) Is Not a Power of Two (Truncated Binary Encoding)

When \(M\) is not a power of two, standard fixed-length binary cannot evenly represent all possible remainders. Golomb coding solves this using truncated binary encoding:

• Let \(b = \lceil \log_2(M) \rceil\).
• Compute the threshold cutoff: \(c = 2^b - M\).
• If \(r < c\), encode \(r\) as a standard binary number using \(b - 1\) bits.
• If \(r \ge c\), encode the value \(r + c\) as a standard binary number using \(b\) bits.

This ensures that the shorter bit patterns are assigned to lower remainder values without introducing ambiguity during decoding.

Step-by-Step Encoding Example

Consider encoding the number \(N = 9\) using the parameter \(M = 4\) (a power of two):

1. Calculate \(q\) and \(r\):
   • \(q = \lfloor 9 / 4 \rfloor = 2\)
   • \(r = 9 \pmod 4 = 1\)
2. Encode the Quotient (\(q = 2\)) in Unary:
   • Unary representation = 110
3. Encode the Remainder (\(r = 1\)) in Binary:
   • Since \(M = 2^2\), remainder length is \(k = 2\) bits.
   • Binary representation = 01
4. Concatenate the Results:
   • Final codeword = 11001

Why the Combination Is Effective

Golomb coding achieves high compression ratios by balancing the strengths of unary and binary numbering systems:

• Unary coding handles the high-order bits (\(q\)). It acts as a variable-length prefix that expands smoothly for large numbers while taking as little as 1 bit for numbers smaller than \(M\).
• Binary coding handles the low-order bits (\(r\)). It compactly captures the uniform distribution of remainders within a fixed or near-fixed number of bits.

By adjusting the parameter \(M\) to match the decay rate of the input data distribution, Golomb coding constructs near-optimal prefix codes without the computational overhead of building dynamic Huffman trees.