Hamming code

In telecommunication, a Hamming code is an error-detecting and error-correcting binary code, used in data transmission, that can (a) detect all single- and double-bit errors and (b) correct all single-bit errors.

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 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