Library

Chapter 4 / 4.5 / 4.5.1

4.5.1 Hamming Distance And Minimum Distance

The error-control capability of a code depends on the number of bit positions in which two codewords differ, defined as the Hamming distance. It can be interpreted algebraically (as the number of differing bits in two binary strings) or geometrically (as the distance between points in an n-dimensional binary space).

The minimum distance, dmin, of a code is the smallest Hamming distance between any pair of valid codewords. For example, between codewords 0110 and 1111, dmin=2. A minimum distance greater than one is required for any degree of error control. The greater the distance between codewords (that is, the greater is dmin), the greater the number of errors that can be detected and possibly corrected.

To demonstrate, we can visualize each n-bit codeword as a vertex of an n-dimensional hypercube, as shown in Figure 4.5. In this first case, where n = k, so dmin=1, a single error can transform a valid codeword into another valid one—no error detection or correction is possible.

Figure 4.5. Codewords as a vector in n-dimensional space with dmin=1.

In Figure 4.6, n = k + 1, so dmin=2. Now, with a greater distance between codewords, any single-bit error (or any odd number of errors) produces an invalid codeword, allowing the decoder to detect that an error has occurred—but not to determine which bit was corrupted because a number of valid codewords could have suffered a single-bit corruption to transform into the received word. Thus, detection is possible, but not correction.

Figure 4.6. Codewords with a minimum distance of dmin=2.

In Figure 4.7, n = k + 2, so dmin=3. For a simple (3,1) code using codewords 000 and 111 (a triple-repetition code), a single-bit error moves the received word to a point that is one bit away from the correct codeword but two bits away from the other valid codeword. Since single-bit errors are most probable, the decoder can not only correctly identify the error but also correct it (that is, the additional redundancy allows it to identify which of the correct codewords has been corrupted). Double-bit errors can still be detected but not corrected.

Figure 4.7. Codewords with a minimum distance of dmin=3.

Extending this concept, Figure 4-8 shows a code with dmin=4, such as the (4,1) quadruple-repetition code using 0000 and 1111. Here, any single-bit error can be corrected, and double-bit or triple-bit errors can be detected—but not corrected.

Figure 4-8. Codewords with a minimum distance of dmin=4.

These simple examples are useful to illustrate the relationship between redundancy, minimum distance, and error-control capability. In general, for any code with a given minimum distance, dmin, with suitable coding it is possible to: