程序代做 SEHH2238: Computer Networking

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