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