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

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: