ERROR DETECTION

CHAPTER 8

1
Lesson Outcomes

• At the end of this lesson, the students should be able

to:
– Differentiate between two types of errors
– Understand the concept of redundancy and
modular arithmetic
– Differentiate between three types of error
detection method
– Perform error detection process using all three
types of error detection method
2
Introduction

• Networks must be able to transfer data from one

device to another with acceptable accuracy
• Any time data can become corrupted during
transmission
• Many factors can alter one or more bits of a message
• Reliable systems must have a mechanism for
detecting and correcting errors in data
communication

3
  Only one bit given data
Types of unit is changed from 1
to 0 or from 0 to 1

Errors  Occur in parallel

transmission (between
CPU and memory)

Single-bit error
 2 or more bits in the
data unit have changed
from 1 to 0 or from 0
to 1
 The length of the burst Burst error
is measured from the
first corrupted bit to
the last corrupted bit
 Occur in serial
transmission
4
 Single-bit error

Burst error of length 5

Image source: Data Communications

5
And Networking, Forouzan
Redundancy Concept

• Error detection uses the concept of redundancy,

which means adding extra bits for detecting errors at
the destination – allow the receiver to detect and
correct corrupted bits
• Error detection – to see if any error has occurred

6
Modular Arithmetic

• Only a limited range of integers is used

• Modular arithmetic used in error detection and
correction is modulo-2 arithmetic – only integer 0
and 1 are used
• Used operation XOR (exclusive OR) for addition and
subtraction – the result is 0 if two bits are the same;
the result is 1 if two bits are different

7
XORing of two single bits or two words

Image source: Data Communications

8
And Networking, Forouzan
 Block Coding

Linear
Block
Coding
Error
Detection
Methods

Cyclic
Checksum
Coding

9
10
Block Coding

• In block coding, a message will be divided into blocks,

each of k bits, called datawords.
• Then a redundant bits, r, is added to each block to make
the length n = k + r.
• The resulting n-bit blocks are called codewords.

11
Datawords and codewords in block coding

Image source: Data Communications

12
And Networking, Forouzan
Block Coding

• Error Detection Process

– If the following two conditions are met, the
receiver can detect a change in the original
codeword:
1. The receiver has (or can find) a list of valid codeword
2. The original codeword has changed to an invalid one

13
Process of error detection in block coding

Image source: Data Communications

14
And Networking, Forouzan
Example 1
Let us assume that k = 2 and n = 3. Table 6.1 shows the list
of datawords and codewords. Later, we will see how to
derive a codeword from a dataword.

Table 6.1 A code for error detection

15
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. 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. Two corrupted bits
have made the error undetectable. 16
Block Coding

• Hamming Distance (HD)

– The HD between two words (of the same size) is
the number of differences between corresponding
bits.

17
Example 3
Find the Hamming distance between two pairs of words:
(000,011) and (10101, 11110)

Solution
1. The Hamming distance, d(000, 011) is 2 because 000
011 is 011 (two 1s)
2. The Hamming distance, d(10101, 11110) is 3 because
10101 11110 is 01011 (three 1s)

18
Block Coding

• Minimum Hamming Distance

– The smallest distance between all possible pairs in
a set of words; define as dmin

19
Example 4
Find the minimum HD of the coding in Table 6.1

Solution
1. Find all the Hamming distances

d(000,011) = 2, d(000,101) = 2, d(000,110) = 2,

d(011,101) = 2, d(011,110) =2, d(101, 110) = 2

2. The Dmin in this case is 2

20
Example 5
Find the minimum HD of the coding in Table 6.2

Solution
1. Find all the Hamming distances

d(00000, 01011) = 3, d(00000, 10101) = 3,

d(00000, 11110) =4, d(01011, 10101) = 4,
d(01011, 11110) = 3, d(10101, 11110) = 3

2. The Dmin in this case is 3

21
22
Linear Block Coding

• A linear block code is a code in which the exclusive

OR of two valid codewords creates another valid
codeword

23
Linear Block Coding

Simple Parity Two-dimensional

Check Parity Check
• A redundant • A block of bits
bit, called is organized in
parity bit, is a table (rows
added to every and columns)
data unit so the • The parity bit is
total number of calculated for
1s become each data unit
even (or odd)
24
Encoder and decoder for simple parity-check code

Image source: Data Communications

25
And Networking, Forouzan
Example 6
Suppose the sender wants to send the word world. In
ASCII the five characters are coded as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent
11101110 11011110 11100100 11011000 11001001

26
Example 7
Now suppose the word world in Example 6 is received by the
receiver without being corrupted in transmission.
11101110 11011110 11100100 11011000 11001001
The receiver counts the 1s in each character and comes up
with even numbers (6, 6, 4, 4, 4). The data are accepted.

27
Example 8
Now suppose the word world in Example 6 is corrupted
during transmission.
11111110 11011110 11101100 11011000 11001001
The receiver counts the 1s in each character and comes up
with even and odd numbers (7, 6, 5, 4, 4). The receiver
knows that the data are corrupted, discards them, and asks
for retransmission.

28
Exercise
Assuming even parity, find the parity bit for each
of the following data units:
1. 1001011 = 10010110
2. 0001110 = 00011101
3. 1100000 = 11000000
4. 1010101 = 10101010
5. 0011111 = 00111111

29
Two dimensional parity-check code

Image source: Data Communications

30
And Networking, Forouzan
Example 9
Suppose the following block is sent:
10101001 00111001 11011101 11100111 10101010
However, it is hit by a burst noise of length 8, and some bits are
corrupted.
10100011 10001001 11011101 11100111 10101010
When the receiver checks the parity bits, some of the bits do not
follow the even-parity rule and the whole block is discarded.
10100011 10001001 11011101 11100111 10101010

31
Exercise
Find the parity bits for the following bit pattern, using Two
Dimensional Parity Check. Assume EVEN parity.

1001011 0001100 1000000 1110111

Solution
1001011 0
0001100 0
1000000 1
1110111 0
1110000 1

10010110 00011000 10000001 11101110 1110000132

33
Cyclic Coding

• In a cyclic code, if a codeword is cylically shifted

(rotated), the result is another codeword
• Example, if 1011000 is a codeword and we cyclically
left-shift, then 0110001 is also a codeword

34
Cyclic Coding

• Cyclic Redundancy Check (CRC)

– CRC is based on binary division
– A sequence of redundant bits, called CRC or CRC
remainder, is appended to the end of data unit
– The redundancy bits are derived by dividing the
data unit by a predetermined divisor

35
CRC encoder and decoder

Image source: Data Communications

36
And Networking, Forouzan
CRC generation at sender side

1. Find the length of the divisor ‘L’

2. Append ‘L – 1’ bits to the original message
3. Perform binary division operation
4. Remainder of the division = CRC

Note: The CRC must be of L – 1 bits

:Use XOR operation

37
Division in CRC encoder (Sender)

Image source: Data Communications

38
And Networking, Forouzan
No Error Error

Division in the CRC decoder for two cases (Receiver)

Image source: Data Communications
39
And Networking, Forouzan
Exercise
Given the dataword 101010 and the divisor 11011.
1. Show the generation of codeword at sender site
2. Show the checking of the codeword at the
receiver site

40
Solution
1) Sender

41
Solution (cont.)
2) Receiver

42
Cyclic Coding

• Polynomials
– A pattern of 0s and 1s can be represented as a
polynomial with coefficients of 0 and 1
– The power of each term shows the position of the
bit; the coefficient shows the value of the bit

43
A polynomial to represent a binary word

Image source: Data Communications

44
And Networking, Forouzan
Exercise
1. Find the polynomial equivalent for the following binary
pattern:
a) 101111 = x5 + x3 + x2 + x + 1
b) 11001 = x4 + x3 + 1
c) 10111101 = x7 + x5 + x4 + x3 + x2 + 1
d) 110110011 = x8 + x7 + x5 + x4 + x + 1
2. Find the binary equivalent for the following polynomial
pattern:
a) x4 + x2 + 1 = 10101
b) x3 + x + 1 = 1011
c) x6 + x5 + x2 + 1 = 1100101
d) x10 + x9 + x5 + x3 + x + 1 = 11000101011 45
46
Checksum

• Based on the concept of redundancy and used by the

higher-layer protocols
• Checksum = check + sum
• Sender side : checksum creation
• Receiver side : checksum validation

47
 Implementation of Checksum
Sender Receiver
• The message is divided into n bits • The message (including checksum)
(usually 16 bits) is divided into n bits (16 bits)
• All words are added using one’s • All words are added using one’s
complement addition complement addition
• The sum is complemented and • The sum is complemented and
becomes the checksum becomes the new checksum
• The checksum is sent with the data • If the value of checksum is 0, the
message is accepted; otherwise, it
is rejected

48
 Example 10 Example 11

• List of five 4-bit numbers are • Instead of sending the

sent to destination numbers with the sum, the
(7,11,12,0,6) sender send the negative
• Sender send all the numbers (complement) of the sum –
together with the sum of all checksum (7,11,12,0,6,-36)
numbers (7,11,12,0,6,36) • The receiver add all numbers
• The receiver adds the five including the checksum
numbers and compare the • If the result is 0, no error. If
result with the sum not, there is an error
• If the two are the same, no
error & accept the data. If not,
discard the data

49
One’s Complement
Present the unsigned numbers between 0 and 2n – 1
using only n bits

If the number has more than n bits, the extra leftmost

bits need to be added to the rightmost bit (wrapping)

A negative number can be represented by inverting all

bits (changing 0 to 1 and 1 to 0)

50
Example 12
Represent the number 21 in one’s complement arithmetic using
only four bits.

Solution
1) The binary equivalent for 21 is 10101 (needs five bits)
2) Wrap the leftmost bit and add to the four rightmost bits
0101 + 1 = 0110 or 6

51
Example 13
Represent the number -6 in one’s complement arithmetic using
only four bits.

Solution
1) The negative number in one’s complement is found by
inverting all bits of the binary equivalent
2) The binary equivalent for +6 is 0110; -6 is 1001 (or 9 in
unsigned numbers)
3) The complement of -6 is 9

52
Checksum – operation at sender site

1. Break the original message in to ‘k’ numbers of

blocks with ‘n’ bits in each blocks.
2. Sum all the ‘k’ data blocks
3. Add the carry to the sum, if any.
4. Do 1’s complement to the sum = checksum

53
Example 14
Suppose the following message is to be sent using checksum of 8
bits : 10101001 00111001

Sender site:
The numbers are added using one’s complement arithmetic:

10101001
+ 00111001
------------
Sum 11100010
Checksum 00011101 (1’s complement)

The pattern sent is 10101001 00111001 00011101 54

Checksum – operation at receiver side

1. Collect all data blocks including the checksum.

2. Sum all the data blocks and checksum
3. If the result is all ‘1’, ACCEPT; else REJECT

55
 Receiver site:
Receiver will adds the three sections using one’s complement
arithmetic. We consider two cases; without errors and with
errors
No errors With errors
Now suppose there is a burst error of length
10101001 5 that affects 4 bits.
00111001 10101111 11111001 00011101
+ 00011101 When the receiver adds the three sections, it
Sum 11 111111 gets
Complement 00000000 10101111
means that the pattern is OK. 11111001
+ 00011101
Partial Sum 1 11000101
Carry + _______1
Sum 11000110
Complement 00111001
means the pattern is corrupted. 56
57
Example 15
Suppose a sender want to send a list of five 4-bit numbers to a
receiver. A set of number is (2,6,9,11,13). Find the checksum at
sender and receiver.
Solution
At sender At receiver
2 2
6 6
9 9
11 11
13 13
CS (initial) 0 CS (received) 4
Sum 41 Sum 45
Wrapped sum 11 Wrapped sum 15
Checksum 4 Checksum 0 58
Note: How to calculate wrapped sum &
checksum
• Wrapped sum
At sender, changed 41 into binary 101001. Hint: Highest number in the
list is 13 (1101) so its have 4 bit only. Bring the rest bit to below &
make addition operation. The same thing at the receiver.

At sender At receiver
101001  1001 101101  1101
+ 10 + 10
1011 11 1111 15
1’s complement 0100 4 1’s complement 0000

1’s complement = checksum

59
Example 16
Suppose a sender want to send a list of four hexadecimal
numbers to a receiver. A set of number is (466F, 726F, 757A,
616E). Find the checksum at the sender and receiver.
Solution
At sender At receiver
Carries 1013 Carries 1013
466F 466F
726F 726F
757A 757A
616E 616E
CS (initial) 0000 CS (received) 7038
Sum (partial) 8FC6 Sum FFFE
Carry 1 Carry 1
Wrapped sum 8FC7 Wrapped sum FFFF
Checksum 7038 Checksum 0000 60
Exercise
1. Calculate the checksum at the sender and receiver site for
the following :

1010011 1000001 1110111

2. A sender needs to send the four data items 345616, ABCC16,

02BC16 and EEEE16
a)Find the checksum at the sender site
b)Find the checksum at the receiver site if there is no error.

61
Solution
Question 1

62
Solution (cont.)
Question 2

63
Image source: Data Communications
And Networking, Forouzan
End of Chapter 8

64