Prefix code

A prefix code is a set of codewords in which no codeword is the initial segment, or prefix, of another distinct codeword. When source symbols are assigned distinct codewords satisfying this condition, an encoded sequence can be decoded from left to right: each symbol is recognized as soon as its codeword ends. Prefix codes are fundamental to information theory and lossless data compression, particularly when symbols are represented by codewords of different lengths. (xlinux.nist.gov)

Definition and example

Let $\Sigma$ be a code alphabet and let $\Sigma^*$ denote the set of finite strings over that alphabet. A set $C\subseteq\Sigma^*$ is prefix-free if, for distinct $u,v\in C$, there is no string $w$ such that $v=uw$. Equivalently, no complete codeword can be the beginning of a longer codeword. A symbol encoder is an injective function assigning source symbols to these codewords. (ocw.mit.edu)

For example, the following binary code is prefix-free:

The encoded string 010110111 separates unambiguously into 0 | 10 | 110 | 111, yielding ABCD. The separators are explanatory; they need not be transmitted. By contrast, the code {0, 1, 01} is not prefix-free, and 01 could represent either one codeword or the concatenation of 0 and 1. (stanforddatacompressionclass.github.io)

Distinct fixed-length codewords also satisfy the prefix condition. Thus, prefix code describes a structural property, not a requirement that codeword lengths vary. Nor does it prohibit shared initial segments: 110 and 111 share 11, but neither complete codeword prefixes the other. (xlinux.nist.gov)

Instantaneous decoding and code trees

A prefix code can be represented by a rooted coding tree. Edges are labeled with code-alphabet symbols, and each codeword is the sequence of labels on a path from the root to an assigned leaf. For binary codes, the edge labels are 0 and 1. Placing codewords only at leaves ensures that no codeword lies on the path to another. (xlinux.nist.gov)

A tree-based decoding algorithm starts at the root and follows one edge for each input symbol. On reaching an assigned leaf, it outputs the corresponding source symbol and returns to the root. It needs no lookahead beyond the current codeword, which explains the alternative name instantaneous code. Here, “instantaneous” concerns decoding delay, not zero computational time. (stanforddatacompressionclass.github.io)

Every prefix code is uniquely decodable: concatenations of codewords determine exactly one source-symbol sequence. The converse does not hold; some uniquely decodable codes require later input, or the end of the message, before an earlier symbol can be identified. (web.mit.edu)

Kraft–McMillan inequality

For a finite prefix code over an alphabet of $D\geq2$ symbols, with codeword lengths $\ell_1,\ldots,\ell_m$, the Kraft–McMillan inequality states that

Conversely, any finite list of positive integer lengths satisfying this inequality can be realized by a prefix code. The inequality therefore characterizes possible length lists—not whether a particular selection of codewords is prefix-free. (ocw.mit.edu)

The tree interpretation gives a counting proof. At depth $L=\max_i\ell_i$, a codeword of length $\ell_i$ occupies a subtree containing $D^{L-\ell_i}$ nodes. These subtrees do not overlap, and the full tree has $D^L$ nodes at that depth. Dividing the resulting counting inequality by $D^L$ gives Kraft’s inequality. (ocw.mit.edu)

The same length constraint holds for uniquely decodable codes. Consequently, their length lists can also be realized by prefix codes, with the same average length for a given source distribution. (stanforddatacompressionclass.github.io)

Compression and optimal codes

Given source-symbol probabilities $p_i$, a binary code’s expected length is

bits per source symbol. Compression exploits unequal probabilities by assigning shorter codewords to more frequent symbols. Prefix-freeness guarantees decodability, but does not itself guarantee a small average length. (web.mit.edu)

For a finite source with at least two positive-probability symbols, define its entropy by

Every binary prefix code satisfies $L\geq H(X)$, and the optimal average length $L^*$ satisfies

One existence construction chooses $\ell_i=\lceil-\log_2p_i\rceil$; these lengths satisfy Kraft’s inequality. Huffman coding produces a prefix code minimizing average length for a given finite symbol distribution under binary, symbol-by-symbol coding with equal cost per bit. Not every prefix code is a Huffman code. (ocw.mit.edu)

For an independently and identically distributed source, coding blocks of $n$ symbols as single units reduces the rounding overhead per original symbol:

This connects prefix coding with the source coding theorem: increasing block length allows average encoded length per symbol to approach entropy. (ocw.mit.edu)

References

1. prefix codexlinux.nist.gov
2. MIT 6.02 DRAFT Lecture Notesweb.mit.edu
3. 441 Information Theory, Lecture 5ocw.mit.edu
4. Prefix Free Codesstanforddatacompressionclass.github.io
5. Kraft Inequalitystanforddatacompressionclass.github.io
6. MITOCW: 18.200 Lecture 17 transcriptocw.mit.edu