Kontrolní číslice - Check digit
![]() | tento článek potřebuje další citace pro ověření.Duben 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
A kontrolní číslice je forma kontrola nadbytečnosti používá detekce chyb na identifikačních číslech, například číslech bankovních účtů, které se používají v aplikaci, kde budou alespoň někdy zadávány ručně. Je to analogické k a binární paritní bit slouží ke kontrole chyb v počítačem generovaných datech. Skládá se z jednoho nebo více číslice vypočteno algoritmem z ostatních číslic (nebo písmen) v zadaném pořadí.
Pomocí kontrolní číslice lze detekovat jednoduché chyby při zadávání řady znaků (obvykle číslic), jako je například jedna chybně zadaná číslice nebo některé obměny dvou po sobě následujících číslic.
Design
Kontrolní číslice algoritmy jsou obecně určeny k zachycení člověk chyby přepisu. Z důvodu složitosti to zahrnuje následující:[1]
- chyby jedné číslice, například 1 → 2
- chyby při transpozici, například 12 → 21
- chyby dvojčat, například 11 → 22
- chyby skokových transpozic, například 132 → 231
- chyby skokových dvojčat, například 131 → 232
- fonetické chyby, například 60 → 16 („šedesát“ až „šestnáct“)
Při výběru systému se vysoká pravděpodobnost zachycení chyb vymění proti obtížnosti implementace; systémy jednoduché kontrolní číslice jsou snadno pochopitelné a implementovatelné lidmi, ale nezachytávají tolik chyb jako složité, které vyžadují implementaci sofistikovaných programů.
Žádoucí vlastností je, že levá výplň s nulami by neměla měnit kontrolní číslici. To umožňuje použít číslice s proměnnou délkou a změnit délku. Pokud je k původnímu číslu přidána jedna kontrolní číslice, systém ne vždy zachytí násobek chyby, například dvě chyby nahrazení (12 → 34), obvykle se však dvojité chyby zachytí 90% času (obě změny by musely změnit výstup započtením částek).
Velmi jednoduchá metoda kontrolní číslice by spočívala v součtu všech číslic (digitální součet ) modulo 10. To by zachytilo jakoukoli jednocifernou chybu, protože taková chyba by vždy změnila součet, ale nezachytila by žádné chyby transpozice (přepnutí dvou číslic), protože nové pořadí nezmění součet.
Trochu složitější metodou je vzít si vážený součet číslic, modulo 10, s různými váhami pro každou pozici čísla.
Pro ilustraci, například kdyby váhy čtyřmístného čísla byly 5, 3, 2, 7 a číslo, které má být kódováno, bylo 4871, pak by bylo třeba 5 × 4 + 3 × 8 + 2 × 7 + 7 × 1 = 65, tj. 65 modulo 10, a kontrolní číslice by byla 5, což by dalo 48715.
Jsou široce používány systémy s váhami 1, 3, 7 nebo 9, přičemž váhy sousedních čísel jsou různé: například 31 31 v UPC kódy, 13 13 závaží EAN čísla (algoritmus GS1) a váhy 371 371 371 používané v bance USA směrování tranzitních čísel. Tento systém detekuje všechny jednociferné chyby a přibližně 90% chyb při provedení. 1, 3, 7 a 9 se používají, protože jsou coprime s 10, takže změna libovolné číslice změní kontrolní číslici; použití koeficientu, který je dělitelný 2 nebo 5, by ztratilo informace (protože 5 × 0 = 5 × 2 = 5 × 4 = 5 × 6 = 5 × 8 = 0 modulo 10), a tak by nezachytilo některé jednociferné chyby. Použití různých vah na sousedních číslech znamená, že většina transpozic změní kontrolní číslici; protože se však všechny váhy liší sudým číslem, nezachytí to transpozice dvou číslic, které se liší o 5, (0 a 5, 1 a 6, 2 a 7, 3 a 8, 4 a 9), protože 2 a 5 násobte, čímž získáte 10.
Kód ISBN-10 místo toho používá modulo 11, které je prvočíslo, a všechny číselné pozice mají různé váhy 1, 2, ... 10. Tento systém tak detekuje všechny jednociferné chyby náhrady a transpozice (včetně skokových transpozic), ale na náklady na kontrolní číslici mohou být 10, což představuje „X“. (Alternativou je jednoduše nepoužívat sériová čísla, jejichž výsledkem je kontrolní číslice „X“.) ISBN-13 místo toho používá algoritmus GS1 použitý v číslech EAN.
Složitější algoritmy zahrnují Luhnův algoritmus (1954), který zachycuje 98% jednociferných chyb při transpozici (nezjistí 90 ↔ 09) a stále sofistikovanější Algoritmus Verhoeff (1969), který zachycuje všechny chyby nahrazení a transpozice jedné číslice a mnoho (ale ne všechny) složitějších chyb. Podobný je další abstraktní algebra - metoda založená na Dammův algoritmus (2004), který také detekuje všechny jednociferné chyby a všechny přilehlé chyby transpozice. Tyto tři metody používají jednu kontrolní číslici, a proto nezachytí přibližně 10% složitějších chyb. Pro snížení této poruchovosti je nutné použít více než jednu kontrolní číslici (například níže uvedená kontrola modulo 97, která používá dvě kontrolní číslice - pro algoritmus viz Mezinárodní číslo bankovního účtu ) a / nebo použít větší počet znaků v kontrolní číslici, například písmena plus čísla.
Příklady
UPC
Poslední číslice a Univerzální kód produktu je kontrolní číslice vypočítaná takto:[2]
- Sčítejte číslice na lichých pozicích zprava (první, třetí, pátý atd. - bez kontrolní číslice) dohromady a vynásobte třemi.
- Přidejte k výsledku číslice (až na kontrolní číslici, ale bez nich) na sudých pozicích (druhá, čtvrtá, šestá atd.).
- Vezměte zbytek výsledku děleno 10 (tj. Operace modulo 10). Pokud je zbytek roven 0, použijte jako kontrolní číslici 0, a pokud ne 0, odečtěte zbytek od 10, abyste odvodili kontrolní číslici.
Například čárový kód UPC-A pro krabici s tkáněmi je „036000241457“. Poslední číslice je kontrolní číslice „7“, a pokud jsou ostatní čísla správná, musí výpočet kontrolní číslice poskytnout 7.
- Přidejte liché číslice: 0 + 6 + 0 + 2 + 1 + 5 = 14.
- Vynásobte výsledek 3: 14 × 3 = 42.
- Přidejte sudé číslice: 3 + 0 + 0 + 4 + 4 = 11.
- Sčítejte dva výsledky dohromady: 42 + 11 = 53.
- Chcete-li vypočítat kontrolní číslici, vezměte zbytek (53/10), který je také známý jako (53 modulo 10), a pokud ne 0, odečtěte od 10. Proto je hodnota kontrolní číslice 7. tj. (53/10 ) = 5 zbytek 3; 10 - 3 = 7.
Další příklad: pro výpočet kontrolní číslice pro následující potravinu "01010101010X".
- Přidejte liché číslice: 0 + 0 + 0 + 0 + 0 + 0 = 0.
- Vynásobte výsledek 3: 0 x 3 = 0.
- Přidejte sudé číslice: 1 + 1 + 1 + 1 + 1 = 5.
- Přidejte dva výsledky dohromady: 0 + 5 = 5.
- Chcete-li vypočítat kontrolní číslici, vezměte zbytek (5/10), který je také známý jako (5 modulo 10), a pokud ne 0, odečtěte od 10: tj. (5/10) = 0 zbytek 5; (10 - 5) = 5. Proto kontrolní číslice X hodnota je 5.
ISBN 10
Konečný znak desetimístného čísla Mezinárodní standardní číslo knihy je kontrolní číslice vypočítaná tak, že vynásobíte každou číslici její pozicí v čísle (počítáno zprava) a vezmete součet těchto produktů modulo 11 je 0. Číslice nejvzdálenější vpravo (vynásobená 1) je kontrolní číslice, která byla vybrána, aby byl součet správný. Možná bude muset mít hodnotu 10, která je reprezentována písmenem X. Vezměte například ISBN 0-201-53082-1: Součet produktů je 0 × 10 + 2 × 9 + 0 × 8 + 1 × 7 + 5 × 6 + 3 × 5 + 0 × 4 + 8 × 3 + 2 × 2 + 1 × 1 = 99 ≡ 0 ( mod 11). ISBN je tedy platný. Pozice lze počítat také zleva, v takovém případě se kontrolní číslice vynásobí 10, aby se ověřila platnost: 0 × 1 + 2 × 2 + 0 × 3 + 1 × 4 + 5 × 5 + 3 × 6 + 0 × 7 + 8 × 8 + 2 × 9 + 1 × 10 = 143 ≡ 0 (mod 11).
ISBN 13
ISBN 13 (používaný leden 2007) se rovná EAN-13 kód nalezen pod čárovým kódem knihy. Jeho kontrolní číslice je generována stejným způsobem jako UPC kromě toho, že sudé číslice jsou vynásobeny 3 místo lichých číslic.[3]
EAN (čísla GLN, GTIN, EAN spravovaná GS1)
EAN (Evropské číslo článku ) zkontrolujte číslice (spravuje GS1 ) se počítají sečtením každého z lichých čísel pozic vynásobených 3 a poté sečtením součtu čísel sudých pozic. Čísla se zkoumají zprava doleva, takže první lichá pozice je poslední číslice v kódu. Konečná číslice výsledku je odečtena od 10 pro výpočet kontrolní číslice (nebo ponechána tak, jak je, je-li již nulová). Kalkulačka kontrolní číslice GS1 a podrobná dokumentace jsou online na GS1 webové stránky.[4]Další oficiální stránka kalkulačky ukazuje, že mechanismus pro GTIN-13 je stejný pro Globální číslo místa / GLN.[5]
Další příklady kontrolních číslic
Mezinárodní
- Mezinárodní číslo SEDOL.
- Poslední číslice čísla ISSN kód nebo Číslo IMO.
- The Mezinárodní identifikační číslo cenných papírů (ISIN).
- Skupina pro správu objektů OBR standardní koncová číslice.[6]
- Mezinárodní Registrační číslo CAS poslední číslice.
- Modulo 10 kontroluje číslice kreditní karta čísla účtů vypočítaná podle Luhnův algoritmus.
- Používá se také v norských číslech KID (identifikační číslo zákazníka) používaných v bankovních giroch (převod),
- Použito v IMEI mobilních telefonů.
- Poslední kontrolní číslice v EAN / UPC serializaci globálního obchodního identifikačního čísla (GTIN ). Platí pro GTIN-8, GTIN-12, GTIN-13 a GTIN-14.
- Poslední číslice a DUNS číslo (i když se to plánuje změnit, například to, že konečná číslice bude volena volně v nových alokacích, místo aby byla kontrolní číslicí).
- Třetí a čtvrtá číslice v Mezinárodní číslo bankovního účtu (Kontrola Modulo 97).
- Poslední číslice v Mezinárodní standardní textový kód.
- Poslední znak zakódovaný do a karta s magnetickým proužkem je vypočítaný Kontrola podélné nadbytečnosti.
V USA
- Desátá číslice čísla Národní identifikátor poskytovatele pro americký zdravotnický průmysl.
- Poslední číslice a POSTNET kód.
- Severoameričan CUSIP číslo.
- Poslední (devátá) číslice čísla Číslo trasy směrování ABA, a bankovní kód používané ve Spojených státech.
- Devátá číslice a Identifikační číslo vozidla (VIN).
- Klinika Mayo identifikační čísla pacientů používaná v Arizoně a na Floridě zahrnují kontrolní kontrolní číslici[Citace je zapotřebí ].
- Jedenáctá číslice a Clo a ochrana hranic číslo záznamu.
Ve Střední Americe
- Guatemalské daňové číslo (NIT - Número de Identificación Tributaria) založené na modulo 11.
V Eurasii
- Spojené království Číslo NHS používá algoritmus modulo 11.
- Španělské fiskální identifikační číslo (número de identificación fiscal, NIF) (na základě modulu 23).
- The holandský Burgerservicenummer (BSN) (národní identifikátor) používá algoritmus modulo 11.
- Devátá číslice čísla izraelský Teudat Zehut (Identifikační číslo karty.
- 13. číslice srbština a Bývalý jugoslávský Unikátní hlavní občanské číslo (JMBG). (ale ne všechny z důvodu chyb nebo nebytí)
- Poslední dvě číslice 11místného čísla Turecké identifikační číslo (turečtina: TC Kimlik Numarası).
- Devátý znak ze 14 znaků EU číslo pasu skotu (cykly od 1 do 7: viz Britská služba pro pohyb skotu ).
- Devátá číslice v islandský Kennitala (národní identifikační číslo).
- Modulo 97 kontrolní číslice v a belgický a srbština čísla bankovních účtů. Srbsko někdy také používá jako referenční číslo modul 11.
- Devátá číslice v a maďarský Číslo TAJ (číslo sociálního pojištění).
- Pro obyvatele Indie, pojmenované jedinečné identifikační číslo Aadhaar má koncovou 12. číslici, která se vypočítá pomocí Algoritmus Verhoeff.[7]
- The Singapurský úřad pro duševní vlastnictví (IPOS) potvrdila nový formát pro čísla žádostí o registraci Duševní vlastnictví (IP, např. ochranné známky, patenty, zapsané vzory ). Bude obsahovat kontrolní znak vypočítaný pomocí Dammův algoritmus.[8]
- Poslední číslice čínského občanského identifikačního čísla (druhá generace) se počítá modulem 11-2, jak je uvedeno v čínské verzi GuoBiao (neboli národní normě) GB11643-1999, která přijímá ISO 7064: 1983. „X“ se používá, pokud je vypočtená kontrolní číslice 10.
V Oceánii
- Australan číslo daňového spisu (na základě modulo 11).
- Sedmý znak a Nový Zéland Číslo NHI.
- Poslední číslice v a Nový Zéland lokomotiva číslo systému sledování provozu (TMS).
Algoritmy
Pozoruhodné algoritmy zahrnují:
- Luhnův algoritmus (1954)
- Algoritmus Verhoeff (1969)
- Dammův algoritmus (2004)
Viz také
- Kontrolní součet
- Vyhání devítky, podobná kontrola modulárního součtu
- Zkontrolujte bit, binární ekvivalent
Reference
- ^ Kirtland, Joseph (2001). Identifikační čísla a schémata kontrolních číslic. Zdroje učeben. Mathematical Association of America. s. 4–6. ISBN 978-0-88385-720-5.
- ^ „Kalkulačka kontrolní číslice GS1“. GS1 USA. 2006. Archivovány od originál dne 2008-05-09. Citováno 2008-05-21.
- ^ „Uživatelská příručka ISBN“. Mezinárodní agentura ISBN. 2005. Citováno 2008-05-21.
- ^ „Check Digit Calculator“. GS1. 2005. Citováno 2008-05-21.
- ^ „Check Digit Calculator, na oficiálním webu GS1 USA“. GS1 USA. Citováno 2012-08-09.
- ^ http://openfigi.com
- ^ „Unikátní identifikační karta“. Geek Gazette. IEEE Student Branch (Podzim 2011 ): 16. Archivovány od originál dne 2012-10-24.
- ^ Dr. Chong-Yee Khoo (20. ledna 2014). „Nový formát pro singapurská čísla IP aplikací na IPOS“. Singapurský patentový blog. Cantab IP. Citováno 6. července 2014.
externí odkazy
- Identifikační čísla a schémata kontrolních číslic (matematické vysvětlení různých schémat kontrolních číslic)
- Kalkulačka kontrolních číslic UPC, EAN a SCC-14
- Kalkulačka kontrolní číslice GS1