Answer 5—Hamming codes are relatively easy to construct because they’re based on parity logic. Each check bit is a parity bit for a particular subset of the data bits, and they’re arranged so that the pattern of parity errors directly indicates the position of the bit error.

It takes 3 check bits to protect 4 data bits (the reason for this will become apparent shortly), giving a total of 7 bits in the encoded word. If you number the bit positions of an 8-bit word in binary, you’ll see that there is one position that has no 1s in its column, three positions that have a single 1 each, and four positions that have two or more 1s.

If the 4 data bits are called A, B, C, and D and the 3 check bits are X, Y, and Z, you’ll place them in the columns such that the check bits are in the columns with one 1 and the data bits are in the columns with more than one 1. The bit in position 0 isn’t used. 

The check bit X is set or cleared so that all of the bits with a 1 in the top row (A, B, C, and X) have even parity. Similarly, the check bit Y is the parity bit for all of the bits with a 1 in the second row (A, B, and D). The check bit Z is the parity bit for all of the bits with a 1 in the third row (A, C, and D).

Now all seven bits (the codeword) are transmitted (or stored), usually reordered so that the data bits appear in their original sequence: A B C D X Y Z. When they’re received (or retrieved) later, the data bits are put through the same encoding process as before, producing three new check bits X¢, Y¢, and Z¢. If the new check bits are XORed with the received check bits, an interesting thing occurs. If there’s no error in the received bits, the result of the XOR is all zeros. But if there’s a single bit error in any of the 7 received bits, the result of the XOR is a nonzero 3-bit number called the “syndrome” that directly indicates the position of the bit error as defined in the table. If the bit in this position is flipped, then the original 7-bit codeword is perfectly reconstructed.

A couple of examples will illustrate this. Let’s assume that the data bits are all zero, which also means that all of the check bits are zero. If bit B is set in the received word, then the recomputed check bits X¢Y¢Z¢ (and the syndrome) will be 110, which is the bit position for B. If bit Y is set in the received word, then the recomputed check bits will be 000 and the syndrome will be 010, which is the bit position for Y.

Hamming codes get more efficient with larger codewords. Basically, you need enough check bits to enumerate all of the data bits plus the check bits plus one. Therefore, 4 check bits can protect up to 11 data bits, 5 check bits can protect up to 26 data bits, and so on. Eventually, you get to the point where if you have 8 bytes of data (64 bits) with a parity bit on each byte, you have enough parity bits to do ECC on the 64 bits of data instead.

Contributor: David Tweed