|
|
|
|
|
|
|
Figure 6.8
ECC code distance. |
|
|
|
|
|
|
|
|
hypercube can be enlarged so that each valid data point is surrounded by associated invalid data points that are caused by a single-bit corruption in the message, the decoder will recognize that the invalid data point belongs to the valid point and be able to restore the message to its original intended form. This can be extended one more step by adding yet another invalid point between two valid data combinations (Figure 6.8). The minimum number of bits by which valid representations may differ is the code distance. This third point indicates that two errors have occurred. Hence, either of two valid code data points are equally likely and the message is detectably flawed but non-correctable. For a message of 64 bits, and for single-bit error correction, each of the 264 combinations must be surrounded by, or must accommodate, a failure of any of the 64 constituent bits (26 = 64). Thus, we need 264+6 total code combinations to be able to identify the invalid states associated with each valid state, or a total of 264+6+1 total data states. We can express this in another way: |
|
|
|
 |
|
|
|
|
2k³ m + k + 1, |
|
|
|
|
|
|
|
|
where m is the number of message bits and k is the number of correction bits that must be added to support single error correction. |
|
|
|
|
|
|
|
|
Hamming codes represent a realization of ECC based on hypercubes. Just as in the block code before, a pair of parity failures address the location of a flawed bit. The k correction bits determine the address of a flawed bit in a Hamming code. The message bits must be arranged to provide an orthogonal basis for the code (as in the case of the columns and rows of the block code). Further, the correction bits must be included in this basis. An orthogonal basis for 16 message bits is shown in Example 6.1, together with the setting of the five correction bits. Adding another bit, a sixth bit, allows us to compute parity on the entire m + k + 1 bit message. Now if we get an indication of a correctable error from the k correct bits, and no indication of parity failure from this new d bit, we know that there is a double error and that any attempt at correction may be incorrect and should not be attempted. These codes are commonly called SECDED (single error correction, double error detection). |
|
|
|
|
|
|
|
|
EXAMPLE 6.1 A HAMMING CODE EXAMPLE |
|
|
|
|
|
|
|
|
Suppose we have a 16-bit message, m = 16. |
|
|
|
|
|
|
|
|
2k³ 16 + k + 1; therefore, k = 5. |
|
|
|
|
|
