Question

Suppose only three messages are needed (for instance, "go," "slow down," "stop"). Find the smallest possible $\mathbf{n}$so that these messages may be transmitted in an $\left(n,k\right)$code that corrects single errors.

Short answer

The smallest possible n is 3, to transmit messages in an $\left(\mathrm{n},\mathrm{k}\right)$code that corrects single errors.

Step-by-step solution

Theorem 16.6 and Corollary 16.4

• Theorem 16.6

If Gis a $\mathbf{k}\mathbf{\times }\mathbf{n}$standard generator matrix, then $\left\{\mathrm{uG}|u\in B\left(k\right)\right\}$is a systematic$\left(n,k\right)$code

• Corollary 16.4

A linear code detects 2terrors and corrects terrors if and only if the Hamming weight of every nonzero codeword is at least 2t+1.

Finding the smallest possible n 

Since we need only three message words, so we need to code only three words so we can use message words from ${\mathrm{\mathbb{Z}}}_3$.

And we can code word according to this

$$\begin{gathered} \mathrm{stop}\to 0 \\ \mathrm{shut}\mathrm{down}\to 1 \\ \mathrm{go}\to 2 \end{gathered}$$

Since the code corrects a single digit, according to corollary 16.4 the humming weight must be $2\times 1+1=3$

Therefore, the smallest n possible must be at least 3

Therefore, the generator matrix is

data-custom-editor="chemistry" $\mathrm{G}=\left(\begin{array}{ccc}1& 1& 1\end{array}\right)$

To get the code words we must multiply them with the generator

$$\begin{gathered} \left(0\right)\left(\begin{array}{ccc}1& 1& 1\end{array}\right)=\left(\begin{array}{ccc}0& 0& 0\end{array}\right) \\ \left(1\right)\left(\begin{array}{ccc}1& 1& 1\end{array}\right)=\left(\begin{array}{ccc}1& 1& 1\end{array}\right) \\ \left(2\right)\left(\begin{array}{ccc}1& 1& 1\end{array}\right)=\left(\begin{array}{ccc}2& 2& 2\end{array}\right) \end{gathered}$$

Hence, we can see from the above that every nonzero element has a humming weight of at least 3. Hence the smallest possible n is 3, so these messages may be transmitted in an $\left(\mathrm{n},\mathrm{k}\right)$code that corrects single errors.