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 .
Hamming codes in action
Let us examine the Hamming (7, 4) code, in which n=7 and k=4.We write a matrix
Writing out the multiplication, we end up with
- a=d_{0}+d_{1}+d_{3},
- b=d_{0}+d_{2}+d_{3}
- c=d_{1}+d_{2}+d_{3}
On decoding, assume one error has occurred in the received codeword r. (this Hamming code cannot detect when more than one error has occurred).
If no error has occurred, we have constructed the codeword to be sent so Hc=0 so we can check this. Say an error has occurred in the ith place, so
- r=c+e_{i}
Then
- Hr=Hc+He_{i}
- Hr=0+He_{i}=He_{i}
Source: from Federal Standard 1037C
See also: Hamming distance