Hamming codes

 

Definition:

A Hamming code of order r over Fq, denoted Hr(q), is an (n, k)-code where n =  and k = n−r, with a parity check matrix whose columns are nonzero and such that no two columns are scalar multiples of each other.

Facts:

1. A decoding algorithm for Hamming codes is shown in Algorithm 1.

2. In the binary case (q = 2), the Hamming code Hr(2) has a parity check matrix whose columns consist of all nonzero binary vectors of length r, each used exactly once.

3. Hr(q) has distance 3, and so is a 1-error correcting code.

4. Any two binary Hamming codes of order r are equivalent.

5. Hr(q) is a perfect code.

Example:

1. Consider H3(2), the binary Hamming code of order 3. The code has length n = 7

and dimension k = 4, and a parity check matrix is

         1 0 0 1 1 0 1

H =   0 1 0 1 0 1 1

         0 0 1 0 1 1 1

If the received word is r = 1011101, compute the syndrome s = 1011101 ・ HT = 001, which is the third column of H. Hence e = 0010000, and correct r to 1001101.

 

Algorithm 1: Decoding algorithm for Hamming codes.

H := a parity check matrix for a Hamming code Hr(q)

r := a received word

compute the syndrome s = rHT of r

if s = 0 then accept r as the transmitted word

else

compare sT with the columns of H

if sT = αhi (where hi is the ith column of H) and α Î Fq then

the error vector e is the vector with α in position i and 0s elsewhere

correct r to c = r − e