error correction
The single-bit error correction method developed by R.W. Hamming involves creatin; special code words from data to be sent. The Hamming code requires the insertion o multiple parity bits in the bit string before sending. The parity bits check the paritying in strategic locations. The idea is that if bits are altered, their positions determine a unique combination of parity check errors. When the frame is sent, the receive recalculates the parity checks. If they fail, the combination of failures tells the, receiver which bits were affected. The receiver then can set the bits to their correct values. This technique is quite common for memory addressing and transferring bit from registers to RAM and back.

For example, to correct a single-bit error in an ASCII character (assume frame as ASCII character), the error correction code must determine which of the seven bit has changed. In this case, we have to distinguish between eight different states; no error, error in position 1, error in position 2, and so on, up to error in position 7 This requires enough redundancy bits to show all eight states.

At first glance, it might seem that a three-bit redundancy code should be adequate because three bits can show eight different states (000 to 111) and can therefore indicate the locations of eight different possibilities. But what if an error occurs in the redundancy bits themselves? Seven bits of data (ASCII character) plus three bits of redundancy equals 10 bits. Three bits, however, can identify only eight possibilities. Additional bits are necessary to cover all possible error locations. We must find a relationship between m and r, where m is the number of data bits in the frame and r is the number of redundancy bits or parity checks. In general, if r parity checks are used, there are 2r possible combinations of failure and successes. 2' must be equal to or greater than m + r + 1.
We must associate each bit position with a unique combination to allow the receiver to analyze the parity checks and conclude where an error occurred. Table 3.1 shows the relationship between data and redundancy bits.
Table 3.1 Relationship between Data and Redundancy Bits

Hamming code can be applied to data units of any length and uses the relationship between data and redundancy bits discussed above. For example, a seven­bit ASCII code requires four redundancy bits that can be added to the end of the data unit or interspersed with the original data bits. Figure illustrates the position of redundancy bits in Hamming code.
11 10 9 8 7 6 5 4 3 2 1 ml     m2     m3        r8   m4     m6        m 6    r4      m7    r2     rl   

Position of redundancy bits in Hamming code.
In the Hamming code, each r bit is the parity bit for one combination of data bits: rl is the parity bit for the first combination of data bits, that is,
rl : bits 1, 3, 5, 7, 9, 11
r2 is the parity bit for the second combination of data bits, that is, r2 : bits 2, 3, 6, 7, 10, 11
r4 is the parity bit for the third combination of data bits, that is, r4 : bits 4, 5, 6, 7
r8 is the parity bit for the fourth combination of data bits, that is, r8 : bits 8, 9, 10, 11
Each data bit may be included in more than one parity calculation.Here, rl bit is calculated using all bit positions whose binary representation includes a 1 in the rightmost position. The r2 bit is calculated using all bit positions with a 1 in the second position, and so on. Figure 3.16 shows the redundancy bit calculation.

Figure shows a Hamming code implementation for an ASCII character with an example of a redundancy bit calculation. In the example, the 11-bit unit contains 7 ASCII character and 4 parity checks. First we place each of the original characters (7 ASCII character) in appropriate positions in the 11-bit unit. In the subsequent steps, we calculate the even parities for various bit combinations. The parity value for each combination is the value of the corresponding r bit.

As the illustration in Figure shows, to get the final 11-bit code; the sender sends a 11-bit code to the receiver through the transmission line.
Now imagine that by the time the above transmission is received, the number 7 bit has been changed from 1 to 0, as shown in Figure .

The receive recalculates four new parity checks (vertical redundancy checks) using the same SE of bits used by the sender plus the relevant parity r bit for each set.

BACK