Forward Error Correction (FEC), the ability of receiving station tocorrect a transmission error, can increase the throughput of a data linkoperating in a noisy environment. The transmitting station must appendinformation to the data in the form of error correction bits, but theincrease in frame length may be modest relative to the cost of retransmission. (sometimes the correction takes too much time and weprefer to re transmit). Hamming codes provide for FEC using a "block parity" mechanism that can be inexpensively implemented. Ingeneral, their use allows the correction of single bit errors anddetection of two bit errors per unit data, called a code word.
The fundamental principal embraced by Hamming codes is parity. Hamming codes, as mentioned before, are capable ofcorrecting one error or detecting two errors but not capable of doingboth simultaneously. You may choose to use Hamming codes as an errordetection mechanism to catch both single and double bit errors or tocorrect single bit error. This is accomplished by using more than oneparity bit, each computed on different combination of bits in the data.
The number of parity or error check bits required is given by theHamming rule, and is a function of the number of bits of informationtransmitted. The Hamming rule is expressed by the following inequality:
p
d + p + 1 < = 2 (1)
Where d is the number of data bits and p is the number of paritybits. The result of appending the computed parity bits to the data bitsis called the Hamming code word. The size of the code word c isobviously d+p, and a Hamming code word is described by the ordered set(c,d).
Codes with values of p< =2 are hardly worthwhile because of theoverhead involved. The case of p=3 is used in the following discussionto develop a (7,4) code using even parity, but larger code words aretypically used in applications. A code where the equality case ofEquation 1 holds is called a perfect code of which a (7,4) code is anexample.
A Hamming code word is generated by multiplying the data bits by agenerator matrix G using modulo-2 arithmetic. This multiplication's result is called the code word vector(c1,c2.c3,.....cn), consisting of the original data bits and thecalculated parity bits.
The generator matrix G used in constructing Hamming codes consistsof I (the identity matrix) and a parity generation matrix A:
G = [ I : A ]
An example of Hamming code generator matrix:
1 0 0 0 | 1 1 1G = 0 1 0 0 | 0 1 1 0 0 1 0 | 1 0 1 0 0 0 1 | 1 1 0
The multiplication of a 4-bit vector (d1,d2,d3,d4) by G results in a7-bit code word vector of the form (d1,d2,d3,d4,p1,p2,p3). It is clearthat the A partition of G is responsible for the generation of theactual parity bits. Each column in A represents one parity calculationcomputed on a subset of d. The Hamming rule requires that p=3 for a(7,4) code, therefore A must contain three columns to produce threeparity bits.
If the columns of A are selected so each column is unique, itfollows that (p1,p2,p3) represents parity calculations of three distinctsubset of d. As shown in the figure below, validating the received codeword r, involves multiplying it by a parity check to form s, thesyndrome or parity check vector.
TH = [A | I] |1| |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| |1| H*r = s
If all elements of s are zero, the code word was received correctly.If s contains non-zero elements, the bit in error can be determined byanalyzing which parity checks have failed, as long as the error involvesonly a single bit.
For instance if r=[1011001], s computes to [101], thatsyndrome ([101]) matches to the third column in H that corresponds tothe third bit of r - the bit in error.