##

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 .

- Put in region of the Venn diagram above, .
- 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