Study Guide
Error Detection
Why data can be damaged on its way across a network, and how parity checks, checksums, echo checks, check digits and automatic repeat query let a receiver notice a mistake and ask for the data again.
Lesson 4.3 Networks, the Internet and Security
For: Cambridge IGCSE Computer Science learners, or anyone who wants to know how a computer can tell that data has been damaged
Stage: Think
A message that changes on the way
In the playground game of whispers, a message is passed along a line of pupils by whispering. By the end, “Meet at the library at three” has become “Eat a pie at the lorry at tea”. Nobody meant to change it.
Think it through
Data travelling through a cable or through the air can be changed in the same way. How might it happen, and how could the receiver tell that a message had been changed, without knowing the original?
- Hint 1: What could disturb an electrical signal in a cable, or a radio signal through the air?
- Hint 2: Could the sender add something extra to the message for the receiver to check?
Show a model answer
Anything that disturbs the signal can change it: electrical noise from nearby machinery, other signals in a neighbouring wire, a weak signal over a long distance, or a radio signal passing through walls. To tell that a message had changed, the sender could add something extra, worked out from the message, which the receiver can work out again and compare. That is the idea behind everything in this lesson.
When something disturbs a signal on its way, the disturbance is called interference. It can damage data in three ways:
| Bits sent | Bits received | Data loss, gain or change? |
|---|---|---|
| 10110010 | 10010010 | |
| 10110010 | 1011001 | |
| 10110010 | 101100101 |
- Count the bits sent and received: are there fewer, more or the same number?
- If the number of bits is the same, compare them one at a time.
Show the completed table
| Bits sent | Bits received | Data loss, gain or change? |
|---|---|---|
| 10110010 | 10010010 | change |
| 10110010 | 1011001 | loss |
| 10110010 | 101100101 | gain |
Stage: Discover
An extra bit that makes the count of 1s even
Suppose the sender and receiver agree on a rule: every byte must have an even number of 1s. A byte has eight bits, and the first seven carry the data. The eighth is a spare bit, which the sender sets to 0 or 1 to make the rule come true.
Think it through
The seven data bits are 1011001. How many 1s do they hold? What must the spare bit be, so that the whole byte has an even number of 1s?
- Hint 1: Count the 1s in 1011001.
- Hint 2: Is that number even or odd? What would you add to make it even?
Show what happens
1011001 has four 1s, which is already even, so the spare bit is 0, and the byte is 0 1011001. If the data had held an odd number of 1s, the spare bit would be 1.
The spare bit is the parity bit. Putting it in the byte so that the number of 1s is even is even parity; making the number odd instead is odd parity. Together, the rule and the process of testing it make up the parity check. The sender and receiver must agree in advance whether they use even or odd parity.
A sender wants to send the seven data bits 0110100 using even parity.
- Count the 1s in the data. 0110100 has three 1s.
- Decide what the parity bit must be. Three is odd, so one more 1 makes four, which is even. The parity bit is 1.
- Put the parity bit at the left and send the byte. The byte is 1 0110100.
- The receiver counts the 1s in the whole byte. If 10110100 arrives, there are four 1s, which is even, so the byte passes the check. If 10110000 arrives, there are three 1s, which is odd, so the receiver knows the byte was damaged.
For odd parity the steps are the same, but the parity bit makes the total odd, so the same data would have been sent as 0 0110100.
| 7 data bits | Number of 1s | Even parity bit | Odd parity bit |
|---|---|---|---|
| 1011001 | 4 | 0 | 1 |
| 1100110 | |||
| 0010000 | |||
| 1111111 | |||
| 0100001 |
- For even parity, the total number of 1s must be even.
- For odd parity, the total must be odd, so the bit is the opposite of the even parity bit.
Show the completed table
| 7 data bits | Number of 1s | Even parity bit | Odd parity bit |
|---|---|---|---|
| 1011001 | 4 | 0 | 1 |
| 1100110 | 4 | 0 | 1 |
| 0010000 | 1 | 1 | 0 |
| 1111111 | 7 | 1 | 0 |
| 0100001 | 2 | 0 | 1 |
Check your understanding
Show the answer
Answer: C. There is an error, because the byte has five 1s, which is an odd number.
Count every 1 in the whole byte: 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5, which is odd, so at least one bit has changed.
Apply it
Show the answer
Answer: A. No error, even though two bits changed: the byte has six 1s, an even number.
The receiver only sees the byte that arrived. 01111011 has six 1s, an even number, so it passes. Parity can miss an error when an even number of bits change.
A parity check does not prove that a byte is correct, and it does not say which bit changed. It only shows that an odd number of bits changed. An even number of changes goes unnoticed. This is why parity is often combined with other checks.
Stage: Predict
Finding the bit that flipped: parity blocks
One check on its own cannot say which bit changed. Imagine that, as well as a parity bit for each byte, a whole block of four bytes is sent with one extra byte at the end, made by checking each column.
Think it through
Suppose one bit in the middle of a block changes. The parity check of its row will fail, because that row now has the wrong number of 1s. If the columns have a parity check too, what will happen to the column that bit is in? How could the receiver use the two together?
- Hint 1: Which row is wrong, and which column is wrong?
- Hint 2: Where do the row and the column cross?
Show what happens
The column the bit belongs to will fail its check too. The receiver finds the row that fails and the column that fails. The flipped bit is where they cross.
A group of bytes sent together is a block. Each byte has its own parity bit. After the last byte comes an extra byte, the parity byte, whose bits are the parity bits of the columns: its first bit makes the first column even, its second bit makes the second column even, and so on. The whole block, with its parity byte, is a parity block.
Here is a block of four bytes, sent with even parity. P is the parity bit of each row. The parity bit of each column is in the last row.
| Row | P | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 2 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| Parity byte | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
The sender worked out the parity byte by counting the 1s in each column of the four rows. Do the same for the columns, and check the answer against the last row of the block. Columns P and 1 are done for you.
| Column | Number of 1s in rows 1 to 4 | Even parity bit for the column |
|---|---|---|
| P | 1 | 1 |
| 1 | 2 | 0 |
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 |
- Count down the column, rows 1 to 4, not including the parity byte.
- If the count is odd, the parity bit must be 1; if even, 0.
Show the completed table
| Column | Number of 1s in rows 1 to 4 | Even parity bit for the column |
|---|---|---|
| P | 1 | 1 |
| 1 | 2 | 0 |
| 2 | 2 | 0 |
| 3 | 3 | 1 |
| 4 | 2 | 0 |
| 5 | 2 | 0 |
| 6 | 2 | 0 |
| 7 | 2 | 0 |
The block is sent, and this arrives. One bit has changed on the way. Find which one.
| Row | P | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 2 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| Parity byte | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| Row | Number of 1s | Passes even parity? |
|---|---|---|
| 1 | 4 | yes |
| 2 | ||
| 3 | ||
| 4 | ||
| Parity byte |
- Count every 1 in the row, including the parity bit P.
- Even parity passes when the count is even.
Show the completed table
| Row | Number of 1s | Passes even parity? |
|---|---|---|
| 1 | 4 | yes |
| 2 | 3 | no |
| 3 | 4 | yes |
| 4 | 4 | yes |
| Parity byte | 2 | yes |
| Column | Number of 1s | Passes even parity? |
|---|---|---|
| P | 2 | yes |
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 |
- Count down the column, including the parity byte at the bottom.
Show the completed table
| Column | Number of 1s | Passes even parity? |
|---|---|---|
| P | 2 | yes |
| 1 | 2 | yes |
| 2 | 2 | yes |
| 3 | 4 | yes |
| 4 | 2 | yes |
| 5 | 1 | no |
| 6 | 2 | yes |
| 7 | 2 | yes |
Check your understanding
Show the answer
Answer: B. Row 2, column 5, which was 1 before: the bit is now 0.
Row 2 and column 5 cross at one bit. The row and column checks together locate it, which a parity check on a single byte cannot do. A system can then correct the bit by flipping it, or ask for the block to be sent again.
Stage: Explain
A sum worked out from the data: the checksum
Parity looks at 1s and 0s. A different idea works with the values of the data: the sender adds up the data, and sends the total as well.
Think it through
A shop sends four numbers to its head office: 200, 150, 90 and 45. How could it send one extra number that lets the head office check that nothing was changed on the way? What would the head office do?
- Hint 1: What could the shop work out from the four numbers?
- Hint 2: What would the head office have to do with the numbers it received?
Show what happens
The shop could add the four numbers and send the total with them. The head office adds the four numbers it received and compares its total with the one sent. If the totals are different, something was changed.
A value worked out from the data by an agreed method and sent with it is a checksum. The receiver works the checksum out again from the data it received. If the two checksums are the same, the data is very likely correct; if they are different, there is an error. Real checksums use many methods; this lesson uses a simple one: add up the byte values, divide the total by 256, and keep the remainder, so that the checksum fits in one byte.
The data bytes are 200, 150, 90 and 45.
- Add the byte values. 200 + 150 = 350, then 350 + 90 = 440, then 440 + 45 = 485.
- Divide by 256 and keep the remainder, so that the result fits in one byte. 485 ÷ 256 = 1, remainder 229. The checksum is 229.
- The sender sends the four bytes and the checksum 229.
- The receiver does the same. Suppose it receives 200, 156, 90, 45. The total is 200 + 156 + 90 + 45 = 491, and 491 − 256 = 235. 235 is not 229, so an error is reported.
| Step | Value |
|---|---|
| Add the first byte: 60 | 60 |
| Add the second byte: 130 | |
| Add the third byte: 99 | |
| Add the fourth byte: 180 | |
| The remainder after dividing by 256: the checksum |
- Add one byte at a time, using the running total.
- The checksum is the remainder after dividing the total by 256. If the total is less than 512, subtract 256 once.
Show the completed table
| Step | Value |
|---|---|
| Add the first byte: 60 | 60 |
| Add the second byte: 130 | 190 |
| Add the third byte: 99 | 289 |
| Add the fourth byte: 180 | 469 |
| The remainder after dividing by 256: the checksum | 213 |
Check your understanding
Show the answer
Answer: D. An error has occurred, because 221 is not 213, so the data or checksum changed.
The values differ, so the receiver reports an error.
A matching checksum makes an error unlikely, not impossible. The bytes 200, 150, 90, 45 and the same bytes in a different order have the same total, so the same checksum: a swap would not be noticed. Real checksums use more careful calculations, which reduce, but do not remove, this risk.
Stage: Predict
Reading the number back: the echo check
A pupil gives a friend a phone number over a noisy phone line. The friend writes it down and reads it back.
Think it through
Why does reading the number back help? And suppose the number read back is different from the number the pupil gave: can the pupil tell whether the friend misheard, or whether the line made a mistake when the friend read it back?
- Hint 1: What does the pupil have to compare?
- Hint 2: Where could the mistake have happened: on the way there, or on the way back?
Show what happens
The pupil compares the number read back with the one they gave. If the two are the same, it is very likely right. If they differ, the pupil knows something went wrong, but not where: the first message could have been damaged, or the reply could have been.
An echo check works in the same way. The receiver sends a copy of the data it received back to the sender, who compares it with the original. If the two are the same, the data was probably sent correctly. If they differ, the data is sent again.
Its weakness is the one in the question. If the data comes back different, the sender cannot tell whether the data was damaged on the way there or on the way back. It also doubles the traffic, because every message is sent twice.
Check your understanding
Show the answer
Answer: C. Something changed somewhere on the round trip, so she sends the word again.
A difference means an error somewhere on the round trip; the check cannot say where.
Stage: Discover
Checking numbers typed by people: check digits
So far the errors came from interference. Errors also happen when a person types a number wrongly, or a scanner misreads it. A shop has to type or scan the 13-digit number printed under a barcode, and a library the 13-digit number of a book (its ISBN, the International Standard Book Number).
Think it through
A librarian types the 13-digit number of a book and makes one mistake in a digit. How could the number be designed so that the computer notices the mistake straight away?
- Hint 1: Could the last digit be worked out from the first twelve?
- Hint 2: What would the computer do with the digits it was given?
Show what happens
The last digit could be worked out from the other twelve by a fixed rule. The computer repeats the calculation on the digits it was given. If the answer does not match the last digit typed, at least one digit is wrong.
A digit added to the end of a number, worked out from its other digits, is a check digit. It is used for data entry: when someone types a code, the computer repeats the calculation and rejects a number that does not match. Check digits are used in ISBNs and in the numbers under bar codes (the EAN-13 code on most products).
The rule for ISBN-13 and EAN-13 is:
- Multiply the first twelve digits, in turn, by 1, 3, 1, 3, 1, 3 …: weight 1 for the first digit, 3 for the second, and so on.
- Add the twelve products.
- Find the remainder when the total is divided by 10.
- The check digit is 10 minus that remainder. If the remainder is 0, the check digit is 0, not 10.
To check a complete number, apply weights 1, 3, 1, 3 … to all thirteen digits, including the check digit. The total is a multiple of 10 if the number is valid.
The first twelve digits are 9 7 8 1 7 1 2 3 4 5 6 7. The weights are 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3.
- Multiply each digit by its weight. 9×1 = 9, 7×3 = 21, 8×1 = 8, 1×3 = 3, 7×1 = 7, 1×3 = 3, 2×1 = 2, 3×3 = 9, 4×1 = 4, 5×3 = 15, 6×1 = 6, 7×3 = 21.
- Add the products. 9 + 21 + 8 + 3 + 7 + 3 + 2 + 9 + 4 + 15 + 6 + 21 = 108.
- Find the remainder when divided by 10. 108 ÷ 10 = 10, remainder 8.
- Subtract the remainder from 10. 10 − 8 = 2. The check digit is 2, so the number is 9781712345672.
- Check it, by including the check digit. The total of all thirteen products is 108 + 2×1 = 110, which is a multiple of 10. The number is valid.
The ISBN is fictional, worked out for this lesson.
A product’s barcode starts 501928374650. Find its check digit.
| Digit | Weight | Digit × weight |
|---|---|---|
| 5 | 1 | 5 |
| 0 | 3 | 0 |
| 1 | 1 | |
| 9 | 3 | |
| 2 | 1 | |
| 8 | 3 | |
| 3 | 1 | |
| 7 | 3 | |
| 4 | 1 | |
| 6 | 3 | |
| 5 | 1 | |
| 0 | 3 | |
| Total of the products | – | |
| Remainder when divided by 10 | – | |
| Check digit | – |
- The weights go 1, 3, 1, 3 …
- Add the products, then find the remainder when the total is divided by 10.
Show the completed table
| Digit | Weight | Digit × weight |
|---|---|---|
| 5 | 1 | 5 |
| 0 | 3 | 0 |
| 1 | 1 | 1 |
| 9 | 3 | 27 |
| 2 | 1 | 2 |
| 8 | 3 | 24 |
| 3 | 1 | 3 |
| 7 | 3 | 21 |
| 4 | 1 | 4 |
| 6 | 3 | 18 |
| 5 | 1 | 5 |
| 0 | 3 | 0 |
| Total of the products | – | 110 |
| Remainder when divided by 10 | – | 0 |
| Check digit | – | 0 |
Apply it
Show the answer
Answer: A. Reject it, because 61 is not a multiple of 10: a digit has been typed wrongly.
The total should be a multiple of 10. 61 is not, so the system rejects the number and asks for it to be typed again.
A check digit shows that a number was probably typed correctly, not that it is the right number for the right product. A number can pass the test and still be a different, valid number. Also, swapping two neighbouring digits is usually, but not always, noticed: swapping two digits that differ by 5 changes the total by a multiple of 10 and goes unnoticed.
Stage: Experiment
Asking for the data again: automatic repeat query
Checks find errors. Something else must fix them, by sending the data again. A pupil who posts a parcel and asks the friend to “text me when it arrives” has the basic idea: if there is no text after a few days, the pupil sends another.
Think it through
A sender sends a packet and waits. Three things could happen: the packet arrives correctly; the packet arrives damaged; the packet never arrives. What should the receiver do in each case, and what should the sender do if it never hears back?
- Hint 1: Which of the three can the receiver notice by checking? Which can it not notice at all?
- Hint 2: How long should the sender wait before giving up on the reply?
Show what happens
If it arrives correctly, the receiver tells the sender so. If it arrives damaged, the receiver tells the sender that it needs to be sent again. If it never arrives, the receiver does not know anything was sent, so it says nothing, and the sender must decide for itself that too long has passed and send the packet again.
Automatic repeat query (ARQ) is a method in which the receiver checks each packet (with a method such as parity or a checksum) and sends the sender a message, an acknowledgement:
- a positive acknowledgement means the packet arrived without error;
- a negative acknowledgement means an error was found, so please send it again.
The sender also starts a timeout: a fixed period of time it waits for an acknowledgement. If none arrives before the timeout ends, the sender assumes the packet or the acknowledgement was lost, and sends the packet again.
Each step names the device that acts. Packet 2 is damaged, and packet 3 is lost.
Sender
Step 1 of 7: Packet 1 is sent, and a timeout starts
The sender sends packet 1 and starts a timer of, say, two seconds.
Receiver
Step 2 of 7: Packet 1 passes the check
The receiver checks the packet and finds no error, so it sends a positive acknowledgement.
Sender
Step 3 of 7: The acknowledgement arrives before the timeout
The sender sees the positive acknowledgement, so it sends packet 2.
Receiver
Step 4 of 7: Packet 2 fails the check
Interference has changed a bit, so the check finds an error. The receiver sends a negative acknowledgement.
Sender
Step 5 of 7: A negative acknowledgement means: send it again
The sender sends packet 2 again. This time it passes the check, and a positive acknowledgement comes back. The sender goes on to packet 3.
Sender
Step 6 of 7: Packet 3 is lost, so nothing comes back
Packet 3 never arrives, so the receiver sends nothing. The sender waits, and the timeout ends with no acknowledgement.
Sender
Step 7 of 7: The timeout ends, so the sender sends packet 3 again
It sends packet 3 again, and this time it arrives and is acknowledged. If this keeps failing, the sender gives up after a set number of attempts.
Apply it
Show the answer
Answer: B. It sends the packet again, because the packet or its reply may have been lost.
The timeout lets the sender recover from a lost packet or a lost acknowledgement, which nobody would otherwise notice.
Stage: Consolidate
Choosing the right check
Apply it
Show the answer
Answer: C. A check digit, worked out from the other digits and repeated when the code is typed.
For mistakes by a person typing or scanning, a check digit.
Think it through
Choose two of the five methods in this lesson (parity, checksum, echo check, check digit, automatic repeat query). Explain, in your own words, how each works, and one thing it cannot do.
- Hint 1: For each one: what is worked out, who compares it, and what is the result?
- Hint 2: Think about what each can miss.
Show a model answer
A good answer, for two methods, might read: “Parity: an extra bit makes the number of 1s even (or odd); the receiver counts the 1s; it cannot find an error if an even number of bits changed. Checksum: a total of the data, sent with it; the receiver works it out again and compares; two different pieces of data can have the same checksum. An echo check: the receiver sends the data back; it cannot say where an error happened. A check digit: an extra digit worked out from the others; the computer repeats the calculation when a number is typed; it cannot tell that a valid number is the wrong one. ARQ: acknowledgements and a timeout make the sender repeat packets that were damaged or lost; it needs another check to find errors.”
- Interference can cause data loss, gain or change, so receivers need to check for errors.
- A parity check adds a parity bit so that the number of 1s in a byte is even (even parity) or odd (odd parity). A parity block adds a parity byte, so that a single flipped bit is found where its failing row and column cross. Parity misses an even number of changes.
- A checksum is a value worked out from the data, sent with it and recalculated by the receiver. Different values mean an error.
- An echo check sends the data back to the sender to compare; it cannot say where an error happened.
- A check digit is an extra digit worked out from the other digits, used in data entry: ISBN-13 and EAN-13 weight the digits 1, 3, 1, 3 … and the total must be a multiple of 10.
- Automatic repeat query uses positive and negative acknowledgements and a timeout so that damaged or lost packets are sent again.
Sources and scope
- What this lesson is. The third lesson of the Networks, the Internet and Security module, written for this site. Its curriculum links are provisional: the wording of each linked specification point has been checked against the published specification, but no link has been verified by the site owner, and the links imply no endorsement by any examination board.
- Original material. The whispers game, the shop and head office, the library and printer, the ISBN 9781712345672, the barcode 5019283746500, the parity block, the checksum values and every other number are fictional, made up and worked out for this lesson; none belongs to a real book or product.
- Simplified on purpose. The checksum method (add the bytes and keep the remainder after dividing by 256) is a teaching example: real checksums and cyclic redundancy checks use more careful calculations. Parity is shown with the parity bit at the left of the byte, and a block of four rows, which real systems may arrange differently. ISBN-10, an older number with a different rule, is not taught. ARQ is described in its simplest form, one packet at a time.
A message from the receiver saying that a packet arrived without error (positive) or with an error (negative).
A method in which the receiver acknowledges each packet and the sender sends it again after a negative acknowledgement or a timeout.
A single binary digit: 0 or 1. The smallest unit of data a computer stores.
A group of eight bits, which can hold one of 256 different patterns.
A digit added to a number, worked out from its other digits, so that a mistake in typing or scanning can be noticed.
A value worked out from data by an agreed method and sent with it, so that the receiver can work it out again and compare.
An error check in which the receiver sends the data back and the sender compares it with the original.
A disturbance of a signal on its way that can cause data loss, data gain or data change.
A small piece of data sent across a network, with a header, a payload and a trailer.
The extra bit added to a byte so that its number of 1s is even or odd, as agreed.
A group of bytes sent with a parity bit in each row and a parity byte at the end, so that a single flipped bit can be found where its row and column cross.
An extra byte sent after a block of bytes, whose bits are the parity bits of the columns.
An error check in which an extra bit makes the number of 1s in each byte even (even parity) or odd (odd parity), and the receiver counts them again.
The fixed time a sender waits for an acknowledgement before it sends the packet again.
Your progress on this lesson
Saved in this browser only. It is not sent anywhere, does not follow you to another device, and is lost if you clear this site’s data.
This browser is not allowing the site to save progress, so it will be forgotten when you leave the page.