Data Communication and
Computer Networks
Error Correction
Ghulam Mustafa
Department of Computer Science
Riphah International University, Faisalabad Campus
[email protected]
Outline
Error detection techniques
Checksum
Cyclic redundancy check
Error correction technique (Hamming
Code)
2
Checksum
The sender’s end:
The data is divided into k segments
each of m bits
The segments are added using 1’s
complement arithmetic to get the sum
The sum is complemented to get the
checksum
The checksum segment is sent along
with the data segments
3
Sender
k=4, m =
8
10110011
10101011
01011010
11010101
4
Checksum
The receiver’s end:
all received segments are added using
1’s complement arithmetic to get the
sum
The sum is complemented.
If the result is zero, the received data is
accepted; otherwise discarded
5
Receiver
10110011
10101011
01011010
11010101
01110000
6
performance
The checksum detects all errors
involving an odd number of bits
It also detects most errors involving
even number of bits
7
Cyclic redundancy check
One of the most powerful and widely
used technique
Given a m-bit block of bit sequence the
sender generates n-bit sequence, known
as frame check sequence (FCS) so that
the resulting frame consisting of m + n
bits is exactly divisible by same
predetermined number
the receiver divides the incoming frame
by that number, and if there is no
remainder, assumer there was no error 8
Basic scheme for CRC
9
Figure Division in CRC encoder
10
Figure Division in the CRC decoder for two cases
11
Table A CRC code with C(7, 4)
12
Polynomials
All the values can be expressed as
polynomials of a dummy variable X
For example, for P = 11001 the
corresponding polynomial is X4+X3+1
Commonly used divisor polynomials are:
CRC-16 = X16 + X15 + X2 + 1
CRC-8 = X8 + X2 + X + 1
CRC-32 = X32 + X26 + X23 + X22 + X16 +
X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2
+X+1
13
Performance
CRC can detect all single-bit errors
CRC can detect all double-bit errors
CRC can detect any odd number of errors
CRC can detect all burst errors of less than the
degree of the polynomial.
CRC detects most of the larger burst errors
with a high probability.
For example CRC-12 detects 99.97% of errors
with a length 12 or more.
14
Error Correction
Error Correction can be handled in
two ways.
One is when an error is discovered; the
receiver can ask the sender retransmit
the entire data unit. This is known as
backward error correction.
In the other, receiver can use an error-
correcting code, which automatically
corrects certain errors. This is known as
forward error correction
15
Error Correction
use more redundancy in the
transmitted data to not only detect
but correct error in the received
data
Key Idea
Requirement for error detection: A
code in an error detecting code if
and only if the minimum distance
between any two code words is two
16
Error Correction
Requirement for error correction: For
a code to be error correcting the
minimum hamming distance
between any two code words must
be more than two.
Number of additional bits be such
that it can point the position of the
bit in error. If k is the no of
additional bits, then the condition is
2k >= m+k+1
17
Hamming Code
To each group of m information bits k
parity bits are added to form (m+k) bit
code
Location of each of the (m+k) digits is
assigned a decimal value.
The k parity bits are placed in positions
1, 2, …, 2k-1
18
Hamming Code
K parity checks are performed on
selected digits of each codeword
At the receiving end the parity bits are
recalculated. The decimal value of the k
parity bits provides the bit-position in
error, if any.
19
2k >= m+k+1
2k-1
C3 C2 C1
0 0 0
20
