## The binary Hamming code

This section provides a good detailed example of the above ideas. It is also historically one of the first error-correcting codes developed. Hamming deveoped the idea in the late 1940's. Hamming, who worked for many years as a mathematician for the telephone company, thought that computers should be able to correct bit errors. We was right and discovered a family of 1-error correcting codes, now called Hamming codes''. We shall focus only on one of them in this section and define the more general codes later.

Let and let be the set of all vectors in the third column below (for simplicity, we write instead of , for example).

 decimal binary hamming (7,4) 0 0000 0000000 1 0001 0001110 2 0010 0010101 3 0011 0011011 4 0100 0100011 5 0101 0101101 6 0110 0110110 7 0111 0111000 8 1000 1000111 9 1001 1001001 10 1010 1010010 11 1011 1011100 12 1100 1100100 13 1101 1101010 14 1110 1110001 15 1111 1111111

This is a linear code of length , dimension , and minimum distance . It is called the Hamming -code. In fact, there is a mapping from to given by , where

A basis for is given by the vectors , , , . Therefore, the matrix

is a generator matrix. The matrix

is an encoding matrix.

An algorithm for decoding the Hamming code

Denote the received word by .

1. Put in region of the Venn diagram above, .
2. Do parity checks on each of the circles , , and .

 parity failure region(s) error position none none A, B, and C 1 B and C 2 A and C 3 A and B 4 A 5 B 6 C 7

Exercise 3.4.14   Decode in the binary Hamming code using this algorithm.

David Joyner 2007-09-03