Elias Gamma Coding: Variable-Length Integer Encoding

Elias gamma coding is a universal variable-length encoding scheme designed to represent positive integers using binary sequences. Unlike fixed-width binary formats that require a predetermined bit-depth, Elias gamma coding dynamically scales the length of the code relative to the magnitude of the integer being stored. This article explains how Elias gamma coding operates, how it encodes and decodes values, and how it extends standard binary representations to create self-delimiting, prefix-free data streams for efficient data compression.

The Limitation of Standard Binary Representation

In standard computing, integers are typically stored in fixed-width binary formats, such as 8-bit, 16-bit, 32-bit, or 64-bit blocks. While fixed-width encoding allows straightforward memory addressing, it introduces two distinct problems in data transmission and compression:

1. Space Inefficiency: Small values like 1 or 5 consume the same amount of storage as large values when stored in fixed 32-bit or 64-bit words.
2. Ambiguity in Bitstreams: Simply truncating leading zeros to save space makes it impossible for a decoder to determine where one integer ends and the next begins without external delimiters or explicit length headers.

Elias gamma coding resolves these limitations by creating a prefix-free (self-delimiting) code, meaning no complete code word is a prefix of another code word in the set. This allows a continuous stream of bits to be decoded unambiguously without separators.

How Elias Gamma Coding Works

Developed by Peter Elias in 1975, Elias gamma coding encodes any positive integer \(x \ge 1\) by splitting the number into two parts: its magnitude (the highest power of 2) and its remainder.

The encoding process follows three steps:

1. Determine the highest power of 2: Find \(N = \lfloor\log_2(x)\rfloor\), which represents the position of the most significant bit of \(x\).
2. Write the Unary Prefix: Output \(N\) zeros followed by a 1 (or simply \(N\) zeros as a prefix).
3. Append the Binary Suffix: Append the remaining \(N\) least significant bits of the standard binary representation of \(x\).

The total bit length for an encoded integer \(x\) is \(2\lfloor\log_2(x)\rfloor + 1\) bits.

Encoding Examples

• Encoding \(x = 1\):
  • \(N = \lfloor\log_2(1)\rfloor = 0\)
  • Unary prefix (\(N\) zeros): None
  • Binary representation: 1
  • Result: 1 (1 bit)
• Encoding \(x = 5\):
  • \(N = \lfloor\log_2(5)\rfloor = 2\)
  • Standard binary for 5: 101
  • Unary prefix: 00
  • Binary suffix (all bits of 5 starting from the leading 1): 101
  • Result: 00101 (5 bits)
• Encoding \(x = 9\):
  • \(N = \lfloor\log_2(9)\rfloor = 3\)
  • Standard binary for 9: 1001
  • Unary prefix: 000
  • Binary suffix: 1001
  • Result: 0001001 (7 bits)

Decoding Elias Gamma Codes

Decoding an Elias gamma bitstream is deterministic and requires no lookahead buffers:

1. Read consecutive zeros from the bitstream until a 1 is encountered.
2. Count the number of zeros read; let this count be \(N\).
3. Keep the 1 and read the subsequent \(N\) bits from the stream.
4. Convert the resulting \((N + 1)\)-bit binary sequence into its decimal integer equivalent.

For example, given the bitstream 001101...: * Count zeros: Two zeros (00), so \(N = 2\). * Read the 1 plus the next 2 bits: 110. * Convert 110 to decimal: \(4 + 2 + 0 = 6\). * The next integer starts immediately with the following bit 1.

Extending Variable-Length Integer Representations

Elias gamma coding extends standard binary logic by functioning as a universal code. In information theory, a code is universal if its asymptotic transmission rate is within a constant factor of the optimal code for an unknown probability distribution, provided the distribution is monotonically decreasing.

Elias gamma coding provides key structural extensions:

• Elimination of Size Limits: Unlike fixed integer types (like uint32), gamma codes have no upper ceiling. Any arbitrarily large integer can be encoded without format changes.
• Optimal Compression for Skewed Distributions: It achieves optimal storage when small integers occur far more frequently than large ones (such as in inverted index posting lists for search engines or delta-encoded time series).
• Foundation for Advanced Encodings: While Elias gamma encoding becomes less space-efficient for very large numbers due to the linear growth of the unary prefix, it serves as the base layer for Elias delta and Elias omega codes, which encode the length component using gamma coding recursively to save additional space.