Sakra algoritmus
Algoritmus Damm je algoritmus pro výpočet kontrolní číslice pro detekci chyb . Poprvé byl navržen v roce 2004 M. Dammem.
Jak to funguje
Damm navrhl použít binární operaci známou jako Dammova kvazigrupa [1] .
| d(j, k) | k | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| j | 0 | jeden | 2 | 3 | čtyři | 5 | 6 | 7 | osm | 9 | |
| 0 | 0 | 3 | jeden | 7 | 5 | 9 | osm | 6 | čtyři | 2 | |
| jeden | 7 | 0 | 9 | 2 | jeden | 5 | čtyři | osm | 6 | 3 | |
| 2 | čtyři | 2 | 0 | 6 | osm | 7 | jeden | 3 | 5 | 9 | |
| 3 | jeden | 7 | 5 | 0 | 9 | osm | 3 | čtyři | 2 | 6 | |
| čtyři | 6 | jeden | 2 | 3 | 0 | čtyři | 5 | 9 | 7 | osm | |
| 5 | 3 | 6 | 7 | čtyři | 2 | 0 | 9 | 5 | osm | jeden | |
| 6 | 5 | osm | 6 | 9 | 7 | 2 | 0 | jeden | 3 | čtyři | |
| 7 | osm | 9 | čtyři | 5 | 3 | 6 | 2 | 0 | jeden | 7 | |
| osm | 9 | čtyři | 3 | osm | 6 | jeden | 7 | 2 | 0 | 5 | |
| 9 | 2 | 5 | osm | jeden | čtyři | 3 | 6 | 7 | 9 | 0 | |
Výsledek operace d(j, k) se nejsnáze určí z tabulky, kde se nachází na průsečíku j-tého řádku a k-tého sloupce tabulky. Operace zvolená Dammem není komutativní , to znamená, že podmínka pro ni není splněna pro všechny a .
Postupným prováděním operace d(j, k), kde j je výsledek předchozí iterace (0 pro první iteraci) a k je další číslice čísla, můžete získat algoritmus výpočtu kontrolní číslice, který je lepší ( v průměru pro nejčastější chyby) než běžné sčítání modulo 10.
Dammův algoritmus umožňuje odhalit dvě běžné chyby při zadávání čísel: nahrazení jedné číslice jinou a permutaci dvou sousedních číslic.
Příklad
Předpokládejme, že se vysílá sekvence číslic 572 .
Výpočet kontrolní číslice
| zpracovaná číslice → index sloupce | 5 | 7 | 2 |
|---|---|---|---|
| stará mezičíslice → řádkový index | 0 | 9 | 7 |
| zadání tabulky → nová mezičíslí | 9 | 7 | čtyři |
Konečný meziobrázek 4 . Je to kontrolní součet. Když to přičteme k číslu, dostaneme 5724 .
Kontrola čísla podle kontrolní číslice
| zpracovaná číslice → index sloupce | 5 | 7 | 2 | čtyři |
|---|---|---|---|---|
| stará mezičíslice → řádkový index | 0 | 9 | 7 | čtyři |
| zadání tabulky → nová mezičíslí | 9 | 7 | čtyři | 0 |
Výsledná mezilehlá číslice je 0 , takže přenášená posloupnost číslic je platná .
| Hashovací funkce | |
|---|---|
| obecný účel | |
| Kryptografický | |
| Funkce generování klíčů | |
| Kontrolní číslo ( srovnání ) | |
| Hashe |
|
Poznámky
- ↑ Dmitrij Maksimov. Kódy, které rozpoznávají chybu // Věda a život . - 2018. - č. 1 . - S. 90-95 .