COMP2610/COMP6261 – Information Theory
Tutorial 8: Source Coding
Young Lee and Bob Williamson
Tutors: Debashish Chakraborty and Zakaria Mhammedi
Week 10 (9th – 13th Oct), Semester 2, 2017
1. Optimal Coding and Huffman Codes
Consider the ensemble X with probabilities PX = p = { 12 ,
1
4
, 31
128
, 1
128
} and the code C = {0, 11, 100, 101}.
(a) What is the entropy H(X)?
(b) What is the expected length L(C,X)? Is C an optimal code for X?
(c) What are the code lengths forX? Construct a prefix Shannon code CS forX . Compute the expected code
length L(CS , X).
(d) What are the probabilities q = {q1, q2, q3, q4} for the code lengths of C?
(e) Compute the relative entropy D(p‖q). What do you notice about D(p‖q), H(X), L(C,X), and
L(CS , X)?
(f) Construct a Huffman code CH for X . How does its code lengths compare to C and CS? How do their
expected code lengths compare?
2. Binary Representations
Express the following numbers in binary.
(a) 4.2510
(b) 8.110
3. Shannon-Fano-Elias Coding
Let X be an ensemble with alphabet AX = {x1, x2, x3, x4} and probabilities pX = (0.25, 0.5, 0.125, 0.125).
(a) Compute the cumulative distribution function F (xi) for each symbol xi.
(b) Compute the symbol intervals [F (xi−1), F (xi)) for each symbolxi. (Recall thatwe assume for convenience
that F (x0) = 0.)
(c) Compute the modified cumulative distribution function F̄ (xi) for each symbol xi.
(d) Compute the Shannon-Fano-Elias codewords for each symbol xi.
(e) Decode the string 10001.
(f) Suppose you only use the first dlog 1
p(x)
e bits to code the above ensemble. Will the result be a prefix code?
4. Arithmetic Coding
(a) For the same ensemble as the previous section, compute an arithmetic code for the sequence c. Assume
here that d = 2, i.e. that the symbol d denotes the end of stream. Assume also that at each iteration, the
probability of the various outcomes is unchanged.
(b) Compute an arithmetic code for the sequence ca, with the same setup as the previous part. Does the
codeword for ca start with that for c?
(c) Compute an arithmetic code for the sequence ca using adaptive probabilities, assuming an initial set of
virtual counts m = (1, 1, 1) and a constant end-of-stream probability p(d) = 0.25.
1