COMP2610/COMP6261
Tutorial 9 Sample Solutions
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. Solution in Tutorial 8.
2. (a) We have p(Y = a) = 0.5 · 0.25, p(Y = b) = 0.5 · 0.5, p(Y = c) = 0.5 · 0.75, and p(Y = d) = 0.5 · 0.5.
ThusH(Y ) = 1.9056. Similarly,H(Y | a) = H(Y | b) = H(Y | c) = H(0.5) = 1. So,H(Y | X) = 1.
Thus, I(X;Y ) = 0.9056 bits.
(b) We have
perr = p(y 6= a) · p(x = a) + p(y 6= b) · p(x = b) + p(y 6= c) · p(x = c)
= 0.5 · 0.25 + 0.5 · 0.25 + 0.5 · 0.5
= 0.5.
(c) We know that the capacity is the maximal mutual information. So, from (a), the capacity is at least 0.9056
bits. We know that we can transmit at rate below the capacity with arbitrarily small error probability. Thus,
Calvin’s claim is possible.
(d) We know that the capacity is at mostmin(log2 |X |, log2 |Y|) = 1.58. We know that we cannot transmit at
rate above C
1−H2(pb)
while achieving bit error pb. Here, the maximal block error is 0.01, which bounds the
average probability of error, and hence the bit error. Here 1−H2(0.1) = 0.9192, and so the maximal rate
is 1.58
0.9192
= 1.7189 bits per transmission. Thus, Hobbes’ claim is not possible.
3. Using I(X;Y ) = H(X)−H(X|Y ) it is easy to show that
I(X;Y ) = H2(p0)− qH2(p0)
since the first term is H(X) by definition of H2. The second term is H(X|Y ) because P (X = 0|Y = 1) = 0
and P (X = 1|Y = 0) = 0 and P (X = 0|Y =?) = p0 and P (X = 1|Y =?) = p1 and P (Y =?) = q. Using
H(X|Y ) =
∑
y H(X|Y = y)P (Y = y) = 0.P (Y = 0) + 0.P (Y = 1) +H2(p0).P (Y =?) gives the above
form for H(X|Y ).
When maximised over p0 the above gives
C = max
pX
I(X;Y ) = max
p0
H2(p0)− q ·H2(p0) = 1− q
since H2(p0) is maximised to 1 when p0 = 0.5.
The (2, 1) code required is {01, 10}. When 01 is passed through the Z-channel there is a probability of q that
the 1 is flipped and so 00 is output. Similarly, if 10 is input then there is a probability q that 00 is output. By
mapping 01 to 0; 10 to 1; and 00 to ? we see that this code simulates the erasure channel.
1
Because we can simulate the erasure channel with two uses of the Z-channel we can always convert any error-
correcting code for the erasure channel into an error-correcting code for a two-use Z-channel. Therefore, a code
with rate R on the erasure channel will have rate R/2 on the Z-channel.
Since the Noisy-Channel Coding Theorem says any rate up to the capacity C is achievable and we have shown
how to convert any rateR code for the erasure channel into aR/2 rate code for the Z-channel the capacity of the
Z-channel must be at least C/2. Thus, the capacity of the Z-channel with flip probability q is at least 1
2
(1− q).
The reason this is a bound and not an exact derivation of the capacity is that we have implicitly used the uniform
distribution (i.e., the one that maximises the erasure mutual information). This may not be the same distribution
that maximises the mutual information for the Z-channel.
2