Check digits and error detection

Se basa en

Requisitos previos obligatorios, hasta el fondo: 5

Aprenderás a

• 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.

Definición

• 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.

Teorema

• 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.

Errores frecuentes

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

Descubrimientos opcionales

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

Lecturas complementarias

• Joseph A. Gallian, Contemporary Abstract Algebra