Description
(1) A DMC has input alphabet X = {0, 1} and output alphabet Y = {0, 1, 2, 3}. Let X be
the channel input, and Y be the channel output. Suppose that
PY |X(0|0) = PY |X(1|1) =
where 0 ≤ ≤ 1.
(a) Determine (in terms of ) the channel transition matrix that maximizes H(Y |X).
(b) Using the transition matrix obtained in (a), find (in terms of ) the channel capacity.
(2) Problem 4.6.
(3) For each of the following discrete memoryless channels (DMCs) find the capacity (in bits)
and determine in each case the capacity achieving input distribution.
(a) DMC 1:
X1 = {a1, a2},Y1 = {b1, b2}, Q1 = [PY1|X1
]
with
Q1 =
1 0
β 1 − β
where 0 < β < 1.
(b) DMC 2:
X2 = {a3, a4, a5},Y1 = {b3, b4, b5}, Q2 = [PY2|X2
]
with
Q2 =
1 − γ (1 − γ)
(1 − γ) 1 − γ
γ (1 − γ) 1 −
where 0 < , γ < 1.
(c) DMC 3:
X3 = {a1, a2, a3, a4, a5},Y3 = {b1, b2, b3, b4, b5}, Q3 = [PY3|X3
]
with
PY3|X3
(b|a) =
PY1|X1
(b|a) if (a, b) ∈ X1 × Y1
PY2|X2
(b|a) if (a, b) ∈ X2 × Y2
0 otherwise
where PYi|Xi
, Xi
, Yi
, i = 1, 2, are defined in parts (a) and (b) above.
(4) Determine (with justification) whether each of the following statements is True or False:
(a) Let X and Y be the input and output, respectively, of a DMC (X ,Y, Q1 = [PY |X]).
Let Y be also fed to the input of another DMC (Y, Z, Q2 = [PZ|Y ]) resulting in
output Z. Assume that |X | = 8, |Y| = 4 and |Z| = 8. Then the capacity of the
channel with input X, output Z and transition matrix Q3 = Q1Q2 (i.e., the channel
formed by concatenating Q1 with Q2) satisfies
C = max
PX
I(X;Z) ≤ 2 (in bits).
(b) Let X1, X2, . . . , Xn be inputs to a DMC (X ,Y, PY |X), with finite input alphabet X
and finite output alphabet Y, and let Y1, Y2, . . . , Yn be the corresponding outputs.
Then it is possible to construct the channel’s transition distribution PY |X and an
input distribution PXn such that the inputs X1, X2, . . . , Xn are dependent while the
corresponding outputs Y1, Y2, . . . , Yn are independent.
(c) It is not possible to transmit a stationary binary Markov source {Ui}
∞
i=1 with
PUi|Ui−1
(0|0) = PUi|Ui−1
(1|1) = 0.9 via a rate-one block source-channel code over
the memoryless binary erasure channel (BEC) with erasure probability α = 0.5 and
losslessly recover it for sufficiently long coding blocklengths.
(5) Given a channel with finite input and output alphabets X and Y, respectively, and given
codebook C = {c1, . . . , cM} of size M and blocklength n with ci = (ci,1, . . . , ci,n) ∈
X
n
, if an n-tuple y
n ∈ Yn
is received at the channel output, then under maximum a
posteriori (MAP) decoding, y
n
is decoded into the codeword c
∗ ∈ C that maximizes
P(Xn = c|Y
n = y
n
) among all codewords c ∈ C. Assume that the channel input n-tuple
is governed by the following distribution
PXn (x
n
) =
Q(ci) if x
n ∈ C
0 if x
n 6∈ C
where Q(·) is an assigned distribution on the codewords in C (such that Q(ci) ≥ 0,
i = 1, . . . , M, and PM
i=1 Q(ci) = 1).
(a) Show that MAP decoding minimizes the probability of error.
(b) Assume that the channel is the memoryless binary symmetric channel (BSC) with
crossover probability ε = 0.1. Assume also that the used code is C = {c1, c2},
where the codewords are given by c1 = 00 and c2 = 11 with assigned probabilities
Q(c1) = p = 1 − Q(c2), where 0.1 ≤ p < 1/2.
(i) Determine the code’s MAP decoding rule and calculate its resulting probability
of error in terms of p.
(ii) Find the value of p ∈ [0.1, 1/2) that minimizes the probability of error and
calculate the resulting (minimal) probability of error.
(6) Answer the following problems.
(i) Consider a discrete memoryless channel with input alphabet
X = {0, 1, . . . , q, q + 1, q + 2, q + 3},
output alphabet
Y = {0, 1, . . . , q, q + 1, q + 2, q + 3, q + 4},
3
where q ≥ 2 is a fixed integer, and transition distribution PY |X given by
PY |X(y|x) =
1 − α if y = x and x ∈ {0, 1, . . . , q − 1}
α if y = q and x ∈ {0, 1, . . . , q − 1}
1 − if y = x + 1 and x ∈ {q, q + 1, q + 2, q + 3}
if y = q + 4 and x = q
if y = x and x ∈ {q + 1, q + 2, q + 3}
0 otherwise
where 0 ≤ α, ≤ 1.
(a) Find the capacity C of the channel (in bits) in terms of α, and q.
(b) Determine the values of α and that yield the largest possible value of C.
(c) We wish to transmit an arbitrary source {Ui}
∞
i=1 with memory via a rate-one
source-channel code over this channel with parameters α and obtained in
part (b). What is the largest possible size of the source alphabet U for which
the source can be reliably sent of the channel? Describe the rate-one sourcechannel code which can achieve such communication.
(ii) [MATH 874 only] Problem 4.8.
(7) Feedback Capacity.
(i) Problem 4.28, Part (a).
Hint: Since Cop,FB ≥ Cop, it suffices to show that Cop,FB ≤ Cop = maxPX
I(X; Y ) to
conclude that Cop,FB = Cop. In other words, show (invoking the data processing and
Fano inequalities) that for any achievable rate with feedback R,
R ≤ Cop = max
PX
I(X; Y ),
and hence Cop,FB = sup{R: R is achievable with feedback} ≤ Cop.
(ii) [MATH 874 only] Problem 4.28, Part (b).
4
