Kontrollnumbrid: Luhn, vöötkoodid, ISBN ja neile märkamatuks jäävad vead

Sisesta kaardi number, IMEI, vöötkood või ISBN ning vali sobiv kontrollimehhanism. Leht näitab, millise panuse annab iga number ja kas kogu arv läbib kontrolli. Seejärel proovib see läbi kõik üheainsa eksimusega tehtud vead ja loetleb need, mida kontrollnumber ei märkaks.

Näidisarvutus — Kontrollnumbrid: Luhn, vöötkoodid, ISBN ja neile märkamatuks jäävad vead

Panuste summa	60
Kontrolli tulemus	0
Ülejäänud numbrite nõutud kontrollnumber	7
Kas arv läbib kontrolli?	Jah
Üks vale number, aga kontrolli tulemus on sama	0 135-st

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Kontrollnumbrid: Luhn, vöötkoodid, ISBN ja neile märkamatuks jäävad vead

Kontrollnumber on üks lisatud number, mis on valitud nii, et kogu arv vastaks kindlale reeglile. Siinses näites tähendab see, et numbrid, mida on vastavalt nende asukohale korrutatud või teisendatud, annavad kokku mooduli (10 või 11) kordse. Viga, mis seda reeglit rikub, on tuvastatud. Viga, mis jätab reegli kehtima, jääb märkamatuks. Seega saab kontrollnumber tõestada, et arv on vale, kuid ei suuda kunagi tõestada, et see on õige.

Mida iga sümbol tähendab

dᵢ: number, mis asub paremalt i kohal; kontrollnumber on d₀
wᵢ: asukoha i kaal: vöötkoodil vaheldumisi 1 ja 3, ISBN-10 puhul i + 1
D(d): Luhni kahekordistamine: 2d, millest on lahutatud 9, kui see ületab 9, seega 0 2 4 6 8 1 3 5 7 9
S: kõigi numbrite panuste summa
m: moodul, 10 Luhni ja vöötkoodi jaoks, 11 ISBN-10 jaoks; arv läbib kontrolli, kui S on m-i kordne

Eeldab: Korral on tehtud vaid üks viga. Kaks viga ühes arvus võivad teineteist tühistada ning lehel toodud arvutused ei võta seda arvesse. Graafik eeldab, et kõik numbripaarid on võrdse tõenäosusega, mida tegelik trükkimine aga pole. Luhni ainus pime kõrvutiste numbrite paar on 09 ja 90, ning see, kui tihti need kaks kõrvuti asuvad, sõltub juba konkreetsetest arvudest.
Ei kehti, kui: Kontrollnumber ei taga turvalisust. Igaüks, kes tunneb algoritmi, suudab luua kontrolli läbiva arvu. Seetõttu näitab Luhni kontrolli läbiv kaardi number vaid seda, et see sisestati õigesti. ISBN-13 kasutab vöötkoodi algoritmi aga seepärast, et ISBN-13 ongi oma olemuselt vöötkoodi number, kuuludes GS1 poolt kasutusse antud eesliidete 978 ja 979 alla.

Luhn püüab kinni kõik kõrvutiste numbrite vahetused peale ühe: 09 ja 90 🖖

Vajuta 1234567890 + kontroll. Vaheta 9 ja 0 ning tulemus 12345678093 läbib kontrolli. Luhni algoritm kahekordistab iga teist numbrit ja liidab saadud arvu numbrid kokku, kui see on kahekohaline. Nii saab 9-st 18 ja seejärel 9, kuid 0 jääb 0-ks. Kahe kõrvutise numbri vahetamine muudab summat selle vahe võrra, mille kahekordistamine neile lisab. Kahekordistamine lisab 0-le 0, 1-le 1, 4-le 4, 5-le −4, 8-le −1 ja 9-le 0. Vaid 0 ja 9 on need kaks numbrit, mida algoritm kohtleb identselt. Seetõttu on vasakpoolses ruudustikus täpselt kaks punast lahtrit, 09 ja 90, ning algoritm püüab kinni 97,8% kõrvutiste numbrite vahetustest. Vajuta IMEI: selles pole 9 ühegi 0 kõrval ja ükski selle 13 kõrvutiste numbrite vahetusest ei pääse läbi.

Ükski mod 10 numbrite liitmisega saadud kontrollnumber ei püüa kinni iga vahetust 🖖

Vajuta UPC vöötkood. Selle üheksast kõrvutiste numbrite vahetusest kaks lähevad läbi: 3 koos 8-ga ja 0 koos 5-ga. Vöötkood korrutab üle ühe asuvaid numbreid 3 ja 1-ga, nii et a ja b vahetamine muudab summat 2(a − b) võrra. See on 10-kordne alati, kui nende vahe on viis. See kehtib 10 paari puhul 90-st. Teised kaalud ei toimi paremini. Iga üksiku vale numbri tabamiseks peab kaal olema mod 10 järgi 1, 3, 7 või 9. Iga kahe säärase kaalu vahe on paarisarv ja paarisarv korda 5 on 10-kordne. Seega on iga kaalusüsteemi laeks 88,9%. Luhni kahekordistamine pole kaal ja saavutab 97,8%. 100%-ni see aga ei jõua. Gallian viitab H. P. Gummi 1985. aasta tõestusele, et ükski numbreid liitev algoritm ei suuda tabada iga üksikut vale numbrit ja iga kõrvutiste numbrite vahetust juhul, kui moodul on paarisarv – sõltumata sellest, kuidas iga asukoht numbreid esmalt teisendab. J. Verhoeff saavutas 1969. aastal mõlemad, kasutades korrutamist viisnurga dieedrirühmas, kus tegurite järjekord on oluline.

Vaheta kaks üle ühe asuvat numbrit ja Luhn ei märka seda kunagi 🖖

Vajuta IMEI. Kõik 12 selle üle ühe numbri vahetust läbivad kontrolli. Need kaks numbrit asuvad sama paarsusega kohtadel, nii et Luhn kahekordistab kas mõlemat või mitte kumbagi ja vöötkood annab mõlemale sama kaalu. Nende vahetamine ei saa seega summat muuta ja graafik asetab mõlemad algoritmid 0,0% peale. ISBN-10 annab igale asukohale oma kaalu 10-st 1-ni. Seega muudab vahetus summat kahe kaalu vahe ja kahe numbri vahe korrutise võrra. Kuna 11 on algarv, pole see korrutis kunagi 11-kordne. Vajuta ISBN-13 ja seejärel ISBN-10: arv on sama, aga esimesest läheb läbi 9 sellist vahetust 9-st ja teisest 0 vahetust 6-st. See on harv viga, moodustades Verhoeffi arvutuste kohaselt reaalsetest vigadest vaid 0,8%, võrreldes kõrvutiste numbrite vahetuste 10,2%-ga. Kuid mod 11 süsteemil on oma nõrkus: see kulutab kontrollnumbri 10 jaoks ära sümboli X ning laseb asukohtades kaaludega 6 ja 5, mille summa on 11, läbi iga korduvate numbrite vea.

Ülesanne täielikult lahendatud

ISBN-10 laialimääritud numbri taastamine 4 sammu
ISBN-10 näeb välja selline: 0-11-000?22-9, kusjuures seitsmes number on laiali määritud. Leia see ja selgita, miks leidub täpselt üks vastus. Vajuta tulemuse kontrollimiseks ISBN-10.

Ava see ülesanne tööriistas
1. Kaalud jooksevad vasakult 10-st 1-ni, nii et laialimääritud seitsmenda numbri kaal on 4. Korruta ülejäänud üheksa numbrit nende kaaludega ja liida kokku.
  
  $S = 10 \cdot 0 + 9 \cdot 1 + 8 \cdot 1 + 7 \cdot 0 + 6 \cdot 0 + 5 \cdot 0 + 3 \cdot 2 + 2 \cdot 2 + 1 \cdot 9 = 36$
2. Kogu summa peab olema 11-kordne, seega 4 korda puuduv number peab puudujäägi katma.
  
  $36 + 4 x \equiv 0 (mod 11) \Rightarrow 4 x \equiv - 36 \equiv 8 (mod 11)$
3. Mod 11 järgi on võimalik jagada, sest 11 on algarv: 4 × 3 = 12 on 1 võrra suurem kui 11, mistõttu 3-ga korrutamine tühistab 4-ga korrutamise.
  
  $4 \cdot 3 = 12 \equiv 1 (mod 11) \Rightarrow x \equiv 8 \cdot 3 = 24 \equiv 2 (mod 11)$
4. Pane 2 tagasi ja lehe summa on 44 ehk täpselt neli ühteteist.
  
  $36 + 4 \cdot 2 = 44 = 4 \cdot 11$
Vastus

See number on 2 ja ISBN on 0-11-000222-9. See on ainus sobiv number, sest 4-ga korrutamine viib üksteist väärtust 0 kuni 10 üheteistkümne erineva mod 11 jäägini, nii et täpselt üks neist satub 8 peale. Seda sama omadust, mis laseb algoritmil tabada selles asukohas iga vale numbri, võib vaadata ka teisest küljest: kaal, mis muudab iga üksiku vea nähtavaks, teeb ühtlasi iga laialimääritud numbri taastatavaks. Mod 10 algoritm, mille kaal selles kohas on 2, annaks kas kaks kandidaati või mitte ühtegi. Lisaks jääks sellele märkamatuks iga asukoha viga, kus trükitud number erineb õigest viie võrra.

$x = 2 : 0 - 11 - 000222 - 9$

Allikad (3)

The Luhn check digit as the IMEI standard defines it, step by step, with the worked example the page's IMEI preset reproduces (26053179311383, sum 53, check digit 7): 3GPP TS 23.003, "Numbering, addressing and identification", Annex B (normative): IMEI Check Digit computation. Published as ETSI TS 123 003 V18.7.0 (2024-09).
The ISBN-13 check digit, the 1-3 weighting that barcodes use, with the manual's own example 978-0-11-000222-4: International ISBN Agency, ISBN Users' Manual, International Edition, sixth edition. London, 2012. Appendix 1, "Check digit calculation".
ISBN-10's mod 11, the barcode's blind pairs 05, 16, 27, 38, 49 and Luhn's 09 and 90, the frequencies of real mistakes from Verhoeff's study, Gumm's theorem that no even-modulus scheme catches every swap, and Verhoeff's dihedral scheme with its tables: J. A. Gallian, "Error detection methods." ACM Computing Surveys 28(3), 1996, pp. 504-517. DOI 10.1145/243439.243457

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.