Data Link Layer:: Error Detection and Correction

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.

[email protected]
http://www.cpe.ku.ac.th/~cpj
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
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
k=?
r=?
n=?
0011 10101 1011 10111

0100 01010 1100 11010
0101 01011 1101 11011
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 dataword?
14
Hamming Distance
Hamming Distance between two words is the
number of differences between corresponding 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 minimum Hamming distance is the
smallest Hamming distance between
all possible pairs in a set of words.
Find the minimum Hamming Distance of

the following codebook
00000
01011
10101
11110
16
Detection Capability of Code
To guarantee the detection of up to s-bit

errors, the minimum Hamming distance in
a block code must be
dmin = s + 1
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
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

Data Link Layer:: Error Detection and Correction

Uploaded by

Copyright:

Available Formats

Data Link Layer:: Error Detection and Correction

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Link Layer:: Error Detection and Correction

Uploaded by

Copyright:

Available Formats

Data Link Layer:

Error Detection and

Adapted from lecture slides by Behrouz A. Forouzan

Asst. Prof. Chaiporn Jaikaeo, Ph.D.

Overview of Data Link Layer

Data Link Layer

Forward error correction

To detect or correct errors, redundant bits

Process of adding redundancy for error detection

Divides the data to be sent into a set of blocks

Treats data as a series of bits, and computes a code over a

Main operation for computing error

Message is divided into k-bit blocks

r redundant bits are added

Blocks become n=k+r bits

Example: 4B/5B Block Coding

0011 10101 1011 10111

Error Detection in Block Coding

An error-detecting code can detect

Other types of errors may remain undetected.

There is no way to detect every possible

Example: Error Correction Code

Minimum Hamming Distance

Find the minimum Hamming Distance of

Detection Capability of Code

To guarantee the detection of up to s-bit

Correction Capability of Code

To guarantee the correction of up to t-bit

Example: Hamming Distance

A code scheme has a Hamming distance

Common Detection Methods

Most common, least complex

Even parity Maintain even number of 1s

E.g., 1011 10111

Odd parity Maintain odd number of 1s

E.g., 1011 10110

Example: Parity Check

1110111 1101111 1110010 1101100 1100100

Example: Parity Check

11111110 11011110 11101100 11011000 11001001

Performance of Parity Check

Can 1-bit errors be detected?

What is its performance?

2D Parity Check: Performance

2D Parity Check: Performance

Cyclic Redundancy Check

In a cyclic code, rotating a codeword

More common representation than binary form

Division Using Polynomial

Can be analyzed using polynomial

M(x) Original message

M(x)xn = Q(x)G(x) + R(x)

If G(x) contains at least two terms, then

If G(x) contains a factor of (x+1), all oddnumbered errors can be detected

Properties of Good Polynomial

It should have at least two terms

CRC's Strength Summary

All burst errors with L n will be detected