Understanding Errors

To understand errors, consider the following:

1. Messages (frames) consist of m data (message) bits and r redundancy bits, yielding an n = (m+r)-bit codeword.
2. Hamming Distance. Given any two codewords, we can determine how many of the bits differ. Simply exclusive or (XOR) the two words, and count the number of 1 bits in the result.
3. Significance? If two codewords are d bits apart, d errors are required to convert one to the other.
4. A code's Hamming Distance is defined as the minimum Hamming Distance between any two of its legal codewords (from all possible codewords).
5. In general, all possible data words are legal. However, by choosing check bits carefully, the resulting codewords will have a large Hamming Distance. The larger the Hamming distance, the better able the code can detect errors.

To detect d 1-bit errors requires having a Hamming Distance of at least d+1 bits. Why?

To correct d errors requires 2d+1 bits. Intuitively, after d errors, the garbled messages is still closer to the original message than any other legal codeword.