Hamming codes

Standard

Hamming codes are a family of error correction (1 bit) and error detection (2 bits) linear codes. The minimum distance (ie Hamming distance) between codewords in a Hamming code is 3.

For each integer i \geq 2 there is a binary code of block length: vectors

n = 2^i - 1

and a message length:

k = n - i

giving a coding rate:

\frac{k}{n} = \frac{n - i}{n} = 1 - \frac{i}{n}

Hamming codes have parity checking matrices the columns of which consist of all the non-zero vectors of length i .

Hence for a (7, 4) Hamming code the parity check matrix would be:

H = \left( {\begin{array} {rrrrrrr} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array} } \right)

Which, (if I have done this correctly!), can give us a generator matrix:

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

The first three columns form an identity matrix, allowing us to use the first three bits of the received code as the original message.

(One interesting point to note is that we can run this process in reverse to compress data in a lossy form – eg we could compress 7 bits into three bits using this Hamming code, provided we were willing to tolerate the errors/losses.)