Error Detection
and Correction
• Types of Errors
• Detection
• Correction
Single-bit error
Multiple-bit error
Burst error
Error Detection -Redundancy
• VRC – Vertical Redundancy Check (Parity Check)
• LRC – Longitudinal Redundancy Check
• CRC – Cyclic Redundancy Check
• Checksum
VRC
Example:
11100111101111 1010010 1101100
11100111 11011110 10100101 11011000
VRC can detect all single-bit errors.
It can detect burst errors only if the total number
of errors in each data unit is odd.
LRC
11100111 11011101 00111001 10101001
11100111
11011101
00111001
10101001
LRC 10101010
11100111 11011101 00111001 10101001 10101010
If two bits in one data unit are damaged and two bits in exactly
the same positions in another data unit are also damaged.
Ex. : 11110000 11000011 changed to 01110001 01000010
LRC
VRC and LRC
Cyclic Redundancy Check (CRC)
• CRC is based on binary division
• Bit strings represented as polynomials with co ef. 0
and 1.
• K bit frame =>xk-1+…+1 (first and last co ef must be
1)
• Example
– 110001 => x5+x4+1
• Polynomial arithmetic is done module 2 i.e.
addition/subtraction = XOR operation
Binary Division
Figure 9-12
Polynomial
WCB/McGraw-Hill The McGraw-Hill Companies, Inc., 1998
Figure 9-13
Polynomial and Divisor
WCB/McGraw-Hill The McGraw-Hill Companies, Inc., 1998
Figure 9-14
Standard Polynomials
WCB/McGraw-Hill The McGraw-Hill Companies, Inc., 1998
• Given a 10-bit sequence 1010011110, and a
divisor of 1011, find the CRC.
Checksum
CheckSum
The sender follows these steps:
•The unit is divided into k sections, each of n bits.
•All sections are added.
•The sum is complemented and becomes the checksum.
•The checksum is sent with the data
The receiver follows these steps:
•The unit is divided into k sections, each of n bits.
•All sections are added to get the sum.
•The sum is complemented.
•If the result is zero, the data are accepted.
Example-4: CheckSum
Suppose the following block of 16 bits is to be sent using a checksum
of 8 bits.
10101001 00111001
The numbers are added
10101001
00111001
-------------
Sum 11100010
Checksum 00011101 ; complemented
The pattern sent is 10101001 00111001 00011101
Example-4 Continue
Now suppose the receiver receives the pattern sent in is
10101001 00111001 00011101
When the receiver adds the three sections, it will get all 1s,
which, after complementing, is all 0s and shows that there
is no error.
Error Correction
2r >= m+r+1, Here r=4
Hamming Code
• r1: 1,3,5,7,9,11
• r2: 2,3,6,7,10,11
• r4: 4,5,6,7
• r8: 8,9,10,11
Hamming Code
Hamming Code
Example of Hamming Code
10011100101
Single-bit error
Error
Detection
Hamming Distance
The Hamming distance between two words is the number of
differences between corresponding bits.