Encyclopedia > Hamming code

  Article Content

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 2mn+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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Haskell Curry

... a doctorate from Göttingen in 1930. He taught at Harvard, Princeton, and then beginning at 1929 for 35 years at Pennsylvania State University. In 1966 he becam ...