700

Coded data made up of two states (or symbols) is called a binary code. Binary codes are the hidden language of computers. The Postnet code (short and long bars) and the Universal Product Code (UPC) bar code (white spaces and dark bars) explained in Chapter 16 are two examples of binary codes. Morse code (dots and dashes) and Braille (bumps and flat markings) are two more. The opinions of two critics rating movies with U for “thumbs up” and D for “thumbs down” could be conveyed by a binary code with the four messages UU, UD, DU, and DD. Fax machines, CDs, DVDs, high-definition television signals, smartphones, and space probes represent data as strings of 0s and 1s rather than the usual digits 0 through 9 and letters through . In this section, we illustrate one way binary codes can be devised so that errors in the transmission of the code can be corrected.

The idea behind error-correction schemes is simple and one you often use. To illustrate, suppose that you are reading the employment section of a newspaper and you see the phrase “must have a minimum of bive years’ experience.” Instantly you detect an error because bive is not a word in the English language. Moreover, you are fairly confident that the intended word is five. Why is that? Because five is a word derived from bive by changing a single letter, and it makes the phrase understandable. In other phrases, words such as bike or give might be sensible alternatives to bive. Using the extra information provided by the context, we often are able to infer the intended meaning when errors occur.

To demonstrate the way binary error-correcting schemes work, suppose that the National Aeronautics Space Administration (NASA) sends a spacecraft to land at 1 of 16 possible landing sites on Mars. The spacecraft orbits Mars while surveying the sites for the most favorable landing conditions. NASA officials have coded the 16 landing sites with four-digit strings of 0s and 1s such as 0000, 0001, 0010, and 0100. (Recall when counting that if each of events can occur in ways, then the total number of ways all events can occur is the product . In this case, there are strings.

Once the desired site has been selected, NASA informs the spacecraft where to land by sending the code for the site. However, signals sent through space are subject to interference called noise. The noise might cause the spacecraft to interpret the signal as 0001 when the signal actually sent was 1001. Fortunately, over the past 60 years, mathematicians, computer scientists, and engineers have devised highly sophisticated schemes to build extra information into messages composed of 0s and 1s that often permits the correct message to be inferred even though the message may have been received incorrectly (see Spotlight 17.1). The process of converting a message or other information into a code is called encoding.

The following example illustrates the basic ideas underlying binary error-correcting schemes.

Using the diagram, we have encoded our message 1001 as 1001101. Now suppose that this encoded message is received as 0001101 (an error in the first position). How would we know an error was made? We place each digit from the received message in its appropriate region, as in Figure 17.3.

Noting that there is an odd number of 1s in both circles and , we instantly realize that something is wrong because the intended message had an even number of 1s in each circle. How do we correct the error? The answer involve; parity. (Parity refers to the oddness or evenness of a number; even integers have even parity and odd integers have odd parity.) Because circles and have the wrong parity and does not, the error is located in the portion of the diagram ir circles and , but not in circle , that is, region I (shaded in Figure 17.4). Here we also see the advantage of using only 0s and 1s to encode data. If you have onh two possibilities and one of them is incorrect, then the other one must be correct Because the 0 in region I is incorrect, we know that 1 is correct.

701

702

Because the circle diagram method was designed to correct a received message with exactly one error, if a received message has two or more errors, the diagram method will never yield the correct message. For example, if the encoded message 0111001 is received as 1111011 (errors in positions 1 and 6), then only circle has an odd number of 1s (see Figure 17.7), so our decoding method assumes that there is an error in a region in circle but not in regions in circles and . Thus, our method incorrectly assumes that a single error occurred in region V (shaded in Figure 17.8).

The diagram technique can be used to encode all 16 possible binary messages of length 4, as shown in Table 17.1. The encoded messages are called code words. The three digits appended to each string of length 4 provide the “extra information” that is sufficient to infer the intended four-digit message, so long as the received seven-digit message has at most one error.

Because the diagram method can be used to encode only four-digit binary messages, it is not practical. We use it merely to illustrate a simple way to encode and decode messages. In the next section, we explain a method that can be used in more general settings.