Prefix-Free Code

Formula#

Kraft’s inequality. For symbols $1, \dots, n$ with codeword lengths $L_1, \ldots, L_n$:

Properties#

• Unique decodability without delimiters. Read bits from left to right until they form a codeword, output its symbol, and continue. Because no codeword is a prefix of another, the first match is the only possible one, so the decoding is unique.
• Lengths constrain each other. Kraft’s inequality is the only restriction: short codewords “use up” $2^{-L_i}$ of the available budget $1$. Codes with $\sum_i 2^{-L_i} = 1$ waste nothing; this is the constraint under which the past exams minimize the expected code length (Entropy-Optimal Code > Properties).
• 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 length.
• UTF-8 is prefix-free on the byte level: the leading bits of the first byte (0, 110, 1110, 11110) determine the number of bytes.

Example#

• $A = 0$, $B = 10$, $C = 110$, $D = 111$ is prefix-free, and $2^{-1} + 2^{-2} + 2^{-3} + 2^{-3} = 1$. The bit string 01000101100111 decodes uniquely as 0|10|0|0|10|110|0|111 $= A, B, A, A, B, C, A, D$.
• $a = 000$, $b = 001$, $c = 01$, $d = 10$, $e = 11$ is prefix-free: $2 \cdot 2^{-3} + 3 \cdot 2^{-2} = 1$.
• $\{0, 01, 10\}$ is not prefix-free ($0$ is a prefix of $01$), and 010 is ambiguous: 0|10 or 01|0.

Sources#

• DBIS Exam WS1516 (not published) Task 2.1 (prove that the unary code is prefix-free), DBIS Exam WS1819 (not published) Task 2.1, DBIS Exam WS1920 (not published) Tasks 2.1–2.2, DBIS Exam WS2122 (not published) Task 2.3
• Not lectured in WS 25/26 (the course was “Information Retrieval” when these exams were set).