Introduction to Cryptography with Coding Theory, 3rd Edition

24.5 Hamming Codes

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

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

In order to obtain a parity check matrix for a code in systematic form, we move the appropriate columns to the end ...