Hamming code (idea)

The set of Hamming codes are called 'Forward Error Correction' and give the ability for the receiving station to correct a transmission error. While this takes more bits to send the information, it means fewer retransmits and thus can actually speed up a noisy connection.

The number of parity bits in the hamming code is given by the Hamming rule. This is a function of the number of bits of information transmitted in a block and is represented by the following inequality:
d + p + 1>= 2^p
'd' is the number of data bits and 'p' is the number of parity bits. Hamming codes are identified by the ordered set (c,d) where 'c' = 'd' + 'p'. The Hamming code (7,4) is the classic example used which describes a word of 4 data bits long and 3 error check bits. This satisfies the above inequality:
4 + 3 + 1 >= 2³

The hamming code word is created by multiplying the data bits by a generator matrix using modulo-2 arithmetic. The result of this is called a code word vector which consists of the original data bits and the parity bits.

The generator matrix used in constructing the hamming code consists of I (the identity matrix) and a parity generation matrix A. For a data size of 4 the following matrix is created:

         I        A
      1 0 0 0 | 1 1 1
      0 1 0 0 | 0 1 1
G =   0 0 1 0 | 1 0 1
      0 0 0 1 | 1 1 0

Multiplying a 4 bit vector (d1, d2, d3, d4) by G results in a 7 bit vector of the form (d1, d2, d3, d4, p1, p2, p3). The A portion is what generates the parity bits. If the selection of the columns of A are unique, it is true that (p1, p2, p3) is the parity calculations of three distinct subsets of the original data.

To validate the code word, it is necessary to multiply the data word by 'H' which is the [inverse A | I] check to form the parity check vector.

          H           r |1|    s
                        |0|
| 1 0 1 1 | 1 0 0 |     |0|   |0|
| 1 1 0 1 | 0 1 0 |  *  |1| = |0|
| 1 1 1 0 | 0 0 1 |     |0|   |0|
                        |0|
H*r=s                   |1|

If all the elements of s are 0, then the entire set has been received correctly. If there are any '1's in s, then there is an error which can be determined by looking at the parity pits that have failed.

If r = [1011001] s will be [101] This matches the third colum of 'H' which corresponds to the bit that has the error.

The (7,4) Hamming code, while good for demonstrations is not the best choice for practical communications - it has allot of overhead and has a non-standard length. The number of parity bits goes up with the log of the number of data bits. Hence, there is less overhead for longer words than shorter words.

The hamming code can detect and fix single bit errors, and detect double bit errors. For the (7,4) hamming code, the following table (error correcting bits are in bold):

decimal binary Hamming(7,4)
   0     0000   0000000
   1     0001   0001110
   2     0010   0010101
   3     0011   0011011
   4     0100   0100011
   5     0101   0100011
   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

The hamming distance from one valid error correcting set to another for the same data is three. This means that it would take three errors to go from one valid message to another. Example:

Sent message:
    0101010
First error:
    0100010 (not valid - correctable)
Second error:
    0100000 (not valid - not correctable)
Third error:
    0000000 (valid)

It is left an excercise to the reader to demonstrate this is the case for all 127 possible cases that the minimum hamming distance between any two valid messages is three.