Chapter 10
Error
Detection
And
Correction
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Chapter 10: Outline
10.1 INTRODUCTION
10.2 BLOCK CODING
10.3 CYCLIC CODES
10.4 CHECKSUM
10.5 FORWARD ERROR CORRECTION
10-1 INTRODUCTION
Let us first discuss some issues
related, directly or indirectly, to
error detection and correction.
10.3
10.10.1 Types of Errors
Whenever bits flow from one point to another, they
are subject to unpredictable changes because of
interference. This interference can change the shape
of the signal. 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 10. The term burst error means that 2 or more
bits in the data unit have changed from 1 to 0 or
from 0 to 10. Figure 10.1 shows the effect of a
single-bit and a burst error on a data unit.
10.4
Figure 10.1: Single-bit and burst error
10.5
10.10.2 Redundancy
The central concept in detecting or correcting errors
is redundancy. To be 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. Their presence allows the receiver to
detect or correct corrupted bits.
10.6
10.10.3 Detection versus Correction
The correction of errors is more difficult than the
detection. In error detection, we are only looking to
see if any error has occurred. The answer is a simple
yes or no. We are not even interested in the number
of corrupted bits. A single-bit error is the same for
us as a burst error. In error correction, we need to
know the exact number of bits that are corrupted
and, more importantly, their location in the message.
10.7
10.10.4 Coding
Redundancy is achieved through various coding
schemes. The sender adds redundant bits through a
process that creates a relationship between the
redundant bits and the actual data bits. The receiver
checks the relationships between the two sets of bits
to detect errors. The ratio of redundant bits to data
bits and the robustness of the process are important
factors in any coding scheme.
10.8
10-2 BLOCK CODING
In block coding, we 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. How the extra r bits
are chosen or calculated is
something
we will discuss later.
10.9
10.2.1 Error Detection
How can errors be detected by using block coding?
If the following two conditions are met, the receiver
can detect a change in the original codeword.
10. The receiver has (or can find) a list of valid
codewords.
2. The original codeword has changed to an invalid
one.
10.10
Figure 10.2: Process of error detection in block coding
10.11
Example 10.1
Let us assume that k = 2 and n = 3. Table 10.1 shows the list
of datawords and codewords. Later, we will see how to
derive a codeword from a dataword.
Table 10.1: A code for error detection in Example
10.1
10.12
Example 10.2
Let us find the Hamming distance between two pairs of
words.
10.13
Figure 10.3: Geometric concept explaining dmin in error
detection
10.14
Example 10.3
The minimum Hamming distance for our first code scheme
(Table 10.1) is 2. This code guarantees detection of only a
single error. For example, if the third codeword (101) is sent
and one error occurs, the received codeword does not match
any valid codeword. If two errors occur, however, the
received codeword may match a valid codeword and the
errors are not detected.
10.15
Example 10.4
A code scheme has a Hamming distance dmin = 4. This code
guarantees the detection of up to three errors (d = s + 1 or
s = 3).
10.16
Example 10.5
The code in Table 10.1 is a linear block code because the
result of XORing any codeword with any other codeword is
a valid codeword. For example, the XORing of the second
and third codewords creates the fourth one.
10.17
Example 10.6
In our first code (Table 10.1), the numbers of 1s in the
nonzero codewords are 2, 2, and 2. So the minimum
Hamming distance is dmin = 2.
10.18
Table 10.2: Simple parity-check code C(5, 4)
10.19
Figure 10.4: Encoder and decoder for simple parity-
check code
10.20
Example 10.7
Let us look at some transmission scenarios. Assume the
sender sends the dataword 10110. The codeword created
from this dataword is 10111, which is sent to the receiver.
We examine five cases:
10.21
10-3 CYCLIC CODES
Cyclic codes are special linear
block codes with one extra
property. In a cyclic code, if a
codeword is cyclically shifted
(rotated), the result is another
codeword. For example, if
1011000 is a codeword and we
cyclically left-shift, then 0110001
is also a codeword.
10.22
10.3.1 Cyclic Redundancy Check
We can create cyclic codes to correct errors.
However, the theoretical background required is
beyond the scope of this book. In this section, we
simply discuss a subset of. cyclic codes called the
cyclic redundancy check (CRC), which is used in
networks such as LANs and WANs.
10.23
Table 10.3: A CRC code with C(7, 4)
10.24
Figure 10.5: CRC encoder and decoder
10.25
Figure 10.6: Division in CRC encoder
10.26
Figure 10.7: Division in the CRC decoder for two cases
10.27
10.3.2 Polynomials
A better way to understand cyclic codes and how
they can be analyzed is to represent them as
polynomials. A pattern of 0s and 1s can be
represented as a polynomial with coefficients of 0
and 10. The power of each term shows the position
of the bit; the coefficient shows the value of the bit.
Figure 10.8 shows a binary pattern and its
polynomial representation.
10.28
Figure 10.8: A polynomial to represent a binary word
10.29
10.3.3 Encoder Using Polynomials
Now that we have discussed operations on
polynomials, we show the creation of a codeword
from a dataword. Figure 10.9 is the polynomial
version of Figure 10.6. We can see that the process
is shorter.
10.30
Figure 10.9: CRC division using polynomials
10.31
10.3.4 Cyclic Code Analysis
We can analyze a cyclic code to find its capabilities
by using polynomials. We define the following,
where f(x) is a polynomial with binary coefficients.
10.32
Example 10.8
Which of the following g(x) values guarantees that a single-
bit error is caught? x + 1, x3 and 1
Solution
10.33
Figure 10.10: Representation of isolated single-bit
errors
10.34
•All burst errors with L r will be detected.
•All burst errors with L = r + 1 will be detected with probability 1 – (1/2)r–
1
.
•All burst errors with L > r + 1 will be detected with probability 1 – (1/2)r.
10.35
Example 10.9
Find the suitability of the following generators in relation to
burst errors of different lengths: x 6 + 1, x18 + x7 + x + 1, and
x32 + x23 + x7 + 10.
Solution
10.36
Example 10.10
Find the status of the following generators related to two
isolated, single-bit errors: x + 1, x 4 + 1, x7 + x6 + 1, and
x15 + x14 + 1
Solution
10.37
Table 10.4: Standard polynomials
10.38
10.3.5 Advantages of Cyclic Codes
We have seen that cyclic codes have a very good
performance in detecting single-bit errors, double
errors, an odd number of errors, and burst errors.
They can easily be implemented in hardware and
software. They are especially fast when implemented
in hardware. This has made cyclic codes a good
candidate for many networks.
10.39
10.3.6 Other Cyclic Codes
The cyclic codes we have discussed in this section
are very simple. The check bits and syndromes can
be calculated by simple algebra. There are, however,
more powerful polynomials that are based on
abstract algebra involving Galois fields. These are
beyond the scope of this book. One of the most
interesting of these codes is the Reed-Solomon code
used today for both detection and correction.
10.40
10.3.7 Hardware Implementation
One of the advantages of a cyclic code is that the
encoder and decoder can easily and cheaply be
implemented in hardware by using a handful of
electronic devices. Also, a hardware implementation
increases the rate of check bit and syndrome bit
calculation. In this section, we try to show, step by
step, the process. The section, however, is optional
and does not affect the understanding of the rest of
the chapter.
10.41
10-4 CHECKSUM
Checksum is an error-detecting
technique that can be applied to
a message of any length. In the
Internet, the checksum technique
is mostly used at the network and
transport layer rather than the
data-link layer. However, to make
our discussion of error detecting
techniques complete, we discuss
the checksum in this chapter.
10.42
Figure 10.15: Checksum
10.43
10.4.1 Concept
The idea of the traditional checksum is simple. We
show this using a simple example.
10.44
Example 10.11
Suppose the message is a list of five 4-bit numbers that we
want to send to a destination. In addition to sending these
numbers, we send the sum of the numbers. For example, if
the set of numbers is (7, 11, 12, 0, 6), we send (7, 11, 12, 0,
6, 36), where 36 is the sum of the original numbers. The
receiver adds the five numbers and compares the result with
the sum. If the two are the same, the receiver assumes no
error, accepts the five numbers, and discards the sum.
Otherwise, there is an error somewhere and the message not
accepted.
10.45
Example 10.12
In the previous example, the decimal number 36 in binary is
(100100)2. To change it to a 4-bit number we add the extra
leftmost bit to the right four bits as shown below.
Instead of sending 36 as the sum, we can send 6 as the sum
(7, 11, 12, 0, 6, 6). The receiver can add the first five
numbers in one’s complement arithmetic. If the result is 6,
the numbers are accepted; otherwise, they are rejected.
10.46
Example 10.13
Let us use the idea of the checksum in Example 10.12. The
sender adds all five numbers in one’s complement to get the
sum = 6. The sender then complements the result to get the
checksum = 9, which is 15 − 6. Note that 6 = (0110)2 and
9 = (1001)2; they are complements of each other. The
sender sends the five data numbers and the checksum (7, 11,
12, 0, 6, 9). If there is no corruption in transmission, the
receiver receives (7, 11, 12, 0, 6, 9) and adds them in one’s
complement to get 15 (See Figure 10.16).
10.47
Figure 10.16: Example 10.13
10.48
Table 10.5: Procedure to calculate the traditional
checksum
10.49
