Error Detection and Correction
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
4.1
Overview of Error detection and correction
Error Detection and Correction
Data can be corrupted during transmission. Some applications require that errors be detected
and corrected.
Types of Errors
Single-Bit Error
Burst Error
4.2
Single-Bit Error
The term single-bit error means that only 1 bit of a given data unit (such as a byte, character,
or packet) is changed from 1 to 0 or from 0 to 1.
4.3
Burst Error
The term burst error means that 2 or more bits in the data unit have
changed from 1 to 0 or from 0 to 1.
4.4
Redundancy
Able to detect or correct errors, we need to send some extra bits with
our data. These redundant bits are added by the sender and removed by the
receiver.
Forward Error Correction Versus Retransmission
Forward error correction is the process in which the receiver
tries to guess the message by using redundant bits.
4.5
Block coding
Definition:
• It divide our message into blocks, each of k bits, called datawords.
• We add r redundant bits to each block to make the length n = k + r. The
resulting n-bit blocks are called codewords.
4.6
Error Detection
To detect the error by using block coding? If the following two conditions are
met, the receiver can detect a change in the original codeword.
• The receiver has (or can find) a list of valid codewords.
• The original codeword has changed to an invalid one
4.7
Assume the sender encodes the dataword 01 as 011 and sends it to the receiver.
Consider the following cases:
1. The receiver receives 011. It is a valid codeword. The receiver extracts the
dataword 01
from it.
2. The codeword is corrupted during transmission, and 111 is received (the
leftmost bit is corrupted). This is not a valid codeword and is discarded.
An error-detecting code can detect only the types of errors for which it is designed other types of errors may remain undetected
4.8
Error Correction
• In error detection, the receiver needs to know only that the received codeword is
invalid;
• In error correction the receiver needs to find (or guess) the original codeword
sent.
4.9
Hamming distance
• The Hamming distance between two words (of the same size) is the number of
differences between the corresponding bits. We show the Hamming distance
between two words x and y as d(x, y).
• The Hamming distance can easily be found if we apply the XOR operation on the
two words and count the number of ls in the result.
Let us find the Hamming distance between two pairs of words.
1. The Hamming distance d(000, 011) is 2 because 000 XOR 011 is 011 (two 1s).
4.10
Minimum Hamming Distance
• The minimum Hamming distance is the smallest Hamming distance between
all possible pairs in set of words We use dmin to define the minimum
Hamming distance in a coding scheme.
•We
To first
findfind
thisallvalue,
the Hamming
we finddistances.
the Hamming distances between all words and
d(00000, 01011) = 3
select the smallest one.
d(01011, 10101) = 4
d(00000, 10101) = 3
d(01011, 11110) = 3
d(00000, 11110) = 4
4.11
d(10101, 11110)= 3
Three Parameters
• Any coding scheme needs to have at least three parameters: the codeword size n, the
dataword size k, and the minimum Hamming distance dmin. A coding scheme C is written
as C(n, k)
Hamming Distance and Error
• The relationship between the Hamming distance and errors occurring during transmission.
• When a codeword is corrupted during transmission, the Hamming distance between the sent
and received code- words is the number of bits affected by the error.
• if the codeword 00000 is sent and 01101 is received, 3 bits are in error and the Hamming
distance between the two is d(00000, 01101) = 3.
4.12
Minimum Distance for Error Detection
• To guarantee the detection of up to s errors in all cases, the minimum
Hamming distance in a block code must be dmin = S+ 1.
• If s errors occur during transmission, the Hamming distance between the sent
codeword and received codeword is s. If our code is to detect up to s errors, the
minimum distance between the valid codes must be s + 1
Minimum Distance for Error Correction
• Error correction is more complex than error detection; a decision is
involved.
• When a received codeword is not a valid codeword, the receiver needs to decide
which valid codeword was actually sent.
To guarantee correction of up to t errors in all cases, the minimum
4.13
