ITT400

Introduction To Data Communication

and Networking

Chapter 6
Error Detection and
Correction

Mazlan Osman, FSKM, UiTM (Terengganu) 2014

 8-1 INTRODUCTION

• Network must be able to transfer data with

complete accuracy.
• But data can be corrupted during
transmission.
• Some mechanism required to detect and
correct errors.

8.2
 TYPES OF ERROR
Single-Bit Error
• Only 1 bit in the data unit has changed from 1
to 0 or from 0 to 1.

Figure 8.1 Single-bit error

8.3
 Burst Error

• 2 or more bits in the data unit have changed

from 1 to 0 or from 0 to 1

8.4 Figure 8.2 Burst error of length 8

 REDUNDANCY CONCEPT
• Redundancy concept – adding extra bits to
original data by the sender in order to detect or
correct errors.

DETECTION VS CORRECTION
• In error detection, just to see if any error has
occurred. Numbers of error is not important
• While in error correction, need to know the
exact number of bits that are corrupted.
Number of the errors are important

8.5
 MODULAR-2 ARITHMETIC
• Use XOR (exclusive OR) operation for both
addition and subtraction.
Adding : 0+0=0 0+1=1 1+0=1 1+1=0
Subtracting : 0 – 0 = 0 0–1=1 1–0=1 1–1=0

8.6 Figure 8.4 XORing of two single bits or two words

 HAMMING DISTANCE
• The Hamming distance between two words (of the same
size) is the number of differences between corresponding
bits.
• Example 8.4
Let us find the Hamming distance between two pairs of words.
1. The Hamming distance d(000, 011) is 2 because

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

• What is minimum Hamming distance? (reading

yourself).
8.7
 8-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.

Figure 8.5 Datawords and codewords in block coding

8.8
 ERROR DETECTION

Figure 8.6 Process of error detection in block coding

8.9
 8-3 LINEAR BLOCK CODES

• Almost all block codes used today belong to

a subset called linear block codes.
• In a linear block code, the exclusive OR
(XOR) of any two valid codewords
creates another valid codeword.

8.10
 Figure 8.10 Encoder and decoder for simple parity-check code

8.11
8.12
8.13
TYPES OF LINEAR BLOCK CODES

Simple Parity-Check Code

• A simple parity-check code is a single-bit
error-detecting code in which n = k + 1 with
dmin = 2
• The extra bit, called the parity bit, is selected to
make the total number of 1s in the codeword
even or odd.
• A simple parity-check code can detect either an
even or odd number of errors

8.14
 • Example 8.2
Let us assume that k = 2 and n = 3. Table 8.1 shows the list of datawords and
codewords. Later, we will see how to derive a codeword from a dataword
Datawords Codewords
00 000
01 011 Table 8.1 A code C(3,2)
10 101 for error detection
11 110

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 syndrome is 0. The

receiver extracts the dataword 01 from it

2.The codeword is corrupted during transmission, and 111 is received. The
syndrome is 1. This is not a valid codeword and is discarded.
3.The codeword is corrupted during transmission, and 000 is received. This
is a valid codeword. The receiver incorrectly extracts the dataword 00. It
means burst error can not be detected.
8.15
 Table 10.3 Simple parity-check code C(5, 4)

10.16
 • Example 8.12
This example refer to Table 10.3. Assume the sender sends the dataword
1011. The codeword created from this dataword is 10111, which is sent
to the receiver. We examine five cases:
1. No error occurs; the received codeword is 10111. The syndrome is 0.
The dataword 1011 is created.
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 a3. The received
codeword is 00110. The syndrome is 0. The dataword 0011 is created
at the receiver. Note that here the dataword is wrongly created due to
the syndrome value.
5. Three bits—a3, a2, and a1—are changed by errors. The received
codeword is 01011. The syndrome is 1. The dataword is not created.
This shows that the simple parity check, guaranteed to detect one
single error and also find any odd number of errors

8.17
 • A better approach is the two-dimensional parity check
• A block of bits is organized in a table (rows and columns).
• At first, the parity bit is calculated for each data unit.
• Second, the parity bit is organized into a table.
• This method increases the likelihood of detecting burst errors.

8.18
8.19 Figure 8.11 Two-dimensional parity-check code
 Hamming Codes
• Originally designed with dmin = 3, which means that they can detect
up to two errors or correct one single error
• The relationship between m and n in these codes is n = 2m − 1 and
k = n – m. the number of check bits r = m. For example, if m = 3, then
n = 7 and k = 4. This is Hamming code C(7,4) with dmin = 3

8.20 Table 8.4 Hamming code C(7, 4)

 Figure 8.12 The structure of the encoder and decoder for a Hamming code

8.21
 Table 8.5 Logical decision made by the correction logic analyzer

• Example 8.13
Let us trace the path of three datawords from the sender to the
destination:
1. The dataword 0100 becomes the codeword 0100011. The codeword
0100011 is received. The syndrome is 000, the final dataword is 0100.
2. The dataword 0111 becomes the codeword 0011001. The syndrome is
011. After flipping b2 (changing the 1 to 0), the final dataword is 0111.
3. The dataword 1101 becomes the codeword 1101000. The syndrome is
101. After flipping b0, we get 0000, the wrong dataword. This shows
that our code cannot correct two errors

8.22
 8-4 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.

8.23
CYCLIC REDUNDANCY CHECK
• Used in networks such as LANs and WANs

Table 8.6 A CRC code with C(7, 4)

8.24
 Figure 8.14 CRC encoder and decoder

8.25
 Encoder

Figure 8.15 Division in CRC encoder

8.26
 Decoder

Figure 8.16 Division in the CRC decoder for two cases

8.27
 Advantages

• CRC can detect all burst errors that affect

an odd number of bits
• CRC can detect all burst errors of length
less than or equal to the degree of the
polynomial

8.28
 Polynomials
 Used to represent CRC divisor
 Useful because
 Short
 Can be used mathematically
 Divisor/polynomial should have the
following properties
 Should not be divisible by x
 Should be divisible by x+1

8.29
 Polynomials representing divisors

• All burst errors of a length equal to the

degree of the polynomial are detected
• All burst errors affecting an odd number of
bits are detected

8.30
 Standard Polynomials

Name Polynomial Application

CRC-8 x8 + x2 + x + 1 ATM header
x10 + x9 + x5 + x4 + x
CRC-10 ATM AAL
2
+1
ITU-16 x16 + x12 + x5 + 1 HDLC
x32 + x26 + x23 + x22
+ x16 + x12 + x11 +
ITU-32 LANs
x10 + x8 + x7 + x5 +
x4 + x2 + x + 1

8.31
 8-5 CHECKSUM

• The checksum is used in the Internet by

several protocols although not at the data
link layer.
• Like linear and cyclic codes, the
checksum is based on the concept of
redundancy

8.32
 ONE’S COMPLEMENT
• Example 8.20
How can we represent the number 21 in one’s complement arithmetic using
only four bits?
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

• Example 8.21
How can we represent the number −6 in one’s complement arithmetic using
only four bits?
Solution
In one’s complement arithmetic, the negative or complement of a number is
found by inverting all bits. Positive 6 is 0110; negative 6 is 1001. If we consider
only unsigned numbers, this is 9. In other words, the complement of 6 is 9.
Another way to find the complement of a number in one’s complement
arithmetic is to subtract the number from 2 n − 1 (16 − 1 in this case).

8.33
 ONE’S COMPLEMENT

8.34
 Figure 8.24 Example 8.22
8.35
 ONE’S COMPLEMENT
• Suppose the following block of 16 bits is to be sent using a checksum of
8 bits.
• 10101001 00111001
• The numbers are added using one’s complement
• 10101001
• 00111001
------------
Sum 11100010
• Checksum 00011101
• The pattern sent is 10101001 00111001 00011101

8.36
 ONE’S COMPLEMENT
• Now suppose the receiver receives the pattern sent in Example 7 and
there is no error.
• 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.
10101001
00111001
00011101
• Sum 11111111
• Complement 00000000 means that the pattern is OK.

8.37
 ONE’S COMPLEMENT
• Now suppose there is a burst error of length 5 that affects 4 bits.
10101111 11111001 00011101
• When the receiver adds the three sections, it gets
10101111
11111001
00011101
• Partial Sum 1 11000101
• Carry 1
• Sum 11000110
• Complement 00111001 the pattern is corrupted.

8.38
 INTERNET CHECKSUM
• Sender site:
1. The message is divided into 16-bit words.
2. The value of the checksum word is set to 0.
3. All words including the checksum are added using one’s complement
addition.
4. The sum is complemented and becomes the checksum.
5. The checksum is sent with the data.

• Receiver site:
1. The message (including checksum) is divided into 16-bit words.
2. All words are added using one’s complement addition.
3. The sum is complemented and becomes the new checksum.
4. If the value of checksum is 0, the message is accepted; otherwise, it is
rejected.

8.39
 • Example 8.23
Let us calculate the checksum for a text of 8 characters (“Forouzan”). The
text needs to be divided into 2-byte (16-bit) words. We use ASCII (see
Appendix A) to change each byte to a 2-digit hexadecimal number. For
example, F is represented as 0x46 and o is represented as 0x6F. Figure 8.25
shows how the checksum is calculated at the sender and receiver sites. In
part a of the figure, the value of partial sum for the first column is 0x36. We
keep the rightmost digit (6) and insert the leftmost digit (3) as the carry in the
second column. The process is repeated for each column. Note that if there is
any corruption, the checksum recalculated by the receiver is not all 0s. We
leave this an exercise.

8.40
 Figure 8.25 Example 8.23

8.41
 Advantages Vs Disadvantage
Advantages
• Checksum can detects all errors involving an
odd number of bits as well as most errors
involving an even number of bits

Disadvantages
• The checksum cannot detect errors when one or
more bits of a segment are damaged and the
corresponding bit or bits of opposite value in a
second segment are also damaged

8.42