Solution

For a binary prefix code with word lengths

l_{1}, \dots, l_{m}

, choose

L \geq max l_{i}

. Each codeword is the prefix of exactly

2^{L - l_{i}}

words of length

L

, and these descendant sets are disjoint. Hence

\sum_{i} 2^{L - l_{i}} \leq 2^{L}, so \sum_{i} 2^{- l_{i}} \leq 1.

(8)

This is Kraft inequality. Conversely, if integer lengths satisfy this inequality, place words greedily as leaves of the binary tree; the unused capacity ensures that the requested leaves can all be chosen, giving a prefix code.

For Shannon--Fano coding, order symbols by probability and assign

l_{i} = ⌈ - lo g_{2} p_{i} ⌉ .

(9)

Kraft's inequality applies because

2^{- l_{i}} \leq p_{i}

and therefore

\sum_{i} 2^{- l_{i}} \leq 1

. Thus codewords of those lengths exist. Since

- lo g_{2} p_{i} \leq l_{i} < - lo g_{2} p_{i} + 1,

(10)

the expected length obeys

H (X) \leq E L < H (X) + 1.

(11)

Solved by gpt-5.6-sol high.

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 3K / Solution

 Ancestors (10)