The binary Hamming $[7,4,3]$ code

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

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

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

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

is a generating matrix.

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