Data link – Error Detection and Correction
Textbook: Ch.9 and Ch.10
SEHH2238: Computer Networking
SEHH2238 Lecture 3 1
Copyright By PowCoder代写 加微信 powcoder
SEHH2238: Computer Networking
Ch 9 Data Link Layer 9.1 Nodes and Links
Main Topics
Ch 10 Error Detection and Correction 10.1 Error Detection and Correction
Types of Errors
10.2 Linear Block Codes
Parity Check
10.3 Cyclic Codes
Cyclic Redundancy Check
SEHH2238 Lecture 3 2
SEHH2238: Computer Networking
Figure 9.1: Communication at the data-link layer
Data-link layer
SEHH2238: Computer Networking
9.1 Nodes and Links
• Communication at the data-link layer is node-to- node.
• It is customary to refer to the two end hosts and the routers as nodes and the networks in between as links.
SEHH2238: Computer Networking
Figure 9.3: A communication with only three nodes 1.5
SEHH2238: Computer Networking
Service of the data-link layer
The data-link layer is located between the physical and the network layers.
Thedata-linklayerprovidesservicestothenetwork layer; it receives services from the physical layer
SEHH2238 Lecture 3 6
SEHH2238: Computer Networking
Ch 10 Error Detection and Correction
10.1 Types of Errors 1. Single-bit error
In a single-bit error, only one bit in the data unit has changed.
SEHH2238 Lecture 3 7
SEHH2238: Computer Networking
2. Burst error
Types of Errors
A burst error means that 2 or more bits in the data unit have changed.
SEHH2238 Lecture 3 8
SEHH2238: Computer Networking
Burst Error
Burst Error – the string of bits between 2 successive corrupted bits including the two bits in error
More likely to happen due to noise duration is usually longer than the duration of 1 bit
Burst error length B – the last corrupted bit in a burst and the first corrupted bit in the following burst must be separated by B+1or more correct bits
SEHH2238 Lecture 3 9
SEHH2238: Computer Networking
Burst error of length 8
Assume the remaining bits are correct SEHH2238 Lecture 3 10
SEHH2238: Computer Networking
Error Detection
Redundancy
• Parity Check
• Cyclic Redundancy Check (CRC)
Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination.
SEHH2238 Lecture 3 11
SEHH2238: Computer Networking
Error Detection (Feedback Error Control)
Each character or frame includes only sufficient additional information to enable the receiver to detect errors
a retransmission control scheme is used
the predominant method because of less
additional bits required
SEHH2238 Lecture 3 12
SEHH2238: Computer Networking
Redundancy
Adding extra bits for detecting errors at the destination
SEHH2238 Lecture 3 13
SEHH2238: Computer Networking
10.2 Linear Block Code –
Parity Check Method
Most common and simple for character- oriented transmission
The data bits in each character are inspected prior to transmission and the parity bit is computed
The parity bit is then added so that the total number of binary 1s is either odd or even:
If odd parity is used, no. of 1s is odd.
If even parity is used, no. of 1s is even.
SEHH2238 Lecture 3 14
SEHH2238: Computer Networking
Parity Check Method (Sender side)
Sender obtains data from upper layer
Determine the parity bit (either 0 or 1) so that the total number of binary 1s is either odd or even:
If odd parity is used, no. of 1s is odd. If even parity is used, no. of 1s is even.
Add the parity bit to data and send it out SEHH2238 Lecture 3 15
SEHH2238: Computer Networking
Parity Check Method (Receiver side)
Receiver receives bits from lower layer
Count the number of 1s
Error is detected if the number does not match, i.e.
Even number of 1s in odd parity Odd number of 1s in even parity
SEHH2238 Lecture 3 16
SEHH2238: Computer Networking
number of error bits
Limitation
Single parity bit is used
Can only detect burst errors with odd
If even number of bits are corrupted, the errors cannot be detected
SEHH2238 Lecture 3 17
SEHH2238: Computer Networking
Even-parity concept
SEHH2238 Lecture 3 18
SEHH2238: Computer Networking
Suppose the sender wants to send the word world. In 7-bit ASCII the five characters are coded as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent using even parity: 11101110 11011110 11100100 11011000 11001001
SEHH2238 Lecture 3 19
SEHH2238: Computer Networking
Example (no error)
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 number of 1s in each character and comes up with even numbers (6, 6, 4, 4, 4).
The data are accepted.
SEHH2238 Lecture 3 20
SEHH2238: Computer Networking
Example (with error)
Now suppose the word world in Example 1 is corrupted during transmission.
11111110 11011110 11101100 11011000 11001001
The receiver counts the number of 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.
SEHH2238 Lecture 3 21
SEHH2238: Computer Networking
Two-dimensional parity check
SEHH2238 Lecture 3 22
SEHH2238: Computer Networking
Two-dimensional parity check
Organize the bits in rows and columns
Calculate the parity bit for each row
same as the single-bit parity check method odd parity or even parity
Calculate the parity bit for each column also for the parity bit of each row
SEHH2238 Lecture 3 23
SEHH2238: Computer Networking
Suppose the following block is sent:
10101001 00111001 11011101 11100111 10101010
However, it is hit by a noise with 8-bit duration, and some bits are corrupted.
10100011 10001001 11011101 11100111 10101010 When the receiver checks the parity bits, some of the bits do not
follow the even-parity rule and the whole block is discarded. 10100011 10001001 11011101 11100111 10101010
What kind of errors can (/cannot) be detected by two- dimensional parity check?
SEHH2238 Lecture 3 24
SEHH2238: Computer Networking
10.3 Cyclic Codes – Cyclic Redundancy Check (CRC)
Parity check does not provide a reliable detection against error bursts
A single set of check digits is computed and appended to the tail of each frame transmitted
The receiver then performs a similar computation to check whether error occurs
SEHH2238 Lecture 3 25
SEHH2238: Computer Networking
Cyclic Redundancy Check (CRC)
The number of check digits varies (16, 32 are most common)
The computed check digits are called cyclic redundancy check (CRC) digits or frame check sequence (FCS) digits
Uses property of modulo 2 arithmetic
uses binary addition with no carries and is
effectively an XOR operation.
SEHH2238 Lecture 3 26
SEHH2238: Computer Networking
CRC generator and checker
SEHH2238 Lecture 3 27
SEHH2238: Computer Networking
CRC Procedure
1. Asetofn“0”sisappendedattheendofa k-bit data frame M.
– Thisisthesameasmultiplyingtheframeby2n so we have (M x 2n)
2. (M x 2n) is divided modulo 2 by a (n+1)-bit binary number G (the generator polynomial), giving the remainder R (n-bit) which is the CRC (or FCS) digits
SEHH2238 Lecture 3 28
SEHH2238: Computer Networking
CRC Procedure
3. R is appended at the end of M and then
transmit M & R together
4. At the receiver, the received bit stream including M & R is again divided by the same polynomial G, i.e. ( M x 2n + R)/G
5. If the remainder = 0 then no errors;
otherwise errors occur
SEHH2238 Lecture 3 29
SEHH2238: Computer Networking
Binary division in a CRC generator
SEHH2238 Lecture 3 30
SEHH2238: Computer Networking
Binary division in CRC checker
SEHH2238 Lecture 3 31
SEHH2238: Computer Networking
CRC Example
Message: 11100110
Polynomial: 11001 (i.e. x4 + x3 + 1) What is the CRC?
Answer: CRC should be 0110
Division is equivalent to performing the XOR operation bit by bit in parallel as each bit in the frame is processed
Could be implemented in hardware
SEHH2238 Lecture 3 32
SEHH2238: Computer Networking
A polynomial representing a divisor
The polynomial is of degree 7 but need 8 bits SEHH2238 Lecture 3 33
SEHH2238: Computer Networking
Standard CRC
Represent the generator polynomial by showing those positions that are binary 1 as powers of X
CRC-CCITT = X16 +X12 +X5 +1(X0)
this is equivalent to 10001000000100001
Also call CRC-16
it will detect all error bursts of length less
than or equal to 16 bits.
SEHH2238 Lecture 3 34
SEHH2238: Computer Networking
Standard CRC
CRC-CCITT (CRC-16) is used extensively with WANs
CRC-32 is used in most LANs
In general, a (n+1)-bit generator polynomial,
with degree n, will detect:
all single-bit, double-bit and odd number of bit
all error bursts with length <= n most error bursts with length > n
SEHH2238 Lecture 3 35
SEHH2238: Computer Networking
Polynomial x8 + x2 + x + 1
Application
CRC-8 CRC-10
x10 +x9+x5+x4+x2 +1
ATM header ATMAAL
CRC-16 CRC-32
x16 +x12 +x5+1
Standard polynomials
x32 +x26+x23 +x22 +x16 +x12 +x11 +x10 +x8 +x7 +x5 +x4 +x2 +x+1
SEHH2238 Lecture 3
SEHH2238: Computer Networking
The CRC-12
x12 + x11 + x3 + x + 1
which has a degree of 12, will detect all burst errors affecting an odd number of bits, will detect all burst errors with a length less than or equal to 12, and will detect 99.97 percent of burst errors with a length of 13 or more.
SEHH2238 Lecture 3 37
SEHH2238: Computer Networking
Error Correction (Forward Error Control)
Each transmitted character or frame contains additional (redundant) information so that the receiver can detect, locate & correct the errors
e.g. Hamming code
SEHH2238 Lecture 3 38
SEHH2238: Computer Networking
Forward Error Control (FEC)
With FEC, sufficient additional check digits are added to each transmitted message to enable the receiver
to detect the presence of one or more errors in a received message
and to locate the position of the error
Correction is achieved simply by inverting
the incorrect bit(s)
SEHH2238 Lecture 3 39
SEHH2238: Computer Networking
Forward Error Control (FEC)
Number of check digits is much higher than that for just error detection
Less efficient than retransmission with error detection
But when the round-trip delay is long or return path is not available, FEC methods are often used
SEHH2238 Lecture 3 40
SEHH2238: Computer Networking
Single-bit errors and burst errors
Error detection by redundancy
Parity Check
Odd parity and even parity
Two-dimentional Parity Check
n-bit check digits detect burst errors <= n bits
More bits are used for error location and correction
Revision Quiz
http://highered.mheducation.com/sites/0073376221/student_view0/chapter
10/quizzes.html
SEHH2238 Lecture 3 41
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com