12.3. Error Detecting and Correcting Codes

In the 1956 short story titled “Minority Report,” by Philip K. Dick (made into a film in 2002 of the same title), specialized humans detect crimes before they happen. There are three of them and typically all three agree about the crime that will be committed, the suspect is apprehended prior to the crime, and all is well. But in some cases, one of them visualizes a future that is different from the one the others envision. In such a case, an “error” has been detected.

Imagine that we have a code that consists of the following code words (00, 01, 10, 11). This code is zero error detecting because changing even one character turns each word into another valid code word. Now, let’s repeat every code word. Now our code words are (0000, 0101, 1010, and 1111). Now we have to change at least two characters to reach another valid code word. Our code is one error detecting. However, if we receive the message 0001 we have no way of knowing if the intended message was 0000 or 0101. Can we find a way to correct as well as detect errors? Here’s where the “Minority Report” comes in.

In this code, each two-digit message is repeated twice (000000, 010101, 101010, 111111). Think of each two-digit substring as the report of a different prophetic human. The Hamming distance is three, so the code is 2 error detecting. Thus, if one receives the message 101000, it is most likely that the message that was intended was 101010. The drawback of this method is that it is very expensive in terms of the length of a message. We are transmitting six digits but only two of those digits carry information. The other four are “check and correct” digits. There must be a way to detect codes without simply repeating messages.