5/15/2024
Chapter 9
Error Detection
and Correction
• Types of Errors
• Detection
• Correction
« Networks must be able to transfer data from one device to
another with complete accuracy.
« 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.
1
5/15/2024
Chapter 9: Error Detection and Correction
Error Detection and Correction
Chapter 9: Error Detection and Correction
9.1 Types of Errors 1/4
Errors
Single-bit Burst
2
5/15/2024
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 10 or 01)
• Least likely type of error in serial data transmission.
• Can happen if we are sending data using parallel transmission.
«If data is sent at 1Mbps then each bit lasts only 1/1,000,000 sec. or 1 μs.
«For a single-bit error to occur, the noise must have a duration of only 1 μs,
which is very rare.
Chapter 9: Error Detection and Correction
Types of Errors 3/4
Burst error
• Burst Error: Two or more bit are 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.
• Burst error is most likely to occur in a serial transmission.
• The number of bits affected depends on the data rate and duration of
noise.
3
5/15/2024
Chapter 9: Error Detection and Correction
Types of Errors 4/4
«Burst error is most likely to happen in serial transmission since the
duration of noise is normally longer than the duration of a bit.
«The number of bits affected depends on the data rate and duration
of noise.
âIf data is sent at rate = 1Kbps then a noise of 1/100 sec can affect 10 bits.
(1/100)*1000=10
âIf same data is sent at rate = 1Mbps then a noise of 1/100 sec can affect
10,000 bits.(1/100)*106
Chapter 9: Error Detection and Correction
Detection 1/21
Error detection means to decide whether the received data is
correct or not without having a copy of the original message.
Error detection uses the concept of redundancy, which means
adding extra bits for detecting errors at the destination.
• Redundancy
4
5/15/2024
Chapter 9: Error Detection and Correction
Detection 2/21
• There are four types of redundancy checks used in data
communications
Chapter 9: Error Detection and Correction
Detection 3/21
• VRC (Vertical Redundancy Check)
- The most common and least expensive mechanism for error
detection is the VRC, often called a parity check.
A redundant bit is appended to every data
unit so that the total number of 1s in the
unit (including the VCR bit) becomes
even. (if the system is checking for even
parity)
5
5/15/2024
Chapter 9: Error Detection and Correction
Detection 4/21
• VRC (Vertical Redundancy Check)
Even-parity circuit
d0
d1
d2
d3 VRC
d4
d5
d6
1
1
0 1
1
0 1
0 1
0
0
1
1
Chapter 9: Error Detection and Correction
Detection 5/21
• VRC ( vertical redundancy check)
Parity checking
VRC
circuit
d0
d1
d2
E
d3
d4
1
R1
d5 R
d6
1
12
0
1 0
D1
0 LED
0 0
0
0 1 0
2
E
0
0
1
1 R1
R
1
12
D1
LED
2
6
5/15/2024
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 Redundancy bits bit
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)
7
5/15/2024
Chapter 9: Error Detection and Correction
Detection 8/21
• LRC (longitudinal redundancy check)
Generate LRC
Chapter 9: Error Detection and Correction
Detection 9/21
• LRC (longitudinal redundancy check)
LRC Checking
8
5/15/2024
Chapter 9: Error Detection and Correction
Detection 10/21
• LRC (longitudinal redundancy check)
LRC Checking
Chapter 9: Error Detection and Correction
Detection 11/21
• LRC (longitudinal redundancy check)
LRC Checking
9
5/15/2024
Chapter 9: Error Detection and Correction
Detection 12/21
• LRC (longitudinal redundancy check)
LRC Checking
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 and two bits in
exactly the same positions, the LRC checker will not detect an error
10
5/15/2024
Chapter 9: Error Detection and Correction
VRC and LRC
Chapter 9: Error Detection and Correction
Detection 14/21
• CRC (Cyclic Redundancy Check)
- CRC is based on binary division
11
5/15/2024
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 new 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
Binary Division
12
5/15/2024
Chapter 9: Error Detection and Correction
Detection 16/21
• CRC (cyclic redundancy check)
- CRC Generator
Chapter 9: Error Detection and Correction
Detection 17/21
• CRC (cyclic redundancy check)
- CRC Checker
13
5/15/2024
Chapter 9: Error Detection and Correction
• M(x)=1101011011
1100001010
• C(x)=10011;
--------------
• k=4 10011 /11010110110000
10011
-----
10011
10011
-----
10110
10011
-----
10100
10011
-----
1110
• P(x) = 1101011011 1110
27
Chapter 9: Error Detection and Correction
Detection 18/21
• CRC (cyclic redundancy check)
- Standard polynomials used in CRC divisor
Polynomial and Divisor
14
5/15/2024
Chapter 9: Error Detection and Correction
• All single-bit errors, as long as the xk and x0 terms have non-zero
coefficients.
• All double-bit errors, as long as G(x) contains a factor with at least
three terms
• Any odd number of errors, as long as G(x) contains the factor (x +
1)
• Any ‘burst’ error (i.e., sequence of consecutive error bits) for
which the length of the burst is less than k bits.
• Most burst errors of larger than k bits can also be detected
29
Chapter 9: Error Detection and Correction
9.6 Checksum
15
5/15/2024
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.
- C o m p l e m e n t t h e r e s u l t . ( o n e ’s
complement)
- That total is then appended to the end of
the original data unit
Chapter 9: Error Detection and Correction
16
5/15/2024
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.
17
5/15/2024
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.
18
5/15/2024
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:
2r m r 1
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
19
5/15/2024
Chapter 9: Error Detection and Correction
Error Correction 5/5
• Hamming code
Chapter 9: Error Detection and Correction
Hamming Code
20
5/15/2024
Chapter 9: Error Detection and Correction
Hamming Code
Example of Hamming Code
Chapter 9: Error Detection and Correction
Hamming Code
Single-bit error
21
5/15/2024
Chapter 9: Error Detection and Correction
Hamming Code
Error
Detection
22