Tuesday, 7 February 2012

Error Detection and Correction


Error Detection:
error detection method is used to detect the presence of error. Parity checking and 2 out 5 code are some of the codes used for error detection. This plays major role in communications. 
Parity checking:
  • It is used to detect single error
  • An extra bit is added to the original code word. This bit is called parity bit.
  • Even parity: total no. of ones in the code word with parity should be even. i.e. if no. of ones in code word is odd then parity bit is 1 else 0
  • Odd parity: total no. of ones in the code word with parity should be odd. i.e. if no. of ones in code word is even then parity bit is 1 else 0
  • When sending data on communication link or to a device along with the data, parity bit is also sent. So if any single bit error occurs it is possible to detect it easily. for example take 0001is data and even parity is used, then data that is sent is 00011. If this data is properly received at destination, even parity computation gives 0(since no. of 1's are even), hence there is no error. Suppose if one data bit is corrupted (let data became10011), the computation of even parity results in 1(since odd no. of ones are present in received data). So there is an error. 
  • Two bit errors can not be detected. For example, consider above data 00011. Let two bits are corrupted, then the data received is 11011(assume). If we compute even parity the result is 0. Which indicates no error. But actually two bits are corrupted. Hence it is not possible to detect two bit errors.      
2-out-of-5 code:
Only 2 bits in the code word are 1’s
For any decimal digit the code has only two 1's in the code. So in the received data also there should be only two 1's. Otherwise there is some error.
Error Correction:
In this method the location of error can also be detected(i.e error bit position), hence it can be corrected. Hamming code is example for error correction method.
  •  Hamming code is used for error correction
  • It uses multiple parity bits. Parity bits are added at 20,21,22,… positions
  • Single error correcting code can detect and correct single error, and can also detect double error but can’t correct it
  • Minimum distance (dmin) is the no. of ones in the code word with fewest no. of ones
  • Let n=no. of information bits,
       K= no. of check bits
Then no. of check bits should satisfy the condition 2k >n+k+1
Ex:
 Let the message to be transmitted is 101101
Here n=6
No. of check bits 2k >6+k+1
2k>k+7 
Hence k=4

Code word

Consider even parity
P1 = (1, 3, 5, 7, 9) = (1010) = 0 consider all positions of weight ‘1’ in binary representation containing ‘1’
P2 = (2, 3, 6, 7, 10) = (1111) = 0 consider all positions of weight ‘2’ in binary representation containing ‘1’
P4 = (4, 5, 6, 7) = (011) = 0 consider all positions of weight ‘4’ in binary representation containing ‘1’
P8= (8, 9, 10) = (01) = 1 consider all positions of weight ‘8’ in binary representation containing ‘1’
Transmitted code word is 1011100100

Transmitted code word is transmitted through medium. Assume that because of noise one bit error occurred in the transmitted code word

So received code word is 1011101100
To recover the original message at the receiver the following procedure needs to be done.

 
Considering even parity
C1 = (1, 3, 5, 7, 9) = (01010) = 0
C2 = (2, 3, 6, 7, 10) = (01111) = 0
C4 = (4, 5, 6, 7) = (1011) = 1
C8 = (8, 9, 10) = (101) = 0
The error position is C8C4C2C1 = 0100 = 4
So, complement received bit at 4th position
Hence corrected code word is 1011100100

Back                                            Contents                                                  Next


No comments:

Post a Comment