Logo der Uni Stuttgart
Hamming Codes

A (k,n) Hamming code is a linear block code that is characterized by the parameter $\tau$ which is always greater than or equal 2 such that:

The number of parity check bits (redundancy) = $\tau$, the codeword length n = $2^{\tau}-1$, the number of information bits k = $2^{\tau}-1-\tau$, the minimum distance $d_{min}=3$, the maximum number of detectable errors = $d_{min}-1=2$ errors, the maximum number of correctable errors over the BEC = $d_{min}-1=2$ errors and the maximum number of correctable errors over the general channel = $\left\lfloor \frac{d_{min}-1}{2}\right\rfloor =1$ error.

For a given block length n and minimum distance $d_{min}=3$, the hamming codes can achieve the highest possible rates. So they are perfect codes.

The parity check matrix H of the hamming code is of size (n-k $\times$ n). Its columns consist of the binary representation of the $2^{\tau}-1$ nonzero digit numbers in arbitrary order and $\tau$ bits per each digit number. The parity check matrices H of the (7,4) hamming code (when $\tau=3$) and the (15,11) hamming code (when $\tau=4$) are shown below:

$$H_{(7,4)}=\begin{pmatrix} 1& 0 &1 &1 &1 &0 &0 \\ 1& 1 & 1 & 0 &0 &1 &0 \\ 0& 1 & 1 & 1 & 0 &0 &1 \end{pmatrix}$$ $$H_{(15,11)}=\begin{pmatrix} 0& 0 & 0 &0 & 0 & 0 &0 &1 &1 & 1 & 1 & 1 & 1 & 1 &1 \\ 0& 0 & 0 &1 &1 & 1 & 1 &0 &0 &0 &0 &1 &1 &1 &1 \\ 0& 1 & 1 &0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1 \\ 1& 0 & 1 & 0 & 1 & 0 & 1 &0 &1 &0 &1 &0 &1 &0 &1 \end{pmatrix}$$