Hamming code

In telecommunication, a Hamming code is an error-detecting and error-correcting code, used in data transmission, that can (a) detect all single- and double-bit errors and (b) correct all single-bit errors. It was named after its inventor: Richard Hamming.

Note: A Hamming code satisfies the relation 2^m ≥ n+1, where n is the total number of bits in the block, k is the number of information bits in the block, and m is the number of check bits in the block, where m = n- k .

The Hamming code is computed as follows:

• Write the data bits in positions whose binary representation has at least two 1 bits.
• Set the bits whose positions are powers of 2 so that the parity of odd-numbered bits is even, the parity of bits whose position is 2 or 3 mod 4 is even, and so on.

To decode it:

• Compute the parity of all odd-numbered bits, the parity of bits whose position is 2 or 3 mod 4, etc.
• Interpret these parities as a number which is a bit position. Flip the bit in that position.
• Read out the data bits.

E.g. To encode '01111101000' where the MSB is written first:

 0111110x100x0xxx
 011111011000001x (the x is bit 0 which is ignored)

Transmit it with an error:

 011101011000001

Compute parities:

 0111010110000010
 01110101          1
 0111    1000      0
 01  01  10  00    1
 0 1 0 0 1 0 0 1   1

Bit 11 (1011 in binary) is in error. Flip it:

 0111110110000010

Extract the data:

 0111110 100 0   

(Bit 0 was appended to the received data so that if there were no errors, we could flip it.)

Other variants of Hamming code are in use; they are rearrangements of the bits so that the parity bits are at the end.

Source: from Federal Standard 1037C