Error Detection and

Correction

Data Transmission
 ERROR DETECTION
Errors occur when transmitting and storing data due to:
• interference (all types of cable can suffer from electrical interference, which can cause data to
be corrupted or even lost)
• problems during packet switching (this can lead to data loss – or it is even possible to gain data)
• skewing of data (this occurs during parallel data transmission and can cause data corruption if
the bits arrive out of synchronisation).
There are four methods of error detection
1. Parity (Check)
2. Checksum
3. Automatic Repeat Request (ARQ)
4. Echo Check
 PARITY CHECK

Parity Checking – Method of error detection based on the number of 1-bits in a byte of data

Parity bit is set before the data was being transmitted (usually the most significant bit or
left-most bit).
The parity can be:
• Odd Parity - have an odd number of 1-bits in the byte
• Even Parit- have an even number of 1-bits in the byte
The parity bit is set according to whether the parity being used is even or odd.
 PARITY CHECK

If even parity system was being used, the parity bit have to be adjusted such that
the total number of 1-bits are even

Empty Total of four 1-bits

Parity-
Bit
0 1 1 0 1 0 1 even

As shown from the above example, there are total of an even four 1-bits. Therefore,
we can set the parity bit to 0 to maintain even number of 1-bits

Total of four 1-bits

0 0 1 1 0 1 0 1 even
 PARITY CHECK

If odd parity system was being used, the parity bit have to be adjusted such that the total number
of 1-bits are odd.

Empty Total of four 1-bits

Parity-
Bit
0 1 1 0 1 0 1 even

As shown from the above example, there are total of four 1-bits which make the number of 1-bits
even. Therefore we can set the parity bit to 1 to change total number of 1-bits into odd.

Total of five 1-bits

1 0 1 1 0 1 0 1 odd
 PARITY CHECK

Before the transmission of data, both the sender and receiver agrees of which type of parity to use
If a byte was sent from the sender to the receiver ( e.g both agreed on even parity), an error would
be flagged if the byte had an odd number of 1-bits
Sent:
0 0 1 1 0 1 0 1

Received:

0 0 1 0 0 1 0 1

There are odd number of 1-bits on the received byte, therefore there is an error during the
transmission.
PARITY CHECK

However, receiver doesn’t know exactly which of the bits have been transmitted incorrectly

One way around this problem is to use PARITY BLOCK by sending a parity byte as well.

Using this method, a block of data is sent and the number of 1-bits are totalled horizontally and
vertically (a parity check is done in both horizontal and vertical directions).

This method not only identifies that an error has occurred but also indicates where the error is.
 PARITY CHECK

The computer will send the following data to a device

Sent:
BIT 1
(PARITY) BIT 2 BIT 3 BIT 4 BIT 5 BIT 6 BIT 7 BIT 8
Byte 1 1 0 1 1 0 0 1 1
Byte 2 0 1 1 0 1 1 0 1
Byte 3 0 1 0 0 1 0 1 0

Parity byte 0 1 1 0 1 0 1 1
 PARITY CHECK

Received:
BIT 1
(PARITY) BIT 2 BIT 3 BIT 4 BIT 5 BIT 6 BIT 7 BIT 8
Byte 1 1 0 1 1 0 0 1 1
Byte 2 0 1 1 0 1 1 0 1
Byte 3 0 1 0 0 1 0 1 0

Parity byte 0 1 1 0 1 0 1 1

The receiver will perform parity check both horizontally and vertically. The error bit is
identified based on the row (byte) and column (bit) that contain the error.
 PARITY CHECK
The computer will send the following data to a device. The system will use EVEN parity.
Complete the block of data

Bit 1
Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 Bit 8
(parity)

Byte 1 0 1 0 0 0 1 1

Byte 2 1 1 1 0 1 0 0

Byte 3 1 0 0 0 0 0 1

Parity byte
• Determine the following:
• parity check used
• Location: ____ byte , ____bit
• Corrected byte

Parity bit Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 Bit 8

Byte 1 1 1 0 0 0 0 0 0
Byte 2 0 0 1 1 1 1 0 0
Byte 3 0 1 0 0 0 1 1 1
Byte 4 1 0 1 0 1 1 1 1
Byte 5 0 0 0 1 0 0 0 1
Byte 6 0 0 1 1 1 1 1 1
Byte 7 1 0 1 1 0 1 0 0
Byte 8 0 1 0 1 0 0 1 1
Byte 9 1 1 1 0 0 0 0 0

Parity byte 0 0 1 1 1 0 0 1
 CHECKSUM
• Data is sent in blocks, and an additional value, called the checksum, is sent at the end of
the block of data.

1. When a block of data is about to be transmitted, the checksum is calculated

from the block of data
2. Calculation performed on data (using the agreed algorithm) to get the checksum
3. Checksum sent with the block of data
4. Checksum recalculated after transmission by the receiver
5. The re-calculated checksum is then compared to the checksum sent with the data block
6. Error detected if checksums are different
 CHECKSUM
Determine the checksum of the following data:
1. 234, 59,198, 169, 98
2. 249, 37, 78, 218, 187
 ECHO CHECK
With echo check, data is sent to another device, this data is sent back again to the sender. The sender’s
computer compares the two sets of data to check if any errors occurred during the transmission process

1. a copy of the data is sent back to the sender

2. the returned data is compared with the original data by the
sender’s computer
3. if there are no differences, then the data was sent without
error
4. if the two sets of data are different, then an error occurred at
some stage during the data transmission.
 Automatic Repeat reQuest
ARQ uses positive and negative acknowledgements and timeout.

1. Request is sent (with data) requiring acknowledgement

2. the receiving device receives an error detection code as part of the
data transmission
3. if no error is detected, a positive acknowledgement is sent back to
the sending device. If an error is detected, the receiving device now
sends a negative acknowledgement to the sending device
4. If no response/acknowledgment within certain time limit, it
automatically re-sends the data until a positive acknowledgement is
received
5. or until a pre-determined number of re-transmissions has taken
place
 Check Digit
A check digit is a form of redundancy check used for error detection on identification numbers, such as bank
account numbers and product codes, which are used in an application where they will at least sometimes be
input manually.

It consists of one or more digits computed by an algorithm from the other digits (or letters) in the sequence
input.
The most common standards:
• UPC – Universal product code
• EAN – European Product code
• ISBN 13 – International Standard Book Number
 ISBN-13 Calculation
The check digit in ISBN 13 is the thirteenth digit in the number.
The check digit is calculated as follows:
1. Add all digits in odd positions.
2. Add all digits in even positions and multiply the sum by 3;
3. Add the results from step 1 and step 2
4. Divide that number by 10 and take the remainder;
5. If the remainder is not 0, subtract the remainder from 10.
 ISBN-13 Calculation
Calculate the check digit of ISBN 9 7 8 0 3 4 0 9 8 3 8 2
1. 9 + 8 + 3 + 0 + 8 + 8 = 36
2. 3 × (7 + 0 + 4 + 9 + 3 + 2) = 75
3. (36 + 75)/10 = 111
4. 111/10 = 11 remainder 1
5. 10 – 1 = 9 the check digit

Hence : 9 7 8 0 3 4 0 9 8 3 8 2 9
 ISBN-13 Re-calculation

To check that an ISBN 13-digit code is correct, including its check digit, a similar process is followed:

• add all the odd numbered digits together, including the check digit

• add all the even number of digits together and multiply the result by 3

• add the results from 1 and 2 together and divide by 10

• the number is correct if the remainder is zero.

ISBN-13 Re-calculation

Using the ISBN 9 7 8 0 3 4 0 9 8 3 8 2 9

• 9 + 8 + 3 + 0 + 8 + 8 + 9 = 45

• 3 × (7 + 0 + 4 + 9 + 3 + 2) = 75

• (45 + 75)/10 = 120/10 = 12 remainder 0

• remainder is 0, therefore number is correct.

 Modulo-11 Calculation
The check digit is calculated from the other 7 digits:
1. each digit in the number is given a weighting based on its digit position starting from the right.
2. each digit in the number is multiplied by its weight then added together
3. this total is divided by 11
4. if the remainder is 0, then the check digit is zero, otherwise, the remainder is then subtracted
from 11 to get the check digit
Weight 8 7 6 5 4 3 2 1
5. if the difference is 10, then the check digit is ’X’
Digits 4 1 5 6 7 1 0 Check Digit
 Modulo-11 Calculation
Calculate the check digit of the code: 4 1 5 6 7 1 0

Weight 8 7 6 5 4 3 2 1
1. x
Digits 4 1 5 6 7 1 0 Check Digit

2. (8 × 4) + (7 × 1) + (6 × 5) + (5 × 6) + (4 × 7) + (3 × 1) + (2 × 0)
3. 32 + 7 + 30 + 30 + 28 + 3 + 0 = 130
4. divide total by 11: 130/11 = 11 remainder 9
Hence : 4 1 5 6 7 1 0 2
5. subtract remainder from 11: 11 – 9 = 2 (check digit)
 Modulo-11 Re-calculation

To check that the eight-digit number is correct, including its check digit, a similar process is
followed:
1. each digit in the number is given a weighting based on its digit position starting from the
right.
2. the digit is multiplied by its weighting and then each value is added to make a total
3. the total is divided by 11
Weight 8 7 6 5 4 3 2 1
4. the number is correct if the remainder is zero
Digits 4 1 5 6 7 1 0 2
 Modulo-11 Re-calculation
Check if the code is correct 4 1 5 6 7 1 0 2

Weight 8 7 6 5 4 3 2 1
1. xDigits 4 1 5 6 7 1 0 2

2. (8 × 4) + (7 × 1) + (6 × 5) + (5 × 6) + (4 × 7) + (3 × 1) + (2 × 0) + (1 × 2 )
= 32 + 7 + 30 + 30 + 28 + 3 + 0 + 2 = 132
3. divide 132 by 11 = 12 remainder 0
4. remainder is 0 so the number is correct
Check Digit

Check digit is generally designed to

capture human transcription errors.
• single digit errors, such as 1 → 2
• transposition errors, such as 12 → 21
• twin errors, such as 11 → 22
• phonetic errors, such as 60 → 16 ("sixty" to "sixteen")
Related videos
• Check sum
https://www.youtube.com/watch?v=RFOGDY2e0mQ&t=15s
https://www.youtube.com/watch?v=ouqVQCbisDs&t=190s
• Parity Check
https://www.youtube.com/watch?v=pUBdJi6eVYA
• ARQ
https://www.youtube.com/watch?v=lSNX2ap7dH0&t=124s
• Check Digit
https://www.youtube.com/watch?v=4C3uwfoR88c
https://www.youtube.com/watch?v=onj7YBaSCkk