Grades 6–8Applied MathematicsPlanned

Check digits and error detection

How ISBNs, bank cards and barcodes catch typing errors with check digits computed by modular arithmetic, and how parity bits protect digital data.

math.applied.check-digits

The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.

Builds on

Required prerequisites, all the way down: 5

Compute and verify ISBN-10 and ISBN-13 check digits.
Explain why the ISBN-10 scheme detects every single-digit error and every swap of two adjacent digits.
Add a parity bit to binary data and show that it detects any single flipped bit.

A check digit is an extra digit computed from the others so that certain errors can be detected.
The digits d₁, …, d₁₀ of an ISBN-10 satisfy 1·d₁ + 2·d₂ + ⋯ + 10·d₁₀ ≡ 0 (mod 11), with X standing for 10.
A parity bit is chosen so that the total number of 1s is even.

ISBN-10 detects every single-digit error and every adjacent transposition, because 11 is prime and the weights are distinct and non-zero modulo 11.
ISBN-13, with weights alternating 1 and 3 modulo 10, detects every single-digit error but misses adjacent transpositions of digits that differ by 5.
A single parity bit detects any odd number of flipped bits and no even number.

Thinking a check digit can correct errors; simple check digits only detect them.
Believing every possible error is detected.

Information theory Error-correcting codes go further and correct errors, and Shannon's noisy-channel theorem limits how efficiently this can be done.