Chapter 9: Error Detection and Correction

Error Detection and Correction

• Data can be corrupted during
transmission. For reliable communication,
errors 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.
Chapter 9: Error Detection and Correction

Types of Errors 1/4

Errors

Single-bit Burst
Chapter 9: Error Detection and Correction

Types of Errors 2/4

• Single-Bit Error: Only one bit of a given data

unit (byte, character, data unit, packet) is
changed (from 10 or 01)
• Least likely type of error in serial data
transmission.
• Can happen if we are sending data using
parallel transmission.
Chapter 9: Error Detection and Correction

Types of Errors 3/4

• Burst Error: Two or more bit is changed.

• A burst error does not mean that the errors
occur in consecutive bits. The length of the
burst is measured from the first corrupted bit
to the last corrupted bit. Some bits between
may not have been corrupted.
Chapter 9: Error Detection and Correction

Types of Errors 4/4

• Burst error is most likely to happen in a

serial transmission.
• The number of bits affected depends on
the data rate and duration of noise.
Chapter 9: Error Detection and Correction

Detection 1/21
• Redundancy
Data
101000000001010101010

Accept
Checking Generating
function function
Reject

1011101
Redundancy check
Receiver Data & redundancy check Sender
101000000001010101010 1011101
Chapter 9: Error Detection and Correction

Detection 2/21
• There are four types of redundancy
checks used in data communications

Detection methods

VRC LRC CRC Checksum

Chapter 9: Error Detection and Correction

Detection 3/21

• VRC (Vertical Redundancy Check)

- The most common mechanism for error
detection is the VRC, often called a parity
check.
Chapter 9: Error Detection and Correction

Detection 4/21
• VRC (Vertical Redundancy Check)
Even-parity circuit
Chapter 9: Error Detection and Correction

Detection 5/21
• VRC ( vertical redundancy check)
Parity checking circuit
Chapter 9: Error Detection and Correction

Detection 6/21
P (for even) = 1
• VRC P (for odd) = 0
7 data Checking R = k/n / 7/8
( Vertical bits bit
Redundancy
Check)

P (for P (for
even) odd)
Chapter 9: Error Detection and Correction

Detection 7/21

• VRC (Vertical Redundancy Check)

- VRC can detect all single-bit errors.
- Can also detect burst errors as long as the
total number of bits changed is odd (1, 3, 5,
etc)
Chapter 9: Error Detection and Correction

Detection 8/21
• LRC (longitudinal redundancy check)
Generate LRC Original data
11100111 11011101 00111001 10101001

11100111
11011101
00111001
10101001
Hình 7 LRC 10101010

11100111 11011101 00111001 10101001 10101010

Original data plus LRC
Chapter 9: Error Detection and Correction

Detection 9/21
• LRC (longitudinal redundancy check)
LRC Checking
Received data
11100111 11011101 00111001 10101001 10101010

11100111
11011101
00111001
10101001
10101010
LRC at 00000000
the
receiver
Correct data
Chapter 9: Error Detection and Correction

Detection 10/21
• LRC (longitudinal redundancy check)
LRC Checking
Received data has
2 damaged bits
00100111 11011101 00111001 10101001 10101010
Row VRC
00100111 0
11011101 0
00111001 0
10101001 0
10101010 0
VRC at
11000000
the
receiver
Error !!
Chapter 9: Error Detection and Correction

Detection 11/21
• LRC (longitudinal redundancy check)
LRC Checking
Received data has
1 damaged bit
01100111 11011101 00111001 10101001 10101010
Row VRC
01100111 1
11011101 0
00111001 0
10101001 0
10101010 0
VRC at
10000000
the
receiver
Error!!
Detect position
of error
Chapter 9: Error Detection and Correction

Detection 12/21
• LRC (longitudinal redundancy check)
LRC Checking
Received data has
2 damaged bits
01100111 01011101 00111001 10101001 10101010

01100111
01011101
00111001
10101001
LRC at 10101010
the 00000000
receiver
Error!!
Can’t detect
position of error
Chapter 9: Error Detection and Correction

Detection 13/21

• LRC (longitudinal redundancy check)

- LRC increases the likelihood of detecting
burst errors
- However, if two bits in one data unit are
damaged a two bits in exactly the same
positions, the LRC checker will not detect an
error
Chapter 9: Error Detection and Correction

Detection 14/21

• CRC (Cyclic Redundancy Check)

- CRC is based on binary division
Data CRC
Data 00...0
n bits
Divisor
Data CRC Divisor n + 1 bits
Remainder Remainder
Zero, accept
CRC n bits
Nonzero, reject
Receiver Sender
Chapter 9: Error Detection and Correction

Detection 15/21
• CRC (cyclic redundancy check)
- Step to find CRC
+ Step 1: Append n 0s bit to the data unit.
The number n is one less than the (n+1) bits of
the divisor.
+ Step 2: This newly data unit is divided by
the divisor using binary division. The remainder
is the CRC.
+ Step 3: Replace n 0s bit by CRC (from step
2). Note that the CRC may consist of all 0s.
Chapter 9: Error Detection and Correction

Detection 16/21
• CRC (cyclic redundancy check)
- CRC Generator
1 0 0 1 0 0 0
0000
0 : 1 0 1 1 = 1 1 1 1 0 1 Data plus extra zeros. The
number of zeros is one
Quotient less than the number of
bits in the divisor
Divisor
1 1 1 1 0 1

1 1 0 1 1 0 0 1 0 0 0 0 0
1 1 0 1

1 0 0 0
1 1 0 1

1 0 1 0
Hình 9
1 1 0 1

1 1 1 0
1 1 0 1

When the leftmost bit of the 0 1 1 0

remainder is zero, we must use 0 0 0 0
0000 instead of the original divisor
1 1 0 0
1 1 0 1

0 0 1

Remainder
Chapter 9: Error Detection and Correction

Detection 17/21
• CRC (cyclic redundancy check)
- CRC Checker Quotient
Divisor Data plus CRC received
1 1 1 1 0 1

1 1 0 1 1 0 0 1 0 0 0 0 1
1 1 0 1

1 0 0 0
1 1 0 1

1 0 1 0
Hình 10
1 1 0 1

1 1 1 0
1 1 0 1

When the leftmost bit of the 0 1 1 0

remainder is zero, we must use 0 0 0 0
0000 instead of the original divisor
1 1 0 1
1 1 0 1

0 0 0

Result
Chapter 9: Error Detection and Correction

Detection 18/21

• CRC (cyclic redundancy check)

- Standard polynomials used in CRC divisor
CRC-12 CRC-16 CRC-ITU-T
x12 + x11 + x3 + x + 1 x16 + x15 + x2 + 1 x16 + x12 + x5 + 1
Hình 13
CRC-32
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
Chapter 9: Error Detection and Correction

Detection 19/21
• Checksum
Checksum Generator
- The checksum generator subdivides the
data unit into equal segments of n bits
(usually 8, 16)
- These segments are added together.
- Complement the result.
- That total is then appended to the end of
the original data unit
Chapter 9: Error Detection and Correction

Detection 20/21
• Checksum
Checksum Checker
- The receiver subdivides the data unit into
equal segments of n bits (same as the
generator) and adds all segments together
and complements the result.
- These segments are added together.
- Complement the result.
- If the result is 0s, the data is accepted,
otherwise, they are rejected
Chapter 9: Error Detection and Correction

Detection 21/21
• Checksum
Checksum detects all errors involving an
odd number of bits, as well as most errors
involving an even number of bits. However, if
one or more of bits of a segment are
damaged and the corresponding bit or bits
of opposite value in a second segment are
also damaged, the sums of those columns
will not change and the receiver will not
detect a problem.
Chapter 9: Error Detection and Correction

Error Correction 1/5

• There are two way:

- When an error is discovered, the receiver
can have the sender retransmit the entire
data unit
- Receiver can use an error-correcting code,
which automatically corrects certain error.
Chapter 9: Error Detection and Correction

Error Correction 2/5

• For example to correct a single-bit error in

an ASCII character, the error correction code
must determine which of the 7 bits has
changed. It requires enough redundancy bits
to show all 8 states.
Chapter 9: Error Detection and Correction

Error Correction 3/5

• Given a number of m data bits

r is redundancy bits
The length of the resulting code: m + r
r must be able to indicate at least
𝑚 + 𝑟 + 1 different states, therefor:
2  m  r 1
r
Chapter 9: Error Detection and Correction

Error Correction 4/5

Number of Number of Total bits

data bits redundancy (m+r)
(m) bits (r)
1 2 3
2 3 5
3 3 6
4 3 7
5 4 9
6 4 10
7 4 11
Chapter 9: Error Detection and Correction

Error Correction 5/5

• Hamming code