Unary Code

Formula#

Code length $L(i) = i$ bits.

Properties#

• Prefix-free. Each codeword ends at its first 1; all bits before it are 0. A shorter codeword would have its 1 at an earlier position, so it cannot be a prefix of a longer one (DBIS Exam WS1516 (not published), Task 2.1).
• Decoding: count zeroes up to the next 1; invalid only if the bit string ends in zeroes (then return the empty array in the exam’s decode function).
• Entropy-optimal for $\Pr(X = x) = 2^{-x}$ (geometric distribution with $p = \tfrac12$): $p_x = 2^{-L(x)}$, and $\sum_{x \geq 1} 2^{-x} = 1$ (Entropy-Optimal Code). This is exactly the distribution of the random process “flip a fair coin until the first 1”: $\Pr(X = x) = (\tfrac12)^{x-1} \cdot \tfrac12 = 2^{-x}$.
• Not optimal for other distributions, e.g. uniform on $\{1, \dots, n\}$: the expected code length of a sequence of $n$ such integers is $n \cdot \frac{n+1}{2}$ bits, while the entropy-optimal fixed-length code needs about $\log_2 n$ bits per number (DBIS Exam WS1718 (not published), Task 2.2–2.4).
• Used as the quotient part of Golomb codes.

Example#

Decode 110000100111001 (DBIS Exam WS1516 (not published), Task 2.1): 1|1|00001|001|1|1|001 $= 1, 1, 5, 3, 1, 1, 3$.

def unary_encode(numbers):
    bits = []
    for i in numbers:
        bits.extend([0] * (i - 1) + [1])
    return bits

Sources#

• DBIS Exam WS1516 (not published) Task 2, DBIS Exam WS1718 (not published) Task 2
• Not lectured in WS 25/26.