Past exam of the communication Theory course of the University of Oxford / 2009 / 2

In the terminology used here, a block code assigns a distinct word of the same length to every source symbol. For a binary code with $m$ symbols this common length must satisfy $2^{\ell }\ge m$. The equal-length property is what matters in this question; elsewhere the term can also refer more generally to coding blocks of source symbols.

A prefix code has no codeword that is a proper prefix of another. Its code tree therefore places source symbols at leaves. It is instantaneous because the decoder knows that a source symbol has ended as soon as its leaf is reached, without needing to inspect later transmitted symbols.

A compact code or optimal prefix code minimizes the expected codeword length ${\sum }_x{p}_x{\ell }_x$ for the given source probabilities and coding alphabet. The relevant comparison here is among binary prefix codes. The minimum is also the minimum among uniquely decodable codes, since the Kraft-McMillan inequality permits every uniquely decodable length list to be realized by a prefix code with the same lengths.

Every internal node of an optimal binary prefix tree has two children. If one had only one child, remove that one-edge detour from all descendant words. Prefix-freeness is preserved and at least one positive-probability word becomes shorter, strictly lowering the expected length. Thus the tree is full.

Take a leaf at maximum depth $L$. Its sibling exists because the tree is full. That sibling cannot be an internal node, since a descendant would be deeper than $L$. Hence it is another leaf at depth $L$, and the corresponding codewords differ only in their final bit. This is the deepest sibling property of an optimal prefix code.

A finite full binary tree satisfies Kraft equality, ${\sum }_x{2}^{-{\ell }_x}=1$, by dividing mass equally down each branch from the root. If all $2^n$ lengths were at least $n$, with at least one strictly greater, that sum would be less than $2^n{2}^{-n}=1$, a contradiction. Since the code is not a block code, the alternative that all lengths equal $n$ is excluded. Therefore some word has length below $n$. Also a longest word must have length above $n$: if all lengths were at most $n$ and some shorter, the Kraft sum would exceed one.

Suppose every sum of two distinct probabilities exceeds every third probability. If an optimal code were not a block code, part (b) gives two deepest sibling leaves $x,y$ at depth $L>n$ and a leaf $z$ at depth $\ell <n$. Replace the sibling pair by a leaf labelled $z$, and replace the former $z$ leaf by two children labelled $x,y$. The resulting tree is still a prefix tree, and other word lengths are unchanged. The change in expected length isHere $L-\ell -1\ge 1$. This contradicts optimality. Thus every optimal code is a block code.

Conversely, suppose distinct $x,y,z$ satisfy $p_x+p_y\le p_z$. Starting with the complete length-$n$ code, arrange $x,y$ as a sibling pair, which is possible by permuting the source labels. Its parent at depth $n-1$ does not contain $z$. Label that parent $z$, and split the old $z$ leaf into children $x,y$. This gives lengths $n-1$ for $z$, $n+1$ for $x,y$, and $n$ otherwise, with expected lengthIf the optimal mean length is below $n$, no optimal code can be a block code: any injective binary block code for $2^n$ symbols has length at least $n$. If the optimal mean is $n$, the constructed non-block code itself is optimal. In either case there is an optimal non-block code. This proves the reverse implication, including the equality case, and hence the strict inequality in the criterion is necessary.

This is the optimality of a fixed-length code for a power-of-two alphabet.