17.3 17.2 Encoding with Parity-Check Sums
Strings of 0s and 1s with extra digits for error correction can be used to send full-text messages. A simple way to do this is to assign an empty space the string 00000, the letter the string 00001, the string 00010, the string 00100, and so on. Because there are 32 possible binary strings of length 5, the five unassigned strings can be used for special purposes, such as indicating uppercase letters or numerals.
For example, we might use the string 11111 to indicate a “shift” from lowercase to uppercase when it precedes the code for a letter (i.e., 1111100010 represents ). This is analogous to the shift key on a keyboard. Similarly, we could use 11110 to indicate a “shift” from letters to numerals. Here, 11110 followed by the code for represents the numeral 0, 11110 followed by the code for represents the numeral 1, and so on up to 9. Punctuation marks could be handled in the same fashion. Rather than using the circle diagram method, messages are encoded by appending extra digits determined by the parity of various sums of certain portions of the messages. We illustrate this method for the 16 messages shown in the left-hand column of Table 17.1. (See also Spotlight 17.2.)
703
Neil Sloane Spotlight 17.2
Neil Sloane is one of the world’s leading researchers on the subject of sphere packing, a field that has become indispensable to modern communications. Without it, we might not have CDs, DVDs, or satellite photos of Neptune.
To exchange information rapidly and correctly, machines must code it. For example, imagine you want to transmit a child’s drawing that uses every one of the 64 Crayola colors. For transmission, you could code each of those colors as a number—say, the integers from 1 to 64. Then you could divide the image into many pixels and assign 6-digit strings of 0s and 1s to each one, based on the color it contains. The transmission would then be a steady stream of those numbers, one for each pixel.
Because there are 64 possible combinations of 0s and 1s in a 6-digit string, you could handle the entire Crayola palette with 64 different 6-digit “code words.” For instance, 000000 could represent the first color, 000001 the next color, 000010 the next, and so on.
But in a noisy signal, two different code words might look nearly identical. A bit of noise, for example, might shift a spike of current to the wrong place, so that 001000 looks like 000100. An efficient way to keep the colors straight in spite of noise is to add four extra digits to the 6-digit code words. The receiver, programmed to know the 64 permissible combinations, now could spot any other combination as an error introduced by noise; then it would correct the error automatically to the “nearest” permissible color.
In fact, says Sloane, “If any of those 10 digits were wrong, you could still figure out what the right crayon was. ”
Source: Information from the article “Math in a Million Dimensions” by David Berreby, Discover, October 1990.
Our goal is to take any binary string and append three check digits so that any single error in any of the seven positions can be corrected. We do this as follows. Choose
The sums , and are called parity-check sums. They are so named because their function is to guarantee that the sum of various components of the encoded message is even. Indeed, is defined so that is even. (Recall that this is precisely how the value in region V in Figure 17.2 was defined.) Similarly, is defined so that is even, and is defined so that is even.
704
EXAMPLE 3 Encoding and Decoding a Message
Let’s revisit the message 1001 that we considered in Figure 17.1. Then, and
So, because , we have .
How is the intended message determined from a received encoded message? This process is called decoding. Say, for instance, that the message 1000, which has been encoded using parity-check sums as , is received as (an error in the third position). We simply compare with each of the 16 code words (that is, the possible correct messages) in Table 17.1 and decode it as the one that differs from in the fewest positions. (Put another way, we decode as the code word that agrees with in the most positions.) This method works even if the error in the message is one of the check digits rather than one of the digits of the original message string. When there is more than one code word that differs from in the fewest positions, we do not decode.
To carry out these comparisons, it is convenient to define the distance between two strings of equal length.
Distance Between Two Strings DEFINITION
The distance between two strings of equal length is the number of positions in which the strings differ.
For example, the distance between and is 1 because they differ in only one position (the third). In contrast, the distance between 1000110 and 0111001 is 7 because they differ in all seven positions. Thus, our decoding procedure is simply to decode any received message as the code word that is “nearest” to it. More specifically, for any received word , we determine the distance between and all code words and decode as the one for which the distance is a minimum. Table 17.2 shows the distance between and all 16 code words. From this table, we see that will be decoded as because it differs from in only one position, whereas it differs from all others in the table in at least two positions. This method is called nearest-neighbor decoding.
| 1010110 | 1010110 | 1010110 | 1010110 | 1010110 | 1010110 | 1010110 | 1010110 | |
| Code word | 0000000 | 0001011 | 0010111 | 0100101 | 1000110 | 1100011 | 1010001 | 1001101 |
| Distance | 4 | 5 | 2 | 5 | 1 | 4 | 3 | 4 |
| 1010110 | 1010110 | 1010110 | 1010110 | 1010110 | 1010110 | 1010110 | 1010110 | |
| Code word | 0110010 | 0101110 | 0011100 | 1110100 | 1101000 | 1011010 | 0111001 | 1111111 |
| Distance | 3 | 4 | 3 | 2 | 5 | 2 | 6 | 3 |
705
Assuming that errors occur independently, the nearest-neighbor method decodes each received message as the one it most likely represents.
Nearest-Neighbor Decoding DEFINITION
The nearest-neighbor decoding method decodes a received message as the code word that agrees with the message in the most positions, provided that there is only one such code word.
Self Check 2
Find the distance between 10010111 and 11011110.
- 3
The scheme we have just described was first proposed in 1948 by Richard Hamming, a mathematician at Bell Laboratories. It is one of a family of codes that are called the Hamming codes. The collection of all possible strings obtained from messages of a given length of 0s and 1s by appending extra 0s and 1s using parity-check sums, as illustrated earlier, is called a binary linear code. The strings with the appended digits are called code words.
Binary Linear Code/Code Words DEFINITION
A binary linear code is a set of words composed of 0s and 1s obtained from all possible messages of a given length by using parity-check sums to append check digits to the messages. The resulting strings are called code words.
You should think of a binary linear code as a set of -digit strings in which each string is composed of two parts: the message part, consisting of the original messages, and the remaining check-digit part.
The longer the messages are, the more check digits are required to correct errors. For example, binary messages consisting of six digits require four check digits to ensure that all messages with one error can be decoded correctly.
Given a binary linear code, how can we tell whether it will correct errors and how many errors it will detect? It is remarkably easy. We examine all the code words to find one that has the fewest number of 1s, excluding the zero code word consisting entirely of 0s. Call this minimum number of 1s in any nonzero code word the weight of the code.
Weight of a Binary Code DEFINITION
The weight of a binary code is the minimum number of 1s that occur among all nonzero code words of that code.
706
The test for the error-detecting and error-correcting capacities of a code is as follows.
Test for Error Detection and Correction Capacity PROCEDURE
- Calculate the weight of the code.
- The code will detect any or fewer errors.
- If is odd, the code will correct any or fewer errors.
- If is even, the code will correct any or fewer errors.
EXAMPLE 4 Error Detection and Correction Capacity
The binary code
has weight 1. It will not detect any error.
The binary code
has weight 2. It will detect any error but will not correct every 1 error.
The binary code
has weight 3. It will detect any or fewer errors or correct any error.
The binary code
has weight 4. It will detect any or fewer errors or correct any error.
Applying this test to the code in Table 17.1, we see that the weight is 3, so it will correct any error or it will detect any or fewer errors. Be careful here. We must decide in advance whether we want to use our code to correct single errors or to detect any two or fewer errors. It can do whichever we choose, but not both. If we decide to detect errors, then we will not decode any message that was not on our original list of encoded messages (just as bive is not a word in the English language). Instead, we simply note that an error was made and, in most applications, request a retransmission. An example occurs when a bar-code reader at the supermarket detects an error and therefore does not emit a sound (in effect, requesting a rescanning). On the other hand, if we decide to correct errors, we will decode any received message as its nearest neighbor.
Here is an example of another binary linear code.
EXAMPLE 5 A Binary Linear Code
We let the set of messages be {000, 001, 010, 100, 110, 101, 011, 111} and append three check digits , and using
707
For instance, if we take as 101, we have
So we encode 101 by appending 001, that is, . The entire code is shown in Table 17.3.
| Message | → | Code Word | Message | → | Code Word |
|---|---|---|---|---|---|
| 000 | → | 000000 | 110 | → | 110011 |
| 001 | → | 001111 | 101 | → | 101001 |
| 010 | → | 010101 | 011 | → | 011010 |
| 100 | → | 100110 | 111 | → | 111100 |
Because the minimum number of 1s of any nonzero code word is three, this code will either correct any single error or detect any two errors, whichever we choose.
It is natural to ask how the method of appending extra digits with parity-check sums enables us to detect or even correct errors. Error detection is obvious. Think of how a computer spell-checker works. If you type bive instead of five, the spell- checker detects the error because the string bive is not on its list of valid words. On the other hand, if you type give instead of five, the spell-checker will not detect the error because give is on its list of valid words.
Our error-detection scheme works the same way, except that if we add extra digits to ensure that our code words differ in many positions—say, positions—then even as many as mistakes will not convert one code word into another code word. And if every pair of code words differs from each other in at least three positions, we can correct any single error because the incorrect received word will differ from the correct code word in exactly one position, but it will differ from all others in two or more positions.
Thus, in this case, the correct word is the unique “nearest neighbor.” So the role of the parity-check sums is to ensure that code words differ in many positions. For example, consider the code in Table 17.1. The messages 1000 and 1100 differ in only the second position. But the two parity-check sums and guarantee that encoded words for these messages have different values in positions 5 and 7 as well as in position 2. It is the job of mathematicians to discover the appropriate parity-check sums to correct several errors in long codes.