ConceptDBISAI-written · not yet proofread

Elias-Gamma Code

The Elias-Gamma code of a positive integer x consists of ⌊log₂ x⌋ zeroes followed by the binary representation of x, and has length 2⌊log₂ x⌋ + 1.

Formula#

L(x) = 2 \lfloor \log_2 x \rfloor + 1

Prefix-free: the number $m$ of leading zeroes determines that exactly $m + 1$ bits (the binary number) follow.
Cheap for small numbers (1 bit for $x = 1$ ), logarithmic in $x$ ; entropy-optimal for $\Pr(x) \approx 2^{-L(x)}$ .
Elias-Delta encodes the zeroes part itself with Gamma and wins for large $x$ .

$x$	Binary	Code	Length
1	`1`	`1`	1
2	`10`	`010`	3
3	`11`	`011`	3
4	`100`	`00100`	5
7	`111`	`00111`	5
8	`1000`	`0001000`	7
15	`1111`	`0001111`	7
16	`10000`	`000010000`	9

DBIS Exam WS2223 (not published) Task 1.2 (codes for 3, 4, 7, 8, 15, 16 and the length formula)
Not lectured in WS 25/26.

Connections

Elias-Delta Code
For $x \geq 1$ let $k = \lfloor \log_2 x \rfloor$ . The Elias-Delta code of $x$ is the Elias-Gamma code of $k + 1$ followed by the last $k$ bits of the binary representation of $x$ (without the leading 1). §
Gap Encoding
For a sorted sequence $a_1 < a_2 < \dots < a_n$ , gap encoding stores $a_1,\ a_2 - a_1,\ a_3 - a_2,\ \dots,\ a_n - a_{n-1}$ . The original sequence is recovered by prefix sums. The gaps are then written with a variable-length code such as Go… §
Prefix-Free Code
Typical proof that a code is prefix-free: show that the end of each codeword can be recognized from the codeword itself, e.g. the first 1 in the Unary Code, or the number of leading zeroes in the Elias-Gamma Code, which fixes the total len… §
Encodings and Compression
Elias-Gamma Code — unary length prefix + binary, no parameter, $2\lfloor \log_2 x \rfloor + 1$ bits §
| Elias-Gamma | $2\lfloor \log_2 x \rfloor + 1$ | $2^{-(2\lfloor \log_2 x \rfloor + 1)}$ (polynomial tail) | – | §