六至八年级Applied Mathematics计划中
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
本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。
前置知识
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.
延伸阅读
- Joseph A. Gallian, Contemporary Abstract Algebra