Algoritmul lui Verhouff

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 15 aprilie 2020; verificarea necesită 1 editare .

Algoritmul Verhoeff este un algoritm de calcul al cifrelor de verificare  pentru detectarea erorilor la introducerea manuală a secvențelor digitale lungi. Publicat pentru prima dată în 1969 de matematicianul olandez Jakob Verhouff . Algoritmul face posibilă detectarea aceluiași număr de erori ca și algoritmul Luhn similar , dar erorile care sunt detectate numai de primul sunt de obicei făcute de oameni mai des decât erorile care sunt detectate doar de al doilea.

Cum funcționează

În loc să însumeze produsele cifrelor după greutăți , Verhouff a propus utilizarea unei operații de grup cunoscută sub numele de grupul diedric D 5 [1] .

d(j,k) k
j 0 unu 2 3 patru 5 6 7 opt 9
0 0 unu 2 3 patru 5 6 7 opt 9
unu unu 2 3 patru 0 6 7 opt 9 5
2 2 3 patru 0 unu 7 opt 9 5 6
3 3 patru 0 unu 2 opt 9 5 6 7
patru patru 0 unu 2 3 9 5 6 7 opt
5 5 9 opt 7 6 0 patru 3 2 unu
6 6 5 9 opt 7 unu 0 patru 3 2
7 7 6 5 9 opt 2 unu 0 patru 3
opt opt 7 6 5 9 3 2 unu 0 patru
9 9 opt 7 6 5 patru 3 2 unu 0

Rezultatul operației d(j, k) este cel mai ușor de determinat din tabel, unde este situat la intersecția j-lea rând și k-a coloană a tabelului. Operația aleasă de Verhouff nu este comutativă , adică condiția nu este îndeplinită pentru ea pentru toți și .

Efectuând secvențial operația d(j, k), unde j este rezultatul iterației anterioare (0 pentru prima iterație) și k este următoarea cifră a numărului, se poate obține un algoritm de calcul al cifrei de verificare care este mai bun decât o adunare obișnuită modulo 10. Într-adevăr, în ciuda faptului că ambii algoritmi detectează erori unice, algoritmul lui Verhouff vă permite să determinați 60 din 90 de erori posibile de permutare a cifrelor adiacente, spre deosebire de adăugarea modulo 10.

Cu toate acestea, Verhouff a mers mai departe. El a sugerat să folosiți ca al doilea parametru d(j, k) nu cifra în sine, ci rezultatul unei alte operații - p(x, y), unde y este o cifră, x este poziția acestei cifre modulo 8. Rezultatul a acestei operațiuni este, de asemenea, convenabil să se determine conform tabelului.

p(x, y) y
X 0 unu 2 3 patru 5 6 7 opt 9
0 0 unu 2 3 patru 5 6 7 opt 9
unu unu 5 7 6 2 opt 3 0 9 patru
2 5 opt 0 3 7 9 6 unu patru 2
3 opt 9 unu 6 0 patru 3 5 2 7
patru 9 patru 5 3 unu 2 6 opt 7 0
5 patru 2 opt 6 5 7 3 9 0 unu
6 2 7 9 3 opt 0 6 patru unu 5
7 7 0 patru 6 9 unu 3 2 5 opt

Algoritm de verificare

  1. Luați valoarea inițială c = 0.
  2. Pentru fiecare cifră a numărului verificat, începând cu cea mai puțin semnificativă (în dreapta), se calculează c = d(c, p(i, n i )), unde i este numărul ordinal al cifrei și n i  este valoarea cifrei.
  3. Dacă c = 0, cifra de verificare este corectă.

Algoritm de calcul

  1. Luați valoarea inițială c = 0.
  2. Pentru fiecare cifră a numărului inițial, începând cu cea mai puțin semnificativă (în dreapta), se calculează c = d(c, p(i + 1, n i )), unde i este numărul ordinal al cifrei și n i  este valoarea cifrei.
  3. Adăugați la dreapta numărului inițial rezultatul operației inv (c), determinat de un alt tabel:
j 0 unu 2 3 patru 5 6 7 opt 9
inv(j) 0 patru 3 2 unu 5 6 7 opt 9

Note

  1. ↑ Dmitri Maksimov. Coduri care recunosc o eroare  // Știință și viață . - 2018. - Nr. 1 . - S. 90-95 .

Link -uri

 Funcții hash
scop general
Criptografic
Funcții de generare a cheilor
Numărul de verificare ( comparație )
Hashes