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

A binary code assigns a finite binary word $c_k$ to each source symbol $x_k$. In the ordinary unframed convention these codewords are nonempty. It is uniquely decodable when concatenation gives an injective map from finite symbol strings to bit strings:The decoder can recover the entire symbol sequence without being told where codewords end. This is stronger than merely assigning distinct words to individual symbols.

An instantaneous code can decode each symbol as soon as its final bit arrives, without waiting for later bits. Equivalently it is prefix-free: no codeword is a proper prefix of another, and different symbols receive different codewords.

For nonempty codewords, decoding greedily from the start of the bit string identifies the first codeword unambiguously; repeating identifies the whole sequence. Thus an instantaneous code is uniquely decodable under the ordinary nonempty-word convention.

The codeword lengths are integers. For necessity, take $L={\max }_k{l}_k$ and view codewords as nodes of the binary tree. A codeword of length $l_k$ has $2^{L-l_k}$ descendant words at depth $L$. Prefix-freeness makes these descendant sets disjoint, soFor sufficiency, reorder the lengths nondecreasingly. Assign words successively. At depth $l_k$, words extending previously assigned codewords numberThe asserted inequality, even after dropping the later nonnegative terms, givesThus at least one depth-$l_k$ word does not extend an earlier word. Choose it. Since lengths are nondecreasing, it cannot be a proper prefix of a shorter earlier word, and equal-length duplicates have been excluded. Induction constructs the required code. Therefore Kraft inequality is necessary and sufficient:

First consider any instantaneous code. Put $K_0={\sum }_k{2}^{-l_k}\le 1$ and $q_k=2^{-l_k}/K_0$. Part 1(a) givesso $\mathbb{E}L\ge H(X)-{\log }_2{K}_0\ge H(X)$.

For the construction, take the Shannon lengths $l_k=\lceil -{\log }_2{p}_k\rceil$. Then $2^{-l_k}\le p_k$, so Kraft's condition holds. Also $l_k<-{\log }_2{p}_k+1$ for every $k$. Averaging givesFor a nontrivial alphabet all $p_k<1$, so these lengths are positive and the ordinary code convention applies. For a deterministic one-symbol source, the usual zero-bit convention uses $l_1=0$ when the number of source symbols is externally known. If strictly nonempty codewords and arbitrary unframed message lengths are required instead, that degenerate case has $\mathbb{E}L\ge 1$ and cannot satisfy the printed strict upper bound. This convention issue does not affect sources with at least two symbols.

Let $F_k={\sum }_{r<k}{p}_r$ and let $J_k=[F_k,F_k+p_k)$ be the probability cell of symbol $k$. Its midpoint is $G_k=F_k+p_k/2$. Use the binary expansion terminating in zeros at a dyadic rational, so truncation to $l_k$ bits givesThe chosen codeword corresponds to the dyadic interval $D_k=[a_k,a_k+2^{-l_k})$. It contains $G_k$, and its width satisfies $2^{-l_k}\le p_k/2$. ConsequentlyThus $D_k\subseteq J_k$. The probability cells are disjoint, so the code intervals are disjoint. If one binary codeword were a prefix of another, its dyadic interval would contain the other's interval, contradicting this disjointness. Hence the code is instantaneous.

Finally, $l_k=\lceil -{\log }_2{p}_k\rceil +1<-{\log }_2{p}_k+2$. Multiplying by $p_k$ and summing yieldsThis is the Shannon-Fano-Elias code: the extra bit makes the dyadic interval narrow enough to remain inside the cell around its midpoint.