Golomb coding
Golomb coding is a family of lossless data compression codes designed for encoding non-negative integers, particularly those drawn from a geometric probability distribution, such as run lengths in binary data sequences.[1] Invented by mathematician Solomon W. Golomb in 1966, the method provides an efficient prefix-free representation that approaches the entropy limit for sources where the probability of a run length n is P(n) = p (1-p)^n for $0 < p < 1.[1] The codes are parameterized by a positive integer m \approx 1/p, ensuring optimality in average code length for the corresponding distribution.[1]
To encode a non-negative integer n, Golomb coding decomposes it as n = q \cdot m + r, where q = \lfloor n / m \rfloor is the quotient and r = n \mod m is the remainder with $0 \leq r < m.[1] The quotient q is represented using a unary code consisting of q ones followed by a zero, while the remainder r is encoded in a fixed-length binary code of k = \lceil \log_2 m \rceil bits; if m is not a power of 2, the binary codes for remainders are truncated or adjusted to form a complete set of unique codewords.[1] This structure allows instantaneous (prefix-free) decoding and is computationally efficient, requiring only integer division and basic bit operations.[1]
A prominent variant is Rice coding, which restricts m to powers of 2 (i.e., m = 2^k) to simplify implementation using bitwise shifts and masks instead of general division, making it suitable for hardware and real-time applications.[2] Another related form, exponential-Golomb coding, generalizes the approach by using a logarithmic decomposition, which is widely adopted in video compression standards like H.264/AVC for encoding syntax elements such as motion vectors and coefficients.[3] Golomb and its variants find extensive use in lossless image compression (e.g., JPEG-LS), deep space telemetry data processing by NASA/JPL, and scientific datasets where residuals or differences follow near-geometric distributions.[2][3]
History and Development
Invention by Solomon Golomb
Solomon W. Golomb invented Golomb coding in 1966 as a method for efficient run-length encoding of data sequences.[1] The technique was introduced in his paper "Run-Length Encodings," published in the IEEE Transactions on Information Theory.[1]
Golomb's primary motivation was to develop codes suitable for sources exhibiting exponentially decaying probability distributions, particularly in applications involving run-lengths of symbols in binary or discrete data streams.[1] Such distributions commonly arise in scenarios like encoding consecutive identical symbols, where the probability of longer runs decreases geometrically.[1] This approach addressed the need for variable-length codes that could compress such data losslessly while maintaining simplicity in implementation.
In the paper, Golomb provided an early theoretical proof demonstrating the optimality of his codes for memoryless sources following a geometric distribution, characterized by parameter p, the probability of a run terminating (i.e., the probability of zero).[1] He showed that these codes achieve the minimal average codeword length among all uniquely decodable prefix codes for such sources under the given probability model.[1]
Golomb first formally defined the code family, parameterized by an integer M, which generates a set of prefix-free and uniquely decodable binary codes tailored to the geometric parameter.[1] The parameter M allows adaptation to different values of p, ensuring near-optimal performance across a range of geometric distributions.[1] This parameterization laid the groundwork for subsequent refinements in entropy coding.
Development of Rice Coding
Rice coding emerged in the 1970s through the work of Robert F. Rice at NASA's Jet Propulsion Laboratory, where it was designed specifically for lossless compression of space telemetry data, including sensor readings from spacecraft.[4] This development addressed the need for efficient data transmission in bandwidth-constrained deep-space environments, building on Solomon Golomb's 1966 theoretical framework for encoding geometric distributions.[1] Rice's approach prioritized computational simplicity to suit the hardware limitations of the era, making it suitable for real-time implementation on early space mission systems.[4]
The technique was first applied in prominent NASA missions, such as Voyager, to compress imaging and telemetry data without loss, enabling more effective use of limited transmission resources during planetary flybys.[5] These applications demonstrated its reliability for handling variable data statistics from scientific instruments, contributing to the success of long-duration space exploration efforts in the late 1970s and beyond.[4] Rice provided a comprehensive description of the method in his 1979 publication, Some Practical Universal Noiseless Coding Techniques, which outlined its structure and performance for practical deployment.[4]
A central innovation in Rice coding was the restriction of the Golomb parameter M to powers of two (M = 2^k, where k is a non-negative integer), which streamlined the encoding of the remainder value.[4] This choice eliminated the need for irregular truncated binary representations, allowing the remainder to be directly encoded in exactly k binary bits.[4] Compared to the general Golomb coding, this modification significantly improved computational efficiency by replacing division and modulo operations with straightforward bit shifts and masking, reducing processing time and hardware requirements for encoding and decoding.[4]
Mathematical Foundations
Geometric Distribution Assumptions
Golomb coding relies on the memoryless property of the geometric distribution to model the probabilities of non-negative integer symbols emitted by the source. Specifically, the probability mass function is given by
P(X = k) = p (1 - p)^k, \quad k = 0, 1, 2, \dots
where p > 0 is the success probability, equivalent to P(X = 0) = p, and $1 - p is the failure probability. This distribution arises naturally in scenarios such as run-length encoding of binary sequences where successes and failures follow independent Bernoulli trials, leading to exponentially decaying probabilities for longer runs.[1]
The coding scheme is asymptotically optimal for sources following this geometric distribution because its structure aligns with the exponential decay in symbol probabilities, enabling the average codeword length to approach the source entropy. The entropy H(X) of a geometric distribution is
H(X) = \frac{ - p \log_2 p - (1 - p) \log_2 (1 - p) }{p}
bits per symbol, which represents the theoretical lower bound on the average code length for lossless prefix coding. By partitioning symbols into groups and assigning unary codes to quotients and truncated binary codes to remainders, Golomb codes achieve this bound in the limit as the parameter is tuned appropriately.[1][2]
Key assumptions underlying the efficiency of Golomb coding include that the source produces independent and identically distributed (i.i.d.) non-negative integers adhering to the geometric distribution, with the parameter p either known a priori or estimable from the data. In practice, such assumptions hold well for applications like quantized wavelet coefficients in image compression, where run-lengths of zeros approximate geometric behavior under i.i.d. conditions. However, deviations from these assumptions—such as correlations in the source data or non-geometric tails—can degrade performance by increasing the average code length beyond the entropy bound.[6]
Extensions of Golomb coding address limitations of the strict geometric assumption by incorporating generalized forms, such as those using flexible indexing functions to better fit distributions like the generalized Pareto or empirically observed non-geometric patterns in subband data. These variants maintain prefix properties while adapting to broader probability models without sacrificing much of the original scheme's simplicity.[6]
Optimal Parameter M Selection
The selection of the optimal parameter M in Golomb coding is crucial for achieving near-entropy compression efficiency when encoding data assumed to follow a geometric distribution. The exact optimal M is the smallest positive integer satisfying (1-p)^M + (1-p)^{M+1} \leq 1 < (1-p)^{M-1} + (1-p)^M. For small p, this can be approximated by M \approx -1 / \log_2(1-p). These derive from balancing the lengths of the unary quotient code and the binary remainder code to closely match the source entropy.[1]
When the distribution parameter p is unknown, M can be estimated from a sample of n nonnegative integers x_1, x_2, \dots, x_n using maximum likelihood methods. First estimate p via maximum likelihood as \hat{p} = n / \sum_{i=1}^n (x_i + 1), then substitute into the approximation M \approx -1 / \log_2(1 - \hat{p}). Alternatively, compute the sample mean \bar{x} = (1/n) \sum x_i, and set M \approx \lfloor \bar{x} + 1 \rfloor, which provides a simple data-driven approximation.[1] Such estimation ensures the code adapts to the empirical distribution without requiring prior knowledge of p.
The choice of M significantly impacts compression performance: if M is too small, the unary portion of the codeword dominates, leading to longer average lengths due to excessive unary bits for larger quotients; conversely, if M is too large, the binary remainder portion wastes bits on less probable small values, as the fixed-width remainders underutilize the allocated bits. To find the globally optimal M, one practical approach is to iterate over a range of candidate values (e.g., around the estimated mean plus one) and select the one yielding the shortest total encoded length on sample data.[2]
The average codeword length for a given M is expressed as L(M) = H(p) + I(M, p), where H(p) = -\log_2 p - \frac{1-p}{p} \log_2 (1-p) is the entropy of the geometric distribution, and I(M, p) \geq 0 represents the inefficiency term arising from the code's structure, which is minimized when M is optimally chosen. This minimization ensures L(M) approaches H(p) closely, often within 1-2% inefficiency for well-tuned parameters.[1]
Encoding and Decoding Mechanics
Core Encoding Procedure
Golomb coding encodes a non-negative integer x using a fixed parameter M > 0, which is chosen to approximate the geometric distribution parameter of the source data.[1] The process begins by dividing x into a quotient q = \lfloor x / M \rfloor and a remainder r = x \mod M, where q captures the higher-order bits and r the lower-order bits ranging from 0 to M-1.[7]
The quotient q is encoded using unary coding, which consists of q consecutive 1 bits followed by a single 0 bit; for example, q = 3 is represented as 1110.[1] This unary representation leverages the expected sparseness of large quotients under a geometric distribution.[1]
The remainder r is encoded using truncated binary coding to achieve near-uniform length close to \log_2 M bits. To do this, compute b = \lceil \log_2 M \rceil and t = 2^b - M. If r < t, encode r in binary using b-1 bits; otherwise, encode r + t in binary using b bits. This ensures that the t smallest remainders use shorter codes, while the remaining M - t use one extra bit, maintaining the prefix-free property overall.[8][7]
The final codeword is the concatenation of the unary code for q and the truncated binary code for r. The prefix-free nature arises because the unary code always terminates with a 0, distinguishing it from potential leading 1s in the following binary code, allowing unambiguous parsing.[1]
The following pseudocode implements the core encoding procedure:
function golomb_encode(x, M):
if M <= 0:
raise ValueError("M must be positive")
q = floor(x / M)
r = x % M
# Unary code for q
unary = '1' * q + '0'
# Truncated binary for r
import math
b = math.ceil(math.log2(M))
t = 2**b - M
if r < t:
r_code = format(r, f'0{b-1}b') # (b-1)-bit binary
else:
r_adjusted = r + t
r_code = format(r_adjusted, f'0{b}b') # b-bit binary
codeword = unary + r_code
return codeword
function golomb_encode(x, M):
if M <= 0:
raise ValueError("M must be positive")
q = floor(x / M)
r = x % M
# Unary code for q
unary = '1' * q + '0'
# Truncated binary for r
import math
b = math.ceil(math.log2(M))
t = 2**b - M
if r < t:
r_code = format(r, f'0{b-1}b') # (b-1)-bit binary
else:
r_adjusted = r + t
r_code = format(r_adjusted, f'0{b}b') # b-bit binary
codeword = unary + r_code
return codeword
Core Decoding Procedure
The core decoding procedure for Golomb coding reverses the encoding process to recover the original non-negative integer x from a prefix-free bitstream, given the parameter M > 0. The input consists of a sequential bitstream and the fixed parameter M, which determines the split between the unary-encoded quotient and the truncated binary-encoded remainder. This procedure ensures instantaneous decodability without requiring lookahead beyond the current codeword, making it suitable for streaming applications.
The decoding begins by extracting the quotient q = \lfloor x / M \rfloor from the unary portion of the codeword. This involves reading bits from the bitstream and counting the number of consecutive 1s until a 0 is encountered, with q equal to the count of 1s; the terminating 0 is consumed but not part of q. If the bitstream ends prematurely without a terminating 0 (e.g., all remaining bits are 1s), the decoding fails as an invalid unary codeword, indicating a potential error in the bitstream or parameter mismatch.[9]
Next, the remainder r = x \mod M (where $0 \leq r < M) is decoded from the subsequent truncated binary representation. Compute b = \lceil \log_2 M \rceil, the minimum bits needed to represent values up to M-1. Read the next b-1 bits to form an intermediate value R (ranging from 0 to $2^{b-1} - 1). Compute the threshold t = 2^b - M. If R < t, then r = R; otherwise, read one additional bit a (0 or 1), and set r = (R \ll 1) + a - t. This adjustment accounts for the variable-length encoding, assigning shorter b-1-bit codes to smaller remainders and longer b-bit codes to larger ones. If M is a power of 2 (i.e., M = 2^k), then b = k, t = 0, and the process simplifies to always reading k bits directly for r, as no length extension occurs. An invalid bit pattern (e.g., insufficient bits after the unary part) triggers a decoding error.[9][10]
Finally, reconstruct the original value as x = q \cdot M + r. The bitstream pointer advances to the next codeword, enabling sequential decoding of multiple integers. This process mirrors the quotient-remainder split used in encoding but operates in reverse, preserving the geometric distribution assumption for efficiency.
The following pseudocode outlines the core decoding function in a procedural style, assuming a bitstream reader that supports sequential bit extraction and error signaling:
function decode_golomb(bitstream, M):
if M <= 0:
raise [Error](/page/Error)("Invalid parameter M")
# Decode unary quotient q
q = 0
while read_bit([bitstream](/page/Bitstream)) == 1:
q += 1
if end_of_stream([bitstream](/page/Bitstream)):
raise [Error](/page/Error)("Invalid unary: no terminating 0")
# The last read_bit was 0, already consumed
# Decode truncated binary remainder r
import math
b = math.ceil(math.log2(M)) if M > 1 else 1
t = (1 << b) - M
R = 0
for i in range(b - 1):
bit = read_bit([bitstream](/page/Bitstream))
if end_of_stream([bitstream](/page/Bitstream)):
raise [Error](/page/Error)("Insufficient bits for remainder")
R = (R << 1) | bit
if R >= t:
a = read_bit([bitstream](/page/Bitstream))
if end_of_stream([bitstream](/page/Bitstream)):
raise [Error](/page/Error)("Insufficient bits for extended remainder")
r = ((R << 1) | a) - t
else:
r = R
# Reconstruct x
x = q * M + r
return x
function decode_golomb(bitstream, M):
if M <= 0:
raise [Error](/page/Error)("Invalid parameter M")
# Decode unary quotient q
q = 0
while read_bit([bitstream](/page/Bitstream)) == 1:
q += 1
if end_of_stream([bitstream](/page/Bitstream)):
raise [Error](/page/Error)("Invalid unary: no terminating 0")
# The last read_bit was 0, already consumed
# Decode truncated binary remainder r
import math
b = math.ceil(math.log2(M)) if M > 1 else 1
t = (1 << b) - M
R = 0
for i in range(b - 1):
bit = read_bit([bitstream](/page/Bitstream))
if end_of_stream([bitstream](/page/Bitstream)):
raise [Error](/page/Error)("Insufficient bits for remainder")
R = (R << 1) | bit
if R >= t:
a = read_bit([bitstream](/page/Bitstream))
if end_of_stream([bitstream](/page/Bitstream)):
raise [Error](/page/Error)("Insufficient bits for extended remainder")
r = ((R << 1) | a) - t
else:
r = R
# Reconstruct x
x = q * M + r
return x
This implementation handles basic error cases such as invalid parameters, premature stream end, or malformed codewords, ensuring robustness in practical use.[9]
Variants for Specific Data Types
Rice Coding Implementation
Rice coding represents a specialized form of Golomb coding where the parameter M is constrained to powers of two, M = 2^k for some non-negative integer k, which streamlines computations by replacing division and modulo operations with bitwise shifts and masks. This restriction enables the remainder to be represented using a fixed-width binary code of exactly k bits, making the scheme particularly amenable to efficient implementation in both software and hardware environments.[2]
The encoding process for a non-negative integer x begins by computing the quotient q = ⌊x / 2^k⌋, which can be obtained via a right shift: q = x >> k. The remainder r is then derived as r = x & (2^k - 1), capturing the least significant k bits of x. The resulting codeword consists of the unary encoding of q—comprising q '1' bits followed by a terminating '0'—immediately followed by the k-bit binary representation of r. This structure ensures prefix-free decoding without requiring table lookups for the remainder.[2]
Decoding mirrors the encoding simplicity: the unary portion is read by counting consecutive '1's until a '0' is encountered, yielding q. The subsequent k bits are interpreted as the binary integer r. The original value is reconstructed using bit operations: x = (q << k) + r, where << denotes a left shift by k bits. These shift-based operations eliminate floating-point or integer division, reducing computational overhead and latency.[2]
The efficiency of Rice coding stems from its avoidance of costly arithmetic operations, relying instead on fast bitwise manipulations that are natively supported in most processors and hardware designs, such as field-programmable gate arrays (FPGAs) used in embedded systems.[2]
Encoding Signed Integers
Golomb coding, originally designed for non-negative integers following a geometric distribution, requires adaptation to encode signed integers losslessly while preserving efficiency for data such as prediction errors in compression applications.[2] A common mapping strategy transforms a signed integer x into a non-negative integer y suitable for standard Golomb encoding, ensuring bijective correspondence and interleaving positive and negative values around zero. Specifically, for a signed residual \hat{e}, the mapping is defined as y = 2|\hat{e}| if \hat{e} \geq 0, and y = 2|\hat{e}| - 1 if \hat{e} < 0 , which equivalently yields y = 2\hat{e} for non-negative \hat{e} and y = -2\hat{e} - 1 for negative \hat{e}. This approach maps the sequence of signed values \dots, -2, -1, 0, 1, 2, \dots to non-negative integers $0, 1, 2, 3, 4, \dots in an interleaved manner, allowing the use of unsigned Golomb procedures thereafter.
An alternative method involves encoding a separate sign bit alongside the Golomb code for the absolute value |x|, which simplifies implementation but is generally less efficient for symmetric distributions around zero, as it incurs an additional bit per symbol without leveraging the parity integration of the primary mapping. This signed-magnitude approach may be used in some contexts, but formats like FLAC employ the primary interleaved mapping (also known as zigzag encoding) for residual encoding.[11]
In Rice coding variants, particularly for bounded signed integers within a fixed b-bit range (e.g., in sensor data or fixed-precision signals), an offset binary transformation is often applied prior to encoding: y = x + 2^{b-1}, shifting the signed range [-2^{b-1}, 2^{b-1}-1] to the unsigned range [0, 2^b - 1] for subsequent Rice application. This method suits scenarios with uniform or known bounds but may introduce inefficiency if the distribution skews heavily toward zero, as it does not inherently favor low-magnitude values.
These adaptations assume a near-zero mean in the signed data, such as prediction errors in image or audio compression, where the geometric distribution parameter \theta is close to 0 for small magnitudes; large deviations or heavy-tailed distributions can lead to suboptimal bit rates, necessitating parameter adjustments or hybrid techniques. For decoding, the inverse mapping reconstructs the original signed value from the unsigned y: if y is even, x = y/2; if odd, x = -(y+1)/2, ensuring lossless recovery when paired with the core Golomb decoding.
Practical Algorithms
Basic Golomb Algorithm
The basic Golomb algorithm provides a non-adaptive method for lossless encoding of non-negative integers under the assumption of a geometric probability distribution, using a fixed positive integer parameter M selected based on the expected distribution parameter. Introduced by Solomon W. Golomb in his seminal work on run-length encodings, the algorithm splits each input value x \geq 0 into a quotient and remainder with respect to M, encoding them separately to achieve compression efficiency for sources where small values are more probable.[1]
Encoding begins by initializing a bit stream buffer to accumulate output bits, which are packed into bytes (typically 8 bits) for efficient storage or transmission, with padding (e.g., zero bits) added during final flush if necessary to align to byte boundaries. For each input x, compute the quotient q = \lfloor x / M \rfloor and remainder r = x \mod M. Output the unary representation of q by writing q consecutive '1' bits followed by a single '0' bit to the stream. Then, encode r using truncated binary coding: compute b = \lceil \log_2 M \rceil and t = 2^b - M; if r < t, write the (b-1)-bit binary representation of r; otherwise, write the b-bit binary representation of r + t. These bits are appended to the stream via bit-level writes, shifting and masking as needed to fill the buffer. The process repeats for the entire sequence, after which the buffer is flushed to produce complete bytes.[1][9]
Decoding mirrors the encoding process in reverse using a bit-level input stream unpacked from bytes. For each symbol, read successive bits from the stream, counting consecutive '1's until a '0' is read to recover q. Then, decode r from the subsequent bits using the known M: compute b = \lceil \log_2 M \rceil and t = 2^b - M; if b = 0, set r = 0; else, read b-1 bits to form a temporary value temp; if temp < t, set r = temp; else, read one additional bit to form the full b-bit value v = (temp \ll 1) | next_bit, and set r = v - t. Reconstruct x = q \cdot M + r. This bit-by-bit reading ensures prefix-free decoding without lookahead beyond the codeword length.[1][9]
The algorithm's time complexity is O(1) per symbol, involving constant-time integer division (or shifts for powers-of-two M), logarithmic bit operations for unary and binary parts, and table lookups for truncated binary decoding when M is small (e.g., b \leq 8); bit packing and unpacking add negligible overhead via buffering.[12]
Despite its simplicity and optimality for stationary geometric sources, the basic Golomb algorithm requires M to be predefined and shared between encoder and decoder, limiting adaptability; it yields suboptimal compression or even expansion for data with varying statistics deviating from the fixed geometric model tuned to M.[1]
Pseudocode
The following pseudocode outlines the full encoder and decoder, assuming a BitStream interface for bit-level I/O with byte packing (implementation details omitted for brevity; in practice, use shifts and masks for buffer management, flushing on 8-bit boundaries).
# Encoder
import math
class BitStream:
def __init__(self):
self.buffer = 0
self.bits = 0
self.output = [] # List of bytes
def write_bit(self, bit):
self.buffer = (self.buffer << 1) | bit
self.bits += 1
if self.bits == 8:
self.output.append(self.buffer)
self.buffer = 0
self.bits = 0
def flush(self):
if self.bits > 0:
self.buffer <<= (8 - self.bits)
self.output.append(self.buffer)
self.bits = 0
def golomb_encode(data, M):
stream = BitStream()
for x in data:
if x < 0:
raise ValueError("Non-negative integers only")
q = x // M
r = x % M
# Unary q
for _ in range(q):
stream.write_bit(1)
stream.write_bit(0)
# Truncated binary r
b = math.ceil(math.log2(M))
t = (1 << b) - M
if r < t:
# b-1 bits
for i in range(b - 2, -1, -1):
stream.write_bit((r >> i) & 1)
else:
val = r + t
for i in range(b - 1, -1, -1):
stream.write_bit((val >> i) & 1)
stream.flush()
return stream.output # Byte array
# Decoder
class InputBitStream:
def __init__(self, bytes_data):
self.bytes = bytes_data
self.byte_idx = 0
self.bit_idx = 0
self.buffer = 0
def read_bit(self):
if self.byte_idx >= len(self.bytes):
raise ValueError("End of stream")
if self.bit_idx == 0:
self.buffer = self.bytes[self.byte_idx]
self.byte_idx += 1
bit = (self.buffer >> 7) & 1
self.buffer <<= 1
self.bit_idx = (self.bit_idx + 1) % 8
return bit
def golomb_decode(num_symbols, M, bytes_data):
stream = InputBitStream(bytes_data)
result = []
for _ in range(num_symbols):
# Unary q
q = 0
while stream.read_bit() == 1:
q += 1
# Truncated binary r
b = math.ceil(math.log2(M))
t = (1 << b) - M
if b == 0:
r = 0
else:
temp = 0
for i in range(b - 2, -1, -1):
temp = (temp << 1) | stream.read_bit()
if temp < t:
r = temp
else:
next_bit = stream.read_bit()
v = (temp << 1) | next_bit
r = v - t
x = q * M + r
result.append(x)
return result
# Encoder
import math
class BitStream:
def __init__(self):
self.buffer = 0
self.bits = 0
self.output = [] # List of bytes
def write_bit(self, bit):
self.buffer = (self.buffer << 1) | bit
self.bits += 1
if self.bits == 8:
self.output.append(self.buffer)
self.buffer = 0
self.bits = 0
def flush(self):
if self.bits > 0:
self.buffer <<= (8 - self.bits)
self.output.append(self.buffer)
self.bits = 0
def golomb_encode(data, M):
stream = BitStream()
for x in data:
if x < 0:
raise ValueError("Non-negative integers only")
q = x // M
r = x % M
# Unary q
for _ in range(q):
stream.write_bit(1)
stream.write_bit(0)
# Truncated binary r
b = math.ceil(math.log2(M))
t = (1 << b) - M
if r < t:
# b-1 bits
for i in range(b - 2, -1, -1):
stream.write_bit((r >> i) & 1)
else:
val = r + t
for i in range(b - 1, -1, -1):
stream.write_bit((val >> i) & 1)
stream.flush()
return stream.output # Byte array
# Decoder
class InputBitStream:
def __init__(self, bytes_data):
self.bytes = bytes_data
self.byte_idx = 0
self.bit_idx = 0
self.buffer = 0
def read_bit(self):
if self.byte_idx >= len(self.bytes):
raise ValueError("End of stream")
if self.bit_idx == 0:
self.buffer = self.bytes[self.byte_idx]
self.byte_idx += 1
bit = (self.buffer >> 7) & 1
self.buffer <<= 1
self.bit_idx = (self.bit_idx + 1) % 8
return bit
def golomb_decode(num_symbols, M, bytes_data):
stream = InputBitStream(bytes_data)
result = []
for _ in range(num_symbols):
# Unary q
q = 0
while stream.read_bit() == 1:
q += 1
# Truncated binary r
b = math.ceil(math.log2(M))
t = (1 << b) - M
if b == 0:
r = 0
else:
temp = 0
for i in range(b - 2, -1, -1):
temp = (temp << 1) | stream.read_bit()
if temp < t:
r = temp
else:
next_bit = stream.read_bit()
v = (temp << 1) | next_bit
r = v - t
x = q * M + r
result.append(x)
return result
[1][9]
Adaptive Golomb-Rice Techniques
Adaptive Golomb-Rice techniques enable dynamic adjustment of the coding parameter to accommodate varying data statistics, particularly in non-stationary sources where fixed parameters lead to suboptimal compression. The core adaptive strategy involves periodically updating the Rice parameter k = \log_2 M based on recent samples, typically every N symbols (e.g., N = 128 to $2048), using a maximum likelihood (ML) estimate derived from the geometric distribution assumption. Specifically, the probability p is estimated as \hat{p} = 1 / (\bar{\mu} + 1), where \bar{\mu} is the sample mean of the absolute values from a buffer of recent symbols, and then k = \max\left\{0, \left\lfloor \log_2 \left( \bar{\mu} + 0.382 \right) \right\rfloor \right\}, providing an efficient approximation to the optimal parameter without exhaustive search.[2]
In run-length encoding (RLE) applications, adaptation is tailored to distinguish short and long runs, adjusting M (or k) separately for run types to better model bursty zero sequences common in quantized data. For instance, the run-length Golomb-Rice (RLGR) scheme maintains a buffer of recent outputs to estimate the exponential decay rate of run lengths, updating k via scaled accumulators that increment or decrement based on observed run completions or interruptions (e.g., full runs increase k_P by 2, partial runs decrease by 1, with k = k_P \gg 2 for smoothing over 4 samples). This backward adaptation from the buffer ensures quick convergence to local statistics, typically within 30 symbols, while favoring run mode for sparse data and Golomb-Rice mode for denser values.[13]
Two primary techniques facilitate low-overhead updates: backward adaptation, where the encoder and decoder synchronously adjust k after each symbol without transmitting parameters (e.g., if the quotient p = u \gg k = 0, decrease scaled K by a constant like 2; if p > 1, increase by p), and forward adaptation, which predicts k from contextual statistics or a preliminary pass over the block before encoding, embedding the value in the stream header for synchronization. Backward methods minimize overhead to near zero by relying on identical update rules, ideal for streaming, while forward approaches suit block-based processing but incur minor header costs (e.g., 4-5 bits per block). These apply particularly to Rice coding variants for binary-efficient encoding of non-negative integers.[14]
A notable example from the literature is the adaptive scheme in the Shorten lossless audio compressor, which dynamically selects Rice parameter k (limited to 0-14 for practical range) per segment of 256 samples based on prediction residual magnitudes, achieving seamless adaptation to signal variance changes.[15][16]
For non-stationary sources, such as varying quantized generalized Gaussian data, adaptive Golomb-Rice techniques reduce average bit rates by 10-20% compared to fixed-parameter coding, especially for peaked distributions with shape parameter \nu \approx 0.5, by closely tracking local entropy without significant computational overhead.[13]
Illustrative Examples
Basic Numerical Encoding
Golomb coding encodes a non-negative integer x using a positive integer parameter M by dividing x into a quotient q = \lfloor x / M \rfloor and a remainder r = x \mod M. The quotient q is represented in unary code as q ones followed by a zero, while the remainder r is encoded using truncated binary coding, which assigns prefix-free binary strings of lengths \lfloor \log_2 M \rfloor or \lceil \log_2 M \rceil to the values 0 through M-1. This construction ensures the overall code is instantaneous (prefix-free), allowing unambiguous decoding.
To illustrate with M = 10 and x = 42, first compute q = \lfloor 42 / 10 \rfloor = 4 and r = 42 \mod 10 = 2. The unary code for q = 4 is 11110. For the remainder, \lceil \log_2 10 \rceil = 4, but truncated binary uses 3 bits for r = 2 as 010 (since b = \lfloor \log_2 9 \rfloor + 1 = 4, with the first $2^b - M = 6 values using 3 bits: 000 for 0, 001 for 1, 010 for 2, etc.). The resulting codeword is 11110010.
Decoding the bitstream 11110010 begins by reading the unary quotient: the first four bits are 1s followed by a 0, yielding q = 4. Knowing M = 10, the decoder then parses the truncated binary remainder by attempting the shortest valid code; the next 3 bits 010 decode to r = 2. Reconstructing gives x = q \cdot M + r = 4 \cdot 10 + 2 = 42. The bitstream visualization shows the packed bits with clear boundaries due to the prefix-free unary terminator (the 0 after the 1s) and the self-delimiting truncated binary:
Unary (q=4): 1 1 1 1 0
Truncated binary (r=2): 0 1 0
Full codeword: 1 1 1 1 0 0 1 0
Unary (q=4): 1 1 1 1 0
Truncated binary (r=2): 0 1 0
Full codeword: 1 1 1 1 0 0 1 0
When M is a power of 2, such as M = 8 (a special case known as Rice coding), the process simplifies because the remainder uses fixed-length binary of k = \log_2 M = 3 bits. For the same x = [42](/page/42), q = \lfloor 42 / 8 \rfloor = 5 and r = 42 \mod 8 = 2; the unary is 111110, and the binary is 010 (3 bits for 2). The codeword is 111110010, contrasting with the general case by avoiding variable-length remainders and using arithmetic shifts for efficiency.[2]
Run-Length Encoding Application
Golomb coding finds a natural application in run-length encoding (RLE), where sequences of identical symbols—such as pixels in sparse binary images—are represented by the symbol value and the length of its run, assuming the run lengths follow a geometric distribution. This distribution is typical in data like fax transmissions or binary graphics, where short runs are more probable than long ones, allowing Golomb codes to assign shorter codewords to frequent short lengths. The encoding process applies the core Golomb procedure to each run length, leveraging the unary coding of the quotient for efficiency on small values and binary coding of the remainder for precision.[1][17]
To illustrate, consider a binary image segment consisting of runs [3 zeros, 1 one, 5 zeros]. Using Rice coding—a Golomb variant with parameter M=4 (equivalent to k=2, where remainders are encoded in 2 bits)—the run lengths 3, 1, and 5 are encoded individually. For length 3: quotient q = ⌊3/4⌋ = 0 (encoded as unary "0"), remainder r = 3 mod 4 = 3 (encoded as "11"), yielding "011". For length 1: q = 0 ("0"), r = 1 ("01"), yielding "001". For length 5: q = 1 ("10"), r = 1 ("01"), yielding "1001". Since the runs alternate between symbols, symbol indicators (e.g., a single bit to specify zero or one) are appended to each codeword to distinguish run types, ensuring unambiguous decoding.[18][1]
The unary component efficiently compresses short runs common in geometric distributions, while the fixed-length remainder handles larger values without excessive bits. In this example, the encoded run lengths total 10 bits ("011" + "001" + "1001"), plus 3 bits for symbol indicators (total 13 bits); in contrast, a raw RLE using 3 fixed bits per length (sufficient for runs up to 7) plus 1 symbol bit per run would require 9 bits for lengths and 12 bits overall. In this specific case, Golomb-Rice uses slightly more bits, but it achieves savings for skewed distributions where short runs predominate. This approach reduces redundancy in sparse data, achieving near-entropy coding when the parameter M approximates the inverse of the geometric probability parameter.[17][19]
Integration with RLE often involves adaptive selection of M for different run types, such as separate parameters for zero runs (typically longer in text-like images) and one runs (shorter), to better match local statistics without prior knowledge of the source. This adaptation enhances performance in varied datasets, like quantized images, by dynamically tuning based on recent run lengths.[19]
Modern Applications
Audio and Image Compression
Golomb coding, particularly its Rice variant, plays a key role in audio compression by efficiently encoding prediction residuals that follow a Laplace distribution, making it suitable for lossless codecs. In the Free Lossless Audio Codec (FLAC), Rice coding is applied to the residual signals generated after linear predictive coding (LPC) prediction, where the residuals are typically small and clustered around zero. The Rice parameter k ranges from 0 to 14, encoded using 4 or 5 bits, and is adaptively selected per subframe partition (up to 256 partitions) to optimize compression based on local signal statistics.[16] When k > 14, an escape code triggers alternative encoding, such as raw binary representation with a specified bit width, ensuring flexibility for atypical residuals.[16] This adaptive approach relies on Rice techniques to achieve low computational overhead, enabling real-time decoding suitable for streaming applications.[16]
In image compression, Golomb-Rice coding is employed in the JPEG-LS standard for encoding mapped prediction errors, exploiting their near-Laplace distribution that aligns well with the geometric probability model assumed by Golomb codes. JPEG-LS uses a Golomb parameter N (a power-of-two variant for efficiency) that is adaptively estimated from context-based statistics of residual magnitudes, allowing sequential refinement during encoding. The residuals, derived from median-edge or other predictors, are transformed into non-negative integers via a simple mapping function before Golomb-Rice application, which provides near-optimal prefix codes for the discrete two-sided geometric distribution of errors. This method contributes to JPEG-LS's overall performance, offering compression ratios superior to earlier lossless JPEG while maintaining low complexity for hardware implementation.
Early applications of Golomb variants in audio include the Shorten codec from 1993, which compressed WAV files using prediction residuals encoded with methods inspired by Golomb efficiency for geometric distributions, though primarily via Huffman.[15] In video standards like H.264/AVC, exponential Golomb codes are used to encode various syntax elements, such as macroblock types and motion vector differences, which often follow geometric distributions.[20] Overall, these implementations demonstrate Golomb coding's ability to yield 20-50% bit reduction on residuals in multimedia scenarios, balancing high compression with minimal processing demands for real-time use.[21]
Biomedical and Sensor Data Processing
In biomedical signal processing, hybrid Golomb-Rice coding systems have been applied to electrocardiogram (ECG) data compression for wearable devices, incorporating preprocessing such as derivative-based differencing and magnitude thresholding on quantized samples from databases like MIT-BIH arrhythmia.[22] Adaptive selection of the parameter k based on mean packet values optimizes the unary quotient and binary remainder encoding, achieving average compression ratios of 2.75 and maximum of 3.14, which reduces transmission energy consumption by minimizing data volume in low-power transceivers.[22] These systems lower overall power to approximately 2.9 W (0.2 W logical and 2.7 W I/O), enhancing battery life in portable health monitors without loss of diagnostic fidelity.[22]
For environmental sensor applications, Golomb-Rice coding enables real-time compression of multi-dimensional ocean buoy data, applying the scheme to prediction errors (deltas) from consecutive samples across dimensions like temperature and salinity.[23] Independent per-dimension encoding with historical statistics supports lossless operation, yielding an average compression rate of 47.40% and up to 38.60% energy savings in telemetry transmissions for long-term, low-power deployments.[23] This approach avoids block delays, facilitating continuous monitoring in remote oceanic settings.[23]
Other sensor data processing leverages Golomb-Rice variants for specialized compression; in power systems, preprocessing techniques like frequency-compensated difference encoding on phasor angles achieve average ratios of 2.1:1, exploiting temporal correlations for efficient synchrophasor transmission in smart grids.[24] Similarly, in database management, an efficient sparse binary sequence algorithm for inverted indexes offers decompression speeds up to 56.1% faster than Golomb-Rice on ARM architectures, with only about 8% less compression efficiency, applied to low-density production data.[25]
Recent advances extend Golomb-Rice for low-entropy sources through optimal code extensions that narrow the gap between source entropy and code length for exponentially distributed data, improving lossless performance in sparse biomedical streams.[26] Hardware optimizations, such as unary part re-encoding in Golomb-Rice implementations, reduce switching power by approximately 7% and bit counts by 6-19% in IoT contexts, synthesized via Verilog for energy-constrained devices handling sensor inputs.[27]
A key challenge in these applications involves handling non-stationary signals, where online adaptation of coding order based on real-time symbol counts addresses rapid statistical shifts without large storage overheads, outperforming arithmetic coding in variability-heavy scenarios like dynamic biomedical waveforms.[28] Such adaptations build briefly on run-length encoding for sparse sensor runs in hybrid setups.[22]