Jävla algoritm
Damm -algoritmen är en algoritm för att beräkna en kontrollsiffra för feldetektering . Det föreslogs första gången 2004 av M. Damm.
Hur det fungerar
Damm föreslog att använda en binär operation känd som Damm-kvasigruppen [1] .
| d(j, k) | k | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| j | 0 | ett | 2 | 3 | fyra | 5 | 6 | 7 | åtta | 9 | |
| 0 | 0 | 3 | ett | 7 | 5 | 9 | åtta | 6 | fyra | 2 | |
| ett | 7 | 0 | 9 | 2 | ett | 5 | fyra | åtta | 6 | 3 | |
| 2 | fyra | 2 | 0 | 6 | åtta | 7 | ett | 3 | 5 | 9 | |
| 3 | ett | 7 | 5 | 0 | 9 | åtta | 3 | fyra | 2 | 6 | |
| fyra | 6 | ett | 2 | 3 | 0 | fyra | 5 | 9 | 7 | åtta | |
| 5 | 3 | 6 | 7 | fyra | 2 | 0 | 9 | 5 | åtta | ett | |
| 6 | 5 | åtta | 6 | 9 | 7 | 2 | 0 | ett | 3 | fyra | |
| 7 | åtta | 9 | fyra | 5 | 3 | 6 | 2 | 0 | ett | 7 | |
| åtta | 9 | fyra | 3 | åtta | 6 | ett | 7 | 2 | 0 | 5 | |
| 9 | 2 | 5 | åtta | ett | fyra | 3 | 6 | 7 | 9 | 0 | |
Resultatet av operationen d(j, k) är lättast att bestämma från tabellen, där det ligger i skärningspunkten mellan den j:te raden och den k:te kolumnen i tabellen. Operationen som valts av Damm är inte kommutativ , det vill säga att villkoret inte är uppfyllt för det för alla och .
Genom att sekventiellt utföra operationen d(j, k), där j är resultatet av föregående iteration (0 för den första iterationen), och k är nästa siffra i numret, kan du få en kontrollsiffraberäkningsalgoritm som är bättre ( i genomsnitt för de vanligaste felen) än vanlig additionsmodulo 10.
Damms algoritm låter dig upptäcka två vanliga fel när du anger siffror: att ersätta en siffra med en annan och att permutera två intilliggande siffror.
Exempel
Låt oss anta att siffersekvensen 572 sänds .
Kontrollera sifferberäkning
| bearbetad siffra → kolumnindex | 5 | 7 | 2 |
|---|---|---|---|
| gammal mellansiffra → radindex | 0 | 9 | 7 |
| tabellinmatning → ny mellansiffra | 9 | 7 | fyra |
Slutlig mellanfigur 4 . Det är en kontrollsumma. Lägger vi det till numret får vi 5724 .
Kontrollera ett nummer mot en kontrollsiffra
| bearbetad siffra → kolumnindex | 5 | 7 | 2 | fyra |
|---|---|---|---|---|
| gammal mellansiffra → radindex | 0 | 9 | 7 | fyra |
| tabellinmatning → ny mellansiffra | 9 | 7 | fyra | 0 |
Den resulterande mellansiffran är 0 , så den överförda siffersekvensen är giltig .
| Hash-funktioner | |
|---|---|
| generell mening | |
| Kryptografisk | |
| Nyckelgenereringsfunktioner | |
| Kontrollnummer ( jämförelse ) | |
| Hashes |
|
Anteckningar
- ↑ Dmitrij Maksimov. Koder som känner igen ett fel // Science and life . - 2018. - Nr 1 . - S. 90-95 .