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

A binary prefix code assigns distinct finite binary strings to the source symbols, with no assigned string a prefix of another. It is instantaneous because a complete codeword is recognized without needing the next word's bits.

Associate a word of length $\ell$ with its dyadic subinterval of $[0,1)$ of length $2^{-\ell }$. A prefix relation corresponds to interval containment. Prefix-free words therefore give disjoint intervals, whose total length is at most one. This proves necessity of Kraft inequality.

For sufficiency, sort the requested nonnegative integer lengths increasingly and construct a code greedily in a binary tree. At depth ${\ell }_j$, the preceding codewords forbid exactly ${\sum }_{i<j}{2}^{{\ell }_j-{\ell }_i}$ nodes. The assumed inequality, retaining the positive contribution of the present word, bounds this integer by $2^{{\ell }_j}-1$. Thus at least one node is available; choose it. It is not below an earlier codeword, and the nondecreasing lengths prevent it from being a proper ancestor of an earlier word. Continue to obtain a prefix code of all the required lengths. Hence

Work on the source support, so its listed probabilities are positive; zero-probability symbols may be omitted. An optimal binary prefix code minimizes the expected codeword length for that distribution. The same optimal expected length is attained when optimization is over uniquely decipherable codes, by the converse and existence parts of Kraft–McMillan inequality.

Choose Shannon lengths ${\ell }_k=\lceil -{\log }_2{p}_k\rceil$. They satisfy $2^{-{\ell }_k}\le p_k$, so the preceding existence theorem gives a prefix code with those lengths. Also ${\ell }_k<-{\log }_2{p}_k+1$ for every symbol, including the integer cases. Thus its expected length is less than $H(X)+1$. An optimal code cannot have a larger expected length, provingFor a deterministic one-symbol source the empty word has length zero, consistent with this bound.

At an interior tree node write $A,B$ for the total masses in its two children, and $S=A+B$. Counting path lengths and telescoping the Shannon entropy over the binary decisions givesIndeed each symbol contributes its probability once per ancestral interior node to the first sum. In the second sum, expanding $Sh(A/S)=S{\log }_{2}S-A{\log }_{2}A-B{\log }_{2}B$ cancels the interior terms and leaves the source Shannon entropy. The supplied inequality now bounds redundancy byConsider the cut between adjacent symbols $k,k+1$ made at one node. If its left side is heavier, moving its last symbol to the right must not improve the chosen cut. Writing $\Delta =A-B\ge 0$, this says $|\Delta -2p_k|\ge \Delta$, which implies $\Delta \le p_k$; when the left side is a singleton the same bound is immediate. If the right side is heavier, the corresponding argument gives $|A-B|\le p_{k+1}$. In all casesRecursive subdivision of contiguous blocks uses each original gap exactly once. Summing over the $m-1$ gaps therefore givesproving $\bar{s}<H(X)+2$. If probabilities are already nonincreasing, each maximum is $p_k$ and the improved bound is $\bar{s}-H(X)\le 1-p_m<1$. Thus the sorted version has expected length less than $H(X)+1$, although it need not be optimal. For one symbol the assertions hold directly. This is the Fano slice code redundancy bound.