COMP2610/COMP6261 – Information Theory
Tutorial 9: Stream and Noisy Channel Coding
Young Lee and Bob Williamson
Tutors: Debashish Chakraborty and Zakaria Mhammedi
Week 11 (16th – 20th Oct), Semester 2, 2017
1. Complete arithmetic coding (Question 4, Tutorial 8) from previous tutorial if you have not completed.
2. Consider a channel with inputs X = {a, b, c}, outputs Y = {a, b, c, d}, and transition matrix
Q =
0.5 0 0
0.5 0.5 0
0 0.5 0.5
0 0 0.5
.
(a) Assuming pX = (0.25, 0.25, 0.5), what is the mutual information I(X;Y ) between the input and output
of the channel?
(b) Assuming pX = (0.25, 0.25, 0.5), what is the average probability of error of the channel?
(c) Calvin claims that he has constructed a block code for Q with rate 0.01 bits per transmission and maximal
block error probability 1%. Is his claim possible? Justify your answer.
(d) Hobbes claims that he has constructed a block code forQ with rate 100 bits per transmission and maximal
block error probability 1%. Is his claim possible? Justify your answer.
3. Noisy Coding (Exercise 10.12 in MacKay)
(a) A binary erasure channel with input x ∈ {0, 1} and output y ∈ {0, ?, 1} has transition matrix
QE =
1− q 0q q
0 1− q
.
Find the mutual information I(X;Y ) between the input and output for a general distribution pX = (p0, p1)
over inputs. Show that the capacity of this channel is CE = 1− q bits.
(b) A Z-channel has transition probability matrix
QZ =
[
1 q
0 1− q
]
.
Show that, using a (2, 1) code, that two uses of a Z-channel can be made to emulate one use of an erasure
channel, and state the erasure probability of that erasure channel. Hence show the capacity of theZ-channel
CZ ≥ 12 (1− q) =
1
2
CE bits.
Explain why this result is an inequality rather than an equality.
1