CHAPTER 10
ERROR DETECTION AND
CORRECTION
1/8/2022 ITT 300 1
Learning Outcomes
Able to differentiate types of errors that
may occur during data transmission
Able to determine how error of data can
be detected and corrected in data
transmission
Able to understand the techniques that
being used for error detection and
correction.
1/8/2022 ITT 300 2
Introduction
The network must be able to transfer
data with acceptable of accuracy.
Data can be corrupted during
transmission.
Some application may require that
errors to be detected and corrected.
1/8/2022 ITT 300 3
Types of Errors
When bit flow from one point to another, they may
unpredictable changes because of interference.
This interference can change the shape of the
signal
2 types of errors
1. Single bit error
2. Burst error
Eg;- 1/100 s burst of impulse noise on transmission
with data rate 1200 bps, it might change all or some
of the 12 bits of information.
1/8/2022 ITT 300 4
Single Bit Error
Only ONE bit of a given data unit (such as
byte, character or packet) is changed from 0
>> 1 and 1 >>> 0.
Ex 00000010 ( ASCII => start of text )
change to 00001010 ( ASCII => line feed )
Occur in parallel transmission
1/8/2022 ITT 300 5
Single Bit Error
10.1 Single-bit error
1/8/2022 ITT 300 6
Burst Error
It means that 2 or more bits in data unit have changed
from 1 to 0 or 0 to 1
Occur in serial transmission
Burst error does not necessarily mean the errors occur in
consecutive bits.
The length of burst is measured from the 1st bit corrupted
bit to the last corrupted bit
Duration of noise normally longer than the duration of 1
bit.
When noise affects data it affects a set of bits.
It depends on the data rate and duration of noise
1/8/2022 ITT 300 7
Burst Error
10.2 Burst error of length 5
1/8/2022 ITT 300 8
Error Detection
Redundancy
The central concept in detecting or correcting
errors.
Error detection mechanism that would send every data
unit twice
In order to detect or correct error, we need to send some
extra bits with our data.
Error detection uses the concept of redundancy, which
means for detecting errors at the destination
1/8/2022 ITT 300 9
10.3 Redundancy
1/8/2022 ITT 300 10
Detection Vs Correction
Correction is more difficult than detection.
In detection – only to see if any error has occurred.
In correction we need required as below:-
The exact number of bits that are corrupted and
importantly the location in the message.
The number of errors and the size of message
Eg:- if we need to correct 1 error in 8-bit data unit,
it may have 8 possible error locations.
1/8/2022 ITT 300 11
Forward error correction vs
Retransmission
2 methods of error correction
a) Forward error correction
process in which the receiver tries to guess the message
by using redundancy bits.
b) Retransmission
Technique in which the receiver detects the
occurrence of an error and ask the sender to
resend the message
1/8/2022 ITT 300 12
Coding
Redundancy can be achieved through
various coding scheme.
The sender adds redundant bits through a
process that create a relationship between
the two sets of bits to detect or correct errors
Factors – ratio of redundant bits to the
data unit and the robustness of the process
1/8/2022 ITT 300 13
Coding
Coding scheme can be divided into two
Block coding
Convolution coding
This subject only cover on block coding
scheme.
1/8/2022 ITT 300 14
Modular Arithmetic
Only limited range of integers, integers 0 to
N-1
This is known as modulus N.
Eg: Modulus 12 means that we use only the
integers 0 to 11.
In Modulo N system, if number is > N, it
will divided by N and the remainder is the
result.
If N is negative, it will change to positive
value.
1/8/2022 ITT 300 15
1/9/2022 ITT 300 16
1/9/2022 ITT 300 17
Modular Arithmetic
Adding
0+0=0 , 0+1=1, 1+0=1, 1+1 = 0
Subtraction
0-0=0, 0-1=1, 1-0=1, 1-1=0
1/8/2022 ITT 300 18
Modular Arithmetic
XOR operation in modular arithmetic
1/8/2022 ITT 300 19
Block Coding
In block coding, our message divided
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.
1/8/2022 ITT 300 20
Figure 10.5 Datawords and codewords in block coding
10.21
Error Detection
How errors can be detected by using
block coding? If 2 conditions are met:-
The receiver has a list of valid codewords.
The original codeword has changed to
invalid one.
Error detection code can detect only types
of errors for which it is designed; other
types of errors remain undetected.
1/8/2022 ITT 300 22
Figure 10.6 Process of error detection in block coding
10.23
Example 10.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:
1. The receiver receives 011. It is a valid codeword. The
receiver extracts the dataword 01 from it.
10.24
Example 10.2 (continued)
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.
10.25
Table 10.1 A code for error detection (Example 10.2)
10.26
Error Correction
It is more difficult than error detection
Error detection, the receiver needs to know
only the received codeword is invalid
But, in error correction the receiver need to
find (guess) the original codeword sent
In other words, we need more redundant
bits for error correction than error
detection
1/8/2022 ITT 300 27
Hamming Distance
It is the central concept in coding for
error control.
The Hamming Distance between two
words is the number differences
between the corresponding bits
1/8/2022 ITT 300 28
Example 10.4
Let us find the Hamming distance between two pairs of
words.
1. The Hamming distance d(000, 011) is 2 because
2. The Hamming distance d(10101, 11110) is 3 because
10.29
Minimum Hamming distance
Although the hamming distance is being used
for error detection and correction
It measurement that used for designing a
code is minimum hamming distance
Minimum hamming distance (dmin) is the
smallest hamming distance all possible
pairs in a set of words.
1/8/2022 ITT 300 30
Relationship Hamming distance and Errors
When a codeword corrupted during
transmission, the hamming distance
between sent and received codeword is the
number of bits affected by error.
In the other words, the hamming distance
between the received codeword and the sent
codeword is the number of bits that are
corrupted during transmission.
1/8/2022 ITT 300 31
Example 10.5
Find the minimum Hamming distance of the coding scheme
in Table 10.1.
Solution
We first find all Hamming distances.
The dmin in this case is 2.
10.32
Example 10.6
Find the minimum Hamming distance of the coding scheme
in Table 10.2.
Solution
We first find all the Hamming distances.
The dmin in this case is 3.
10.33
Minimum distance for error
detection
In the Hamming distance able to detect error as s
error,
The minimum distance between the valid codes
must be s +1
To guarantee the detection of up to s error in all
cases, the minimum Hamming distance in a block
code must be dmin = s + 1 .
eg:- If dmin = 3 the min erorr, s is 2
1/8/2022 ITT 300 34
Linear Block Codes
Today block codes is subset to linear block
codes.
The nonlinear block codes for error detection
and correction is not widespread because
their structure make difficult to analyze and
implement.
Linear block codes is a code in which the
exclusive OR (XOR) of two valid
codewords creates another valid
codeword
1/8/2022 ITT 300 35
Error Detection-Linear Block
codes
Three types of redundancy detection
method
1. Parity check
2. Cyclic redundancy check (CRC)
3. Checksum
1/8/2022 ITT 300 36
Error Detection-Linear Block
codes
Types of
redundancy
check
Parity Cyclic
Redundancy Checksum
Check Check (CRC)
Simple Parity 2 dimensional
Check parity check
1/8/2022 ITT 300 37
Parity Check
2 types of parity check
1. Simple Parity Check
2. 2 dimensional parity check
1/8/2022 ITT 300 38
Simple Parity Check
In parity check, a parity bit is added to
every data unit so that the total number
of 1s is even (or odd for odd-parity)
Simple parity check can detect all
single-bit errors.
It can detect burst errors only if the
total number of errors in each data unit is
odd
1/8/2022 ITT 300 39
Simple Parity Check Code
In this code, k-bit dataword is changed to n-
bit codeword when, n= k+1.
An extra bit called parity bit is selected to
make the total number of 1s in the
dataword is EVEN.
The minimum hamming distance for this
Simple Parity code is dmin = 2, which means
that this code is a single bit error detection
code
1/8/2022 ITT 300 40
Simple Parity Check
10.5 Even-parity concept
1/8/2022 ITT 300 41
Simple Parity Check
Encoder Side
Generator will take copy of k-bit dataword and
generates the parity bit. The codeword will be
created when
codeword (n) = k(dataword) + 1 (parity bit)
This parity bit make the number of 1s in the
codeword EVEN
SYNDROME 0 = when the number of 1s in
codeword is EVEN
SYNDROME 1 = when the number of 1s in
codeword is ODD
1/8/2022 ITT 300 42
Example 1
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
1/8/2022 ITT 300 43
Simple Parity Check
Decoder Side
The syndrome will passed logic analyzer
SYNDROME 0 = no error in the received
codeword. The data is ACCEPTED
SYNDROME 1 = the data portion of the received
codeword is discarded. The data is NOT
Created/Accepted.
Performance
Only single bit error can be detected
1/8/2022 ITT 300 44
Example 2
Now suppose the word world in Example 1 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.
1/8/2022 ITT 300 45
Example 3
Now suppose the word world in Example 1 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.
1/8/2022 ITT 300 46
Two Dimensional Parity Check
In two-dimensional parity check, a
block of bits is divided into rows and a
redundant row of bits is added to the
whole block
The Hamming code for this category
is dmin = 3. It means that it can detect
error up to 2 or one single error.
1/8/2022 ITT 300 47
Two dimensional parity check
The integer of m >=3
The relationship between m (the
number of check bits) and n is
n= 2m -1 and k = n-m.
Eg:- m =3, then n=7 and k= 4. The
Hamming code is (7,4) with dmin = 3.
1/8/2022 ITT 300 48
Figure 10.11 Two-dimensional parity-check code
10.49
10.6 Two-dimensional parity
1/8/2022 ITT 300 50
Figure 10.11 Two-dimensional parity-check code
10.51
Figure 10.11 Two-dimensional parity-check code
10.52
Example 4
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
1/8/2022 ITT 300 53
Two Dimensional Parity Check
Performance
Hamming code can detect single bit error or
double error (min detection)
How to solve?
- By slpitting burst error to several
codeword, 1 erorr for each codeword.
-They send one codeword at a time, we
arrange the codeword in a table and send
the bits in the table a column at a time
1/8/2022 ITT 300 54
Cyclic code
Codeword is cyclically shifted that
result to another codeword.
Eg:- 1011000 is a codeword, then it
cyclically left-shifted to become
0110001 codeword
1011000
1/8/2022 ITT 300 55
Cyclic Redundancy Check (CRC)
10.7 CRC generator and checker
1/8/2022 ITT 300 56
Figure 10.14 CRC encoder and decoder
10.57
Figure 10.15 Division in CRC encoder
10.58
Cyclic Redundancy Check (CRC)
Characteristics Descriptions
Encoder Take dataword and augmented with n – k number
of 0s . Then divide the augmented dataword by
divisor.
Decoder Same as division process as the encoder. The
remainder of division is syndrome.
If syndrome 0 = no errors, dataword is ACCEPTED
Otherwise it will be discarded
Divisor The divisor has n – k +1 bits which predefined or
all 0s.
The left most of the bit not needed because the
result of the operation ALWAYS 0s.
1/8/2022 ITT 300 59
Cyclic Redundancy Check (CRC)
Characteristics Descriptions
Augmented It fixed in position with divisor bit shifting to the
Dataword right. 1 bit for each step
The divisor bits are aligned with the augmented
dataword
Remainder In encoder => the remainder will attached to the
dataword
In decoder => the remainder is equal to zero
means data is ACCEPTED otherwise it will be
discarded.
It normallly used as register in hardware
implementation
1/8/2022 ITT 300 60
The CRC Encoder Generator
10.8 Binary division in a CRC generator
1/8/2022 ITT 300 61
The CRC Decoder Generator
10.9 Binary division in CRC checker
1/8/2022 ITT 300 62
Figure 10.16 Division in the CRC decoder for two cases
10.63
Polynomials
How the cyclic code can be analyzed?
By using Polynomial
A pattern of 0s and 1s represented in polynomial with
coeffiecient of 0 and 1
10.10 A polynomial
1/8/2022 ITT 300 64
Polynomials
10.11 A polynomial representing a divisor
1/8/2022 ITT 300 65
Figure 10.21 A polynomial to represent a binary word
10.66
Polynomial
Degree of polynomial is the highest power in the
polynomial
Eg:- The highest degree of polynomial is 7.
1/8/2022 ITT 300 67
Polynomial
Shifting
Shifting to the left
adding extra 0s at the right most bit
it can be accomplished by multiplying each term of
polynomial with Xm
Shifting to the rights
deleting some the right most bits
It can be accomplished by dividing each term with the
polynomial by Xm
Shifting left 3 bits – 10011 =>10011000
x4+x+1 => x7+x4+x3
Shifting right 3 bits – 10011 => 10
x4+x+1 => x
1/8/2022 ITT 300 68
Polynomial
The augmented dataword in CRC encoder under
polynomial form will SHIFTED the bits to the left
Eg:-
Dataword 1001 => x3+1, divisor = x3+x+1
To find the augmented dataword, it need to left-shifted
the dataword in 3 bits (multiplying the dataword with
x3) and become x6+x3
1/8/2022 ITT 300 69
Figure 10.22 CRC division using polynomials
10.70
Table 10.1 Standard polynomials
Name Polynomial Application
CRC-8 x8 + x2 + x + 1 ATM header
CRC-10 x10 + x9 + x5 + x4 + x 2 + 1 ATM AAL
ITU-16 x16 + x12 + x5 + 1 HDLC
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10
ITU-32 LANs
+ x8 + x7 + x5 + x4 + x2 + x + 1
1/8/2022 ITT 300 71
Cyclic Redundancy Check (CRC)
It can be implement in networks such as LAN and
WANS
This error can be detected in data link and transport
layer in OSI model.
Performance
Advantages
- have a very good performance in detecting single bit,
double errors, odd number of errors and burst errors
- It can easily implemented in hardware and software.
- It can very fast in hardware implementation
- It can be applied in many networks
1/8/2022 ITT 300 72
Checksum
The checksum is used in the Internet by
several protocols although not at the data link
layer.
It normally implement in network and
transport layer.
It used based on redundancy.
It used One’s complement – All the bits will
change to from 0 to 1 and from 1 to 0
1/8/2022 ITT 300 73
Checksum
10.12 Checksum
1/8/2022 ITT 300 74
Checksum
10.13 Data unit and checksum
1/8/2022 ITT 300 75
Checksum
The sender follows these steps:
The unit is divided into k sections, each of
n bits
All sections are added using one’s
complement to get the sum
The sum is complemented and becomes
the checksum
The checksum is sent with the data
1/8/2022 ITT 300 76
Checksum
The receiver follows these steps:
The unit is divided into k sections, each of
n bits
All sections are added using one’s
complement to get the sum
The sum is complemented
If the result is zero, the data are accepted:
otherwise, rejected
1/8/2022 ITT 300 77
Example 7
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 1’s complement
Checksum 00011101
The pattern sent is 10101001 00111001 00011101
1/8/2022 ITT 300 78
Example 8
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.
1/8/2022 ITT 300 79
Example 9
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.
1/8/2022 ITT 300 80
Checksum
Performance
Advantage
It can detect single, double and burst error but
Less strong than CRC error checking capability
Disadvantage
- If one value of one word increment and the value
of the another word is decrement by the same
amount- it make 2 errors cannot be detected
because the sum and checksum remain the same.
Solution – each word multiplied by number (its
weight) that related to its position in the text.
1/8/2022 ITT 300 81
Summary
Criteria Simple parity Two-dimensional Cyclic Checksum
check Parity check Redundancy
check
Approach of Linear block Linear block codes Linear block + Redundancy
coding scheme codes Cyclic code code
n = 2m -1
The Min. n=k+1
dmin = 3 NA NA
Hamming Code dmin = 2
Network and
Data link and
Implementation Data link layer Data link Transport
transport layer
layer
1/8/2022 ITT 300 82
Summary
Criteria Simple parity Two- Cyclic Redundancy Checksum
check dimensional check
Parity check
•Single bit error, double
bit error, odd numbers •It can detect
•Single bit error and burst error any type of
•Single bit error
Performance and double bit •Faster in detecting errors
can be detect
error errors •Less strong
•Easy to implement in than CRC
hardware and software
Category of
network
LAN LAN LANs and WANs LAN
Software Software Hardware and
Application Software
Software
1/8/2022 ITT 300 83
End of Chapter 10
1/8/2022 ITT 300 84
