�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