Skip to main content

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

Let X → Y be a binary symmetric channel of crossover p=1/4, and let X be uniform on {0,1}

Problem

Information Theory and Digital Communications practice problem

Let X→YX\to Y be a binary symmetric channel of crossover p=1/4p=1/4, and let XX be uniform on {0,1}\{0,1\}. The information density of a pair (x,y)(x,y) isi(x;y)=log⁡2P(Y=y∣X=x)P(Y=y).i(x;y)=\log_2\frac{\mathbb P(Y=y\mid X=x)}{\mathbb P(Y=y)}.Write i(X;Y)i(X;Y) for the random variable obtained by evaluating ii at the random pair (X,Y)(X,Y). Mutual information is the mean of this random variable.

1. Compute the two possible values of i(X;Y)i(X;Y) and the probabilities of
those two values. Identify which value occurs on the event {Y=X}\{Y=X\} and which occurs on {Y≠X}\{Y\ne X\}.

2. Compute the mean E[i(X;Y)]\mathbb E[i(X;Y)] and simplify it to
(3/4)log⁡23−1(3/4)\log_2 3-1. Confirm that the same number equals I(X;Y)=1−h2(1/4)I(X;Y)=1-h_2(1/4) by expanding h2(1/4)h_2(1/4).

3. Compute the variance of i(X;Y)i(X;Y). Use the two-point formula
Var=q(1−q)(a−b)2\mathrm{Var}=q(1-q)(a-b)^2 and simplify the gap a−ba-b.

4. Audit both sentences: (i) “information density is just mutual
information, so i(X;Y)i(X;Y) is the constant 1−h2(1/4)1-h_2(1/4) on every pair”; (ii) “the variance is the Bernoulli variance (3/4)(1/4)(3/4)(1/4) with no logarithmic gap, or else the mean is log⁡2(3/2)\log_2(3/2).”

Do not replace the BSC by a BEC, and do not compute a cascade crossover in place of the density.

Hint

Hint

Uniform input forces P(Y=y)=1/2P(Y=y)=1/2. The channel likelihoods are 3/43/4 and 1/41/4, so the two densities are log⁡2((3/4)/(1/2))\log_2((3/4)/(1/2)) and log⁡2((1/4)/(1/2))\log_2((1/4)/(1/2)).

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