Dammův algoritmus - Damm algorithm - Wikipedia

v detekce chyb, Dammův algoritmus je kontrolní číslice algoritmus který detekuje vše jednociferné chyby a všechno sousední chyby transpozice. Prezentoval ji H. Michael Damm v roce 2004.[1]

Silné a slabé stránky

Silné stránky

Dammův algoritmus je podobný Verhoeffův algoritmus. Také to zjistí Všechno výskyty dvou nejčastěji se vyskytujících typů chyby přepisu, jmenovitě změna jedné jediné číslice a transpozice dvou sousedních číslic (včetně transpozice koncové kontrolní číslice a předchozí číslice).[1][2] Ale Dammův algoritmus má tu výhodu, že se obejde bez speciálně konstruované obměny a jeho pozice specifická pravomoci je neodmyslitelnou součástí Verhoeffovo schéma. Dále tabulka inverze lze upustit za předpokladu, že všechny hlavní diagonální položky tabulky operací jsou nulové.

Dammův algoritmus netrpí překročením počtu 10 možných hodnot, což vede k potřebě použít neciferný znak (jako X v 10místné ISBN kontrolní číslice systém).

Příprava úvodních nul nemá vliv na kontrolní číslici.[1]

Existují zcela anti-symetrické kvazoskupiny, které detekují všechny fonetické chyby spojené s anglickým jazykem (13 ↔ 30, 14 ↔ 40, ..., 19 ↔ 90). Tabulka použitá v ilustrativním příkladu je založena na instanci takového druhu.

Slabé stránky

Jelikož předběžné nuly neovlivňují kontrolní číslici,[1] kódy s proměnnou délkou by se neměly ověřovat společně, protože např. 0, 01 a 001 atd. vytvářejí stejnou kontrolní číslici. Všechny algoritmy kontrolního součtu jsou však vůči tomu zranitelné.

Design

Jeho podstatnou součástí je a kvazigroup z objednat 10 (tj. Mít a 10 × 10 Latinský čtverec jako tělo jeho operační stůl ) se zvláštním rysem bytí slabě zcela anti-symetrický.[3][4][i][ii][iii] Damm odhalil několik metod, jak vytvořit zcela anti-symetrické kvazoskupiny řádu 10, a uvedl několik příkladů ve své disertační práci.[3][i] Tím Damm také vyvrátil starou domněnku, že neexistují naprosto anti-symetrické kvazoskupiny řádu 10.[5]

Kvazigroup (Q, ∗) se nazývá naprosto anti-symetrický, pokud pro všechny C, X, y ∈ Q, platí následující důsledky:[4]

  1. (C ∗ X) ∗ y = (C ∗ y) ∗ X ⇒ X = y
  2. X ∗ y = y ∗ X ⇒ X = y,

a nazývá se to slabý, zcela anti-symetrický, pokud platí pouze první implikace. Damm dokázal, že existuje naprosto anti-symetrická kvazskupina řádu n je ekvivalentní existenci slabé zcela anti-symetrické kvazskupiny řádu n. Pro Dammův algoritmus s kontrolní rovnicí(...((0 ∗ Xm) ∗ Xm−1) ∗ ...) ∗ X0 = 0slabá zcela anti-symetrická kvazskupina s touto vlastností X ∗ X = 0je potřeba. Takovou kvazoskupinu lze zkonstruovat z jakékoli zcela anti-symetrické kvazoskupiny přeskupením sloupců takovým způsobem, aby všechny nuly ležely na úhlopříčce. A na druhou stranu z jakékoli slabé zcela anti-symetrické kvazoskupiny lze vytvořit zcela anti-symetrickou kvazoskupinu přemístěním sloupců tak, aby byla první řada v přirozeném pořadí.[3]

Algoritmus

Platnost číselné sekvence obsahující kontrolní číslici je definována přes kvazigroup. Tabulka kvazoskupiny připravená k použití může být převzata z Dammovy disertační práce (strany 98, 106, 111).[3] Je užitečné, když je každá hlavní položka úhlopříčky 0,[1] protože to zjednodušuje výpočet kontrolní číslice.

Ověření čísla podle přiložené kontrolní číslice

  1. Nastavte prozatímní číslici a inicializujte ji na 0.
  2. Zpracujte číslici po číslici: Použijte číslici čísla jako index sloupce a prozatímní číslici jako index řádků, vezměte záznam v tabulce a nahraďte jej prozatímní číslicí.
  3. Číslo je platné tehdy a jen tehdy, má-li výsledná přechodná číslice hodnotu 0.[1]

Výpočet kontrolní číslice

Předpoklad: Hlavní diagonální položky tabulky jsou 0.

  1. Nastavte prozatímní číslici a inicializujte ji na 0.
  2. Zpracujte číslici po číslici: Použijte číslici čísla jako index sloupce a prozatímní číslici jako index řádků, vezměte záznam v tabulce a nahraďte jej prozatímní číslicí.
  3. Výsledná průběžná číslice dává kontrolní číslici a bude připojena jako koncová číslice k číslu.[1]

Příklad

Bude použita následující tabulka operací.[1] Lze jej získat ze zcela anti-symetrické kvazigroup X ∗ y v Dammově disertační práci strana 111[3] přeskupením řádků a změnou položek s permutací φ = (1 2 9 5 4 8 6 7 3) a definování X ⋅ y = φ−1(φ(X) ∗ y).

⋅0123456789
00317598642
17092154863
24206871359
31750983426
46123045978
53674209581
65869720134
78945362017
89438617205
92581436790

Předpokládejme, že zvolíme číslo (číslice) 572.

Výpočet kontrolní číslice

číslice ke zpracování → index sloupce572
starý průběžná číslice → index řádků097
položka tabulky → nová průběžná číslice974

Výsledná průběžná číslice je 4. Toto je vypočítaná kontrolní číslice. Připojíme to k číslu a získáme 5724.

Ověření čísla podle přiložené kontrolní číslice

číslice ke zpracování → index sloupce5724
starý průběžná číslice → index řádků0974
položka tabulky → nová průběžná číslice9740

Výsledná průběžná číslice je 0, proto je číslo platný.

Grafické znázornění

Toto je výše uvedený příklad zobrazující podrobnosti algoritmu generujícího kontrolní číslici (zlomená modrá šipka) a ověřující číslo 572 s kontrolní číslicí.

Zkontrolujte číslici TA quasigroup dhmd111rr ilustrace eg5724.svg

Reference

  1. ^ A b C d E F G h Fenwick, Peter (2014). "Kontrolní součty a kontrola chyb". Úvod do reprezentace počítačových dat. Vydavatelé Bentham Science. str.191–218. doi:10.2174/9781608058822114010013. ISBN  978-1-60805-883-9.
  2. ^ Typy běžných chyb a jejich frekvence viz Salomon, David (2005). Kódování pro datovou a počítačovou komunikaci. Springer Science + Business Media, Inc. str. 36. ISBN  978-0387-21245-6.
  3. ^ A b C d E Damm, H. Michael (2004). Totální anti-symetrický kříž Quasigruppen (PDF) (Dr. rer. Nat.) (V němčině). Philipps-Universität Marburg. urn: nbn: de: hebis: 04-z2004-05162.
  4. ^ A b Damm, H. Michael (2007). "Naprosto antisymetrické kvazoskupiny pro všechny objednávky." n≠2,6". Diskrétní matematika. 307 (6): 715–729. doi:10.1016 / j.disc.2006.05.033. ISSN  0012-365X.
  5. ^ Damm, H. Michael (2003). „O existenci zcela anti-symetrických kvazoskupin řádu 4k + 2". Výpočetní. 70 (4): 349–357. doi:10.1007 / s00607-003-0017-3. ISSN  0010-485X.
  1. ^ A b Beliavscaia Galina; Izbaş Vladimir; Şcerbacov Victor (2003). "Zkontrolovat znakové systémy přes kvazoskupiny a smyčky" (PDF). Kvazigroup a související systémy. 10 (1 ): 1–28. ISSN  1561-2848. Viz strana 23.
  2. ^ Chen Jiannan (2009). "NP-úplnost dokončení částečných anti-symetrických latinských čtverců" (PDF). Sborník příspěvků z mezinárodního semináře 2009 o informační bezpečnosti a aplikacích (IWISA 2009). Nakladatelství Academy. str.322–324. ISBN  978-952-5726-06-0. Viz strana 324.
  3. ^ Mileva, A .; Dimitrova, V. (2009). "Kvazigrupy vytvořené z kompletních mapování skupiny (Z2n,⊕)" (PDF). Příspěvky, Sec. Matematika. Tech. Sci., MANU / MASA. XXX (1–2): 75–93. ISSN  0351-3246. Viz strana 78.

externí odkazy