 Solution

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

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-31

First consider any instantaneous code. Put

K_{0} = \sum_{k} 2^{- l_{k}} \leq 1

and

q_{k} = 2^{- l_{k}} / K_{0}

. Part 1(a) gives

0 \leq d (p, q) = - H (X) + E L + lo g_{2} K_{0},

so

E L \geq H (X) - lo g_{2} K_{0} \geq H (X)

.

For the construction, take the Shannon lengths

l_{k} = ⌈ - lo g_{2} p_{k} ⌉

. Then

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

, so Kraft's condition holds. Also

l_{k} < - lo g_{2} p_{k} + 1

for every

k

. Averaging gives

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

For 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

E L \geq 1

and cannot satisfy the printed strict upper bound. This convention issue does not affect sources with at least two symbols.

 Read the full article

 New to topics? Read the docs here!