CIE IGCSE | 2.2 Error Detection

Lesson objective

Explain how errors occur, apply parity and checksum checks, distinguish check digits from transmission checks, and describe acknowledgements and timeouts in ARQ.

Learn

2.2 | PARITY, CHECKSUM, CHECK DIGIT AND ARQ

01 | WHY CHECK RECEIVED DATA?

A sender transmits 01000001, but the receiver reads 01000000. Only one bit changed, yet the value is different.

Interference can cause data to be changed, gained or lost during transmission. Noise, a damaged connection or a disrupted signal can make the received data differ from the original.

Error detection looks for evidence of an error. It is different from correcting the data, encrypting it or checking whether the original information was sensible. A check can miss some error patterns.

02 | PARITY: COUNT THE ONES

A parity bit is added so that the total number of 1s in the data and parity bit follows an agreed rule.

  • Even parity: the total number of 1s must be even.
  • Odd parity: the total number of 1s must be odd.
Parity bit shown separately from seven data bits
Data bitsNumber of 1sEven parity bitOdd parity bit
1011001401
1011000310
0000000001

Zero is an even count. Parity concerns the number of 1s, not whether the binary value is an odd or even number.

Both sides must agree the rule and the parity-bit position. In these examples the parity bit is placed after the data.

03 | WHAT PARITY CAN AND CANNOT DETECT

Send 1011001 with even parity bit 0. The complete unit contains four 1s. If one bit flips, the count becomes odd and the check fails.

If two bits flip, the count may stay even. For example, changing the first two data bits gives 0111001 with parity bit 0. The data changed but still contains four 1s, so the error is missed.

Simple parity detects an odd number of bit flips in the checked unit, including a flipped parity bit. It does not reliably detect an even number of flips, identify the incorrect bit or repair it.

04 | PARITY BYTES AND BLOCK CHECKS

A block can be arranged into rows of data bits. A parity byte supplies parity bits for the columns. A two-dimensional parity block check adds row parity as well as column parity.

Small four-column teaching block using even parity
RowColumn 1Column 2Column 3Column 4Row parity
Data row 110111
Data row 201010
Data row 311000
Column parity row00101

Every row and column has an even number of 1s. The bottom row here is a short teaching example; with eight data columns, the column parity bits form a parity byte.

If the bit at data row 2, column 3 changes from 0 to 1, both that row and that column fail. Their intersection locates a single-bit error, assuming only one bit changed.

Multiple errors can be ambiguous. Four flips at the corners of a rectangle can preserve every row and column parity. Do not claim that block parity always finds or corrects all errors.

05 | TRY IT: SET THE PARITY BIT

Change one bit and calculate again. Then change two bits. Explain why the required parity bit may return to its original value.

06 | CHECKSUM: CALCULATE, SEND, COMPARE

A checksum is a value calculated from a block of data. The sender calculates it using an agreed algorithm and sends it with the data. The receiver calculates a checksum from the received data using the same algorithm and compares the values.

A mismatch indicates an error. A match means no error was detected by that check, not that errors are impossible.

A simple teaching checksum, not a universal checksum algorithm
StepIllustrative calculation
AlgorithmAdd the byte values and keep the remainder after division by 256
Original bytes10, 20, 30
Sender checksum(10 + 20 + 30) mod 256 = 60
Received bytes with a change10, 21, 30
Receiver checksum61; different from 60, so the check fails

If 10, 20, 30 becomes 11, 19, 30, the sum is still 60. This error is missed by the example algorithm. Swapping byte order also leaves this particular sum unchanged.

Real checksum algorithms vary. Follow the method given in the question rather than assuming every checksum is a simple sum.

07 | ECHO CHECK: SEND IT BACK

In an echo check, the receiver sends the received data back to the sender. The sender compares the returned data with the original.

For example, the sender transmits 10110. If the receiver echoes 10010, the sender finds a mismatch and can arrange another transmission.

Echoing adds return traffic and time because the data is transmitted again. A return-path error can also affect the comparison. A matching echo is not an absolute guarantee against every possible error pattern.

08 | CHECK DIGITS: CHECK DATA ENTRY

A check digit is calculated from the other digits of a code and included in that code. It helps detect mistakes when the code is typed or scanned, such as a changed digit or some transpositions.

ISBNs and many product barcodes include check digits. A check digit does not establish that the book, product or entered information is the right one. It checks consistency under an algorithm.

For a simple classroom rule, choose the final digit so that the sum of all digits is a multiple of ten. For data digits 4, 2, 7, 1, the sum is 14, so the check digit is 6. The complete code is 42716.

If someone enters 42726, the total is 21, so the check fails. Swapping two digits leaves this simple sum unchanged, so that error is missed. This classroom rule is not the ISBN algorithm.

09 | WORKED ISBN-13 EXAMPLE

ISBN-13 uses alternating weights of 1 and 3 for the first twelve digits. Choose the check digit so that the weighted total including the final digit is divisible by ten.

Worked example: 978030640615
First twelve digitsWeightsWeighted products
9 7 8 0 3 0 6 4 0 6 1 51 3 1 3 1 3 1 3 1 3 1 39 21 8 0 3 0 6 12 0 18 1 15

The products total 93. The next multiple of ten is 100, so the check digit is 7 and the complete ISBN is 9780306406157.

If the weighted sum already ends in 0, the check digit is 0, not 10. You do not need to assume all check-digit systems use these weights; use the algorithm supplied.

10 | ARQ: CHECK, ACKNOWLEDGE, RETRY

Automatic repeat query (ARQ) combines an error check with acknowledgements and retransmission. It provides a way to request data again when a check fails or an expected response does not arrive.

  1. The sender transmits a block or packet and starts a timer.
  2. The receiver checks the data using the agreed error-detection method.
  3. If the check passes, the receiver sends a positive acknowledgement, ACK.
  4. If the check fails, a negative acknowledgement, NAK, can request retransmission.
  5. If the sender receives a NAK, it retransmits the relevant data.
  6. If no expected acknowledgement arrives before the timeout, the sender retransmits.

The acknowledgement itself can be lost. Sequence identifiers help a reliable protocol recognise retransmitted duplicates rather than treating them as new data. Some ARQ designs rely on timeouts without explicit NAKs.

ARQ is not the calculation that detects the error. It uses a check and a response process to recover. Continued faults can prevent completion, and an undetected error can still pass a weak check.

11 | FOLLOW AN ARQ EXCHANGE

Illustrative reliable exchange with sequence identification
EventReceiver / sender response
Packet 1 arrives with detected corruptionReceiver sends NAK
Sender receives NAKSender retransmits packet 1
Packet 1 now passes its checkReceiver sends ACK
ACK is lostSender gets no expected response
Timer expiresSender retransmits packet 1 again
Receiver recognises a duplicateAvoids delivering the data twice and sends ACK again

A timeout is a waiting limit, not proof that the data packet was corrupted. It may mean the packet or its acknowledgement was lost or delayed.

12 | KEEP THE METHODS DISTINCT

Detection, entry checking and recovery serve different roles
MethodCore ideaImportant limitation
ParityCheck whether the count of 1s obeys an odd/even ruleEven numbers of flips can be missed
Parity blockCheck rows and columnsMultiple errors can be ambiguous or undetected
ChecksumCompare calculated values for a data blockDifferent data can give the same value
Echo checkCompare returned data with the originalAdds return traffic; return errors can affect checking
Check digitCheck consistency of an entered codeDoes not verify meaning or catch every entry mistake
ARQUse checks, acknowledgements and timeouts to trigger repeatsNeeds communication to succeed; depends on error checks

MATCH THE ERROR-DETECTION TERM

FURTHER READING

International ISBN Agency: ISBN structure and check digits

Terminology

Terminology

Transmission error

A change, gain or loss of data during transmission.

Parity bit

A bit added so that the total number of 1s follows an agreed odd or even rule.

Even parity

A rule requiring an even total number of 1s, including the parity bit.

Odd parity

A rule requiring an odd total number of 1s, including the parity bit.

Parity byte

A set of column parity bits for a block with eight data columns.

Parity block check

A check using both row and column parity on a block of data.

Checksum

A value calculated from data and compared to help detect changes.

Echo check

Returning received data to the sender for comparison with the original.

Check digit

A digit calculated from other digits to help detect code-entry errors.

ACK / NAK

Positive / negative acknowledgements used in a communication process.

Timeout

A defined waiting period after which a missing response can trigger action.

ARQ

Automatic repeat query: error checks, acknowledgements and timeouts used to arrange retransmission.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. What even parity bit belongs after 1011001?
2. What odd parity bit belongs after 1011000?
3. Which statements about simple parity are correct?
4. The teaching checksum is sum mod 256. Which changes can be missed for 10,20,30?
5. Which describe an echo check?
6. Which statements about check digits are correct?
7. Which events can trigger an ARQ retransmission?
8. Which statements about parity blocks are correct?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Describe how a parity check detects a transmission error.

2. Explain why two flipped bits may pass a parity check.

3. Describe checksum checking and one limitation.

4. Explain how a check digit differs from a checksum used after transmission.

5. Explain what ARQ does if an expected acknowledgement is not received.

6. Explain how a parity block can locate a single-bit error.

CALCULATE | SHOW YOUR WORKING

1. Add an even parity bit after 1100101. 2. Calculate sum mod 256 for bytes 200, 100, 50. 3. Under the classroom sum-to-a-multiple-of-ten rule, find the check digit after 5, 8, 2, 1.

Reveal answers

1. Four 1s, so parity bit 0. 2. Total 350; 350 mod 256 = 94. 3. Sum 16, so check digit 4 makes 20.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

    Selections are kept while this page is open.

    Workbook

    Workbook

    COMING SOON

    The workbook for 2.2 Error Detection is coming soon. Complete the parity, checksum and check-digit calculations in your exercise book.