Skip to main content

Information Theory and Digital Communications · Discrete channels, mutual information, and capacity

Let X → Z → Y be the cascade of two independent binary symmetric channels: X → Z has…

Problem

Information Theory and Digital Communications practice problem

Let X→Z→YX\to Z\to Y be the cascade of two independent binary symmetric channels: X→ZX\to Z has crossover p1=1/10p_1=1/10 and Z→YZ\to Y has crossover p2=1/5p_2=1/5. The input XX is uniform on {0,1}\{0,1\}. Write h2h_2 for binary entropy. The data-processing inequality asserts I(X;Y)≤I(X;Z)I(X;Y)\le I(X;Z) and I(X;Y)≤I(Z;Y)I(X;Y)\le I(Z;Y) along this Markov chain.

1. Prove that the composition X→YX\to Y is itself a BSC, and compute its
crossoverpeq=p1(1−p2)+(1−p1)p2p_{\mathrm{eq}}=p_1(1-p_2)+(1-p_1)p_2as a reduced fraction.

2. Compute I(X;Y)I(X;Y) for the uniform input, in the form 1−h2(peq)1-h_2(p_{\mathrm{eq}}).
Also record I(X;Z)I(X;Z) and I(Z;Y)I(Z;Y) in the same shape.

3. Compare peqp_{\mathrm{eq}} with p1p_1 and p2p_2 on the interval
[0,1/2][0,1/2], and use the increase of h2h_2 on that interval to give a strict data-processing audit: I(X;Y)<I(Z;Y)<I(X;Z)I(X;Y)<I(Z;Y)<I(X;Z).

4. Audit both sentences: (i) “the cascade crossover is p1+p2=3/10p_1+p_2=3/10,
or else the product p1p2=1/50p_1 p_2=1/50”; (ii) “data processing is an equality, so I(X;Y)=I(X;Z)I(X;Y)=I(X;Z), or else the mutual informations add.”

Do not replace the cascade by a single BEC, and do not compute an information density in place of the equivalent crossover.

Hint

Hint

Y differs from X when exactly one of the two hops flips. That event has probability (1/10)(4/5)+(9/10)(1/5).

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Information Theory and Digital Communications sample problem: Try the free sample problem.

More Information Theory and Digital Communications practice problems