Ch 2 · 2.2 Methods of Error Detection · O Level Computer Science 2210
Topic 2 of 3 in Data Transmission — O Level Computer Science 2210 — 68 lessons.
Introduction
A single flipped bit can turn a payment of 100 into 228. When data travels along wires or through the air, errors happen. This lesson covers the methods computers use to spot them, and to ask for the data again. (Syllabus section 2.2.)
Key ideas — Why errors happen
During transmission, interference (electrical noise, weak wireless signals, damaged cables) can corrupt data:
🧑🏫 Teacher's explanation
Imagine you are sending a text message to a friend, but you are standing next to a loud construction site. The noise from the drill might cause you to mishear a word (data change), cause you to skip a word entirely (data loss), or cause you to repeat a word twice (data gain). In computer science, 'noise' isn't just sound; it is electrical interference that disrupts the signals traveling through cables or airwaves.
📖 Definitions
🔍 Worked example — Easy
A 7-bit data packet is transmitted as 1011001. Due to interference, a bit is flipped. Identify the three possible resulting bit patterns if only one bit changes.
🔍 Worked example — Standard
A data stream is sent as 11010110. During transmission, a bit is lost (data loss). List two possible received sequences that are 7 bits long.
🔍 Worked example — Exam-style
A system uses a parity check. A byte is sent as 10101101. If a single bit is flipped (data change), what is the new bit pattern? Assume we are checking for even parity.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Identify the type of error that has occurred. [1] (b) Explain why the receiver needs to perform an error detection check on the received data. [2] [3 marks]
Key ideas — Parity check
Before sending, a parity bit is added to each byte (usually as the MSB) so that the total number of 1s is:
🧑🏫 Teacher's explanation
Imagine you are sending a secret message to a friend using a flashlight. To make sure they receive the right message, you decide that every time you flash a sequence of lights, you will add one extra flash at the end to ensure the total number of flashes is always an even number. If your friend counts the flashes and gets an odd number, they know you made a mistake.
📖 Definitions
🔍 Worked example — Easy
A sender uses even parity. The data byte to be sent is 1011001. Determine the parity bit and the resulting transmitted byte.
🔍 Worked example — Standard
A system uses odd parity. A byte arrives at the receiver as 11011101. Does an error occur? Show the count of 1s.
🔍 Worked example — Exam-style
A 4 imes 4 data block is sent using a parity block check (even parity). The bits are: Row 1: 1010 Row 2: 0110 Row 3: 1100 Row 4: 0001 If the receiver calculates the column parity byte and finds the error is at Row 2, Column 3, what was the original bit in Row 2, Column 3?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Explain how the receiver can use this information to correct the error. [2] (b) State one limitation of using a simple parity bit instead of a parity block. [1] [3 marks]
Key ideas — Checksum
🧑🏫 Teacher's explanation
Imagine you are sending a long list of numbers to a friend via text message. To make sure they didn't misread a digit, you add all the numbers together and send that total at the end. Your friend then adds up the numbers they received. If their total matches your total, they can be confident the list is correct. If the totals don't match, they know something went wrong.
📖 Definitions
🔍 Worked example — Easy
A sender transmits the following sequence of 8-bit bytes: 01101001, 01101110, and 01100101. The agreed algorithm is to sum the decimal values of the bytes and send the remainder when divided by 256. Calculate the checksum.
🔍 Worked example — Standard
A data block contains the bytes: 10, 20, 30, 40. The checksum is the sum of these values. During transmission, the byte 30 is corrupted to 35. If the original checksum was 100, what is the new checksum calculated by the receiver?
🔍 Worked example — Exam-style
A system uses a checksum algorithm where the checksum is the sum of all bits (1s) in a data stream. The data stream is 11010110. Calculate the checksum. If the receiver receives 11011110, explain why the error is detected.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — Echo check
Drawback: it doubles the amount of data sent, and if they differ you cannot tell whether the error happened on the way there or on the way back.
🧑🏫 Teacher's explanation
Imagine you are playing a game of 'Telephone' where you whisper a secret to a friend. To make sure they heard you correctly, you ask them to whisper the exact same secret back to you. If the secret they whisper back is different from the one you originally said, you know someone made a mistake. This is exactly how an echo check works in computer networks.
📖 Definitions
🔍 Worked example — Easy
A sender transmits the binary string 10110110. The receiver echoes back 10110111. Determine if an error is detected and state the outcome.
🔍 Worked example — Standard
A system uses an echo check for a file of size 100 ext MB. Calculate the total amount of data transmitted (original + echo) assuming no errors occur.
🔍 Worked example — Exam-style
A sender transmits A = 1100 and receives echo B = 1100. A second transmission sends C = 1010 and receives D = 1011. For the second transmission, identify the error type and the limitation of the echo check.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — Check digits (data entry)
A check digit is an extra digit calculated from the other digits of a number and added to the end. It detects errors made when the number is entered (typed or scanned), such as a wrong digit or two digits swapped (transposed).
🧑🏫 Teacher's explanation
Imagine you are writing a long list of phone numbers for a friend. To make sure you haven't made a typo, you decide that the last digit of every number should be the sum of all the previous digits, modulo 10. If you accidentally type a '7' instead of a '4', your 'check digit' won't match the sum of the other numbers, and you'll know immediately that you made a mistake.
📖 Definitions
🔍 Worked example — Easy
A simple check digit is calculated by taking the sum of the first four digits of a code and finding the remainder when divided by 10. If the code is 4521, calculate the check digit.
🔍 Worked example — Standard
Using an ISBN-13 style weighting where digits are multiplied by alternating weights of 1 and 3, calculate the check digit for the sequence 9780123.
🔍 Worked example — Exam-style
A barcode uses a check digit. The sum of the digits (including the check digit) must be divisible by 10. A user enters the digits 5678 and then enters 2 as the check digit. Determine if this is a valid entry.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Explain how the system can use this check digit to detect if a user has made an error during entry. [2]
Key ideas — Automatic repeat query (ARQ)
ARQ uses acknowledgements and timeouts:
🧑🏫 Teacher's explanation
Imagine you are sending a series of fragile glass vases through the mail. To ensure they arrive safely, you ask the recipient to send you a text message every time a box arrives. If they text you 'Box 1 received!', you move to the next one. If they text 'Box 1 broken!', you send it again. If you don't hear from them for three days, you assume the package was lost in transit and you send it again anyway.
📖 Definitions
🔍 Worked example — Easy
A sender transmits a packet. The receiver detects a checksum error. Describe the immediate next step in the ARQ process.
🔍 Worked example — Standard
A sender transmits packet P_1. The sender waits for 500 extms. If no signal is received within 500 extms, what action is taken?
🔍 Worked example — Exam-style
Trace the following scenario:
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Describe how the receiver uses acknowledgements to ensure data is received without error. [3] (b) Explain why a 'timeout' is necessary in the ARQ process. [2] [5 marks]
Worked example
Example 1: even parity. Which of these bytes contains an error, if even parity is used? 10110100 (four 1s: OK), 01110011 (five 1s: error), 11000011 (four 1s: OK).
🔍 Worked example — Standard
Calculate the check digit for the number 5291 using weights 1, 3, 1, 3 and a modulus 10 system (subtracting the result from 10).
🔍 Worked example — Exam-style
A data packet is sent using ARQ. The receiver receives the packet but the checksum does not match. Describe the sequence of events that occurs to ensure data integrity.
⚠️ Common errors
Common mistakes
Practice
Answers: (1) Data loss, data gain, data change (caused by interference). (2) 1100101 has four 1s; odd parity needs an odd total, so the parity bit is 1: 11100101. (3) Each byte has a parity bit and a parity byte checks each column; the wrong bit lies where the row with the parity error crosses the column with the parity error. (4) The sender calculates a checksum from the data and sends it with the data; the receiver recalculates it; if the values differ, there is an error and the data is re-sent. (5) If the sender receives no acknowledgement within the timeout, it assumes the packet was lost or corrupted and re-sends it. (6) Any two: ISBNs, bar codes, account numbers.