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>= 2p
'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 >= 23
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.