Answer 8—Any single-error correcting Hamming code can be extended to reliably detect double bit errors by adding one more parity bit over the entire encoded word. This type of code is called a single-error correcting, double-error detecting (SECDED) code. It can always distinguish a double bit error from a single bit error, and it detects more types of multiple bit errors than a bare Hamming code does.

It works like this: All valid code words are (a minimum of) Hamming distance three apart. The Hamming distance between two words is defined as the number of bits in corresponding positions that are different. Any single-bit error is distance one from a valid word, and the correction algorithm converts the received word to the nearest valid one.

If a double error occurs, the parity of the word isn’t affected, but the correction algorithm still corrects the received word, which is distance two from the original valid word but distance one from some other valid (but wrong) word. It does this by flipping 1 bit, which may or may not be one of the erroneous bits. Now the word has either 1 or 3 bits flipped, and the parity checker detects the original double error.

Note that this works even when the parity bit itself is involved in a single-bit or double-bit error. It isn’t hard to work out all the combinations.

Contributor: David Tweed