Cyfra kontrolna - Check digit
Cyfra kontrolna jest formą kontroli nadmiarowej używane do wykrywania błędów o numerach identyfikacyjnych, takich jak numery kont bankowych, które są stosowane w aplikacjach, gdzie będą przynajmniej czasami być wprowadzane ręcznie. Jest to analogiczne do binarnego bitu parzystości używanego do sprawdzania błędów w danych generowanych komputerowo. Składa się z jednej lub więcej cyfr (lub liter) obliczonych przez algorytm z pozostałych cyfr (lub liter) we wprowadzanej sekwencji.
Dzięki cyfrze kontrolnej można wykryć proste błędy we wprowadzaniu szeregu znaków (zwykle cyfr), takie jak pojedyncza błędnie wpisana cyfra lub niektóre permutacje dwóch kolejnych cyfr.
Projekt
Algorytmy cyfr kontrolnych są zazwyczaj przeznaczone do przechwytywania błędów transkrypcji dokonywanych przez człowieka . W kolejności złożoności są to:
- błędy literowe/cyfrowe, takie jak l → 1 lub O → 0
- błędy jednocyfrowe, takie jak 1 → 2
- błędy transpozycji, takie jak 12 → 21
- bliźniacze błędy, takie jak 11 → 22
- błędy transpozycji skoku, takie jak 132 → 231
- przeskakuj błędy bliźniaków, takie jak 131 → 232
- błędy fonetyczne, takie jak 60 → 16 („sześćdziesiąt” do „szesnastu”)
Przy wyborze systemu wysokie prawdopodobieństwo wyłapania błędów jest wymieniane na trudności w implementacji; proste systemy cyfr kontrolnych są łatwo zrozumiałe i wdrożone przez ludzi, ale nie wychwytują tylu błędów, co te złożone, których wdrożenie wymaga zaawansowanych programów.
Pożądaną cechą jest to, że lewe dopełnienie zerami nie powinno zmieniać cyfry kontrolnej. Pozwala to na użycie numerów o zmiennej długości i zmianę długości. Jeśli do oryginalnego numeru zostanie dodana pojedyncza cyfra kontrolna, system nie zawsze wykryje wiele błędów, takich jak dwa błędy zastępcze (12 → 34), chociaż zazwyczaj podwójne błędy zostaną wyłapane w 90% przypadków (obie zmiany trzeba zmienić wynik przez kompensowanie kwot).
Bardzo prostą metodą cyfr kontrolnych byłoby wzięcie sumy wszystkich cyfr ( suma cyfrowa ) modulo 10. Wyłapałoby to każdy błąd jednocyfrowy, ponieważ taki błąd zawsze zmieniałby sumę, ale nie wychwytuje żadnych błędów transpozycji (przełączanie dwie cyfry), ponieważ ponowne zamówienie nie zmienia sumy.
Nieco bardziej złożoną metodą jest wzięcie ważonej sumy cyfr, modulo 10, z różnymi wagami dla każdej pozycji liczby.
Aby to zilustrować, na przykład jeśli wagi dla liczby czterocyfrowej wynosiły 5, 3, 2, 7, a numer do zakodowania to 4871, to należałoby wziąć 5×4 + 3×8 + 2×7 + 7×1 = 65, czyli 65 modulo 10, a cyfrą kontrolną będzie 5, co daje 48715.
Powszechnie stosowane są systemy o wagach 1, 3, 7 lub 9, przy czym wagi na sąsiednich numerach są różne: np. 31 31 wag w kodach UPC , 13 13 wag w numerach EAN (algorytm GS1) i 371 371 371 wagi używane w numerach tranzytowych banku w Stanach Zjednoczonych . System ten wykrywa wszystkie błędy jednocyfrowe i około 90% błędów transpozycji. 1, 3, 7 i 9 są używane, ponieważ są względnie pierwsze z 10, więc zmiana dowolnej cyfry zmienia cyfrę kontrolną; użycie współczynnika podzielnego przez 2 lub 5 spowodowałoby utratę informacji (ponieważ 5×0 = 5×2 = 5×4 = 5×6 = 5×8 = 0 modulo 10), a tym samym nie wyłapałoby niektórych błędów jednocyfrowych. Użycie różnych wag na sąsiednich liczbach oznacza, że większość transpozycji zmienia cyfrę kontrolną; jednak ponieważ wszystkie wagi różnią się liczbą parzystą, nie obejmuje to transpozycji dwóch cyfr różniących się o 5, (0 i 5, 1 i 6, 2 i 7, 3 i 8, 4 i 9), ponieważ 2 i 5 pomnóż, aby uzyskać 10.
Kod ISBN-10 używa zamiast tego modulo 11, który jest liczbą pierwszą, a wszystkie pozycje liczbowe mają różne wagi 1, 2, ... 10. Ten system w ten sposób wykrywa wszystkie błędy w podstawieniu i transpozycji pojedynczych cyfr (w tym transpozycje skoku), ale przy koszt cyfry kontrolnej prawdopodobnie wynosi 10, reprezentowanej przez „X”. (Alternatywą jest po prostu unikanie używania numerów seryjnych, które skutkują cyfrą kontrolną „X”.) Zamiast tego ISBN-13 używa algorytmu GS1 używanego w numerach EAN.
Bardziej skomplikowane algorytmy obejmują algorytm Luhna (1954), który wychwytuje 98% jednocyfrowych błędów transpozycji (nie wykrywa 90 ↔ 09) oraz jeszcze bardziej zaawansowany algorytm Verhoeffa (1969), który wyłapuje wszystkie jednocyfrowe błędy podstawienia i transpozycji, i wiele (ale nie wszystkie) bardziej złożone błędy. Podobna jest inna metoda oparta na algebrze abstrakcyjnej , algorytm Damm (2004), który również wykrywa wszystkie błędy jednocyfrowe i wszystkie sąsiednie błędy transpozycji. Te trzy metody wykorzystują pojedynczą cyfrę kontrolną i dlatego nie wychwytują około 10% bardziej złożonych błędów. Aby zmniejszyć ten wskaźnik awaryjności, konieczne jest użycie więcej niż jednej cyfry kontrolnej (na przykład czek modulo 97, o którym mowa poniżej, który wykorzystuje dwie cyfry kontrolne - dla algorytmu, patrz Międzynarodowy Numer Rachunku Bankowego ) i/lub użycie szerszy zakres znaków w cyfrze kontrolnej, na przykład litery plus cyfry.
Przykłady
UPC
Ostatnia cyfra uniwersalnego kodu produktu to cyfra kontrolna obliczana w następujący sposób:
- Dodaj cyfry w nieparzystych pozycjach od prawej (pierwszy, trzeci, piąty itd. - nie licząc cyfry kontrolnej) i pomnóż przez trzy.
- Dodaj do wyniku cyfry (do cyfry kontrolnej, ale bez niej) na pozycjach parzystych (druga, czwarta, szósta itd.).
- Podziel resztę wyniku przez 10 (tj. operacja modulo 10). Jeśli reszta jest równa 0, użyj 0 jako cyfry kontrolnej, a jeśli nie, odejmij resztę od 10, aby uzyskać cyfrę kontrolną.
Na przykład kod kreskowy UPC-A dla pudełka chusteczek to „036000241457”. Ostatnia cyfra to cyfra kontrolna „7”, a jeśli inne liczby są poprawne, obliczenie cyfry kontrolnej musi dać 7.
- Dodaj nieparzyste cyfry liczb: 0+6+0+2+1+5 = 14.
- Pomnóż wynik przez 3: 14 × 3 = 42.
- Dodaj cyfry parzyste: 3+0+0+4+4 = 11.
- Dodaj oba wyniki razem: 42 + 11 = 53.
- Aby obliczyć cyfrę kontrolną, weź resztę z (53 / 10), która jest również znana jako (53 modulo 10), a jeśli nie, odejmij od 10. Dlatego wartość cyfry kontrolnej wynosi 7. tj. (53 / 10 ) = 5 reszta 3; 10 - 3 = 7.
Inny przykład: aby obliczyć cyfrę kontrolną dla następującego artykułu spożywczego "01010101010 x ".
- Dodaj nieparzyste cyfry liczb: 0+0+0+0+0+0 = 0.
- Pomnóż wynik przez 3: 0 x 3 = 0.
- Dodaj cyfry parzyste: 1+1+1+1+1=5.
- Dodaj oba wyniki razem: 0 + 5 = 5.
- Aby obliczyć cyfrę kontrolną, weź resztę z (5 / 10), znaną również jako (5 modulo 10), a jeśli nie 0, odejmij od 10: tj. (5 / 10) = 0 reszta 5; (10 - 5) = 5. Dlatego wartość cyfry kontrolnej x wynosi 5.
Numer ISBN 10
Ostatnim znakiem dziesięciocyfrowego międzynarodowego znormalizowanego numeru księgi jest cyfra kontrolna obliczona w taki sposób, że pomnożenie każdej cyfry przez jej pozycję w liczbie (licząc od prawej) i wzięcie sumy tych iloczynów modulo 11 wynosi 0. Najdalsza cyfra po prawej stronie (która jest pomnożona przez 1) znajduje się cyfra kontrolna wybrana, aby suma była poprawna. Może wymagać wartości 10, która jest reprezentowana jako litera X. Weźmy na przykład numer ISBN 0-201-53082-1 : Suma iloczynów to 0×10 + 2×9 + 0×8 + 1× 7 + 5×6 + 3×5 + 0×4 + 8×3 + 2×2 + 1×1 = 99 ≡ 0 (mod 11). Czyli ISBN jest ważny. Zwróć uwagę, że pozycje można również liczyć od lewej, w takim przypadku cyfra kontrolna jest mnożona przez 10, aby sprawdzić poprawność: 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 (w użyciu w styczniu 2007) odpowiada kodowi EAN-13 znajdującemu się pod kodem kreskowym książki. Jego cyfra kontrolna jest generowana w taki sam sposób jak UPC, z tym wyjątkiem, że cyfry parzyste są mnożone przez 3 zamiast cyfr nieparzystych.
EAN (numery GLN, GTIN, EAN administrowane przez GS1)
Cyfry kontrolne EAN ( European Article Number ) (administrowane przez GS1 ) są obliczane przez zsumowanie nieparzystych numerów pozycji pomnożonych przez 3, a następnie przez dodanie sumy parzystych numerów pozycji. Liczby są sprawdzane od prawej do lewej, więc pierwsza nieparzysta pozycja to ostatnia cyfra w kodzie. Ostatnia cyfra wyniku jest odejmowana od 10, aby obliczyć cyfrę kontrolną (lub pozostawioną bez zmian, jeśli jest już zero). Kalkulator cyfr kontrolnych GS1 i szczegółowa dokumentacja są dostępne online na stronie internetowej GS1 . Inna oficjalna strona kalkulatora pokazuje, że mechanizm GTIN-13 jest taki sam dla Globalnego Numeru Lokalizacyjnego /GLN.
NCDA
Stosowany od 2004 roku algorytm NOID Check Digit Algorithm (NCDA) jest przeznaczony do stosowania w identyfikatorach trwałych i pracuje z ciągami liter i cyfr o zmiennej długości, zwanymi cyframi rozszerzonymi. Jest szeroko stosowany ze schematem identyfikatorów ARK i nieco używany ze schematami, takimi jak Handle System i DOI . Rozszerzona cyfra jest ograniczona do znaków betanumerycznych , które są alfanumerycznymi minus samogłoski i literą „l” (ell). To ograniczenie pomaga przy generowaniu nieprzezroczystych ciągów, które prawdopodobnie nie utworzą słów przez przypadek i nie będą zawierać zarówno O i 0, jak i l i 1. Mając podstawę liczby pierwszej równej R=29, repertuar betanumeryczny pozwala algorytmowi zagwarantować wykrywanie pojedynczych znaków. błędy znaków i transpozycji dla łańcuchów o długości mniejszej niż R=29 znaków (poza nimi zapewnia to nieco słabsze sprawdzenie). Algorytm uogólnia się na dowolny repertuar znaków z podstawą podstawową R i ciągami krótszymi niż R znaków.
Inne przykłady cyfr kontrolnych
Międzynarodowy
- Międzynarodowy numer SEDOL.
- Ostatnia cyfra kodu ISSN lub numeru IMO .
- Te międzynarodowe numer identyfikacyjny papierów wartościowych (ISIN).
- Grupa Zarządzania Obiektami FIGI standardowa ostatnia cyfra.
- Ostatnia cyfra międzynarodowego numeru rejestru CAS .
- Modulo 10 cyfr kontrolnych w numerach kont kart kredytowych , obliczony algorytmem Luhna .
- Używane również w norweskich numerach KID (numer identyfikacyjny klienta) używanych w przekazach bankowych (polecenie przelewu),
- Używany w IMEI telefonów komórkowych.
- Ostatnia cyfra kontrolna w serializacji EAN/UPC Globalnego Numeru Identyfikacyjnego Handlu ( GTIN ). Dotyczy GTIN-8, GTIN-12, GTIN-13 i GTIN-14.
- Ostatnia cyfra numeru DUNS (chociaż ma się to zmienić, na przykład ostatnia cyfra zostanie wybrana swobodnie w nowych alokacjach, a nie będzie cyfrą kontrolną).
- Trzecia i czwarta cyfra w międzynarodowym numerze konta bankowego (czek Modulo 97).
- Ostatnia cyfra w międzynarodowym standardowym kodzie tekstowym .
- Ostatni znak zakodowany na karcie z paskiem magnetycznym to obliczona kontrola nadmiarowości wzdłużnej .
W USA
- Dziesiąta cyfra krajowego identyfikatora dostawcy dla amerykańskiej branży opieki zdrowotnej.
- Ostatnia cyfra kodu POSTNET .
- Numer CUSIP w Ameryce Północnej .
- Ostatnia (dziewiąta) cyfra numeru tranzytowego trasy ABA , kodu banku używanego w Stanach Zjednoczonych.
- Dziewiąta cyfra numeru identyfikacyjnego pojazdu (VIN).
- Numery identyfikacyjne pacjentów Mayo Clinic używane w Arizonie i na Florydzie zawierają ciągłą cyfrę kontrolną.
- Jedenasta cyfra numeru wpisu do ochrony celnej i granicznej .
W Ameryce Środkowej
- Gwatemalski numer podatkowy (NIT – Número de Identificación Tributaria) na podstawie modulo 11.
W Eurazji
- Numer NHS w Wielkiej Brytanii wykorzystuje algorytm modulo 11.
- Hiszpański numer identyfikacji podatkowej (número de identificación tax, NIF) (na podstawie modulo 23).
- Holenderski Burgerservicenummer (BSN) (identyfikator krajowy) korzysta z algorytmu modulo 11.
- Dziewiąta cyfra numeru izraelskiego Teudat Zehut (dowód osobisty).
- 13. cyfra serbskiego i byłego jugosłowiańskiego unikalnego numeru obywatela głównego (JMBG) . (ale nie wszystkie z powodu błędów lub braku miejsca zamieszkania)
- Dwie ostatnie cyfry 11-cyfrowego tureckiego numeru identyfikacyjnego ( turecki : TC Kimlik Numarası ).
- Dziewiąty znak w 14-znakowym numerze unijnego paszportu bydła (cykle od 1 do 7: patrz British Cattle Movement Service ).
- Dziewiąta cyfra w islandzkiej Kennitali (krajowy numer identyfikacyjny).
- Cyfry kontrolne Modulo 97 w belgijskich i serbskich numerach kont bankowych. Serbia czasami używa również modulo 11 jako numeru referencyjnego.
- Dziewiąta cyfra węgierskiego numeru TAJ (numer ubezpieczenia społecznego).
- W przypadku mieszkańców Indii unikalny numer identyfikacyjny o nazwie Aadhaar ma końcową dwunastą cyfrę obliczaną za pomocą algorytmu Verhoeffa .
- Urzędzie Własności Intelektualnej w Singapurze (IPO) potwierdził nowy format numerów aplikacyjnych wpisaniu do rejestru własności intelektualnej (IP, np znaków towarowych , patentów , zarejestrowanych wzorów ). Będzie zawierał znak kontrolny obliczony algorytmem Damm .
- Ostatnia cyfra numeru identyfikacyjnego obywatela Chin (druga generacja) jest obliczana przez modulo 11-2, jak określono w chińskim GuoBiao (znanym jako norma krajowa) GB11643-1999, który przyjmuje ISO 7064:1983. „X” jest używany, jeśli obliczona cyfra kontrolna to 10.
- 11. cyfra estońskiego Isikukood (osobisty kod identyfikacyjny).
W Oceanii
- Numer australijskiego pliku podatkowego (na podstawie modulo 11).
- Siódma postać nowozelandzkiego numeru NHI .
- Ostatnia cyfra w numerze systemu monitorowania ruchu (TMS) lokomotywy w Nowej Zelandii .
Algorytmy
Godne uwagi algorytmy obejmują:
- Algorytm Luhna (1954)
- Algorytm Verhoeffa (1969)
- Algorytm Damm (2004)
Zobacz też
- Suma kontrolna :
- Wyrzucanie dziewiątek , podobna suma modułowa sprawdzania
- Sprawdź bit ; odpowiednik binarny
Bibliografia
Zewnętrzne linki
- Numery identyfikacyjne i schematy cyfr kontrolnych (matematyczne wyjaśnienie różnych schematów cyfr kontrolnych)
- Kalkulator cyfr kontrolnych UPC, EAN i SCC-14
- Kalkulator cyfr kontrolnych GS1