Error-Detecting Codes We shall now begin an extended example of “error-detecting codes,” a concept that is interesting in its own right and also leads to an interesting inductive proof. When we transmit information over a data network, we code characters (letters, digits, punctuation, and so on) into strings of bits, that is, 0’s and 1’s. For the moment let us assume that characters are represented by seven bits. However, it is normal to transmit more than seven bits per character, and an eighth bit can be used to help detect some simple errors in transmission. That is, occasionally, one of the 0’s or 1’s gets changed because of noise during transmission, and is received as the opposite bit; a 0 entering the transmission line emerges as a 1, or vice versa.

It is useful if the communication system can tell when one of the eight bits has been changed, so that it can signal for a retransmission. To detect changes in a single bit, we must be sure that no two characters are represented by sequences of bits that differ in only one position. For then, if that position were changed, the result would be the code for the other character, and we could not detect that an error had occurred. For example, if the code for one character is the sequence of bits 01010101, and the code for another is 01000101, then a change in the fourth position from the left turns the former into the latter.

One way to be sure that no characters have codes that differ in only one position Parity bit is to precede the conventional 7-bit code for the character by a parity bit. If the total number of 1’s in a group of bits is odd, the group is said to have odd parity. If the number of 1’s in the group is even, then the group has even parity. The coding scheme we select is to represent each character by an 8-bit code with even parity; we could as well have chosen to use only the codes with odd parity. We force the parity to be even by selecting the parity bit judiciously.