Golomb Code

Formula#

If $M = 2^k$, the remainder uses exactly $k$ bits and the code length is $q + 1 + k$ bits.

Properties#

• Prefix-free: the unary part ends at its first 1, which fixes the number of remaining bits.
• Tunable by $M$: a larger $M$ shortens the unary part but lengthens the remainder. A good $M$ matches the typical size of the numbers, which is why Golomb codes suit gaps of inverted lists.
• Building block of the WS 16/17 custom code: for $x \geq 1$ write $\lfloor \log_2 x \rfloor$ with Golomb modulus $M = 4$, then $x$ in binary without its leading 1. With $\ell = \lfloor \log_2 x \rfloor$ the length is $\lfloor \ell / 4 \rfloor + 1 + 2 + \ell$ (unary quotient, 2-bit remainder, binary tail) (DBIS Exam WS1617 (not published), Task 2).

Example#

$M = 8$ ($k = 3$): gap $9$ has $q = 1$, $r = 1$, code 01 001 (5 bits); gap $1$ has $q = 0$, $r = 1$, code 1 001 (4 bits). The sequence $1, 10, 11, 20, 21, 30, 31, 40$ has gaps $1, 9, 1, 9, 1, 9, 1, 9$, hence $4 \cdot 4 + 4 \cdot 5 = 36$ bits (DBIS Exam WS1314 (not published), Task 1.1; computed here with the convention above, the official solution is not in the exam note).

WS 16/17 code for $x = 10$: $\ell = 3$, Golomb($3$, $M = 4$) $=$ 1 11, tail 010: 111010.

Sources#

• DBIS Exam WS1314 (not published) Task 1, DBIS Exam WS1617 (not published) Task 2
• Not lectured in WS 25/26.