I am working on the following exercise:
Let $\mathcal{C} = (\mathcal{X}, P, \mathcal{Y})$ be the following channel:
$$\mathcal{X} = \{0,1,2,3\}$$
$$\mathcal{Y} = \{0,1,2,3,4,5,6,7\}$$
$$P = \begin{bmatrix}
0 &1/8 &1/8 &0 &1/4 &0 &1/2 &0 \\
0 &1/8 &0 &1/2 &1/4 &1/8 &0 &0 \\
0 &1/8 &1/4 &0 &0 &1/8 &0 &1/2 \\
1/2 &1/8 &1/8 &0 &0 &1/4 &0 &0 \\ \end{bmatrix}$$Compute the channel capacity.
I know that the channel capacity $Cap(\mathcal{C)}$ is defined as
$Cap(\mathcal{C}) := \max_{p(\cdot)} I(X;Y)$
, where $X$ and $Y$ are the input and output RVs. However, I do not see how to compute $\max_{p(\cdot)} I(X;Y)$ in this case since the outputs of this channel are overlapping, so I can not use that in
$$I(X;Y) = H(X)- H(X \mid Y)$$
$H(X \mid Y) = 0$, which until now always worked in the previous examples. Could you help me?
Best Answer
What you have is a weakly symmetric channel, i.e. (1) all rows are permutations of each other, and (2) all column sums are equal.
For weakly symmetric channels, channel capacity is achieved by a uniform distribution on the input alphabet. (See Theorem 7.2.1 in Cover and Thomas.)