Error Correction

Error Correction can be handled in two ways

1.     When an error is discovered, the receiver can have the sender to retransmit the entire data unit.

2.     A receiver can use an error correcting code, which automatically correct certain errors.

Error correcting codes are more sophisticated than error-detection codes and require more redundancy bits.

In single bit error detection only two states are sufficient.

1) error

2) no error

Two states are not enough to detect an error but not to correct it.

Redundancy Bits

Ø  To calculate the number of redundancy bit(r) required to correct a given number of data bits (m), we must find a relationship between m and r.

Ø  Add m bits of data with r bits. The length of the resulting code is m+r.

Data and Redundancy bits

Ø  If the total number of bits are m+r, then r must be able to indicate at least m+r+1 different states. r bits can indicate 2^r different states. Therefore, 2^r must be equal to or greater than m+r+1

2^r >=m+r+1

Ø  For example if the value of m is 7 the smallest r value that can satisfy this equation is 4.

 Relationship between data and redundancy bits

Number of Data Bits (m)	Number of redundancy Bits(r)	Total bits (m+r)
1	2	3
2	3	5
3	3	6
4	3	7
5	4	9
6	4	10
7	4	11

Hamming Code

R.W. Hamming provides a practical solution for the error correction.

Positioning the Redundancy Bits

For example, a seven-bit ASCII code requires four redundancy bits that can be added to the end of the data or intersperse with the original data bits. These redundancy bits are placed in positions 1, 2, 4 and 8. We refer these bits as r1, r2, r3 and r4

Position of redundancy bits in Hamming code

The combination used to calculate each of the four r values for a seven-bit data sequence are as follows

Ø  The r1 bit is calculated using all bits positions whose binary representation include a 1 in the rightmost position

Ø  r2 is calculated using all bit position with a 1 in the second position and so on

                    r1: bits 1,3,5,7,9,11

                    r2: bits 2, 3, 6, 7, 10, 11

                    r3: bits 4, 5, 6, 7

                    r4: bits 8, 9, 10, 11

Redundancy bits calculation

Calculating the r values

Ø  Place each bit of the original character in its appropriate position in the 11-bit unit.

Ø  Calculate the even parities for the various bit combination.

Ø  The parity value for each combination is the value of the corresponding r bit.

For example,

Ø  The value of r1 is calculated to provide even parity for a combination of bits 3,5,7,9 and 11.

Ø  The value of r2 is calculated to provide even parity with bits 3, 6, 7, 10 and 11.

Ø  The value of r3 is calculated to provide even parity with bits 4,5,6 and 7.

Ø  The value of r4 is calculated to provide even parity with bits 8,9,10 and 11.