2.2 Methods of Error Detection - IGCSE Computer Science

Learning Objectives

By the end of this lesson, you will be able to:

Understand theneed to check for errorsafter data transmission and how these errors can occur
Describe the processes involved inparity checks(odd and even), includingparity byte and parity block checks
Describe the process of achecksum
Describe the process of anecho check
Describe how acheck digitis used to detect errors in data entry, includingISBNandbarcodes
Describe how anAutomatic Repeat Request (ARQ)can be used to establish that data is received without error, includingpositive/negative acknowledgementsandtimeout

Key Terms

Data Loss

Data is lost in transmission.

Data Gain

Additional data is received that was not sent.

Data Change

Some bits have been changed or flipped (e.g. 0 becomes 1).

Parity Bit

An extra bit added to a byte so the total number of 1s is either odd or even.

Even Parity

The total number of 1s in the byte (including the parity bit) is even.

Odd Parity

The total number of 1s in the byte (including the parity bit) is odd.

Parity Byte

An extra byte sent with a block of data containing the parity bits from the vertical parity check.

Parity Block Check

Performing horizontal and vertical parity checks on a block of data to identify and correct errors.

Checksum

A value calculated from a block of data and transmitted with it; recalculated at the destination to check for errors.

Echo Check

The received data is sent back to the sender, who compares it with the original to check for errors.

Check Digit

The final digit in a code, calculated from the other digits, used to detect errors in data entry.

ISBN

International Standard Book Number — uses a check digit (Modulo-11) to validate book codes.

Automatic Repeat Request (ARQ)

An error detection method using acknowledgements and timeout; if no acknowledgement is received, data is automatically resent.

Acknowledgement

A message sent by the receiver indicating that data has been received correctly (positive) or incorrectly (negative).

Timeout

The time allowed to elapse before an acknowledgement is received; if it expires, data is automatically resent.

Modulo-11

A check digit calculation method used by ISBN-10, involving weights and division by 11.

1. Why Errors Occur

With the complexity of computers and the vast amounts of 1s and 0s being transmitted, there is always a possibility that data can belost, gained or changedalong the way.

Causes of Errors

Electrical interference (noise)— every type of cable can suffer from electrical interference, which can cause data to become lost or corrupt (1s become 0s and 0s become 1s).
Problems during packet switching— issues during the packet switching process can cause data to be lost, or in some cases, gained.
Skewing of data— occurs during parallel data transmission and can cause data corruption if bits arrive out of synchronisation.
Wireless interference— signals can be blocked by physical barriers (buildings, walls, cars) or affected by bad weather or other signals.

Results of Interference

Data loss— data is lost in transmission.
Data gain— additional data is received.
Data change— some bits have been changed or flipped.

Data loss can also occur from interruptions to data transmission such as a blocked signal or if the transmission is intermittent.

Real-Life Example: Text Corruption

Look at the following text:'I cnudo't bvleeie taht I culod aulactly uesdtannrd waht rm onurrddeine was asynig'

This shows how corruption can make text unreadable. Checking for errors is important because computers aren't able to check that text is correct — they can only recognize whether a word is in their built-in dictionary or not.

Why Check for Errors?

Computers expect data in certainformats— a way of arranging data so it can be easily understood.
If data is not as expected, things can go wrong. For example, if a receiver expected a date in format DD/MM/YY as 03/04/17 but received 04/03/17, did the sender mean 3rd April 2017 or 4th March 2017?
Anerror or corruptionoccurs when data received is not as expected and therefore is difficult or impossible to process.

Activity 1: Causes and Outcomes of Interference

Alex receives an email over a wireless connection from a work colleague containing an important document.

Identify what interference Alex could experience and the outcomes of interference. [3]
Explain why Alex should check to make sure the document contains no errors. [2]

Solution:

Weather conditions or physical barriers such as buildings can affect signals [1]. Bits could be flipped in the document making it hard to understand the original meaning. Data could be lost, additional data could be gained or data could be changed [2].
As Alex received an important work document, they need to check for errors so that their work is unaffected [1] and they do not receive incorrect information [1].

Check Your Understanding: Why Errors Occur

1. State three outcomes of interference during data transmission. [3 marks]

[1]Data loss — data is lost in transmission
[1]Data gain — additional data is received
[1]Data change — some bits have been changed or flipped

2. What is electrical interference and how does it affect data? [2 marks]

[1]Electrical interference (noise) is a disturbance caused by electrical fields or signals
[1]It can cause data to become lost or corrupt — 1s become 0s and 0s become 1s

3. Why is it important for computers to check for errors after data transmission? [2 marks]

[1]Data corruption can make data difficult or impossible to process
[1]Computers expect data in certain formats — if data is not as expected, errors occur

4. Give one reason why wireless transmission is more prone to errors than wired transmission. [1 mark]

[1]Wireless signals can be blocked by physical barriers (buildings, walls, cars) or affected by bad weather / other signals

5. What is meant by a data format and why is it important in data transmission? [2 marks]

[1]A format is a way of arranging data so that it can be easily understood by people and computers
[1]People agree to certain formats so that systems work more efficiently and there is little chance of misunderstanding

6. Explain how packet switching can lead to data errors. [2 marks]

[1]Problems during the packet switching process can cause data to be lost
[1]Or, in some cases, additional data can be gained

2. Parity Checks (Odd and Even)

Parity checkingis one method used to check whether data has been changed or corrupted following transmission. A byte of data is allocated aparity bit, allocated before transmission takes place.

How Parity Works

TheMost Significant Bit (MSB)is reserved and used as a parity bit.
Systems that useEVEN PARITYhave an even number of 1-bits (including the parity bit).
Systems that useODD PARITYhave an odd number of 1-bits (including the parity bit).
Before data is transferred, an agreement is made between sender and receiver regarding which type of parity is used. This is an example of aprotocol.
Parity checks can only detect that an error has occurred — they do not reveal where the error(s) occurred.

Standard ASCII & Parity

Standard ASCII characters store letters in7 bitsand do not make use of the MSB.
This means the MSB can potentially be turned into aparity bit.
For example, the character 'G' in ASCII is 1000111 (7 bits).
With even parity, the parity bit would be 0 → 01000111 (four 1s).
With odd parity, the parity bit would be 1 → 11000111 (five 1s).

Examples of Parity Bits

Interactive Parity Bit Calculator

Enter a 7-bit binary value and select the parity type to see the parity bit that would be added.

7-bit binary value

Parity Type

Even Parity Example

Byte:01011010

Count the number of 1s in the 7 data bits: there arefour 1s.
Four is already an even number.
Therefore, the parity bit must be0so the total stays even.
Full byte with parity:0 01011010

Odd Parity Example

Byte:1111110

Count the number of 1s: there aresix 1s.
Six is an even number, but we need odd parity.
Therefore, the parity bit must be1to make the total odd (seven 1s).
Full byte with parity:1 1111110

Detecting Errors with Parity

If a byte has been transmitted and even parity is used, an error is flagged if the byte now has anodd number of 1-bitsat the receiver's end.
Example: Sender sends01011100(four 1s, even parity). Receiver gets01001100(three 1s, odd parity). Error detected!
Limitation:If two bits change value following data transmission, it may be impossible to locate the error using parity alone — the total number of 1s could still match the agreed parity.

Activity 2: Parity Bit Practice

Find the parity bit for each of the following bytes:

1 1 0 1 1 0 1 (even parity)
0 0 0 1 1 1 1 (even parity)
0 1 1 1 0 0 0 (even parity)
1 1 1 0 1 0 0 (odd parity)
1 0 1 1 0 1 1 (odd parity)

Which of the following bytes have an error following data transmission?

11101101 (even parity used)
01001111 (even parity used)
00111000 (even parity used)
11110100 (odd parity used)
11011011 (odd parity used)

Solution:

Parity bits:

1101101 has four 1s → even parity → parity bit =0
0001111 has four 1s → even parity → parity bit =0
0111000 has three 1s → even parity → parity bit =1
1110100 has four 1s → odd parity → parity bit =1
1011011 has five 1s → odd parity → parity bit =0

Error detection:

11101101 — six 1s → even parity →No error
01001111 — five 1s → even parity expected but odd found →Error
00111000 — three 1s → even parity expected but odd found →Error
11110100 — five 1s → odd parity →No error
11011011 — six 1s → odd parity expected but even found →Error

Check Your Understanding: Parity Checks

1. What is a parity bit? [2 marks]

[1]An extra bit added to a byte before transmission
[1]Used to make the total number of 1s either odd or even (depending on the agreed parity)

2. What is the difference between odd parity and even parity? [2 marks]

[1]In even parity, the total number of 1s in the byte (including the parity bit) must be even
[1]In odd parity, the total number of 1s in the byte (including the parity bit) must be odd

3. A byte using even parity is received as 10110100. Has an error occurred? Explain. [2 marks]

[1]The byte contains four 1s, which is an even number
[1]Therefore no error has been detected (the parity matches)

4. What is a limitation of parity checking? [2 marks]

[1]If an even number of bits change (e.g. two bits flip), the parity can remain the same
[1]This means the error will not be detected

5. Calculate the parity bit for the byte 0110010 using odd parity. [2 marks]

[1]The byte contains three 1s (odd)
[1]To maintain odd parity, the parity bit must be 0 (total remains three 1s)

6. Why is a parity check described as a protocol? [2 marks]

[1]A protocol is an agreed set of rules for communication
[1]The sender and receiver must agree before transmission whether they are using odd or even parity

3. Parity Block Checks & Parity Byte

We have seen how parity can detect an error in a single byte. However, thepositionof the error cannot be worked out. Our only option is to ask for the data to be sent again.

If we send multiple bytes as atransmission block, not only can we spot that an error has occurred, but it can also beidentified and correctedby performing both horizontal and vertical parity checks on the whole block of data.

How Parity Block Checks Work

Using even parity, a message is sent as a block of 8-bit bytes.
Ahorizontal parity checkis performed on each byte (the parity bit for each row).
Additionalvertical parity checksare performed on the whole block — this produces theparity byte.
The error can now be identified and corrected without having to ask for the data to be re-sent.

Key Points

Theparity byteis sent with the data and contains the parity bits from the vertical parity calculation.
The parity byte also indicates theend of the blockof data.
Bycross-referencingthe horizontal and vertical parity values, the exact position of the error can be pinpointed.
The error can be fixed automatically, or a retransmission request could be sent.

Interactive Parity Block Visualisation

This demonstrates how horizontal and vertical parity checks identify the position of an error.

Worked Example: Parity Block Check

Nine bytes of data have been transmitted. Agreement has been made thateven paritywill be used. Another byte, known as theparity byte, has also been sent.

	Parity bit	Bit 2	Bit 3	Bit 4	Bit 5	Bit 6	Bit 7	Bit 8
Byte 1	1	1	1	1	0	1	1	0
Byte 2	1	0	0	1	0	1	0	1
Byte 3	0	1	1	1	1	1	1	0
Byte 4	1	0	0	0	0	0	1	0
Byte 5	0	1	1	0	1	0	0	1
Byte 6	1	0	0	0	1	0	0	0
Byte 7	1	0	1	0	1	1	1	1
Byte 8	0	0	0	1	1	0	1	0
Byte 9	0	0	0	1	0	0	1	0
Parity byte	1	1	0	1	0	0	0	1

A careful study shows:Byte 8has incorrect parity (there are three 1s, which is odd — even parity expected).Bit 5(column 5) also has incorrect parity (there are five 1s, which is odd). At the intersection of row 8 and column 5, the position of the incorrect bit value can be found.

This means that byte 8 should have the value:00010010(instead of00011010). The error can be corrected automatically.

Activity 3: Parity Block Check Practice

The following block of data was received after transmission from a remote computer.Odd paritywas being used by both sender and receiver. One of the bits has been changed during transmission. Locate where this error is and suggest a corrected byte value.

	Parity bit	Bit 2	Bit 3	Bit 4	Bit 5	Bit 6	Bit 7	Bit 8
Byte 1	0	1	1	0	0	0	1	0
Byte 2	1	0	1	1	1	1	1	1
Byte 3	1	0	0	1	1	0	0	0
Byte 4	0	1	1	0	1	0	1	0
Byte 5	1	1	1	0	0	1	1	0
Byte 6	1	0	0	0	0	1	0	1
Byte 7	0	1	1	1	0	0	0	0
Byte 8	0	0	0	0	0	0	1	1
Byte 9	0	1	1	1	1	0	1	0
Parity byte	1	0	1	1	1	1	0	0

Solution:

Byte 5has incorrect parity (four 1s — even — but odd parity expected).
Column 4(Bit 4) has incorrect parity (four 1s — even — but odd parity expected).
The error is at the intersection:Byte 5, Bit 4.
The corrected byte value is:11111010(changing the 0 in Bit 4 to 1).

Check Your Understanding: Parity Block Checks

1. What is a parity byte? [2 marks]

[1]An extra byte sent with a block of data containing the parity bits from the vertical parity check
[1]It also indicates the end of the block of data

2. How does a parity block check improve on a simple parity check? [2 marks]

[1]A simple parity check can only detect that an error has occurred
[1]A parity block check can identify the exact position of the error (using horizontal and vertical checks) so it can be corrected

3. A block of data is sent using even parity. Byte 3 has odd parity and Column 2 has odd parity. Where is the error? [2 marks]

[1]The error is at the intersection of Byte 3 and Column 2
[1]The bit at Byte 3, Column 2 needs to be flipped to correct the error

4. What are the two directions of parity checking in a parity block check? [2 marks]

[1]Horizontal parity check (on each byte/row)
[1]Vertical parity check (on each column, producing the parity byte)

5. Why is a parity block check more useful than a single parity check? [2 marks]

[1]It can identify the exact location of the error
[1]This means the error can be corrected without retransmitting the entire block of data

6. What happens if two bits change value in the same byte during transmission? [2 marks]

[1]It may be impossible to locate the error using the parity block method
[1]The parity of the byte and the column may still match, so the error goes undetected

4. Checksum

Achecksumis another way to check if data has been changed or corrupted following data transmission. Data is sent inblocksand an additional value, the checksum, is also sent at the end of the block of data.

How a Checksum Works

When a block of data is about to be transmitted, thechecksumfor the bytes is first calculated.
This value is thentransmitted with the block of data.
At the receiving end, the checksum isrecalculatedfrom the block of data received.
This calculated value is thencomparedto the checksum transmitted.
If they are the same value, then the data was transmitted without any errors.
If the values are different, then a request is sent for the data to be retransmitted.

Checksum Algorithm

Assume the checksum of a block of data is 1 byte in length. This gives a maximum value of 255. The value 0000 0000 is ignored in this calculation.

If the sum of all bytes in the data block is ≤ 255, the checksum is this value.
If the sum ≥ 255, the checksum is found using the algorithm shown below.

Checksum Algorithm Steps

Suppose X = 1185

1. Divide X by 256: 1185 ÷ 256 = 4.629

2. Round down to nearest whole number: Y = 4

3. Multiply: Z = Y × 256 = 1024

4. Difference: X − Z = 1185 − 1024 = 161

Checksum = 161

Algorithm Summary

1. Divide the sum, X, of the bytes by 256

2. Round the answer down to the nearest whole number, Y

3. Z = Y × 256

4. Calculate the difference (X − Z)

5. This value is the checksum

Interactive Checksum Calculator

Enter a sum of bytes to calculate the checksum using the algorithm.

Sum of bytes (X)

Activity 4: Checksum Calculations

Calculate the checksum for blocks of data with the following byte sums:

148
905
1450
4095

Solution:

148 is ≤ 255, so the checksum is148.
905 ÷ 256 = 3.535 → Y = 3; Z = 3 × 256 = 768; 905 − 768 =137
1450 ÷ 256 = 5.664 → Y = 5; Z = 5 × 256 = 1280; 1450 − 1280 =170
4095 ÷ 256 = 15.996 → Y = 15; Z = 15 × 256 = 3840; 4095 − 3840 =255

Check Your Understanding: Checksum

1. What is a checksum? [2 marks]

[1]A value calculated from a block of data using an agreed algorithm
[1]It is transmitted with the data and recalculated at the destination to check for errors

2. How does the receiver know if the data has been transmitted correctly when using a checksum? [2 marks]

[1]The receiver recalculates the checksum from the received data
[1]If the recalculated checksum matches the transmitted checksum, no errors occurred; otherwise an error is detected

3. Calculate the checksum for a byte sum of 2000. [2 marks]

[1]2000 ÷ 256 = 7.8125 → Y = 7; Z = 7 × 256 = 1792
[1]Checksum = 2000 − 1792 = 208

4. If a checksum of 0 is calculated, what happens? [1 mark]

[1]The value 0000 0000 is ignored in the calculation — the checksum would not be 0

5. Why might a checksum fail to detect an error? [2 marks]

[1]If multiple errors occur that cancel each other out (e.g. one bit changes from 0 to 1 and another from 1 to 0)
[1]The sum of bytes could remain the same, so the checksum would match and the error goes undetected

6. What happens if the checksums do not match at the receiving end? [1 mark]

[1]A request is sent for the data to be retransmitted

5. Echo Check

Echo check:when data is sent to another device, this data is sent back again to the sender. The sender compares the two sets of data to check if any errors occurred during the transmission process.

How Echo Check Works

A copy of the data is sent back to the sender.
The returned data is compared with the original data by the sender's computer.
If there are no differences, then the data was sent without error.
If the two sets of data are different, then an error occurred at some stage during data transmission.
If an error occurs, the sender will retransmit the data.

Limitations

This method isn't very reliable.
If the two sets of data are different, it isn't known whether the error occurred when sending the data in the first place, or if the error occurred when sending the data back for checking.
However, if no errors occurred, it is another way to check that the data was transmitted correctly.

Real-Life Example: Echo Check in Communication

Think of an echo check like a phone conversation where you repeat back what the other person said to confirm you heard them correctly. If you repeat it back incorrectly, the other person knows there was a misunderstanding. However, you can't tell if the misunderstanding was because they said it wrong or because you heard it wrong!

Activity 5: Echo Check

Describe how an echo check is used to detect errors in data transmission. [3]
Explain one limitation of the echo check method. [2]

Solution:

The receiving device sends an exact copy of the data it has just received back to the sender [1]. The sender compares the returned data with the original data [1]. If there are no differences, the data was transmitted correctly; if there are differences, an error occurred [1].
The method is unreliable because if the two sets of data are different, it isn't known whether the error occurred when sending the data in the first place, or if the error occurred when sending the data back for checking [2].

Check Your Understanding: Echo Check

1. What is an echo check? [2 marks]

[1]The receiving device returns an exact copy of the data it has just received to the sender
[1]The sender compares the returned data with the original to check for errors

2. Why is an echo check considered unreliable? [2 marks]

[1]If the data is different, it isn't known whether the error occurred when sending the data originally
[1]Or if the error occurred when sending the data back for checking

3. What happens if the sender's data and the echoed data are the same? [1 mark]

[1]The data was transmitted without error

4. What happens if an error is detected during an echo check? [1 mark]

[1]The sender will retransmit the data

5. Which two devices are involved in an echo check? [1 mark]

[1]The sender and the receiver (the receiver echoes the data back to the sender)

6. Compare echo check with parity check. [2 marks]

[1]Parity check adds an extra bit to each byte and the receiver checks if the parity matches
[1]Echo check sends the entire data back to the sender for comparison; it can detect errors that parity might miss but is less efficient

6. Check Digits (ISBN & Barcodes)

Acheck digitis the final digit included in a code; it is calculated from all the other digits in the code. It is used to detect errors indata entry.

Types of Errors Detected

Phonetic errors— e.g. 13 (thirteen) instead of 30 (thirty)
Transposition errors— where two numbers have changed order, e.g. 4087 instead of 4807
Incorrect digit entered— e.g. 5327 entered instead of 5307
Omitted or extra digits— e.g. 537 instead of 5307, or 53107 instead of 5307

Applications of Check Digits

ISBN— International Standard Book Numbers
Barcodes— on products in shops
Vehicle Identification Numbers (VIN)
Bank account numbers

ISBN-10 Check Digit (Modulo-11)

Calculating a Check Digit (Modulo-11)

The ISBN-10 number system used for books makes use of a process calledModulo-11to create its check digit.

Example: Product code 817525765

Product code: 8 1 7 5 2 5 7 6 5

Weighting: 10 9 8 7 6 5 4 3 2

Multiply: 80 + 9 + 56 + 35 + 12 + 25 + 28 + 18 + 10 = 273

273 ÷ 11 = 24 remainder 9

11 − 9 = 2

Check digit = 2; complete number: 8175257652

Checking a Check Digit

To check that a code number is valid, it is NOT necessary to recalculate the check digit completely. If the check digit itself is assigned a weight of 1, and the products of the digits (including the check digit) and their respective weights are calculated, their sum will be divisible by 11 if the check digit is correct.

Checking 8175257652

Weighting: 10 9 8 7 6 5 4 3 2 1

Products: 80 + 9 + 56 + 35 + 12 + 25 + 28 + 18 + 10 + 2 = 275

275 ÷ 11 = 25 remainder 0

Remainder is 0 → the number is valid

Barcodes

Barcodes consist of black and white lines which can be scanned using barcode scanners.
Barcode scanners shine a laser on the black and white lines which reflect light into the scanner.
The scanner reads the distance between these lines as numbers and can identify the item.
Thefinal digiton a barcode is usually thecheck digit— this can be used to validate and authenticate an item.

Interactive Check Digit Calculator (Modulo-11)

Enter a 9-digit product code to calculate its check digit.

Product code (9 digits)

Activity 6: Check Digits

Calculate the check digit for the code number 4 2 4 1 5 0 8. Show all working. [3]
An operator has just keyed in the following code number: 3 2 4 0 0 4 5 X. Has the operator correctly keyed in the code number? Give a reason for your answer. [3]

Solution:

(4×1) + (2×2) + (4×3) + (1×4) + (5×5) + (0×6) + (8×7)
= 4 + 4 + 12 + 4 + 25 + 0 + 56 = 105
105 ÷ 11 = 9 remainder 6
Check digit =6
Incorrect check digit [1]. The calculation is: (3×1) + (2×2) + (4×3) + (0×4) + (0×5) + (4×6) + (5×7) = 3 + 4 + 12 + 0 + 0 + 24 + 35 = 78 [1]. 78 ÷ 11 = 7 remainder 1, so the check digit should be1, not X [1].

Check Your Understanding: Check Digits

1. What is a check digit? [2 marks]

[1]The final digit included in a code or identification number
[1]It is calculated from all the other digits and used to validate the code

2. Name two applications of check digits. [2 marks]

[1]ISBN (International Standard Book Numbers) or barcodes
[1]Vehicle Identification Numbers (VIN) or bank account numbers

3. What types of errors can a check digit detect? [3 marks]

[1]Phonetic errors (e.g. thirteen instead of thirty)
[1]Transposition errors (two digits swapped)
[1]Incorrect digit entered, or omitted/extra digits

4. Calculate the check digit for product code 123456789. [3 marks]

[1](1×10) + (2×9) + (3×8) + (4×7) + (5×6) + (6×5) + (7×4) + (8×3) + (9×2)
[1]= 10 + 18 + 24 + 28 + 30 + 30 + 28 + 24 + 18 = 210
[1]210 ÷ 11 = 19 remainder 1; 11 − 1 =10→ check digit isX

5. How is a check digit used with barcodes? [2 marks]

[1]The final digit on a barcode is usually the check digit
[1]It can be used to validate and authenticate an item when scanned

6. What is the Modulo-11 method? [2 marks]

[1]A method of calculating a check digit where each digit is assigned a weight and multiplied by that weight
[1]The sum of the products is divided by 11, and the remainder is subtracted from 11 to give the check digit

7. Automatic Repeat Request (ARQ)

Automatic Repeat Request (ARQ)— also known as Automatic Repeat Query — is another method used to check whether data has been correctly transmitted. It uses anacknowledgementand atimeout.

How ARQ Works

The receiving device receives the data transmission along with anerror detection code(typically a Cyclic Redundancy Check — CRC).
The code is used to determine if the data contains any transmission errors.
Ifno errorshave been detected, apositive acknowledgementis sent back to the sending device.
If anerroris detected, anegative acknowledgementis sent and a re-transmission request is made.
After a pre-determined amount of time (thetimeout), if the sending device hasn't received any form of acknowledgement, it will automatically re-send the data.
It will keep doing this until it either receives a positive acknowledgement or a pre-determined number of attempts have taken place.

Key Concepts

Acknowledgement— a message sent by the receiver indicating that data has been received correctly (positive) or incorrectly (negative).
Timeout— the time allowed to elapse before an acknowledgement is received. If an acknowledgement isn't sent back to the sender before timeout occurs, then the message is automatically resent.
ARQ is an error control and packet recovery method for data transmission.
Application:ARQ is used by mobile phone networks to guarantee data integrity.

Positive vs Negative Acknowledgements

Positive Acknowledgement

Sent when no errors have been detected. This tells the sender that the data was received correctly and no re-transmission is needed.

Negative Acknowledgement

Sent when an error is detected. This tells the sender that the data is corrupted and a re-transmission is requested.

Activity 7: Automatic Repeat Request

Explain how Automatic Repeat Request (ARQ) is used in error detection. [4]
State one application where ARQ is used. [1]

Solution:

Any four from:
- Uses acknowledgement and timeout
- A check is performed on received data (e.g. parity check, checksum) to detect errors
- If an error is detected, a request is sent to resend the data (negative acknowledgement)
- If no error is detected, a positive acknowledgement is sent
- If no acknowledgement is received within a certain time frame, the data is automatically resent
- The resend request is repeated until the packet is received error-free or a limit is reached
Mobile phone networks / any appropriate application [1]

Check Your Understanding: ARQ

1. What is an Automatic Repeat Request (ARQ)? [2 marks]

[1]An error detection method that uses acknowledgement and timeout
[1]If a response is not sent back to the sender in an agreed amount of time, the data is resent

2. What is a positive acknowledgement? [1 mark]

[1]A message sent by the receiver indicating that data has been received correctly

3. What is a negative acknowledgement? [1 mark]

[1]A message sent by the receiver indicating that data has NOT been received correctly and requesting a re-transmission

4. What is a timeout in ARQ? [2 marks]

[1]The time allowed to elapse before an acknowledgement is received
[1]If no acknowledgement is received within this time, the sender automatically resends the data

5. What happens if the sender does not receive any acknowledgement? [2 marks]

[1]After a timeout period, the sender automatically re-sends the data
[1]It will keep doing this until it receives a positive acknowledgement or a pre-determined number of attempts have taken place

6. Why is ARQ useful for mobile phone networks? [2 marks]

[1]Mobile phone signals can be affected by interference and physical barriers, causing data errors
[1]ARQ ensures data integrity by automatically resending data that is not acknowledged, so calls and messages are not corrupted

Key Takeaways

Errors occur during data transmission due tointerference(electrical noise, wireless signals) andpacket switching problems. Results includedata loss, data gain, and data change.
Parity check:An extra bit is added to a byte so the total number of 1s is either odd or even. The sender and receiver must agree on the type of parity before transmission.
Parity block check:Horizontal and vertical parity checks on a block of data can identify the exact position of an error and allow it to be corrected. Aparity byteis sent with the block.
Checksum:A value calculated from a block of data using an algorithm, transmitted with the data. The receiver recalculates and compares. If they differ, an error occurred.
Echo check:The receiver sends the data back to the sender, who compares it. Simple but unreliable — cannot determine where the error occurred.
Check digit:The final digit in a code, calculated from the other digits. Used inISBN,barcodes, andVINs. Detects phonetic errors, transposition errors, incorrect digits, and omitted/extra digits.
Modulo-11:A check digit calculation method where digits are weighted, multiplied, summed, divided by 11, and the remainder subtracted from 11.
ARQ (Automatic Repeat Request):Usespositive acknowledgement(data received correctly),negative acknowledgement(error detected, resend), andtimeout(if no acknowledgement received within a set time, data is automatically resent).
Parity checks are quick but can miss errors if an even number of bits change. Parity block checks are more robust.
ARQ is used by mobile phone networks to guarantee data integrity.

Question Bank

1. Describe how a parity check can be used to detect errors in data transmission. [4 marks]

[1]The most significant bit is used as a parity bit
[1]The parity bit is set so the total number of 1s is either odd or even (depending on agreed parity)
[1]The sender and receiver must agree on the type of parity before transmission
[1]If the number of 1s does not match the agreed parity at the receiver's end, an error is detected

2. A system uses even parity. Write the appropriate parity bit for each byte. [3 marks]

10100111→ 5 ones → parity bit =1
01111110→ 6 ones → parity bit =0
00000101→ 2 ones → parity bit =0

3. Explain how a parity block check can identify the position of an error. [4 marks]

[1]Data is sent as a block of bytes with a parity byte
[1]A horizontal parity check is performed on each byte
[1]A vertical parity check is performed on each column, producing the parity byte
[1]The intersection of the byte and column with incorrect parity identifies the error position

4. Describe how a checksum is used to detect errors in data transmission. [4 marks]

[1]A checksum is calculated using an agreed algorithm applied to the block of data
[1]The checksum is transmitted with the data
[1]The receiver recalculates the checksum using the received data
[1]If the checksums match, no errors occurred; if they differ, an error occurred and a retransmission is requested

5. Describe how an echo check is used to detect errors in data transmission. [3 marks]

[1]The receiving device sends an exact copy of the data back to the sender
[1]The sender compares the returned data with the original data
[1]If there are differences, an error occurred and the data is re-sent

6. Explain how Automatic Repeat Request (ARQ) is used in error detection. [5 marks]

[1]The receiver checks the received data for errors using an error detection code
[1]If no error is detected, a positive acknowledgement is sent back
[1]If an error is detected, a negative acknowledgement / re-transmission request is sent
[1]The sender waits a pre-determined time (timeout) for an acknowledgement
[1]If no acknowledgement is received within the timeout, the data is automatically re-sent until a positive acknowledgement is received or a limit is reached

7. A 7-digit code number has a check digit. Calculate the check digit for 4 2 4 1 5 0 8. Show all working. [3 marks]

[1](4×1) + (2×2) + (4×3) + (1×4) + (5×5) + (0×6) + (8×7)
[1]= 4 + 4 + 12 + 4 + 25 + 0 + 56 = 105
[1]105 ÷ 11 = 9 remainder 6; 11 − 6 =5

8. Explain what is meant by a check digit and give two examples of where check digits are used. [4 marks]

[1]A check digit is the final digit in a code or identification number
[1]It is calculated from all the other digits and used to validate the code
[1]ISBN (International Standard Book Numbers)
[1]Barcodes / Vehicle Identification Numbers (VIN)

9. A parity check may not identify that a bit has been transmitted incorrectly. Describe one situation in which this could occur. [2 marks]

[1]An even number of bits are changed during transmission
[1]The total number of 1s still matches the agreed parity, so the error goes undetected

10. What is a positive acknowledgement and when is it sent in ARQ? [2 marks]

[1]A message sent by the receiver indicating that data has been received correctly
[1]It is sent when no errors are detected in the received data

11. Explain how a parity block check can detect and correct an error. [4 marks]

[1]Each byte has a horizontal parity check
[1]Each column has a vertical parity check (the parity byte)
[1]An error is detected if a row and a column both have incorrect parity
[1]The intersection identifies the exact bit that is incorrect, which can then be corrected

12. Explain why a checksum might not detect an error even if the data has been corrupted. [2 marks]

[1]Multiple errors could occur that cancel each other out (e.g. one bit changes from 0 to 1 and another from 1 to 0)
[1]The sum of bytes could remain the same, so the recalculated checksum matches and the error goes undetected

13. What is the purpose of a timeout in ARQ? [2 marks]

[1]It is the time allowed to elapse before an acknowledgement is received
[1]If the sender does not receive an acknowledgement within the timeout, it automatically resends the data

14. A barcode system uses odd parity. The binary number from the barcode is 1011010. What is the parity bit? [2 marks]

[1]There are four 1s in the binary number (even)
[1]To make odd parity, the parity bit must be1(total = five 1s)

15. Compare parity checks with checksums as error detection methods. [4 marks]

[1]Parity checks add one bit per byte; checksums calculate a value from a whole block of data
[1]Parity checks can only detect that an error has occurred; a parity block check can identify the location
[1]Checksums can detect errors where parity might miss them (e.g. multiple bit changes)
[1]Both require an agreed algorithm/protocol between sender and receiver, and both may fail to detect certain types of errors