ConceptDBISAI-written · not yet proofread

Elias-Delta Code

The Elias-Delta code of x ≥ 1 is the Elias-Gamma code of ⌊log₂ x⌋ + 1 followed by the last ⌊log₂ x⌋ bits of x (its binary form without the leading 1).

Know these firstElias-Gamma Code

Formula#

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

Properties#

Prefix-free: the Gamma part is self-delimiting and gives $k$ , hence the number of trailing bits.
Asymptotically $\log_2 x + O(\log \log x)$ bits against Gamma’s $2 \log_2 x$ , so more efficient for large integers; Gamma is shorter for small $x$ .

Example#

$x$	$k$	Gamma of $k+1$	Remaining bits	Code
1	0	`1`	none	`1`
7	2	`011`	`11`	`01111`
16	4	`00101`	`0000`	`001010000`

Sources#

DBIS Exam WS2122 (not published) Task 2.2 (codes for 1, 7, 16, Gamma part underlined)
Not lectured in WS 25/26.

Connections

Prerequisites know first1

Elias-Gamma Code

Mentioned in inline links3

Elias-Gamma Code
Elias-Delta encodes the zeroes part itself with Gamma and wins for large $x$ . §
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… §
Encodings and Compression
Elias-Delta Code — Elias-Gamma for the length, shorter than Gamma for large $x$ §
| Elias-Delta | $\lfloor \log_2 x \rfloor + 2\lfloor \log_2(\lfloor \log_2 x \rfloor + 1) \rfloor + 1$ | heavier tail than Gamma | – | §

Search in these mentions →

Links to from this note1

Elias-Gamma Code