PART III
Data Link Layer
Kyung Hee
University
1
Position of the data-link layer
Kyung Hee
University
2
Data link layer duties
Kyung Hee
University
3
LLC and MAC sublayers
Kyung Hee
University
4
IEEE standards for LANs
Kyung Hee
University
5
Chapters
Chapter 10 Error Detection and Correction
Chapter 11 Data Link Control and Protocols
Chapter 12 Point-To-Point Access
Chapter 13 Multiple Access
Chapter 14 Local Area Networks
Chapter 15 Wireless LANs
Chapter 16 Connecting LANs
Chapter 17 Cellular Telephone and Satellite Networks
Chapter 18 Virtual Circuit Switching
Kyung Hee
University
6
Error Detection and Correction
Prof. Choong Seon HONG
Kyung Hee
University
7
10 장 Error Detection and Correction
10.1 Types of Errors
10.2 Detection
10.3 Error Correction
Kyung Hee
University
8
Error Detection and Correction
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
Kyung Hee
University
9
10.1 Type of Errors
Kyung Hee
University
10
Type of Errors(cont’d)
Single-Bit Error
~ is when only one bit in the data unit has changed (ex :
ASCII STX - ASCII LF)
Kyung Hee
University
11
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)
Kyung Hee
University
12
Type of Errors(cont’d)
Burst Error
~ means that 2 or more consecutive bits in the data unit
have changed
Kyung Hee
University
13
10.2 Detection
Error detection uses the concept of redundancy, which
means adding extra bits for detecting errors at the
destination
Kyung Hee
University
14
Detection(cont’d)
Redundancy
Kyung Hee
University
15
Detection(cont’d)
Detection methods
Kyung Hee
University
16
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
Kyung Hee
University
17
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
Kyung Hee
University
18
Detection – examples
Example 2
Now suppose the word world in Example 1 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). The data are accepted.
Kyung Hee
University
19
Detection – examples
Example 3
Now suppose the word world in Example 1 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.
Kyung Hee
University
20
Two –Dimensional Parity Check
Kyung Hee
University
21
Detection - example
Example 4
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
Kyung Hee
When the receiver checks the parity bits, some of the bits
University
22
Detection(cont’d)
CRC(Cyclic Redundancy Check)
~ is based on binary division.
Kyung Hee
University
23
Detection(cont’d)
CRC generator
~ uses modular-2 division.
Binary Division
in a
CRC Generator
Kyung Hee
University
24
Detection(cont’d)
Binary Division
in a
CRC Checker
Kyung Hee
University
25
Detection(cont’d)
Polynomials
CRC generator(divisor) is most often represented not as
a string of 1s and 0s, but as an algebraic polynomial.
Kyung Hee
University
26
Detection(cont’d)
A polynomial representing a divisor
Kyung Hee
University
27
Detection(cont’d)
Standard polynomials
Kyung Hee
University
28
Detection(cont’d)
Checksum
~ used by the higher layer protocols
~ is based on the concept of redundancy(VRC, LRC, CRC
….)
Kyung Hee
University
29
Detection(cont’d)
Checksum Generator
Kyung Hee
University
30
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.
Kyung Hee
University
31
Detection(cont’d)
data unit and checksum
Kyung Hee
University
32
Detection(cont’d)
Kyung Hee
University
33
Detection(cont’d)
예제 9.7 ( at a sender)
Original data : 10101001 00111001
10101001
00111001
--------------
11100010 Sum
00011101 Checksum
10101001 00111001 00011101 전송
Kyung Hee
University
34
Detection(cont’d)
Example ( at a receiver)
Received data : 10101001 00111001 00011101
10101001
00111001
00011101
---------------
11111111 Sum
00000000 Complement
Kyung Hee
University
35
10.3 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.
Kyung Hee
University
36
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)
Kyung Hee
University
37
Error Correction(cont’d)
Redundancy Bits
~ to calculate the number of redundancy bits (R) required
to correct a given number of data bit (M)
Kyung Hee
University
38
Error Correction(cont’d)
If the total number of bits in a transmittable unit is m+r,
then r must be able to indicate at least m+r+1 different
states
2r m + 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
Kyung Hee
University
39
Error Correction(cont’d)
Relationship between data and redundancy bits
Number of Data Bits Number of Redundancy Bits Total Bits
(m) (r) (m+r)
1 2 3
2 3 5
3 3 6
4 3 7
5 4 9
6 4 10
7 4 11
Kyung Hee
University
40
Error Correction(cont’d)
Hamming Code
~ developed by R.W.Hamming
positions of redundancy bits in Hamming code
Kyung Hee
University
41
Error Correction(cont’d)
each r bit is the VRC bit for one 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
Kyung Hee
University
42
Error Correction(cont’d)
Redundancy bits calculation(cont’d)
Kyung Hee
University
43
Error Correction(cont’d)
Redundancy bits calculation
Kyung Hee
University
44
Error Correction(cont’d)
Calculating the r values
Calculating Even Parity
Kyung Hee
University
45
Error Correction(cont’d)
Error Detection and Correction
Kyung Hee
University
46
Error Correction(cont’d)
Error detection using Hamming Code
Kyung Hee
University
47
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
Kyung Hee
University
48
CRC
All burst errors of length less than or equal to n.
All burst errors affecting an odd number of bits.
All burst errors of length equal to n + 1 with probability
(2^(n-1) − l)/2^n − 1
All burst errors of length greater than n + 1 with probability
(2^(n-1) − l)/2^n [the CRC-32 polynomial will detect all burst
errors of length greater than 33 with probability (2^32 −
l)/2^32; This is equivalent to a 0.49 accuracy rate]
Kyung Hee
University
49
Hamming Code
For the (7,4) Hamming code:
It can detect and correct single-bit errors.
It can detect but not correct double-bit errors.
For the (8,4) extended Hamming code:
It can detect and correct single-bit errors.
It can detect but not correct double-bit errors.
It can also detect some triple-bit errors, but not all.
Kyung Hee
University
50
Checksum
The error detection capability of a 16-bit checksum primarily
depends on the probability of undetected errors occurring
during transmission. With a 16-bit checksum, it can detect
most single-bit errors and some multiple-bit errors.
Kyung Hee
University
51
