Describe how a check digit is used and identify examples such as ISBN and bar codes

Methods of Error Detection – Check Digits and Related Techniques

Learning Objective

Students will be able to:

• Explain why transmission errors occur.
• Describe the five error‑detection methods required by the Cambridge IGCSE 0478 syllabus:
  1. Parity check
  2. Checksum (additive)
  3. Echo check (acknowledgement)
  4. Check digit
  5. Automatic Repeat reQuest (ARQ)
• Calculate and verify a check digit (ISBN‑10, ISBN‑13/EAN‑13, UPC‑A, IBAN).
• Perform a simple parity‑check and checksum calculation by hand.
• Explain, in a few sentences, how ARQ provides reliable communication.

1. Why Errors Occur in Digital Communication?

When data are stored, transmitted or entered, the following disturbances can change the original bits or digits:

• Interference / noise – random electrical disturbances that flip bits.
• Signal attenuation or gain – the level becomes too weak or too strong, causing mis‑reading.
• Synchronization loss – the receiver mis‑aligns with the start of a character.
• Human error – mistyping, swapping adjacent digits, omitting a character.

Because errors are inevitable, systems use low‑cost detection techniques before deciding whether to accept the data.

2. Overview of the Five Error‑Detection Methods

Method	What it detects	Typical use (Cambridge examples)	Key idea
Parity check	Any single‑bit error	8‑bit data bytes in simple micro‑controller projects	Append one extra bit so that the total number of 1’s is even (or odd).
Checksum (additive)	Single‑byte errors and many multi‑byte errors	Data packets in basic networking or file‑transfer exercises	Sum all data bytes (mod 256) and send the result as an extra byte.
Echo check	Lost or corrupted frames	Hand‑shake between two computers in a lab experiment	Receiver sends the same data back (“echo”); sender compares with the original.
Check digit	Single‑digit errors, adjacent transpositions, omission/insertion of a digit	ISBN, EAN/UPC bar‑codes, IBAN numbers (exam focus)	Calculate a digit from the other digits using a weighted‑modulus algorithm.
ARQ (Automatic Repeat reQuest)	Any error that is detected by the above methods	Stop‑and‑wait protocol in the “Data communication” topic	Sender retransmits a frame until a positive acknowledgement (ACK) is received.

3. Detailed Descriptions & Worked Calculations

3.1 Parity Check (odd or even)

• Definition: Add one extra bit (the parity bit) so that the total number of 1’s in the transmitted unit is either even (even parity) or odd (odd parity).
• Detection capability: Guarantees detection of any single‑bit error; two‑bit errors may go undetected if they change the parity by an even number.

Example – even parity for the 8‑bit byte 10110010

1. Count the 1’s: 1 + 0 + 1 + 1 + 0 + 0 + 1 + 0 = 4 (already even).
2. Parity bit = 0 (no change needed).
3. Transmitted byte = 10110010 0 (9 bits including parity).
4. If the receiver reads 10110011 0 (the third bit flipped), the count becomes 5 → odd → error detected.

3.2 Additive Checksum (mod 256)

• Definition: Sum all data bytes, keep only the lowest 8 bits (i.e. take the result modulo 256), and transmit this sum as the checksum byte.
• Detection capability: Detects any single‑byte error and many multi‑byte errors; it cannot detect a wrap‑around error where the sum changes by a multiple of 256.

Example – 4‑byte packet: 0x3A, 0x7F, 0x12, 0xC4

1. Convert to decimal: 58 + 127 + 18 + 196 = 399.
2. Modulo 256: 399 − 256 = 143 (0x8F).
3. Checksum byte = 0x8F. The transmitted sequence is 3A 7F 12 C4 8F.
4. At the receiver, repeat the sum (including the checksum). If the total modulo 256 equals 0, the packet is valid.

3.3 Echo Check (hand‑shake)

• Definition: After receiving a data block, the receiver immediately sends the same block back to the sender. The sender compares the echoed block with the original.
• Detection capability: Detects any error that changes the block, because the sender will notice a mismatch.

Simple diagram (textual)

Sender ──► Data block ──► Receiver
Sender ◄── Echo (same block) ◄── Receiver

If the echoed block differs, the sender requests a retransmission.

3.4 Check Digit (focus for the exam)

3.4.1 What is a Check Digit?

• An extra digit (or character) appended to a numeric identifier.
• Calculated from the other digits using a fixed algorithm (weights + modulus).
• When the code is entered or scanned, the same algorithm is applied; a mismatch signals an error.

3.4.2 General Procedure

1. Write down the data digits (all digits except the check digit).
2. Assign a weight to each digit – the pattern is defined by the scheme.
3. Multiply each digit by its weight and add the products.
4. Apply the modulus operation (e.g. % 10, % 11, % 97) to obtain a remainder.
5. Derive the check digit, usually (M – remainder) mod M.

Mathematically:

\[ C = \bigl(M - (\sum_{i=1}^{n} w_i d_i \bmod M)\bigr) \bmod M \]

3.4.3 Common Schemes (Cambridge‑relevant)

Scheme	Typical use	Modulus (M)	Weight pattern	Special rule	Example (full code)
ISBN‑10	Books published before 2007	11	10 → 2 (left‑to‑right)	Remainder = 10 → check digit = X	0‑306‑40615‑2
ISBN‑13 (EAN‑13 format)	Books (current)	10	1, 3 alternating, start with 1 on the left	None	978‑0‑306‑40615‑7
EAN‑13 / UPC‑A	Retail bar‑codes	10	1, 3 alternating from the rightmost digit (check digit itself not weighted)	None	4006381333936
IBAN (Mod‑97)	International bank account numbers	97	Positional powers of 10 after moving the country code & check digits to the end	Result must be 1 for a valid IBAN	GB82 WEST 1234 5698 7654 32

3.4.4 Worked Examples

Example 1 – ISBN‑10

Find the missing check digit for 0‑306‑40615‑?.

1. Digits (without check digit): 0 3 0 6 4 0 6 1 5
2. Weights 10 → 2: 10, 9, 8, 7, 6, 5, 4, 3, 2
3. Weighted sum = 0·10 + 3·9 + 0·8 + 6·7 + 4·6 + 0·5 + 6·4 + 1·3 + 5·2 = 130
4. Remainder: 130 mod 11 = 9
5. Check digit: 11 − 9 = 2 (if result were 10, write X)
6. Full ISBN‑10: 0‑306‑40615‑2

Example 2 – ISBN‑13 (EAN‑13)

Find the check digit for the 12‑digit prefix 978030640615.

1. Digits: 9 7 8 0 3 0 6 4 0 6 1 5
2. Weights 1, 3 alternating: 1·9 + 3·7 + 1·8 + 3·0 + 1·3 + 3·0 + 1·6 + 3·4 + 1·0 + 3·6 + 1·1 + 3·5 = 115
3. Remainder: 115 mod 10 = 5
4. Check digit: 10 − 5 = 5 (remainder 0 → digit 0)
5. Full ISBN‑13: 978‑0‑306‑40615‑7

Example 3 – EAN‑13 / UPC‑A

Determine the check digit for 400638133393.

1. From the right, sum digits in odd positions (1st, 3rd,…): 3 + 3 + 3 + 8 + 0 + 4 = 21
2. Sum digits in even positions, multiply by 3: (9 + 9 + 1 + 6 + 6 + 0) × 3 = 31 × 3 = 93
3. Total = 21 + 93 = 114
4. Smallest number to reach a multiple of 10: 120 − 114 = 6
5. Check digit = 6 → complete EAN‑13 4006381333936

Example 4 – IBAN Mod‑97

Validate GB82 WEST 1234 5698 7654 32.

1. Move the first four characters to the end: WEST12345698765432GB82
2. Replace letters with numbers (A=10 … Z=35):
   W=32, E=14, S=28, T=29, G=16, B=11 → 32 14 28 29 12 34 56 98 76 54 32 16 11 82
3. Form the large integer and compute integer mod 97. The remainder is 1, so the IBAN is valid.

4. Why These Methods Matter for the IGCSE Computer Systems Paper

• They illustrate the principle of error detection without requiring advanced coding theory.
• Exam questions frequently ask you to:
  • Calculate a missing check digit or parity bit.
  • Verify a given code (ISBN, EAN, IBAN, checksum).
  • Explain which types of errors a particular method can detect.
  • Describe, in two sentences, how ARQ ensures reliable transmission.
• Being comfortable with the hand‑calculation steps saves time in the short‑answer and structured‑question sections.

5. Quick Reference – How to Verify a Code

1. Identify the scheme (Parity, Checksum, Echo, Check digit, ARQ).
2. Separate the check component (parity bit, checksum byte, check digit, etc.) from the data.
3. Apply the scheme’s specific weighting / addition rule.
4. Perform the required modulus operation.
5. Re‑derive the check component and compare it with the one transmitted.
6. Result: “Valid” or “Error detected”.

6. Key Points to Remember

• All methods generate a *derived* value that is not part of the original information.
• Different schemes use different moduli (10, 11, 97, 256) and weight patterns.
• Parity detects any single‑bit error; checksum detects many single‑byte errors; check digits detect single‑digit errors and adjacent transpositions.
• ARQ does not itself detect errors; it *reacts* to errors detected by the above methods by requesting retransmission.
• Hand‑calculation skills are essential for the exam, but the same logic is built into scanners, cash registers, and banking software.

7. Suggested Classroom Diagram (flowchart)

Draw the following steps on the board to visualise any detection method:

1. Input data (including check component)
2. Separate check component
3. Apply weighting / addition
4. Modulus operation
5. Re‑calculate check component
6. Compare with received check component
7. Output: “Valid” or “Error – request repeat (ARQ)”.