Algorytm Verhoeffa

Algorytm Verhoeffa to formuła sumy kontrolnej do wykrywania błędów , opracowana przez holenderskiego matematyka Jacobusa Verhoeffa i po raz pierwszy opublikowana w 1969 roku. Był to pierwszy dziesiętny algorytm cyfry kontrolnej , który wykrywa wszystkie błędy jednocyfrowe i wszystkie błędy transpozycji obejmujące dwie sąsiednie cyfry, co było wówczas uważane za niemożliwe przy takim kodzie.

Cele

Verhoeff miał na celu znalezienie kodu dziesiętnego - takiego, w którym cyfra kontrolna jest pojedynczą cyfrą dziesiętną - który wykryłby wszystkie błędy jednocyfrowe i wszystkie transpozycje sąsiednich cyfr. W tamtym czasie rzekome dowody na nieistnienie tych kodów sprawiły, że kody base-11 stały się popularne, na przykład w cyfrze kontrolnej ISBN .

Jego cele były również praktyczne i oparł ocenę różnych kodów na aktualnych danych z holenderskiego systemu pocztowego, stosując system punktów ważonych dla różnych rodzajów błędów. Analiza podzieliła błędy na kilka kategorii: po pierwsze, o ile cyfr jest błędnych; dla osób z błędnymi dwiema cyframi istnieją transpozycje ( ab → ba ), bliźniaki ( aa → „bb”), transpozycje skokowe ( abc → cba ), fonetyczne ( 1a → a0 ) i przeskocz bliźniaki ( aba → cbc ). Dodatkowo występują cyfry pominięte i dodane. Chociaż częstość niektórych tego rodzaju błędów może być niewielka, niektóre kody mogą być na nie odporne, oprócz głównego celu wykrywania wszystkich pojedynczych i transpozycji.

W szczególności błędy fonetyczne wykazały skutki językowe, ponieważ w języku niderlandzkim liczby są zwykle czytane parami; a także, chociaż 50 brzmi podobnie do 15 w języku niderlandzkim, 80 nie brzmi jak 18.

Biorąc za przykład liczby sześciocyfrowe, Verhoeff podał następującą klasyfikację błędów:

Błędne cyfry	Klasyfikacja	Liczyć	Częstotliwość
1	Transkrypcja	9574	79,05%
2	Transpozycje	1237	10,21%
	Bliźnięta	67	0,55%
	Fonetyczny	59	0,49%
	Inne obok	232	1,92%
	Transpozycje skokowe	99	0,82%
	Skocz bliźniaki	35	0,29%
	Inne błędy skoku	43	0,36%
	Inny	98	0,81%
3		169	1,40%
4		118	0,97%
5		219	1,81%
6		162	1,34%
Całkowity		12112

Opis

Ogólną ideą algorytmu jest przedstawienie każdej z cyfr (od 0 do 9) jako elementów grupy dwuściennej ${\ displaystyle D_ {5}}$ . Oznacza to, że mapuj cyfry na $cyfry$ manipuluj nimi, a następnie mapuj z powrotem na Niech to odwzorowanie będzie ${\ Displaystyle m: [0,9] \ do D_ {5}}$

$3 i 4 i 5 i 6 i 7 i 8 i 9 \\ e& r & r ^ { 2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\end{pmacierz}}}$

${n}}$ -tą cyfrą będzie niech liczba cyfr będzie ${\ displaystyle a_$ .

Na przykład, biorąc pod uwagę kod 248, to ${\ displaystyle k}$ wynosi 3 i ${\ displaystyle a_ {3} = m (8) = r ^ {3} s}$ .

Teraz zdefiniuj permutację ${\ Displaystyle f: D_ {5} \ do D_ {5}}$

${\ Displaystyle f = {\ rozpocząć {pmatrix} e&r&r ^ {2}&r ^ {3}&r ^ {4}&s&rs&r ^ {2}s&r ^ {3}s&r ^ {4}s\\r&s&r ^ {2}s&rs&r ^{2}&r^{3}s&r^{3}&e&r^{4}s&r^{4}\end{pmacierz}}}$

Na przykład ${\ displaystyle f (r ^ {3}) = rs}$ . Innym przykładem jest ${\ Displaystyle f ^ {2} (r ^ {3}) = r ^ {3}}$ ponieważ ${\ Displaystyle f (f (r ^ {3})) = f (rs) = r ^ {3}}$

Używając notacji multiplikatywnej dla operacji grupowej , cyfra kontrolna jest wtedy po prostu wartością ${\ displaystyle$ , że $D_ {5}}$

${\ Displaystyle f (a_ {1}) \ cdot f ^ {2} (a_ {2})\cdot \ldots \cdot f^{k}(a_{k})\cdot f^{k+1}(c)=e}$

$}$ jest wyraźnie podane przez odwrotną permutację

${\ Displaystyle c = f ^ {-1-k} \ lewo (\ prod _ {n = 1} ^ {k} f^{n}(a_{n})^{-1}\prawo)}$

Na przykład cyfra kontrolna dla 248 to 5. Aby to zweryfikować, użyj odwzorowania na i wstaw do LHS poprzedniego równania ${\ displaystyle D_ {5}}$

${\ Displaystyle f (r ^ {2}) \ cdot f ^ {2} (r ^ { 4})\cdot f^{3}(r^{3}s)\cdot f^{4}(s)=e}$

Aby szybko ocenić tę permutację, użyj tego

${\ Displaystyle f ^ {4} (s) = f ^ {3} (r ^ {3}s)=f^{2}(r^{4})=f(r^{2})=r^{2}s}$

aby to dostać

${\ Displaystyle r ^ {2} s \ cdot r ^ {2} s \ cdot r ^ {2} s \ cdot r ^ {2} s =e}$

To jest to samo odbicie, które jest iteracyjnie mnożone. Użyj tego, że odbicia są ich odwrotnością.

${\ Displaystyle (r ^ {2} s \ cdot r ^ {2} s) \ cdot (r ^ {2} }s\cdot r^{2}s)=e^{2}=e}$

W praktyce algorytm jest implementowany przy użyciu prostych tabel przeglądowych bez konieczności rozumienia, jak generować te tabele z podstawowej teorii grup i permutacji. Jest to bardziej właściwie uważane za rodzinę algorytmów, ponieważ działają również inne permutacje. Verhoeff zauważa, że ​​szczególna permutacja podana powyżej jest wyjątkowa, ponieważ ma właściwość wykrywania 95,3% błędów fonetycznych.

Mocną stroną algorytmu jest to, że wykrywa wszystkie błędy transliteracji i transpozycji, a dodatkowo większość błędów bliźniaczych, podwójnych przeskoków, przeskoków transpozycji i błędów fonetycznych.

Główną słabością algorytmu Verhoeffa jest jego złożoność. Wymaganych obliczeń nie można łatwo wyrazić w postaci wzoru, powiedzmy. ${\ Displaystyle {\ Displaystyle \ mathbb {Z} / 10 \ mathbb {Z}}$ } Tabele przeglądowe są wymagane do łatwego obliczania. Podobnym kodem jest algorytm Damma , który ma podobne cechy.

Algorytm oparty na tabelach

Algorytm Verhoeffa można zaimplementować za pomocą trzech tablic: tabliczki mnożenia d , tablicy odwrotnej inv i tablicy permutacji p .

${\ Displaystyle d (j, k)}$		k
		0	1	2	3	4	5	6	7	8	9
J	0	0	1	2	3	4	5	6	7	8	9
	1	1	2	3	4	0	6	7	8	9	5
	2	2	3	4	0	1	7	8	9	5	6
	3	3	4	0	1	2	8	9	5	6	7
	4	4	0	1	2	3	9	5	6	7	8
	5	5	9	8	7	6	0	4	3	2	1
	6	6	5	9	8	7	1	0	4	3	2
	7	7	6	5	9	8	2	1	0	4	3
	8	8	7	6	5	9	3	2	1	0	4
	9	9	8	7	6	5	4	3	2	1	0

J	${\ Displaystyle inv (j)}$
0	0
1	4
2	3
3	2
4	1
5	5
6	6
7	7
8	8
9	9

${\ Displaystyle p (pos, numer)}$		liczba
		0	1	2	3	4	5	6	7	8	9
pozycja (mod 8)	0	0	1	2	3	4	5	6	7	8	9
	1	1	5	7	6	2	8	3	0	9	4
	2	5	8	0	3	7	9	6	1	4	2
	3	8	9	1	6	0	4	3	5	2	7
	4	9	4	5	3	1	2	6	8	7	0
	5	4	2	8	6	5	7	3	9	0	1
	6	2	7	9	3	8	0	6	4	1	5
	7	7	0	4	6	9	1	3	2	5	8

Pierwsza tabela, d , jest oparta na mnożeniu w grupie dwuściennej _D5 . i jest po prostu tabelą Cayleya grupy. Zauważ, że ta grupa nie jest przemienna , to znaczy dla niektórych wartości j i k , d ( j , k ) ≠ d ( k , j ).

Tablica odwrotna inv reprezentuje multiplikatywną odwrotność cyfry, czyli wartość, która spełnia d ( j , inv ( j )) = 0.

Tabela permutacji p stosuje permutację do każdej cyfry na podstawie jej pozycji w liczbie. W rzeczywistości jest to pojedyncza permutacja (1 5 8 9 4 2 7 0)(3 6) stosowana iteracyjnie; tj. p ( ja + jot , n ) = p ( ja , p ( jot , n )).

Obliczenie sumy kontrolnej Verhoeffa odbywa się w następujący sposób:

1. ₀ Utwórz tablicę n z poszczególnych cyfr liczby, pobranych od prawej do lewej (cyfra najbardziej po prawej to n itd.).
2. Zainicjuj sumę kontrolną c na zero.
3. Dla każdego indeksu i tablicy n, zaczynając od zera, zamień $, p (i {\ bmod {8}}, n_ { ja}))}$ ( ja .

Oryginalny numer jest ważny wtedy i tylko wtedy, gdy ${\ displaystyle c = 0}$ .

0 Aby wygenerować cyfrę kontrolną, dołącz a , wykonaj obliczenia: poprawna cyfra kontrolna to ${\ displaystyle inv (c)}$ .

Przykłady

Wygeneruj cyfrę kontrolną dla 236 :

I	n ja	p ( ja, n ja )	C
0	0	0	0
1	6	3	3
2	3	3	1
3	2	1	2

c wynosi 2, więc cyfrą kontrolną jest inv (2), czyli 3.

Zatwierdź cyfrę kontrolną 2363 :

I	n ja	p ( ja, n ja )	C
0	3	3	3
1	6	3	1
2	3	3	4
3	2	1	0

c wynosi zero, więc sprawdzenie jest poprawne.

Linki zewnętrzne

• Szczegółowy opis algorytmu Verhoeffa