= Solution
A <binary symmetric channel> independently flips each input bit with probability $p$, so, with rows indexed by the input and columns by the output, its channel matrix is
$$
\boxed{
\begin{pmatrix}
1-p&p\\
p&1-p
\end{pmatrix}}
.
$$
If $p>1/2$, complementing every received bit converts the channel into one with crossover probability $1-p<1/2$ without changing its information-carrying ability. The <completely noisy binary symmetric channel>[case $p=1/2$] has identical rows and <binary symmetric channel capacity>[capacity] zero, so it suffices to study $p<1/2$.
The <Shannon second coding theorem> states that for every rate below the <channel capacity> there are arbitrarily long codes whose decoding error tends to zero, whereas no sequence of codes with rate above capacity can have vanishing error. It also identifies
$$
C=\max_{P_X}I(X;Y).
$$
For the present channel,
$$
I(X;Y)=H(Y)-H(Y\mid X)=H(Y)-h_2(p).
$$
The output entropy is at most one bit, with equality for a uniform input. Hence the <binary symmetric channel capacity> is
$$
\boxed{C=1-h_2(p)}
$$
bits per channel use.
Back to article page
