0.13 Coding  (Page 21/22)

Consider again the majority rules code $\mathcal{C}$ with two elements $\{000,111\}$ . This code has $d_{min}=3$ and can be used as follows:

1. $t=1$ , $s=0$ . In this mode, using decoding sets [link] , code words could suffer any single error and still be correctly decoded.But if two errors occurred, the message would be incorrect.
2. $t=0$ , $s=2$ . In this mode, using decoding sets [link] , the code word could suffer up to two errors and the error would be detected, but there would beno way to correct it with certainty.

Consider the code $\mathcal{C}$ with two elements $\{0000000,1111111\}$ . Then, $d_{min}=7$ . This code can be used in the following ways:

1. $t=3$ , $s=0$ . In this mode, the code word could suffer up to three errors and still be correctly decoded.But if four errors occurred, the message would be incorrect.
2. $t=2$ , $s=2$ . In this mode, if the codeword suffered up to two errors, then it would be correctly decoded. If there were three or fourerrors, then the errors are detected, but because they cannot be corrected with certainty, no (incorrect) message isgenerated.

Thus, the minimum distance of a code is a resource that can be allocated between error detection and error correction.How to trade these off is a system design issue. In some cases, the receiver can ask for a symbol to be retransmitted when an erroroccurs (for instance, in a computer modem or when reading a file from disk), and it may be sensible to allocate $d_{min}$ to detecting errors.In other cases (such as broadcast), it is more common to focus on error correction.

The discussion in this section so far is completely general; that is, the definition and results on minimum distance apply to any codeof any size, whether linear or nonlinear. There are two problems with large nonlinear codes:

• It is hard to specify codes with large $d_{min}$ .
• Implementing coding and decoding can be expensive in terms of memory and computational power.

To emphasize this, consider a code that combines binary digits into clusters of 56 and codes these clusters using 64 bits. Such a code requiresabout ${10}^{101}$ code words. Considering that the estimated number of elementary particles in the universe is about ${10}^{80}$ , this is a problem. When the code is linear, however, it is notnecessary to store all the code words; they can be generated as needed. This was noted in the discussion of the $(5,2)$ code of the previous section. Moreover, finding the minimum distance of a linear codeis also easy, since $d_{min}$ is equal to the smallest number of nonzero coordinates in any code word (notcounting the zero code word). Thus $d_{min}$ can be calculated directly from the definition by finding the distances between allthe code words, or by finding the code word that has the smallest number of 1's. For instance, in the $(5,2)$ code, the two elements 01011 and 10101 each have exactly three nonzero terms.

Some more codes

This section gives two examples of $(n,k)$ linear codes. If the generator matrix $G$ has the form