Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 2 / 3H (Coding & Cryptography)

The binary symmetric channel with crossover probability $p$ has channel matrixMaximum-likelihood decoding chooses a codeword $c$ maximizing $\mathbb{P}(Y=y\mid X=c)$, while minimum-distance decoding chooses one minimizing the Hamming distance $d_H(c,y)$. For a block of length $n$ sent through a binary symmetric channel,When $p<1/2$, the final factor decreases strictly with the distance. Thus maximum-likelihood and minimum-distance decoding agree.

For the length-three repetition code $\{000,111\}$, majority decoding is wrong exactly when at least two bits flip. Therefore