The Hamming codes are an important class of single error correcting codes that can easily encode and decode. They were originally used in controlling errors in long-distance telephone calls. Binary Hamming codes have the following parameters:

1. Code length: $n=2^m-1$

2. Dimension: $k=2^m-m-1$

3. Minimum distance: $d=3$

The easiest way to describe a Hamming code is through its parity check matrix. For a binary Hamming code of length $n=2^m-1$, first construct an $m\times n$ matrix whose columns are all nonzero binary $m$-tuples. For example, for a $[7\text{,}4]$ binary Hamming code we take $m=3$, so $n=7$ and $k=4$, and start with

In order to obtain a parity check matrix for a code in systematic form, we move the appropriate columns to the end so that the matrix ends with the $m\times m$ identity matrix. The order of the other columns is irrelevant. The result is the parity check matrix $H$ for a Hamming $[n\text{,}k]$ code. In our example, we move the 4th, 2nd, and 1st columns to the end to obtain

which is the matrix $H$ from Exercise 3.

We can easily calculate a generator matrix $G$ from the parity check matrix $H$. Since Hamming codes are single error correcting codes, the syndrome method for decoding can be simplified. In particular, the error vector $e$ is allowed to have weight at most 1, and therefore will be zero or will have all zeros except for a single $1$ in the $j$th position.

The Hamming decoding algorithm, which corrects up to one bit error, is as follows:

1. Compute the syndrome $s=y{H}^T$ for the received vector $y$. If $s=0$, then there are no errors. Return the received vector and exit.

2. Otherwise, determine the position $j$ of the column of $H$ that is the transpose of the syndrome.

3. Change the $j$th bit in the received word, and output the resulting code.

As long as there is at most one bit error in the received vector, the result will be the codeword that was sent.