The binary Hamming $ [7,4,3]$ 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 $ F=\mathbb{F}_2$ and let $ C$ be the set of all vectors in the third column below (for simplicity, we write $ 0000000$ instead of $ (0,0,0,0,0,0,0)$, 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 $ 7$, dimension $ 4$, and minimum distance $ 3$. It is called the Hamming $ [7,4,3]$-code. In fact, there is a mapping from $ F^4$ to $ C$ given by $ \phi(x_1,x_2,x_3,x_4)={\bf y}$, where

\begin{displaymath} {\bf y}= \left( \begin{array}{c} y_1 \\ y_2 \\ y_3 \\ y_4... ... \\ x_2 \\ x_3 \\ x_4 \end{array}\right) \ ({\rm mod}\ 2). \end{displaymath}

A basis for $ C$ is given by the vectors $ \phi(1,0,0,0)=(1,0,0,0,1,1,1)$, $ \phi(0,1,0,0)=(0,1,0,0,0,1,1)$, $ \phi(0,0,1,0)=(0,0,1,0,1,0,1)$, $ \phi(0,0,0,1)=(0,0,0,1,1,1,0)$. Therefore, the matrix

\begin{displaymath} G= \left( \begin{array}{ccccccc} 1&0&0&0&1&1&1\\ 0&1&0&0&0&1&1\\ 0&0&1&0&1&0&1\\ 0&0&0&1&1&1&0 \end{array}\right) \end{displaymath}

is a generator matrix. The matrix

\begin{displaymath} E=\left( \begin{array}{cccc} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&1&0... ...&0&0&1 \\ 1&0&1&1 \\ 1&1&0&1 \\ 1&1&1&0 \end{array}\right) \end{displaymath}

is an encoding matrix.

\begin{figure}\begin{center} \begin{picture}(200,150) \put(50,100){\circle{150}}... ...(77,102){6} \put(37,102){5} \put(57,67){7} \end{picture}\end{center}\end{figure}

An algorithm for decoding the Hamming $ [7,4,3]$ code

Denote the received word by $ {\bf w}=(w_1,w_2,w_3,w_4,w_5,w_6,w_7)$.

  1. Put $ w_i$ in region $ i$ of the Venn diagram above, $ i=1,2,...,7$.
  2. Do parity checks on each of the circles $ A$, $ B$, and $ C$.

    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 $ (0,1,0,0,0,0,1)$ in the binary Hamming code using this algorithm.


David Joyner 2007-09-03