Data Link Layer:
Error Detection and
Correction
01204325: Data
Communication and
Computer Networks
Adapted from lecture slides by Behrouz A. Forouzan
The McGraw-Hill Companies, Inc. All rights reserved
Asst. Prof. Chaiporn Jaikaeo, Ph.D.
chaiporn.j@[Link]
[Link]
Computer Engineering Department
Kasetsart University, Bangkok, Thailand
Outline
Overview of Data Link Layer
Types of errors
Redundancy
Correction vs. detection
Coding
Data Link Layer
Error Control
Detecting errors
Correcting errors
Forward error correction
Automatic repeat request
Types of Errors
Single-bit errors
Burst errors
Redundancy
To detect or correct errors, redundant
bits of data must be added
Coding
Process of adding redundancy for error
detection or correction
Two types:
Block codes
Divides the data to be sent into a set of blocks
Extra information attached to each block
Memoryless
Convolutional codes
Treats data as a series of bits, and computes a code
over a continuous series
The code computed for a set of bits depends on the
current and previous input
7
XOR Operation
Main operation for computing error
detection/correction codes
Similar to modulo-2 addition
Block Coding
Message is divided into k-bit blocks
Known as datawords
r redundant bits are added
Blocks become n=k+r bits
Known as codewords
Example: 4B/5B Block
Coding
Data Code Data Code
0000 11110 1000 10010
0001 01001 1001 10011
0010 10100 1010 10110
0011 10101 1011 10111
0100 01010 1100 11010
0101 01011 1101 11011
k=?
r=?
n=?
0110 01110 1110 11100
0111 01111 1111 11101
10
Error Detection in Block
Coding
11
Notes
An error-detecting code can detect
only the types of errors for which it is
designed
Other types of errors may remain
undetected.
There is no way to detect every
possible error
12
Error Correction
13
Example: Error Correction
Code
k, r, n = ?
The receiver receives 01001, what is the original datawo
14
Hamming Distance
Hamming
Hamming Distance
Distance between
between two
two words
words is
is the
the
number
number of
of differences
differences between
between corresponding
corresponding
bits.
bits.
d(01, 00) = ?
d(11, 00) = ?
d(010, 100) = ?
d(0011, 1000) = ?
How many 8-bit words are n bits
away from 10000111?
15
Minimum Hamming
Distance
The
The minimum
minimum Hamming
Hamming distance
distance is
is the
the
smallest
smallest Hamming
Hamming distance
distance between
between
all
all possible
possible pairs
pairs in
in aa set
set of
of words.
words.
Find the minimum Hamming Distance
of the following codebook
0000
0
0101
1
1010
16
Detection Capability of
Code
To guarantee the detection of up to sbit errors, the minimum Hamming
distance in a block code must be
dmin
=s+1
min
17
Correction Capability of
Code
To guarantee the correction of up to
t-bit errors, the minimum Hamming
distance in a block code must be
dmin
= 2t + 1
min
18
Example: Hamming
Distance
A code scheme has a Hamming
distance dmin = 4. What is the error
detection and correction capability of
this scheme?
19
Common Detection
Methods
Parity check
Cyclic Redundancy Check
Checksum
20
Parity Check
Most common, least complex
Single bit is added to a block
Two schemes:
Even parity Maintain even number of
1s
E.g., 1011 10111
Odd parity Maintain odd number of 1s
E.g., 1011 10110
21
Example: Parity Check
Suppose the sender wants to send the word world. In
ASCII the five characters are coded (with even parity) as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent
11101110 11011110 11100100 11011000 11001001
22
Example: Parity Check
Receiver receives this sequence of words:
11111110 11011110 11101100 11011000 11001001
Which blocks are accepted? Which are rejected?
23
Parity-Check:
Encoding/Decoding
24
Performance of Parity
Check
Can 1-bit errors be detected?
Can 2-bit errors be detected?
:
25
2D Parity Check
What is its performance
26
2D Parity Check:
Performance
27
2D Parity Check:
Performance
28
Cyclic Redundancy Check
In a cyclic code, rotating a codeword
always results in another codeword
Example:
29
CRC Encoder/Decoder
30
CRC Generator
31
Checking CRC
32
Polynomial
Representation
More common representation than binary
form
Easy to analyze
Divisor is commonly called generator
polynomial
33
Division Using
Polynomial
34
Strength of CRC
Can be analyzed using polynomial
M(x) Original message
G(x) Generator polynomial of degree n
R(x) Generated CRC
M(x)xn = Q(x)G(x) + R(x)
Transmitted message is
M(x) xn R(x)
which is divisible by G(x)
35
Strength of CRC
Received message is
M(x) xn R(x) + E(x)
where E(x) represents bit errors
Receiver does not detect any error
when E(x) is divisible by G(x), which
means either:
E(x) 0 No error
E(x) 0 Undetectable error
36
Strength of CRC
If G(x) contains at least two terms, then
all single-bit errors can be detected
If G(x) cannot divide xt + 1 (0 t < n), then
all isolated double errors can be
detected
If G(x) contains a factor of (x+1), all oddnumbered errors can be detected
37
Properties of Good
Polynomial
It should have at least two terms
The coefficient of the term x0 should
be 1
It should not divide xt + 1, for t
between 2 and n 1
It should have the factor x + 1
38
CRC's Strength Summary
All burst errors with L n will be
detected
All burst errors with L = n + 1 will be
detected with probability 1 (1/2)n1
All burst errors with L > n + 1 will be
detected with probability 1 (1/2)n
39
Example: CRC
Generators
Which of the following polynomials
guarantees that a single-bit error can
be detected
(a) x+1
(b) x3
(c) 1
40
Example: CRC
Generators
Criticize the following CRC generators
x3
x10 + x9 + x5
x6+1
41
Standard Polynomials
42
Error Correction
Two methods
Retransmission after detecting error
Forward error correction (FEC)
43
Forward Error Correction
Consider only a single-bit error in k bits of data
k possibilities for an error
One possibility for no error
#possibilities = k + 1
Add r redundant bits to distinguish these
possibilities; we need
2r k+1
But the r bits are also transmitted along with
data; hence
2r k+r+1
44
Number of Redundant
Bits
Number of
data bits
k
Number of
redundancy bits
r
Total
bits
k+r
1
2
3
4
5
6
7
10
11
45
Hamming Code
Simple, powerful FEC
Widely used in computer memory
Known as ECC memory
error-correcting bits
46
Redundant Bit
Calculation
47
Example: Hamming Code
48
Example: Correcting
Error
Receiver receives 10010100101
49
Strength of Hamming
Code
Minimum Hamming Distance is 3
It can correct at most 1 bit error
It can detect at most 2 bit error
But not both!!! (Why?)
SECDED Extended Hamming code
with one extra parity bit
Achieves minimum Hamming distance of
4
Can distinguish between one bit and two
bit errors
50
Burst Error Correction
51