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`^{3}

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 = [10*1*1001] 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 000**0**0**00**
1 0001 000**1**1**10**
2 0010 001**0**1**01**
3 0011 001**1**0**11**
4 0100 010**0**0**11**
5 0101 010**0**0**11**
6 0110 011**0**1**10**
7 0111 011**1**0**00**
8 1000 100**0**1**11**
9 1001 100**1**0**01**
10 1010 101**0**0**10**
11 1011 101**1**1**00**
12 1100 110**0**1**00**
13 1101 110**1**0**10**
14 1110 111**0**0**01**
15 1111 111**1**1**11**

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:
010**0**010 (not valid - correctable)
Second error:
01000**0**0 (not valid - not correctable)
Third error:
0**0**00000 (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.