Data Link
Layer
Error Control-Error Detection
Techniques
Error Detection
Techniques
• Parity Checker
• CRC (Cyclic Redundency
Check)
• Checksum
Parity Checker
•Parity Checker:- In this approach, an extra bit
is added to the data before transmission
•Types of parity checker:-
• Even Parity- Number of 1’s in the given
word should be even
• Odd Parity- Number of 1’s in the given
word should be odd
•Limitations of parity checker
• Not suitable for detection of burst error
• Unable to detect the location of
erroneous bit and correct the same.
Parity Checker
Parity Checker
Two-
dimensional
parity-checker
• A better approach is the
two-dimensional parity
check.
• In this method, the
dataword is organized in a
table (rows and columns).
• It can detect up to three bit
error
Two-
dimensional
parity-checker
• A better approach is the
two-dimensional parity
check.
• In this method, the
dataword is organized in a
table (rows and columns).
• It can detect up to three bit
error
Two-dimensional parity-check code
Two-dimensional parity-check code
Two-dimensional parity-check code
Two-dimensional parity-check code
• Error affecting 4 bit may not be detected
Cyclic
Redundancy
Check
•Cyclic codes are special linear
block codes with one extra
property. In a cyclic code, if a
codeword is cyclically shifted
(rotated), the result is another
codeword.
• It is based on the concept of
binary division
Cyclic Redundancy Check
• The divisor in a cyclic code is normally called the generator polynomial or
simply the generator.
Division in CRC encoder
• Message= 1001
• Sender appends number of zeros in message
equals to degree of generator polynomial
• Divide the appended message with generated
polynomial using modulo 2 arithmetic
• Remainder becomes CRC
• Remove the appended zeros from message
and append the calculated CRC
• Send the code word to receiver
Division in the CRC decoder for two cases
At receiver Side
• Receiver takes the code
word
• It divides the codeword
with same generator
polynomial using modulo
2 arithmetic
• If remainder contains all
zero bits, message is
accepted otherwise it is
discarded
CRC division using polynomials
Cyclic Redundancy Check
• If the generator has more than one term and the coefficient of x0 is 1, all
single errors can be caught.
• If a generator cannot divide xt + 1 (t between 2 and n – 1), then all
isolated double errors can be detected. The variable 𝑛n represents the
length of the data/message (in bits) that is being transmitted and
checked for errors using CRC.
• A generator that contains a factor of x + 1 can detect all odd-numbered
errors.
CHECKSUM
• In this method, each data word
is added to the previous data
word and total sum
(checksum) is calculated.
• Data along with checksum is
then transmitted.
• This method detects all odd bit
error; Even bit error may or
may not be detected
•
Idea of Checksum
• Suppose data is a list of five 4-bit numbers (7, 11, 12, 0, 6),
• Sender will send (7, 11, 12, 0, 6, 36), where 36 is the sum of the
original numbers.
• The receiver adds the five numbers and compares the result with
the sum.
• If the two are the same, the receiver assumes no error, accepts the
five numbers and discards the sum
• If the two are not same, the receiver assumes there is an error
somewhere and the data are not accepted.
• To make the job of the receiver easier if we send the negative
(complement) of the sum, called the checksum.
• In this case, we send (7, 11, 12, 0, 6, −36).
• The receiver can add all the numbers received (including the
checksum).
• If the result is 0, it assumes no error; otherwise, there is an error.
Exampl
e:
Checks
um
Internet Checksum
Sender Receiver
1. The message is divided into 16-bit words. 1. The message (including checksum) is
2. The value of the checksum word is set to 0. divided into 16-bit words.
3. All words including the checksum are 2. All words are added using one’s
added using one’s complement addition. complement addition.
4. The sum is complemented and becomes 3. The sum is complemented and becomes
the checksum. the new checksum.
5. The checksum is sent with the data. 4. If the value of checksum is 0, the message
is accepted; otherwise, it is rejected.
