Prefix Codes and Unique Decodability — Mathematics Knowledge System

Overview

A prefix code (prefix-free code) is a code where no codeword is a prefix of another. This ensures unique decodability without needing separators between codewords. Binary prefix codes correspond bijectively to binary trees via the Kraft inequality. Huffman codes are optimal prefix codes.

Intuition

Imagine decoding a binary string 001011. With a prefix code, you scan left to right and as soon as you've seen a complete codeword, output the symbol -- no ambiguity possible because no codeword is a prefix of another. Compare to a non-prefix code where '0' and '01' are both codewords: seeing '0' you don't know if the next bit belongs to this symbol or not.

Formal Definition

Definition

A code C: Sigma -> {0,1}^* is a prefix code if for all distinct x, y in Sigma, C(x) is not a prefix of C(y). Kraft inequality: for a binary prefix code with codeword lengths l_1, ..., l_n: sum_{i=1}^n 2^{-l_i} <= 1. Conversely, any set of lengths satisfying Kraft's inequality can be realized by a prefix code. Average codeword length L = sum p_i * l_i.

\sum_{i=1}^n 2^{-l_i} \leq 1

Kraft inequality

L = \sum_{i=1}^n p_i \cdot l_i

Average codeword length

H(X) \leq L < H(X) + 1

Optimality of Huffman codes

Notation

Notation	Meaning
$l_i$	Length of codeword for symbol i
$H(X)$	Shannon entropy of source X

Theorems

Theorem 1: Kraft-McMillan Theorem

A uniquely decodable code exists with lengths l_1,...,l_n if and only if the Kraft inequality holds: sum 2^{-l_i} <= 1. Prefix codes achieve this bound; any uniquely decodable code can be replaced by a prefix code with the same lengths.

Worked Examples

1
Sum = 2^{-1} + 2^{-2} + 2^{-3} + 2^{-3}.
$= \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} = 1 \leq 1$
2
Equality holds -- this is a complete prefix code (full binary tree).
$\text{Valid prefix code}$

✓ Answer

Yes, Kraft inequality satisfied with equality. A prefix code exists (e.g., 0, 10, 110, 111).

Practice Problems

Mediumapplication

Can there be a binary prefix code with lengths {1, 1, 2}?

Common Mistakes

Common Mistake

Thinking all uniquely decodable codes are prefix codes.

Not all uniquely decodable codes are prefix codes, but by the Kraft-McMillan theorem, any uniquely decodable code can be replaced by a prefix code with the same codeword lengths.

Quiz

A prefix code over a binary alphabet satisfies the Kraft inequality with:

sum 2^{l_i} >= 1sum 2^{-l_i} <= 1sum l_i = log_2(n)sum p_i * l_i = H(X)

Historical Background

The study of uniquely decodable codes developed alongside information theory. Fano and Shannon independently proposed the Shannon-Fano code (1948). David Huffman (1952), as a student at MIT, improved this to find the optimal prefix code in an exam problem that became one of the most cited papers in information theory.

1948
Shannon and Fano propose the Shannon-Fano coding method
Claude Shannon, Robert Fano
1952
David Huffman discovers the optimal prefix code (Huffman coding)
David Huffman

Summary

Prefix code: no codeword is a prefix of another. Ensures unique decodability.
Kraft inequality: sum 2^{-l_i} <= 1. Necessary and sufficient for a binary prefix code with given lengths.
Huffman codes achieve H(X) <= L < H(X) + 1 -- optimal among all prefix codes.
Complete prefix code: Kraft inequality holds with equality (full binary tree).

References

BookCover, T.M. and Thomas, J.A. Elements of Information Theory. 2nd ed. Wiley, 2006.