Computer Networks
Course Code- CMP330
Data Link Layer
Error Control (Correction)
Heena Tariq
Lecturer
Queen Mary Collage, Lahore
notifyqmc.heena@gmail.com
1
2
3
Error correcting code is to include enough redundant
information along with each block of data sent to enable the
receiver to deduce what the transmitted character
must have been.
4
Error Correction must be handled in two ways :
1. When an error is discovered, the receiver can have
the sender retransmit the entire data unit.
2. Receiver can use an error correcting code, which
automatically corrects certain errors.
5
Two methods for error correction.
1. Error correction by Retransmission
2. Forward Error Correction (FEC)
6
It allows The Receiver to inform The Sender of any frame
Lost or Damaged in transmission.
Coordinates The Re-Transmission of those frames by The
Sender. This process is called Automatic Repeat
Request(ARQ).
For this we use three common flow control mechanisms :
1. Stop-and-Wait ARQ
2. Go-back-N ARQ
3. Selective-Repeat ARQ 7
Receiver can use an error correcting code, which
automatically correct certain errors.
There are two types of Forward Error Correcting
techniques :
Single Bit Error Correction.
Burst Bit Error Correction.
Error Correction can be done with the help of HAMMING
CODE.
8
It is a technique developed by R.W. Hamming.
Hamming code is mainly used to solve Single Bit
Error Correction.
We can solve Burst Bit Error Correction using
The concept of Single Bit Error Correction.
9
Single Bit Error Correction
Hamming code can be applied to data units of any
length and uses the relationship between data and
redundancy bits. For instance,
A 7 bit ASCII code requires 4 redundancy bits that can
be added to the end of the data unit or scatter with the
original data bits.
These bits are placed in positions 1,2,4 and 8. We
refer to these bits as r1,r2,r4 and r8.
10
If the number of data bit is 7, then the position of
redundant bits are:
2^0=1 2^1=2
2^2=4 2^3=8
11
Single Bit Error Correction
To calculate the number of redundant bit r to correct an
data bit of length k we must know the relationship
between r and k.
So, if data bit is k and redundant bit is r,
then we have to satisfy the relation
2^r >= k+r+1
12
Single Bit Error Correction
Ex : if the value of k is 7, the relation will satisfy if the
minimum value of r is 4. 2^4 = 16 > 7+4+1
13
Single Bit Error Correction
In the Hamming code, each r bit is the parity bit
for one combination of data bits:
r1 is the one combination of data bits.
r2 is another combination of data bits.
and so on.
14
Single Bit Error Correction
The combination used to calculate each of the
four values for a 7 bit data sequence are as
follows :
r1 : bits 1,3,5,7,9,11.
r2 : bits 2,3,6,7,10,11.
r4 : bits 4,5,6,7.
r8 : bits 8,9,10,11.
15
16
17
Let Receiver receives
10010100101
18
Burst Bit Error Correction
Hamming code cannot correct a burst error directly.
It is possible to rearrange the data and then apply the code.
Instead of sending all the bits in the data unit together, we
can organize n units in a column.
19
Burst Bit Error Correction
Send the first bits of each followed by the second bit of
each, and so on.
In this way, if a Burst Error of m bit occurs (m<n), then
the error does not corrupt m bit of single unit, it corrupt
only 1 bit of unit.
Then we can correct it using Hamming Code Scheme.
20
21
Thank You
22
