Algoritmul Damm
Algoritmul Damm este un algoritm pentru calcularea unei cifre de verificare pentru detectarea erorilor . A fost propus pentru prima dată în 2004 de M. Damm.
Cum funcționează
Damm a propus să utilizeze o operație binară cunoscută sub numele de cvasigrupul Damm [1] .
| d(j,k) | k | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| j | 0 | unu | 2 | 3 | patru | 5 | 6 | 7 | opt | 9 | |
| 0 | 0 | 3 | unu | 7 | 5 | 9 | opt | 6 | patru | 2 | |
| unu | 7 | 0 | 9 | 2 | unu | 5 | patru | opt | 6 | 3 | |
| 2 | patru | 2 | 0 | 6 | opt | 7 | unu | 3 | 5 | 9 | |
| 3 | unu | 7 | 5 | 0 | 9 | opt | 3 | patru | 2 | 6 | |
| patru | 6 | unu | 2 | 3 | 0 | patru | 5 | 9 | 7 | opt | |
| 5 | 3 | 6 | 7 | patru | 2 | 0 | 9 | 5 | opt | unu | |
| 6 | 5 | opt | 6 | 9 | 7 | 2 | 0 | unu | 3 | patru | |
| 7 | opt | 9 | patru | 5 | 3 | 6 | 2 | 0 | unu | 7 | |
| opt | 9 | patru | 3 | opt | 6 | unu | 7 | 2 | 0 | 5 | |
| 9 | 2 | 5 | opt | unu | patru | 3 | 6 | 7 | 9 | 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 Damm 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, puteți obține un algoritm de calcul al cifrei de verificare care este mai bun ( în medie pentru cele mai frecvente erori) decât adunarea obișnuită modulo 10.
Algoritmul lui Damm vă permite să detectați două erori comune la introducerea numerelor: înlocuirea unei cifre cu alta și permutarea a două cifre adiacente.
Exemplu
Să presupunem că secvența de cifre 572 este transmisă .
Calcul cifrei de verificare
| cifră prelucrată → index de coloană | 5 | 7 | 2 |
|---|---|---|---|
| cifră intermediară veche → index de rând | 0 | 9 | 7 |
| introducere în tabel → nouă cifră intermediară | 9 | 7 | patru |
Figura intermediară finală 4 . Este o sumă de control. Adăugând-o la număr, obținem 5724 .
Verificarea unui număr cu o cifră de verificare
| cifră prelucrată → index de coloană | 5 | 7 | 2 | patru |
|---|---|---|---|---|
| cifră intermediară veche → index de rând | 0 | 9 | 7 | patru |
| introducere în tabel → nouă cifră intermediară | 9 | 7 | patru | 0 |
Cifra intermediară rezultată este 0 , deci secvența de cifre transmisă este validă .
| Funcții hash | |
|---|---|
| scop general | |
| Criptografic | |
| Funcții de generare a cheilor | |
| Numărul de verificare ( comparație ) | |
| Hashes |
|
Note
- ↑ Dmitri Maksimov. Coduri care recunosc o eroare // Știință și viață . - 2018. - Nr. 1 . - S. 90-95 .