Error Detection And Correction

error detection and error correction methods used while sending the data

1. Rutvi ShahRutvi Shah 11
ERROR
CORRECTION
&
ERROR
DETECTION

2. Rutvi ShahRutvi Shah 22
Data can be corrupted during Data can be corrupted during
transmission. For reliable communication, transmission. For reliable communication,
errors must be detected and corrected.errors must be detected and corrected.
Error detection and correction are Error detection and correction are
implemented either at data link layer or implemented either at data link layer or
the transport layer of the OSI model.the transport layer of the OSI model.

3. Rutvi ShahRutvi Shah 33
TYPES OF ERRORSTYPES OF ERRORS
Single bit error :-Single bit error :-
--Only one bit in the data unit has Only one bit in the data unit has
changed.changed.
Burst error :-Burst error :-
--It means that two or more bits in the It means that two or more bits in the
data unit has changed. data unit has changed.

4. Rutvi ShahRutvi Shah 44
Single bit ErrorSingle bit Error
01010000 01000000
Burst Error
00 100001 11000010
000001 1111011010
0 changed to 1
Received Sent
Sent
Received
Bits corrupted by Burst Error

5. Rutvi ShahRutvi Shah 55
ERROR DETECTIONERROR DETECTION
Error detecting code is to include only Error detecting code is to include only
enough redundancy to allow the receiver enough redundancy to allow the receiver
to deduce that an error occurred, but not to deduce that an error occurred, but not
which error, and have it request a re-which error, and have it request a re-
transmission.transmission.
Error detection uses the concept of Error detection uses the concept of
redundancy, which means adding extra redundancy, which means adding extra
bits for detecting error at the destination.bits for detecting error at the destination.

6. Rutvi ShahRutvi Shah 66
RedundancyRedundancy
Instead of repeating the entire data Instead of repeating the entire data
stream, a shorter group of bits may be stream, a shorter group of bits may be
appended to the end of each unit. This appended to the end of each unit. This
technique is called Redundancy because technique is called Redundancy because
the extra bit are redundant to the the extra bit are redundant to the
information. They are discarded as soon information. They are discarded as soon
as the accuracy of the transmission has as the accuracy of the transmission has
been determined.been determined.

7. Rutvi ShahRutvi Shah 77

8. Rutvi ShahRutvi Shah 88
There are basically four types of There are basically four types of
redundancy checks. They are:redundancy checks. They are:
1.1.VRCVRC (Vertical Redundancy Check). (Vertical Redundancy Check).
2.2.LRCLRC (Longitudinal Redundancy Check). (Longitudinal Redundancy Check).
3.3.CRCCRC (Cyclical Redundancy Check). (Cyclical Redundancy Check).

9. Rutvi ShahRutvi Shah 99
ERROR DETECTIONERROR DETECTION
VERTICAL REDUNDUNCY CHECKVERTICAL REDUNDUNCY CHECK
LONGITUDINAL REDUNDANCY CHECKLONGITUDINAL REDUNDANCY CHECK
CYCLIC REDUNDANCY CHECKCYCLIC REDUNDANCY CHECK

10. Rutvi ShahRutvi Shah 1010
VERTICAL
REDUNDANCY CHECK
It is also known as parity check
It is least expensive mechanism for error
detection
In this technique,the redundant bit called
parity bit is appended to every data unit
so that the total number of 1s in the unit
becomes even (including parity bit)

11. Rutvi ShahRutvi Shah 1111
VERTICAL
REDUNDANCY CHECK
Checking function
Is total number
of 1s even ?
Receiver
1100001 | 1
Even – parity
generator
1100001
1
Data
VRC
Sender

12. Rutvi ShahRutvi Shah 1212
Example :Example :
1110110 1101111 1110010 1110110 1101111 1110010
- After adding the parity bit- After adding the parity bit
1110110111011011 1101111 110111100 1110010 111001000

VERTICAL REDUNDANCY VERTICAL REDUNDANCY
CHECKCHECK

13. Rutvi ShahRutvi Shah 1313
VRC can detect all single – bit errorsVRC can detect all single – bit errors
It can detect burst errors if the total It can detect burst errors if the total
number of errors in each data unit is odd.number of errors in each data unit is odd.
VRC can not detect errors where the total VRC can not detect errors where the total
number of bits changed is even. number of bits changed is even.
VERTICAL REDUNDANCY VERTICAL REDUNDANCY
CHECKCHECK

14. Rutvi ShahRutvi Shah 1414
LONGITUDINAL REDUNDANCY CHECK(LRC)
In this method , a block of bits is
organized in table(rows and columns)
calculate the parity bit for each column
and the set of this parity bit is also
sending with original data.
From the block of parity we can check
the redundancy.

15. Rutvi ShahRutvi Shah 1515
LRC ExampleLRC Example
11100111 1101101 00111001 10101001 10101010
11100111
11011101
00111001
10101001
11100111 11011101 00111001 1010100111100111 11011101 00111001 10101001
LRC 10101010
Original data plus
LRC

16. Rutvi ShahRutvi Shah 1616
LRC ExampleLRC Example
Suppose the following block is sent :Suppose the following block is sent :
10101001 00111001 11011101 11100111 10101001 00111001 11011101 11100111 1010101010101010
(LRC)(LRC)
However,it is hit by burst of length eight and some bits However,it is hit by burst of length eight and some bits
are corrupted (Yellow bits are changed)are corrupted (Yellow bits are changed) : :
101010100000111 1 11000001001 11011101 11100111 1010101001001 11011101 11100111 10101010
(LRC)(LRC)
When the receiver checks the LRC,some of the bits are When the receiver checks the LRC,some of the bits are
not not
follow even parity rule and whole block is discardedfollow even parity rule and whole block is discarded
(the non matching bits are shown in red ) :(the non matching bits are shown in red ) :
10100011 10001001 11011101 11100111 10100011 10001001 11011101 11100111 1100110011001100

17. Rutvi ShahRutvi Shah 1717
Advantage :Advantage :
-> LRC of n bits can easily detect burst -> LRC of n bits can easily detect burst
error of n bits.error of n bits.
Disadvantage :Disadvantage :
-> If two bits in one data units are damaged -> If two bits in one data units are damaged
and two bits in exactly same position in and two bits in exactly same position in
another data unit are also damaged , the LRC another data unit are also damaged , the LRC
checker will not detect the error.checker will not detect the error.

18. Rutvi ShahRutvi Shah 1818
CYCLIC REDUNDANCY CHECK CYCLIC REDUNDANCY CHECK
(CRC)(CRC)
In this method , a sequence of redundant bits ,In this method , a sequence of redundant bits ,
called the CRC or the CRC remainder, is appended to the end of called the CRC or the CRC remainder, is appended to the end of
the unit so that the resulting data unit become exactly divisible the unit so that the resulting data unit become exactly divisible
by a second, predetermined binary number. At its destination , by a second, predetermined binary number. At its destination ,
the incoming data unit is divided by the same number. If at this the incoming data unit is divided by the same number. If at this
step there is no remainder ,the data unit assume to be correct step there is no remainder ,the data unit assume to be correct
and is accepted, otherwise it indicate that data unit has been and is accepted, otherwise it indicate that data unit has been
damaged in transmission and therefore must be rejected.damaged in transmission and therefore must be rejected.

The redundancy bits is used by CRC are derived by dividing the The redundancy bits is used by CRC are derived by dividing the
data unit by a predetermined divisor. The remainder is the data unit by a predetermined divisor. The remainder is the
CRC.CRC.

19. Rutvi ShahRutvi Shah 1919
CRC generator and checkerCRC generator and checker
DATA CRC
DIVISOR
REMAINDER CRC
DATA CRC
DIVIS0R
DATA 00…0
Zero accept
Nonzero reject
N bits
N+1 bits
N bits
Receiver Sender

20. Rutvi ShahRutvi Shah 2020
DivisorDivisor

The divisor is determined according to the The divisor is determined according to the
algebraic polynomial.algebraic polynomial.
for e.g.for e.g.
A polynomial isA polynomial is

X^7 + x^5 + x^2 + x + 1X^7 + x^5 + x^2 + x + 1
generation of divisor from polynomialgeneration of divisor from polynomial




X^7 + X^5 + X^2 + X + 1
1 0 1 0 0 1 1 1
X^4 X^3X^6

21. Rutvi ShahRutvi Shah 2121
A polynomial should be selected A polynomial should be selected
according to the following rule:-according to the following rule:-
3.3.It should not be divisible by x.It should not be divisible by x.
4.4.It should be divisible by x+1.It should be divisible by x+1.

22. Rutvi ShahRutvi Shah 2222
 Example :-Example :-
The CRC generator at sender end :The CRC generator at sender end :

1 1 0 1
1 1 1 1 0 1
1 0 0 1 0 00 0 0
1 1 0 1
1 0 0 0
1 1 0 1
1 0 1 0
1 1 0 1
1 1 1 0
1 1 0 1
0 1 1 0
0 0 0 0
1 1 0 0
1 1 0 1
0 0 1

23. Rutvi ShahRutvi Shah 2323
The CRC checker at receiver end :The CRC checker at receiver end :

1 1 0 1
1 1 1 1 0 1
1 0 0 1 0 00 0 1
1 1 0 1
1 0 0 0
1 1 0 1
1 0 1 0
1 1 0 1
1 1 1 0
1 1 0 1
0 1 1 0
0 0 0 0
1 1 0 1
1 1 0 1
0 0 0

24. Rutvi ShahRutvi Shah 2424
ERROR CORRECTIONERROR CORRECTION
Error correcting code is to include enough Error correcting code is to include enough
redundant information along with each block of redundant information along with each block of
data sent to enable the receiver to deduce what data sent to enable the receiver to deduce what
the transmitted character must have been.the transmitted character must have been.
Error Correction must be handled in two ways :Error Correction must be handled in two ways :
--When an error is discovered, the receiver When an error is discovered, the receiver
can have the sender retransmit the entire can have the sender retransmit the entire
data unit.data unit.
--Receiver can use an error correcting code, Receiver can use an error correcting code,
which automatically corrects certain errors.which automatically corrects certain errors.

25. Rutvi ShahRutvi Shah 2525
There are two types of Error Correcting There are two types of Error Correcting
techniques :techniques :
1. 1. Single bit error correction.Single bit error correction.
2. 2. Burst error correction.Burst error correction.
Error Correction can be done with the help Error Correction can be done with the help
of HAMMING CODE.of HAMMING CODE.

26. Rutvi ShahRutvi Shah 2626
HAMMING CODEHAMMING CODE
It is a technique developed by It is a technique developed by
R.W.Hamming.R.W.Hamming.
Hamming code can be applied to data Hamming code can be applied to data
units of any length and uses the units of any length and uses the
relationship between data and redundancy relationship between data and redundancy
bits. For eg.bits. For eg.

27. Rutvi ShahRutvi Shah 2727
A 7 bit ASCII code requires 4 Redundancy A 7 bit ASCII code requires 4 Redundancy
bits that can be added to the end of the bits that can be added to the end of the
data unit or interspersed with the original data unit or interspersed with the original
data bits.data bits.
These bits are placed in positions 1,2,4 These bits are placed in positions 1,2,4
and 8. We refer to these bits as r1,r2,r4 and 8. We refer to these bits as r1,r2,r4
and r8.and r8.

28. Rutvi ShahRutvi Shah 2828
r r d r d d d r d d d
Redundancy Bits
Positions of Redundancy Bits in Hamming Code
11 10 9 8 7 6 5 4 3 2 1

29. Rutvi ShahRutvi Shah 2929
In the Hamming code, each r bit is the VRC bit In the Hamming code, each r bit is the VRC bit
for one combination of data bits :for one combination of data bits :
--r1 is the one combination of data bits.r1 is the one combination of data bits.
--r2 is another combination of data bits.r2 is another combination of data bits.
and so on.and so on.
The combination used to calculate each of the The combination used to calculate each of the
four values for a 7 bit data sequence are as four values for a 7 bit data sequence are as
follows :follows :
--r1 : bits 1,3,5,7,9,11.r1 : bits 1,3,5,7,9,11.
--r2 : bits 2,3,6,7,10,11.r2 : bits 2,3,6,7,10,11.
--r4 : bits 4,5,6,7.r4 : bits 4,5,6,7.
--r8 : bits 8,9,10,11.r8 : bits 8,9,10,11.

30. Rutvi ShahRutvi Shah 3030
1 0 1 1 0 0 1
1 1 0 1 1 0 0 1
1 0 1 0 1 1 0 0 1
1 01 0 0 1 1 0 0 1
1 0 1 0 0 1 1 1 0 0 1
Data : 1 0 0 1 1 0 1
Data
Adding r1
Adding r2
Adding r4
Adding r8
Code : 1 0 0 1 1 1 0 0 1 0 1
1110987 6543 21

31. Rutvi ShahRutvi Shah 3131
1 0 1 0 0 1 1 1 0 0 1
1 0 1 0 0 1 0 1 0 0 1
Sent
Received
Error

32. Rutvi ShahRutvi Shah 3232
1 0 1 0 0 1 0 1 0 0 1
1110987 6543 21
1 0 1 0 0 1 0 1 0 0 1
1110987 6543 21
1 0 1 0 0 1 0 1 0 0 1
1110987 6543 21
1 0 1 0 0 1 0 1 0 0 1
1110987 6543 21
0 1 1 1The bit in position 7 is in error