= Solution
The <Shannon second coding theorem> says that a memoryless channel permits transmission at any fixed <code rate> $R<C$ with error probability tending to zero as block length tends to infinity. Conversely, a sequence of codes with error probability tending to zero cannot have a limiting rate above $C$. The <channel capacity>, in bits per use, is
$$
\boxed{C=\sup_{P_X}I(X;Y).}
$$
For a finite <discrete memoryless channel> with transition probabilities $W(y\mid x)$, the supremum is a maximum and its <mutual information> is
$$
I(X;Y)=\sum_{x,y}P_X(x)W(y\mid x)
\log_2\frac{W(y\mid x)}{\sum_{x'}P_X(x')W(y\mid x')}.
$$
For a general memoryless channel, <mutual information> is the <relative entropy> of the joint input-output law with respect to the product of its marginal laws; the same supremum is taken over the admissible input laws.
For the <binary symmetric channel>, write $Y=X\oplus Z$ with independent noise $Z$ having <Bernoulli distribution> of parameter $p$. Given either input bit, the output <conditional entropy> is $h_2(p)$. Thus
$$
I(X;Y)=H(Y)-H(Y\mid X)=H(Y)-h_2(p)\leq1-h_2(p).
$$
An input with <uniform distribution> makes the output have <uniform distribution>, attaining $H(Y)=1$. The <binary symmetric channel capacity> is therefore
$$
\boxed{C_{\mathrm{BSC}}(p)=1-h_2(p)\ \text{bits per channel use}.}
$$
Back to article page
