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 name the data-entry errors it detects.
2. Use a given algorithm (ISBN-13 or modulo-11) to calculate and verify a check digit.
3. Describe how an Automatic Repeat Request (ARQ) uses acknowledgements and a timeout.

Textbook: Chapter 2, §2.2.3–2.2.4 (pp. 59–62) — check digits and automatic repeat requests.

Recap / Warm-Up 5 min

Lesson 3 checked data after transmission: parity, checksum and echo check. Today adds a check on data typed or scanned in, and a smarter transmission check that re-sends by itself.

Quick starter

In a checksum, who recalculates the value — the sender or the receiver? And what happens if the values differ?

Key Concept 14 min

1 · Check digits

A check digit is the final digit of a code. It is calculated from all the other digits. It is used on barcodes, book numbers (ISBNs) and Vehicle Identification Numbers (VINs). It catches mistakes made when a person types a code, or a scanner misreads a barcode.

2 · Two check-digit methods

3 · Automatic Repeat Request (ARQ)

An ARQ checks data after transmission. It uses acknowledgements and a timeout:

• The data arrives with an error-detection code (typically a CRC).
• No error found → the receiver sends a positive acknowledgement.
• Error found → it sends a negative acknowledgement and asks for the data again.
• The sender waits a set time — the timeout. If no acknowledgement arrives in time, it re-sends automatically.
• This repeats until a positive acknowledgement arrives, or a set number of re-sends has been tried.

Worked Example 12 min

(a) Generate and verify an ISBN-13 check digit

Question: the barcode photo shows ISBN 978-984-96088-0-?. Calculate the check digit, then verify the full ISBN.

1. Odd positions: 9 + 8 + 8 + 9 + 0 + 8 = 42.positions 1, 3, 5, 7, 9 and 11.
2. Even positions: 7 + 9 + 4 + 6 + 8 + 0 = 34, then 34 × 3 = 102.the × 3 weighting is what catches most swapped digits.
3. 42 + 102 = 144; 144 ÷ 10 = 14 remainder 4.
4. Remainder is not 0, so check digit = 10 − 4 = 6. This matches the photo: 978-984-96088-0-6.
5. Verify: add the check digit to the odd total: 42 + 6 = 48. Then 48 + 102 = 150; 150 ÷ 10 = 15 remainder 0 → the ISBN is correct.the check digit sits in position 13, which is odd.
6. Now suppose the 11th digit is mistyped as 3. The odd total (with the check digit) becomes 43, and 43 + 102 = 145 → remainder 5, not 0, so the error is caught.

(b) Generate a modulo-11 check digit, then catch a transposition

Question: find the modulo-11 check digit for the 7-digit product code 3825146.

1. Multiply and add: 24 + 56 + 12 + 25 + 4 + 12 + 12 = 145.weights start at 8 because the code becomes 8 digits long.
2. 145 ÷ 11 = 13 remainder 2 (13 × 11 = 143).
3. Check digit = 11 − 2 = 9. Full code: 38251469.
4. Verify with weights 8 … 1: 145 + 9 × 1 = 154 = 14 × 11, remainder 0 ✓.
5. An operator swaps the 3rd and 4th digits: 38521469. New total: 24 + 56 + 30 + 10 + 4 + 12 + 12 + 9 = 157 → remainder 3, not 0, so the transposition is detected.different weights on each position mean swapped digits change the total.

The ISBN-13 check digit as an algorithm

// ISBN-13 check digit from 12 digits
DECLARE Index : INTEGER
DECLARE Digit : INTEGER
DECLARE Total : INTEGER
DECLARE Remainder : INTEGER
DECLARE CheckDigit : INTEGER
Total ← 0
FOR Index ← 1 TO 12
  OUTPUT "Enter digit ", Index
  INPUT Digit
  IF Index MOD 2 = 1
    THEN
      Total ← Total + Digit
    ELSE
      Total ← Total + Digit * 3
  ENDIF
NEXT Index
Remainder ← Total MOD 10
IF Remainder = 0
  THEN
    CheckDigit ← 0
  ELSE
    CheckDigit ← 10 - Remainder
ENDIF
OUTPUT "Check digit is ", CheckDigit

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

Check digit is 6

Try It Yourself 12 min

📝 Exam Practice 10 min

Recap & Key Terms 3 min

A check digit is calculated from the other digits of a code and catches entry errors such as wrong, swapped, missing or extra digits. ISBN-13 and modulo-11 are two ways to make one. ARQ uses acknowledgements and a timeout to re-send data until it arrives correctly.

Check digit

An additional digit added to a number to check the number was entered without error; a data-entry check, not a transmission check.

Transposition error

An error where two digits are swapped over, e.g. 5037 entered instead of 5307.

Automatic Repeat Request (ARQ)

A method of checking transmitted data that uses acknowledgements and a timeout to request re-sending automatically.

Acknowledgement

A message sent back to say whether data was received correctly (positive) or not (negative).

Timeout

The time interval allowed to elapse before an acknowledgement is received; after it, the data is re-sent.

Homework 1 min

Task (≤ 15 min): a librarian types ISBN 9780306406175 into a computer. Use the ISBN-13 verification method to decide whether it was typed correctly. Then name the type of error that has probably happened. [4]