Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 11I (Coding and Cryptography)

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 isIf $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 case $p=1/2$ has identical rows and 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 identifiesFor the present channel,The output entropy is at most one bit, with equality for a uniform input. Hence the binary symmetric channel capacity isbits per channel use.

Let $X\in \{0,1\}$ denote whether $00$ or $11$ was sent, and writewhere $E_1,E_2$ are independent Bernoulli variables of parameter $p$. Because $X$ is uniform, $Y_1$ is uniform, while $H(Y_1\mid X)=h_2(p)$. Thus the mutual information in the first received digit is

By the chain rule for mutual information, the extra information in the second digit is $I(X;Y_2\mid Y_1)$. Conditional on $X$, the second channel error is independent of the first output, soMoreover,Given either value of $Y_1$, the second output therefore differs from it with probability $2p(1-p)$, andConsequently the incremental information in a twofold binary repetition code isbits.

Every row of the channel matrix is a permutation of $(1-2\alpha ,\alpha ,\alpha )$, and every column sum is one. It is therefore a weakly symmetric channel. The uniform input makes the output uniform, with entropy ${\log }_{2}3$, while the conditional output entropy is the entropy of one row:The weakly symmetric channel capacity formula now gives the ternary symmetric channel capacitybits per channel use, for $0\le \alpha \le 1/2$, with the convention $0{\log }_{2}0=0$.