Unit-2
Data Link Layer
Services to data-link layer
Type of Errors
Data can be corrupted during transmission. For reliable
communication, error must be detected and corrected
Error Detection and Correction are implemented either at
the data link layer or the transport layer of the OSI model
Type of Errors
Single-Bit Error
~ is when only one bit in the data unit has changed
Type of Errors(cont’d)
Multiple-Bit Error
~ is when two or more nonconsecutive bits in the data
unit have changed(ex : ASCII B - ASCII LF)
Type of Errors(cont’d)
Burst Error
~ means that 2 or more consecutive bits in the data unit
have changed
Detection
Error detection uses the concept of redundancy, which
means adding extra bits for detecting errors at the
destination
Detection(cont’d)
Detection methods
Detection(cont’d)
Parity Check
A parity bit is added to every data unit so that the total number
of 1s(including the parity bit) becomes even for even-parity
check or odd for odd-parity check
Simple parity check
11000011|0|
11000011
Detection -examples
Example 1
Suppose the sender wants to send the word world. In
ASCII the five characters are coded as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent
11101110 11011110 11100100 11011000 11001001
Detection – examples
Now suppose the word world is received by the receiver
without being corrupted in transmission.
11101110 11011110 11100100 11011000
11001001
The receiver counts the 1s in each character and comes up
with even numbers (6, 6, 4, 4, 4). Data are accepted.
Detection – examples
Now suppose the word world is corrupted during
transmission.
11111110 11011110 11101100 11011000
11001001
The receiver counts the 1s in each character and comes up
with even and odd numbers (7, 6, 5, 4, 4). The receiver
knows that the data are corrupted, discards them, and asks
for retransmission.
Two –Dimensional Parity Check
Detection - example
Example 2
Suppose the following block is sent:
10101001 00111001 11011101 11100111
10101010
However, it is hit by a burst noise of length 8, and some
bits are corrupted.
10100011 10001001 11011101 11100111
10101010
When the receiver checks the parity bits, some of the bits
CRC (Cyclic Redundancy Check)
Detection
~ is based on binary division.
to detect accidental changes to data transmitted via
telecommunications networks
Detection of Bursty errors over noisy channels
Detection(cont’d)
Detection(cont’d)
CRC generator
~ uses modular-2 division.
Binary Division
in a
CRC Generator
CRC
Detection(cont’d)
Binary Division
in a
CRC Checker
Detection(cont’d)
A bit stream 1101011011 is transmitted using the
standard CRC method. The generator polynomial is
x4+x+1. What is the actual bit string transmitted?
The generator polynomial G(x) = x4 + x + 1 is encoded
as 10011.
Clearly, the generator polynomial consists of 5 bits.
So, a string of 4 zeroes is appended to the bit stream to
be transmitted.
The resulting bit stream is 11010110110000.
The code word to be
transmitted is obtained by
replacing the last 4 zeroes
of 11010110110000 with the
CRC.
Thus, the code word
transmitted to the receiver
= 11010110111110. CRC
Detection(cont’d)
Standard polynomials
Detection(cont’d)
Checksum Generator
Detection(cont’d)
To create the checksum the sender does the following:
The unit is divided into K sections, each of n bits.
Section 1 and 2 are added together using one’s
complement.
Section 3 is added to the result of the previous step.
Section 4 is added to the result of the previous step.
The process repeats until section k is added to the result
of the previous step.
The final result is complemented to make the checksum.
Detection(cont’d)
data unit and checksum
Detection(cont’d)
Detection(cont’d)
9.7 ( at a sender)
Original data : 10101001 00111001
10101001
00111001
--------------
11100010 Sum
00011101 Checksum
10101001 00111001 00011101
Detection(cont’d)
Example ( at a receiver)
Received data : 10101001 00111001 00011101
10101001
00111001
00011101
---------------
11111111 Sum
00000000 Complement
Error Correction
~ can be handled in two ways
when an error is discovered, the receiver can have the
sender retransmit the entire data unit.
a receiver can use an error-correcting code, which
automatically corrects certain errors.
Error Correction(cont’d)
Single-Bit Error Correction
parity bit
The secret of error correction is to locate the invalid bit
or bits
For ASCII code, it needs a three-bit redundancy
code(000-111)
Detects 2 Bit errors can correct max of 1 bit error
Error Correction(cont’d)
Redundancy Bits
~ to calculate the number of redundancy bits (r) required
to correct a given number of data bit (m)
Error Correction(cont’d)
If the total number of bits in a transmittable unit is d+r,
then r must be able to indicate at least d+r+1 different
states
2r d + r + 1
ex) For value of m is 7(ASCII), the smallest r value that
can satisfy this equation is 4
24 7 + 4 + 1
24 8 + 4 + 1
Error Correction(cont’d)
Relationship between data (d) and redundancy (r) bits
Number of Data Bits Number of Redundancy Bits Total Bits
(d) (r) (d+r)
1 2 3
2 3 5
3 3 6
4 3 7
5 4 9
6 4 10
7 4 11
8
Error Correction(cont’d)
Hamming Code, developed by R.W.Hamming
positions of redundancy bits in Hamming code
Error Correction(cont’d)
Rule for determining bit is the Parity combination of
data bits
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
Error Correction(cont’d)
Redundancy bits calculation(cont’d)
Error Correction(cont’d)
Redundancy bits calculation
Error Correction(cont’d)
Calculating the r values Calculating Even Parity
Message / Data
Error Correction(cont’d)
Error Detection and Correction
Error Correction(cont’d)
Error detection using Hamming Code
Error Correction(cont’d)
Multiple-Bit Error Correction
redundancy bits calculated on overlapping sets of data
units can also be used to correct multiple-bit errors.
Ex) to correct double-bit errors, we must take into consideration
that two bits can be a combination of any two bits in the entire
sequence
