How is error correction done in Computer Network? Expalin different methods with examples.
ERROR CORRECTION
Error correction is handled in two ways. In
one, when an error is discovered, the receiver can have the sender retransmit
the entire data unit. In the other, a receiver can use an error correcting
code, which automatically corrects certain errors.
Types of error correction:
 Single bit error correction
 Burst bit error correction
Single Bit Error Correction
To correct a single bit error in an ASCII
character, the error correction code must determine which of the seven bits has
changed. In this case we have to determine eight different states: no error,
error in position 1, error in position 2, error in position 3, error in
position 4, error in position 5, error in position 6, error in position 7. It
looks like a three bit redundancy code should be adequate because three bits
can show eight different states. But what if an error occurs in the redundancy
bits? Seven bits of data and three bits of redundancy bits equal 10 bits. So
three bits are not adequate.
To calculate the number of redundancy bits (r)
required to correct a given number of data bits (m) we must find a relationship
between m and r.
If the total number of bits in a transmittable
unit is m+r then r must be able to indicate at least m+r+1 different state. Of
these, one state means no error and m+r states indicate the location of an
error in each of the m+r positions.
So m+r+1 state must be discoverable by r bits.
And 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
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:
The hamming code can be applied to data units of any length
and uses the relationship between data and redundancy bits.
Positions of
redundancy bits in hamming code
Hamming Code 
The combinations used to calculate each of the
four r values for a seven bit data sequence are as follows:
r1 :1,3,5,7,9,11
r2 : 2,3,6,7,10,11
r3 : 4,5,6,7
r4 : 8,9,10,11
Here, r1 bit is calculated using all bit
positions whose binary representation includes a 1 in the rightmost position
(0001, 0011, 0101, 0111, 1001, and 1011). The r2 bit is calculated using all
bit positions with a 1 in the second position (0010, 0011, 0110, 0111, 1010 and
1011), and for r3 1 at third bit position (0100, 0101, 0110 and 0111) for r4 1
at fourth bit position (1000, 1001, 1010 and 1011).
Calculating the r Values:
In the first step, we place each bit of the
original character in its appropriate positions in the 11 bit unit. Then, we
calculate the even parities for the various bit combinations. The parity value
of each combination is the value of the corresponding r bit. For example r1 is
calculated to provide even parity for a combination of bits 3, 5, 7, 9, 11.
Error Detection and Correction:
Example:
At the sender:
Data to be sent: 1001101
Redundancy bit calculation:
Data sent with redundancy bits: 10011100101
During transmission:
At the receiver:
The receiver takes the transmission and
recalculates four new r values using the same set of bits used by the sender
plus the relevant parity (r) bit for each set. Then it assembles the new parity
values into a binary number in order of r position (r8, r4, r2, r1).
Once
the bit is identified, the receiver can reverse its value and correct the
error.
Burst Bit Error Correction:
A hamming code can be designed to correct burst
errors of certain length. The number of redundancy bits required to make these
corrections, however, is dramatically higher than that required for single bit
errors. To correct double bit errors, for example, we must take into
consideration that the two bits can be a combination of any two bits in the
entire sequence. Three bit correction means any three bits in the entire
sequence and so on.
0 comments:
Feel free to contact the admin for any suggestions and help.