 Solution

ID: past-exam-of-the-communication-theory-course-of-the-university-of-oxford/2011/2/b/i/solution

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-31

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, so

\sum_{k} 2^{L - l_{k}} \leq 2^{L}, hence \sum_{k} 2^{- l_{k}} \leq 1.

For sufficiency, reorder the lengths nondecreasingly. Assign words successively. At depth

l_{k}

, words extending previously assigned codewords number

\sum_{i < k} 2^{l_{k} - l_{i}} .

The asserted inequality, even after dropping the later nonnegative terms, gives

\sum_{i < k} 2^{l_{k} - l_{i}} + 1 \leq 2^{l_{k}} .

Thus 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:

a binary prefix code with these lengths exists ⟺ k \sum 2^{- l_{k}} \leq 1.

 Read the full article

 New to topics? Read the docs here!