Hamming code (original) (raw)

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.

We write a matrix

(note each column is a binary digit) and we create a codeword vector:

where a, b, and c are check digits, created by making the multiplication Hc=0.

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

and we send the codeword c with these values.

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 _i_th place, so

r=c+ei

where ei is a vector with a 1 in the _i_th place and zeroes otherwise.

Then

Hr=Hc+Hei

Now Hc=0, so

Hr=0+Hei=Hei

picking out the _i_th column of H, and thus since this column is a binary digit (say k), we can correct the error in the _k_th place of the received codeword.

Source: from Federal Standard 1037C