Co to jest cyfra kontrolna?

R.J.Żyłła - na podstawie wielu źródeł w internecie,
rozmów osobistych z urzędami, e-maili czytelników.
Poprawione algorytmy i programy.
¤ Trochę historii
¤ Cyfra kontrolna w numerach ewidencyjnych
¤ Jak obliczyć cyfrę kontrolną?
¤ Numer PESEL
    ¤    Czy ten algorytm jest optymalny?
    ¤    Ciekawostki w kodowaniu numeru PESEL
¤ Inne numery
    ¤    NIP   REGON   REGON14
    ¤    EAN13   EAN8
    ¤    ISBN   ISMN   ISSN   ISTC
    ¤    IACS - numery kolczyków krów
    ¤    numer identyfikacyjny gospodarstwa
    ¤    BANK   IBAN   KARTY KREDYTOWE
    ¤    Numery recept (Dz. U. Nr 85, poz. 785)   
    ¤    Numery Prawa Wykonywania Zawodu Lekarza
    ¤    Numery Prawa Wykonywania Zawodu Farmaceuty
    ¤    Paszporty, dowody ...
    ¤    Kody Nowej Księgi Wieczystej
    ¤    Numery substancji chemicznych CAS EC/WE Index Nowość
    ¤    Identyfikator kontenera
    ¤    Europejski numer pojazdu kolejowego
¤ Syntetyczne podsumowanie algorytmów
    ¤    Słowniczek pojęć
    ¤    Programy do weryfikacji (online)
    ¤    JavaScript do weryfikacji
    ¤    Lektura dodatkowa
¤ Kody terytorialne GUS
    ¤    Kody miejscowosci SIMC
¤ Tablice rejestracyjne pojazdów

Co mają wspólnego numery PESEL, NIP, REGON, numer konta bankowego, Dowodu Osobistego, paszportu, ISBN, EAN13, EAN8, IACS ? Oto typowe odpowiedzi:

  • numery identyfikacyjne są używane przez komputery zamiast nazw, bo komputery działają na liczbach
  • zawierają cyfry i myślniki, ale różnią się długością,
  • jeśli traktować je jako liczby to muszą być większe niż liczba elementów im przyporządkowanych,
  • grupy cyfr w tych numerach określają cechy obiektów identyfikowanych,
  • są niepowtarzalne ?.

Formalnie są to ciągi cyfr. Ale równie dobrze identyfikatorami mogą być ciągi cyfr i liter tak jak np. numery rejestracyjne samochodów, jachtów, statków albo identyfikatory krótkofalowców.
Ale jest jeszcze jedna cecha, która jest wspólna dla tych numerów. Występuje w nich cyfra kontrolna – zwykle na końcu numeru.


Trochę historii

W systemach narażonych na błędy stosuje się pewien sposób nadmiarowego zapisu danych tak aby ewentualne błędy mogły być zauważone. W zapisach na taśmach perforowanych (czy ktoś jeszcze pamięta, że w Polsce produkowano prawdziwe komputery ODRA ?) każdy znak ASCII był kodowany w siedmiu bitach. Bit=1 to była dziurka, bit=0 to był brak dziurki w odpowiedniej pozycji. W ósmym bicie, tzw. bicie parzystości kodowano czy w siedmiu bitach była parzysta czy nieparzysta liczba dziurek.
Jeśli była nieparzysta to na ósmej pozycji taśma była dziurkowana, w przeciwnym przypadku na ósmej pozycji nie było dziurki.
Krótka analiza powyższego zdania prowadzi do wniosku, że gdy się wzięło pod uwagę wszystkie bity-dziurki to była ich zawsze parzysta liczba. Wbudowanie odpowiedniej elektroniki do czytnika taśmy, która by sprawdzała parzystość nie była trudna. Jeśli do taśmy przyczepił się jakiś paproszek i podczas czytania zatkał jedną z dziurek to czytnik łatwo to wykrywał. W ten sposób do komputera nie przedostawały się „brudne” dane :-).

taśma perforowana ASCII 7 bit ODRA1300 MERA400

Na ilustracji powyżej widać taśmę perforowaną z fragmentem programu w języku BASIC-EXT na komputer MERA400. Wyperforowane znaki to:
'LF 100 REM REPLIKA ALGOLOWEGO PROG. 02/04/80 SALFORD'.
Widać jeszcze rządek mniejszych dziurek; jest to tzw. ścieżka prowadząca, która dla czytnika mechanicznego spełniała rolę perforacji jak na taśmie filmowej, natomiast dla czytnika optycznego pełniła rolę synchronizatora i wskaźnika braku uszkodzeń taśmy.

Według podobnej zasady działają pamięci RAM z tzw. bitem parzystości. Niestety ten dodatkowy bit kosztuje i tandetniejsze komputery go nie stosują.

Nie będziemy (bo się nie znamy :) tu omawiać kodowania nadmiarowego, które umożliwia odtworzenie brakujących bitów - ta metoda jest stosowanna na przykład w zapisie płyt CD i na dyskach twardych.


Cyfra kontrolna w numerach ewidencyjnych

Przy „ręcznym” wprowadzaniu danych często popełnia się błędy np. zamiany kolejności cyfr lub błędnego rozpoznania niewyraźnie napisanej cyfry w formularzu.
Aby częściowo zapobiec tym błędom, a właściwie aby nie przepuścić takich błędów i nie wprowadzić błędnego numeru do komputera stosuje się właśnie cyfrę kontrolną.

J. Verhoeff (Error Detecting Decimal Codes, Mathematical Centre Tract 29, The Mathematical Centre, Amsterdam, 1969), podał bardziej szczegółowy podział na rodzaje błędów jakie robią ludzie podczas wpisywania cyfr - na podstawie około 12tys. błędów.

  • pojedynczy błąd: a wpisane jako b (60% do 95% wszystkich błędów)
  • pominięcie lub dodanie cyfry (10% to 20%)
  • zamiana sąsiednich cyfr - tzw. czeski błąd: ab wpisane jako ba (10% to 20%)
  • błędy bliźniacze: aa wpisane jako bb (0.5% to 1.5%)
  • zamiana niesąsiednich cyfr: acb wpisane jako bca (0.5% to 1.5%)
  • błędy bliźniacze niesąsiednich cyfr: aca wpisane jako bcb (poniżej 1%) [niższe dla dalszych]
  • błędy fonetyczne: a0 wpisane jako 1a [gdyż te mają podobna wymowę, np thirty i thirteen] (0.5% to 1.5%)

w powyższych przykładach a nie jest równe b, c może być dowolną cyfrą.

Jak obliczyć cyfrę kontrolną?

Nasuwa się tu prosty algorytm:
  -  sumujemy wszystkie cyfry z całego numeru,
  -  jako cyfrę kontrolną bierzemy ostatnią cyfrę z tej sumy.

Algorytm jest bardzo prosty, ale nie bierze pod uwagę, że przy tzw. czeskim błędzie (zamiana kolejności cyfr lub liter przy szybkim wprowadzaniu danych z klawiatury) suma cyfr wyjdzie taka sama. A więc taki algorytm by nie wykrył czeskich błędów.

Dlatego wprowadzono modyfikację i nie sumuje się cyfr ale iloczyny cyfr i współczynników wagowych. Ażeby algorytm wykrywał czeskie błędy współczynniki wagowe dla sąsiednich cyfr powinny się różnić i żaden współczynnik nie może być zerem.
Patrz Dobór współczynników wagowych.

Ostatnią cyfrę sumy znajduje się przez dzielenie modulo 10. Ostatnia cyfra sumy może być cyfrą kontrolną, ale często jako cyfrę kontrolną bierze się dopełnienie do dziesięciu - czyli w uproszczeniu różnicę (10 - ostatnia cyfra sumy). Wzięcie dopełnienia do 10 w rzeczywistości upraszcza weryfikację poprawności numeru.
Jak to możliwe? Ano tak, że przy weryfikacji nie oblicza się cyfry kontrolnej, ale do obliczenia sumy iloczynów bierze się także cyfrę kontrolną weryfikowanego numeru z wagą 1 i sprawdza ostatnią cyfrę sumy. Jeśli ostatnia cyfra sumy wynosi 0 to numer jest zweryfikowany jako poprawny.

Jak sprawdzić cyfrę kontrolną?

Podkreślmy więc, że do weryfikacji poprawności numeru „zabezpieczonego” cyfrą kontrolną nie musimy jej wcale obliczać! Obliczenie jest tylko potrzebne do generowania cyfry kontrolnej gdy mamy jakiś numer (ciąg cyfr) i chcemy mu „dokleić” cyfrę kontrolną.


ciąg dalszy



Słowniczek pojęć:

Modulo
jest to reszta z dzielenia. Przykład 13 mod 6 = 1
PESEL
jedenasto cyfrowy identyfikator
(Powszechny Elektroniczny System Ewidencji Ludności)
NIP
dziesięcio cyfrowy identyfikator podatkowy
(Numer Identyfikacji Podatkowej)
REGON
dziewięcio cyfrowy identyfikator statystyczny
(Rejestr Gospodarki Narodowej)
Nr konta bankowego -
pierwsze osiem cyfr konta bankowego oznacza
bank w którym jest założone owo konto.
ISBN
Międzynarodowy Znormalizowany Numer Książki
International Standard Book Number
ISSN
International Standard Serial Number
ISMN
International Standard Music Number
Międzynarodowy Znormalizowany Numer Druku Muzycznego,
Zaczyna się literą M, po której następuje 9 cyfr
ISRN
International Standard Technical Report Number
IACS
The EU Integrated Administration and Control System
Zintegrowany System Zarządzania i Kontroli

          (od 2 stycznia 2001)
          ostatnie poprawki 2013

Valid HTML 4.01 Transitional