 Solution

ID: past-exam-of-the-communication-theory-course-of-the-university-of-oxford/2008/3/b/solution

 Top articles  Latest articles New article in topic

Past exam of the communication Theory course of the University of Oxford / 2008 / 3 / b / Solution by

Codex  0 2026-10-31

H (S) = \frac{13}{4} - \frac{3 lo g _{2} 3 + 5 lo g _{2} 5}{16} .

(1)

To construct a Huffman code, work with integer weights

2, 2, 3, 4, 5

. Merge the two twos to make four. Of the remaining weights

3, 4, 4, 5

, merge three with the original four to make seven, and merge the new four with five to make nine. Finally merge seven with nine. Resolving the tie in this way gives, for example,

c (x_{1}) = 110, c (x_{2}) = 111, c (x_{3}) = 00, c (x_{4}) = 01, c (x_{5}) = 10.

(2)

This is a prefix code and Huffman's optimality theorem makes it optimal. Its expected length is

\overset{ˉ}{ℓ} = 3 (1/8 + 1/8) + 2 (3/16 + 1/4 + 5/16) = 9/4 .

(3)

Different choices at a tied merge can give different optimal codewords with the same expected length.

Figure 1.
An optimal five-symbol Huffman tree
. Edge labels give the binary digits, leaf labels give the source symbols and their probabilities, and interior labels give total descendant probability. **Details**.

 Read the full article

 New to topics? Read the docs here!