Computer ScienceFoundation18 min read

Methods of Error Detection

Noticing that data arrived wrong, and sometimes fixing it

This topic appears in:

O Level Computer Science (2210) · ch.2A Level Computer Science (9618) · ch.6
01

Why errors happen at all

Data travelling along a wire or through the air can be corrupted by electrical interference, by attenuation — the signal weakening over distance until a 1 is misread as a 0 — or by skew in parallel transmission.

None of these can be prevented entirely, so systems are built to detect corruption instead. Every method works the same way: send extra information alongside the data, and check on arrival that it still agrees.

MethodExtra data sentDetectsCan correct?
Parity check1 bit per bytean odd number of flipped bitsno
Parity blocka parity byte as wella single flipped bityes — locates it
Checksuma calculated totalmost corruptionno
Echo checkthe whole data back againany differenceno — resend
Check digitone digit on the endentry errors in a codeno
ARQacknowledgements and timeoutslost or corrupted packetsyes — by resending
02

Parity checking

One bit of each byte is reserved as the parity bit, set so that the total number of 1s in the byte is even (even parity) or odd (odd parity). Both sender and receiver must agree which system is in use beforehand.

On arrival the receiver counts the 1s. If the count no longer matches the agreed parity, at least one bit has been corrupted.

Its weakness is fundamental: if two bits in the same byte flip, the parity is restored and the error passes undetected. And even when an error is found, the check cannot say which bit is wrong.

Switch to One bit flipped. The row containing the error fails its check and so does the column — and the single cell where the two failures cross is the corrupted bit, which can then simply be flipped back.

A parity block can correct as well as detect

Send a block of bytes each with its parity bit, and add one extra parity byte at the end whose bits give the parity of each column. A single corrupted bit now fails exactly one row check and one column check, and their intersection identifies the faulty bit precisely — so the receiver can flip it back with no resend at all.

03

Checksums, echo checks and check digits

A checksum is a value calculated from all the data by an agreed arithmetic rule and sent with it. The receiver recalculates from what arrived and compares. Agreement means the data is almost certainly intact; disagreement means it is not, and the block is requested again.

An echo check is cruder: the receiver sends the entire data back and the sender compares it with what it sent. It is simple, but doubles the traffic and cannot tell whether the corruption happened on the way out or on the way back.

A check digit guards data entered by a human rather than transmitted. An extra digit is calculated from the others and appended, so ISBNs, barcodes and account numbers can be checked the moment they are typed. It catches the two commonest typing mistakes: a single wrong digit, and two adjacent digits transposed.

Worked example

A system uses even parity. The byte 01101011 arrives, where the leftmost bit is the parity bit. Has an error occurred?

  1. Count the 1s in the whole byte: 0,1,1,0,1,0,1,1 gives five.The parity bit is included in the count — it was set to make the total even.
  2. Five is odd, but the system uses even parity.
  3. So the byte is corrupted — at least one bit has flipped in transmission.
  4. But the check cannot say which bit, and if two bits had flipped it would have found nothing at all.Stating the limitation is usually worth a mark.

Yes — five 1s under even parity means an error, though not which bit.

04

Automatic Repeat reQuest

ARQ is the system that ties the others together into something reliable. The receiver checks each packet, using a checksum or parity, and sends back a positive acknowledgement if it is intact or a negative one if it is not.

The sender also starts a timer when it transmits. If no acknowledgement arrives before the timer expires, the packet is assumed lost and resent. That covers the case the checks cannot: a packet that never arrived at all, so the receiver had nothing to check.

A limit is placed on the number of retries, so a permanently broken link produces an error rather than an endless loop of resends.

Before you leave this chapter

  1. Errors come from interference, attenuation and skew, and cannot be prevented — only detected.
  2. A parity bit makes the number of 1s even or odd; two flipped bits in one byte defeat it.
  3. A parity block adds a parity byte, and the row and column that both fail locate the bad bit.
  4. Checksum recalculates and compares; echo check returns the data; check digit guards typed input.
  5. ARQ uses acknowledgements and a timeout, so a packet that never arrives is also resent.
05

Choosing a method, and what each costs

Every error-detection method sends extra data alongside the real data. That overhead is the price of the checking, and choosing a method means deciding how much of it is worth paying.

A single parity bit costs one bit in eight — about 12% — and catches only some errors. A parity block costs an extra byte per block and can correct a single-bit error outright. An echo check costs 100% overhead, since everything is sent twice. A checksum costs very little and catches most corruption but cannot correct anything.

MethodOverheadStrengthWeakness
Parity bitabout 12%very cheap and simplemisses two flipped bits
Parity blocka byte per blocklocates and corrects one bad bitstill defeated by multiple errors
Checksumvery smallcatches most corruptioncannot correct, only detect
Echo check100%simple to implementdoubles traffic; direction unknown
ARQacknowledgementsguarantees eventual deliveryadds delay, needs a return path

Detection and correction are different things

Only the parity block in this list can repair the data. Everything else tells you something is wrong and leaves you to ask for it again — which is why detection is nearly always paired with ARQ in a real system. A question asking how a system "ensures the data is correct" wants both halves: a check, and a mechanism for resending what fails it.

Practice questions

6 questions · 20 marks · full working on every one

Try each one on paper first, then open the working. The marks are shown where they are actually awarded, because that is where they are actually lost.

Short questions

3 · 6 marks

Two marks each, in the style of the short-question section of the paper. Answer in two or three lines.

SQ1[2 marks]
Explain how an even parity check works.
Model answer

One bit of each byte is set so that the total number of 1s is even. The receiver counts the 1s in the byte it received; if the total is odd, at least one bit has been corrupted in transmission.

Examiner tip. Say that the parity bit is included in the count. Students often describe counting only the data bits, which gives the wrong total.

SQ2[2 marks]
Give one limitation of a single parity check.
Model answer

If two bits flip in the same byte, the parity is restored and the error is not detected. It also cannot identify which bit is wrong, so the data must be resent rather than repaired.

Examiner tip. Either limitation earns the mark, but the two-bit failure is the one examiners ask about most.

SQ3[2 marks]
What is a check digit used for?
Model answer

An extra digit calculated from the others and appended to a code such as an ISBN, barcode or account number, so that a data entry error can be detected immediately when the code is typed in.

Examiner tip. Check digits guard human entry, not transmission. That distinction is what separates them from parity and checksums.

Solved numericals

2 · 8 marks

Full working, one step per line, with the marks shown where they are awarded.

N1[4 marks]
Explain how a parity block allows a single corrupted bit to be both detected and corrected.
Full working
  1. Each byte carries a parity bit, so a corrupted byte fails its own row check[1]
  2. An extra parity byte is sent whose bits give the parity of each column across the block[1]
  3. A single flipped bit causes exactly one row and exactly one column to fail their checks[1]
  4. The bit at the intersection of that row and column is the faulty one, so it can simply be flipped back — no resend is neededthe intersection is the key idea[1]

The failing row and failing column intersect at the corrupted bit, which is then flipped back.

Examiner tip. This is the only method in the syllabus that corrects rather than merely detecting, which is exactly why it is asked about.

N2[4 marks]
Describe how Automatic Repeat reQuest ensures reliable delivery, including what happens if a packet is lost entirely.
Full working
  1. The receiver checks each packet using an error-detection method such as a checksum[1]
  2. It sends back a positive acknowledgement if the packet is intact, or a negative one if it is corrupted, prompting a resend[1]
  3. The sender starts a timer when it transmits each packet[1]
  4. If no acknowledgement arrives before the timeout, the packet is assumed lost and resent — which covers a packet that never arrived, since the receiver had nothing to checkthe timeout is the mark most often missed[1]

Acknowledgements handle corrupted packets; a timeout handles ones that never arrive.

Examiner tip. The timeout is the half students forget. Error checking alone cannot detect a packet that was never received at all.

Long questions

1 · 6 marks

Theory and numerical together, as they appear in the long-question section.

LQ1[6 marks]
A hospital transmits patient records between buildings over a long cable.
  1. Explain two causes of transmission errors over such a link.
  2. Recommend an error-detection method and justify it for this application.
  3. Explain why detection alone is not sufficient here, and what must be added.
Mark scheme
  1. Attenuation — the signal weakens over the distance until a bit is misread[1]
  2. Interference from nearby electrical equipment, which a hospital has a great deal ofaccept skew if parallel[1]
  3. A checksum on each packet, since it detects most corruption across the whole block rather than one byte at a timeaccept parity block with justification[1]
  4. Patient data must be exactly correct — a single wrong digit in a dosage could cause harm — so a strong check is justified even at the cost of extra datathe justification must fit the context[1]
  5. Detection only tells you the data is wrong; it does not deliver the correct data[1]
  6. ARQ must be added so that any packet failing the check, or failing to arrive at all, is automatically requested again until it is received intact[1]

(a) attenuation and interference (b) a checksum, because the data must be exact (c) detection must be paired with ARQ so faulty packets are resent

Examiner tip. The distinction in part (c) matters: every method in this chapter except the parity block only tells you something is wrong. Getting the right data requires a resend mechanism on top.