Solution

The inhabitants of planet Quatro wish to beam a message to Earth. The alphabet used on Quatro has four letters: A, B, C, and D, which the people of Quatro have encoded as $00000$, $10110$, $01011$, and $11101$, respectively. What is the maximum number of single digit errors that this encoding scheme can correct in the transmission of any one letter?



For the sake of reference, let us denote the codewords by

$$\begin{array}{rcl} c_A &=& 00000\\ c_B &=& 10110\\ c_C &=& 01011\\ c_D &=& 11101 \end{array}$$

If we let $d(c_i,c_j)$ be the Hamming distance between codewords $c_i$ and $c_j$, then we find all of the following by inspection:

$$\begin{array}{rcl} d(c_A,c_B) &=& 3\\ d(c_A,c_C) &=& 3\\ d(c_A,c_D) &=& 4\\ d(c_B,c_C) &=& 4\\ d(c_B,c_D) &=& 3\\ d(c_C,c_D) &=& 3 \end{array}$$

Since the minimum distance between any two codewords is $3$, the maximum number of errors that can be corrected in the transmission of any one letter is given by

$$\left\lfloor \frac{3-1}{2} \right\rfloor = 1$$