= Solution
The <binary symmetric channel> with crossover probability $p$ has channel matrix
$$
\boxed{\begin{pmatrix}1-p&p\\p&1-p\end{pmatrix}.}
$$
<Maximum-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,
$$
\mathbb P(Y=y\mid X=c)
=p^{d_H(c,y)}(1-p)^{n-d_H(c,y)}
=(1-p)^n\left(\frac p{1-p}\right)^{d_H(c,y)}.
$$
When $p<1/2$, the final factor decreases strictly with the distance. Thus \b[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
$$
\boxed{\mathbb P(\text{error})
=\binom32p^2(1-p)+p^3
=3p^2-2p^3.}
$$
Back to article page
