Check Digits & ARQ

Syllabus & Goals 3 min

Cambridge 2.2 · Methods of error detection Paper 1 · Computer Systems

By the end of this lesson you can:

1. Explain what a check digit is and what errors it catches.
2. Apply a given algorithm (ISBN-13) to calculate a check digit.
3. Describe how an Automatic Repeat reQuest (ARQ) works.

Recap / Warm-Up 5 min

Parity and checksum catch errors made during transmission. A check digit catches errors made during data entry — a mis-typed or mis-scanned number.

Quick starter

If you type 5037 when you meant 5307, what kind of mistake have you made?

Key Concept 14 min

1 · Check digits

A check digit is an extra digit placed at the end of a code, calculated from all the other digits. When the code is entered or scanned, the digit is recalculated; if it doesn't match, an error is flagged.

Check digits catch:

• Incorrect digit — e.g. 5327 instead of 5307.
• Transposition — two digits swapped, e.g. 5037 instead of 5307.
• Omitted / extra digit — e.g. 537 or 53107 instead of 5307.
• Phonetic errors — e.g. 13 ("thirteen") for 30 ("thirty").

2 · Automatic Repeat reQuest (ARQ)

An ARQ checks data after transmission using acknowledgements and a timeout:

• The data carries an error-detection code (a CRC). The receiver checks it.
• If no error → a positive acknowledgement is sent back.
• If an error → a negative acknowledgement is sent and re-transmission is requested.
• If no acknowledgement arrives within the timeout, the sender automatically re-sends — until a positive acknowledgement comes, or a set number of tries is reached.

Worked Example 12 min

ISBN-13 check digit

The given algorithm (you are not expected to memorise it — it will be provided):

1. Add all the odd-positioned digits.
2. Add all the even-positioned digits and multiply by 3.
3. Add the two results and divide by 10 — take the remainder.
4. If the remainder is 0 the check digit is 0; otherwise it is 10 − remainder.

For the ISBN 9 7 8 0 3 4 0 9 8 3 8 2:

• Odd positions: 9 + 8 + 3 + 0 + 8 + 8 = 36
• Even positions: 3 × (7 + 0 + 4 + 9 + 3 + 2) = 3 × 25 = 75
• (36 + 75) ÷ 10 = 111 ÷ 10 = 11 remainder 1
• 10 − 1 = 9 → the check digit

The ISBN-13 check digit as code

Cambridge pseudocode

// Generate the ISBN-13 check digit from the first 12 digits
DECLARE Digits : ARRAY[1:12] OF INTEGER
DECLARE Index, Total, Remainder, CheckDigit : INTEGER
Digits ← [9, 7, 8, 0, 3, 4, 0, 9, 8, 3, 8, 2]
Total ← 0
FOR Index ← 1 TO 12
    IF Index MOD 2 = 1
        THEN
            Total ← Total + Digits[Index]
        ELSE
            Total ← Total + Digits[Index] * 3
    ENDIF
NEXT Index
Remainder ← Total MOD 10
IF Remainder = 0
    THEN
        CheckDigit ← 0
    ELSE
        CheckDigit ← 10 - Remainder
ENDIF
OUTPUT "Check digit is ", CheckDigit

The same algorithm in Python (IDLE)

# Generate the ISBN-13 check digit from the first 12 digits
digits = [9, 7, 8, 0, 3, 4, 0, 9, 8, 3, 8, 2]
total = 0
for i in range(12):
    if i % 2 == 0:
        total = total + digits[i]
    else:
        total = total + digits[i] * 3
remainder = total % 10
if remainder == 0:
    check_digit = 0
else:
    check_digit = 10 - remainder
print("Check digit is", check_digit)

Output

Check digit is 9

Try It Yourself 12 min

📝 Exam Practice 10 min

Recap & Key Terms 3 min

A check digitis calculated from a code's other digits to catch data-entry mistakes like transpositions. An ARQ uses positive/negative acknowledgements and a timeout to re-send data until it arrives correctly.

Check digit

A final digit calculated from a code's other digits to detect data-entry errors.

Transposition error

A data-entry error where two digits swap places.

Automatic Repeat reQuest (ARQ)

Re-sending data, using acknowledgements and a timeout, until it is received correctly.

Acknowledgement

A message back to the sender saying data was (positive) or was not (negative) received correctly.

Homework 1 min

Task (≤ 15 min): Using the ISBN-13 algorithm, find the check digit for 9 7 8 0 2 4 0 5 3 7 4 4, showing each step.