程序代写代做代考 information theory COMP2610/COMP6261 – Information Theory

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