Chapter 7 – Data Link Control Protocols Error Detection and Correction

by William Stallings Data can be corrupted during transmission.

Some applications require that errors be detected and
corrected.
• Data Communication need layer of logic Data Link
(Data Link Layer) above Physical, to manage Layer
exchange of data over a link
• Jobs done on Data link layer
– Error control
– Frame synchronization
– Flow control
– Addressing
– Control and data
– Link management

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2000

1 2

INTRODUCTION
Error Detection
Types of error
Redundancy
In a single-bit error, only 1 bit in the data unit has changed.
•Parity Check
•Cyclic Redundancy Check (CRC)
•Checksum
Figure 1 Single-bit error

A burst error means that 2 or more bits in the data unit have changed. Error Correction
Hamming Code

Figure 2 Burst error of length 8

3 4

1
BLOCK CODING Figure Datawords and codewords in 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.

An error-
detecting code
can detect only
the types of
errors for which
it is designed;
other types of Example 1
errors may
remain
undetected.
The 4B/5B block coding discussed in Chapter 4 is a good example
of this type of coding. In this coding scheme,
Figure 10.6 Process of error detection in block coding k = 4 and n = 5. As we saw, we have 2k = 16 datawords and 2n = 32
codewords. We saw that 16 out of 32 codewords are used for
message transfer and the rest are either used for other purposes or
unused.

5 6

Example.2
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.

Assume the sender encodes the dataword 01 as 011 and sends it to the receiver. Consider the
following cases:
Table 1 A code for error Table 2 A code for
1. The receiver receives 011. It is a valid codeword. The receiver extracts the dataword 01
detection (Example 2) error correction
from it.
(Example 3)
2. The codeword is corrupted during transmission, and 111 is received. This is not a valid
codeword and is discarded.
3. The codeword is corrupted during transmission, and 000 is received. This is a valid Example 3
codeword. The receiver incorrectly extracts the dataword 00. Two corrupted bits have
made the error undetectable. Let us add more redundant bits to Example 2 to see if the receiver can correct an
error without knowing what was actually sent. We add 3 redundant bits to the 2-bit
dataword to make 5-bit codewords. Assume the dataword is 01. The sender creates
the codeword 01011. The codeword is corrupted during transmission, and 01001 is
Table A code for error detection received. First, the receiver finds that the received codeword is not in the table. This
(Example 2) means an error has occurred. The receiver, assuming that there is only 1 bit
corrupted, uses the following strategy to guess the correct dataword.

7 8

2
Example 3 (continued)
1. Comparing the received codeword with the first codeword in the Hamming Distance
table (01001 versus 00000), the receiver decides that the first
codeword is not the one that was sent because there are two The Hamming distance between two words is the
different bits. number of differences between corresponding bits.
2. By the same reasoning, the original codeword cannot be the
third or fourth one in the table. The minimum Hamming distance is the smallest Hamming
3. The original codeword must be the second one in the table distance between all possible pairs in a set of words.
because this is the only one that differs from the received
Example 4
codeword by 1 bit. The receiver replaces 01001 with 01011 and
consults the table to find the dataword 01. Let us find the Hamming distance between two pairs of words.
Table 2 A code for
error correction
(Example 3) 1. The Hamming distance d(000, 011) is 2 because

2. The Hamming distance d(10101, 11110) is 3 because

9 10

Example 5 Example 7
The minimum Hamming distance for our first code scheme (Table 1) is 2. This code
Find the minimum Hamming distance of the coding scheme in guarantees detection of only a single error. For example, if the third codeword (101)
Table 1. 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
Solution We first find all Hamming distances.
codeword and the errors are not detected.
Example 8
Our second block code scheme (Table 2) has dmin = 3. This code can detect up to
The dmin in this case is 2. two errors. Again, we see that when any of the valid codewords is sent, two errors
create a codeword which is not in the table of valid codewords. The receiver
Example 6 cannot be fooled.

Find the minimum Hamming distance of the coding scheme in However, some combinations of three errors change a valid codeword to another
Table 2. valid codeword. The receiver accepts the received codeword and the errors are
undetected.
Solution We first find all the Hamming distances.

The dmin in this case is 3.

11 12

3
 Figure 8 Geometric concept for finding dmin in error detection Example 9
A code scheme has a Hamming distance dmin = 4. What is the error detection and
correction capability of this scheme?

To guarantee correction of
Solution
up to t errors in all cases, This code guarantees the detection of up to three errors
the minimum Hamming (s = 3), but it can correct up to one error. In other words,
distance in a block code if this code is used for error correction, part of its capability is wasted. Error
must be dmin = 2t + 1. correction codes need to have an odd minimum distance (3, 5, 7, . . . ).

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.

Figure 9 Geometric concept for finding dmin in error correction

13 14

3 LINEAR BLOCK CODES Example 10

Let us see if the two codes we defined in Table 1 and Table 2 belong to the class of
Almost all block codes used today belong to a subset called linear linear block codes.
block codes. A linear block code is a code in which the exclusive OR 1. The scheme in Table 1 is a linear block code
(addition modulo-2) of two valid codewords creates another valid because the result of XORing any codeword with any
other codeword is a valid codeword. For example, the
codeword. XORing of the second and third codewords creates the
A code word is written as C(n,m), fourth one.
n= size of codeword and 2. The scheme in Table 2 is also a linear block code.
m= size of dataword We can create all four codewords by XORing two
other codewords.

Example 11
In our first code (Table 1), the numbers of 1s in the nonzero codewords are 2, 2, and
2. So the minimum Hamming distance is dmin = 2. In our second code (Table 2), the
numbers of 1s in the nonzero codewords are 3, 3, and 4. So in this code we have dmin
= 3.

Table 1 A code for error Table 2 A code for error

detection C(3,2) correction C(5,2)

15 16

4
 Example 12
Simple Parity-Check Code Let us look at some transmission scenarios. Assume the sender sends the dataword
1011. The codeword created from this dataword is 10111, which is sent to the receiver.
A simple parity-check code is a single-bit error-detecting code in which We examine five cases:
n = k + 1 with dmin = 2.
A code word is written as C(n,m), 1. No error occurs; the received codeword is 10111.The syndrome is0. The dataword
n= size of codeword and 1011 is created.
m= size of dataword 2. One single-bit error changes a1 . The received codeword is 10011. The syndrome is
1. No dataword is created.
3. One single-bit error changes r0 . The received codeword is 10110. The syndrome is
1. No dataword is created.
4. An error changes r0 and a second error changes a 3 . The received codeword is
Table 3 00110. The syndrome is 0. The dataword 0011 is created at the receiver. Note tha here
Simple the dataword is wrongly created due to the syndrome value.
parity-check 5. Three bits—a3, a2, and a1—are changed by errors. The received codeword is 01011.
code C(5, 4) The syndrome is 1.The dataword is not created. This shows that the simple
parity check, guaranteed to detect one single error, can also find any odd number of
errors.

A simple parity-check code can detect an odd number of errors.

17 18

Two-dimensional parity-check code Two-dimensional parity-check code

A simple parity-check code can detect an odd number of errors.
Two Dimensional code can solve the problem

19 20

5
CYCLIC CODES
Cyclic codes are special linear block codes with one extra property. In
Cyclic Redundancy Check (CRC)
a cyclic code, if a codeword is cyclically shifted (rotated), the result is
another codeword.
Modulo 2 arithmetic uses
binary addition with no
Table A CRC code with C(7, 4) carries, which is just the XOR
operation. Binary subtraction
with no carries is also
interpreted as the XOR
operation: For example,

Figure Division in CRC encoder

21 22

Figure Division in the CRC decoder for two cases

23 24

6
 Figure A polynomial to represent a binary word

Figure CRC
division using
polynomials

25 26

Example 5
Polynomial selection It is obvious that we cannot choose x (binary 10) or x2 + x
(binary 110) as the polynomial because both are divisible
◼ A Polynomial should be selected to have at by x. However, we can choose x + 1 (binary 11) because
least the following two conditions it is not divisible by x, but is divisible by x + 1. We can
1. It should not be divisible by x also choose x2 + 1 (binary 101) because it is divisible by
◼ This Guarantees that all burst errors of a length equal x + 1 (binary division).
to the degree of the polynomial are detected
2. It should be divisible by x+1
◼ This Gaurantees that all burst errors affecting an odd
number of bits are detected

27 28

7
 CHECKSUM
Example 6
The last error detection method we discuss here is called the checksum.
The CRC-12
The checksum is used in the Internet by several protocols although not
x12 + x11 + x3 + x + 1 at the data link layer. However, we briefly discuss it here to complete
our discussion on error checking
which has a degree of 12, will detect all burst errors affecting an
odd number of bits, will detect all burst errors with a length less Example 18
than or equal to 12, and will detect, 99.97 percent of the time, burst
errors with a length of 12 or more. Suppose our data 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
Table compares the result with the sum. If the two are the same, the
Standard
polynomials receiver assumes no error, accepts the five numbers, and discards
the sum. Otherwise, there is an error somewhere and the data are
not accepted.

29 30

Example 19 Example 21
We can make the job of the receiver easier if we send the negative
How can we represent the number −6 in one’s complement
(complement) of the sum, called the checksum. In this case, we
arithmetic using only four bits?
send (7, 11, 12, 0, 6, −36). The receiver can add all the numbers
received (including the checksum). If the result is 0, it assumes no Solution
error; otherwise, there is an error. In one’s complement arithmetic, the negative or complement of a
number is found by inverting all bits. Positive 6 is 0110; negative 6
Example 20 is 1001. If we consider only unsigned numbers, this is 9. In other
How can we represent the number 21 in one’s complement words, the complement of 6 is 9. Another way to find the
arithmetic using only four bits? complement of a number in one’s complement arithmetic is to
subtract the number from 2n − 1 (16 − 1 in this case).

Solution
The number 21 in binary is 10101 (it needs five bits). We can wrap
the leftmost bit and add it to the four rightmost bits. We have (0101
+ 1) = 0110 or 6.

31 32

8
Example 22
Figure Example 22
Let us redo Exercise 19 using one’s complement arithmetic. Figure
shows the process at the sender and at the receiver. The sender
initializes the checksum to 0 and adds all data items and the checksum
(the checksum is considered as one data item and is shown in color).
The result is 36. However, 36 cannot be expressed in 4 bits. The extra
two bits are wrapped and added with the sum to create the wrapped
sum value 6. In the figure, we have shown the details in binary. The
sum is then complemented, resulting in the checksum value 9 (15 − 6 =
9). The sender now sends six data items to the receiver including the
checksum 9.
The receiver follows the same procedure as the sender. It adds all data
items (including the checksum); the result is 45. The sum is wrapped
and becomes 15. The wrapped sum is complemented and becomes 0.
Since the value of the checksum is 0, this means that the data is not
corrupted. The receiver drops the checksum and keeps the other data
items. If the checksum is not zero, the entire packet is dropped.

33 34

Sender site: Error correcting codes

1. The message is divided into 16-bit words.
2. The value of the checksum word is set to 0. ◼ For Error correction we have to distinguish between
3. All words including the checksum are added using one’s only two states
complement addition. ◼ Error
4. The sum is complemented and becomes the checksum. OR
◼ No Error
5. The checksum is sent with the data.
◼ Suppose there is a single bit data. A bit has two states
Receiver site: ◼ 1
◼ 0
1. The message (including checksum) is divided into 16-bit
◼ So a Single bit parity can work, so total size of
words. codeword =2
2. All words are added using one’s complement addition. ◼ Example of Even parity
3. The sum is complemented and becomes the new 11
checksum.
4. If the value of checksum is 0, the message is accepted;
00
Data Bit Parity Bit
otherwise, it is rejected.

35 36

9
 Error correcting codes Error correcting codes
◼ Let m be the length of data and r be the length of redundancy bits
required to correct m bits
◼ But if we want to correct the error in a longer data ,two states ◼ So the total number of bits in a transmittable unit is m+r
are not enough ◼ But what if error occurs in redundant bit itself??
◼ For example for a 7 bit data => it will reach destination in one ◼ Then r must be able to indicate atleast m+r+1 different states
of the following states (Assuming at most 1 bit error occurs) ◼ 2
(r) >= m+r+1
Number of Number of Total
◼ No error bits
data bits redundant bits
◼ Error in position 1 m r m+r
◼ Error in position 2 8 Possibilities
◼ . 1 2 3
◼ . 2 3 5
◼ Error in position 7 Table : Data and
◼ So there are 8 different states redundancy bits 3 3 6

◼ To Correct a single bit error in a 7 bit word ,the error 4 3 7

correction code must determine which of 7 bit is in error 5 4 9
◼ 3 bits are required to give only 8 possibilities 6 4 10
◼ In general r bits indicates 2(r) different states
7 4 11

37 38

Creating Code word

◼ The key to the Hamming Code is the use of extra parity bits to allow the
identification of a single error. Create the code word as follows:
◼ Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32,
64, etc.)
◼ All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, Example of redundancy bit calculation
13, 14, 15, 17, etc.) Each parity bit calculates the parity for some of the bits in the code Suppose 7 bit data= 1001101
word. The position of the parity bit determines the sequence of bits that it alternately
checks and skips.
Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,...)
Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,...)
Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc.
(4,5,6,7,12,13,14,15,20,21,22,23,...)
Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,...)
Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-
95,...)
Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-
127,160-191,...)
etc.
Positions of redundancy bits in Hamming code => in orders of 2 to the power

39 40

10
 Error correction using Hamming code
Burst error correction using Hamming code

Direction of Transmission in the form of signal

41 42

Burst error correction example

Provided a burst error of M bits is less then the length of a unit N i.e. (M<N)

Table 4
Hamming code
C(7, 4)

Hamming code can easily be implemented on Hardware and errors can easily be
corrected out before handing it over to the receiver

43 44

11