Algorytm Damma
W wykrywaniu błędów algorytm Damma jest algorytmem cyfry kontrolnej , który wykrywa wszystkie błędy jednocyfrowe i wszystkie sąsiadujące błędy transpozycji . Został przedstawiony przez H. Michaela Damma w 2004 roku.
Mocne i słabe strony
Silne strony
Algorytm Damma jest podobny do algorytmu Verhoeffa . Wykryje również wszystkie wystąpienia dwóch najczęściej występujących rodzajów błędów transkrypcyjnych , a mianowicie przeróbki pojedynczej cyfry lub transpozycji dwóch sąsiednich cyfr (w tym transpozycji końcowej cyfry kontrolnej i cyfry poprzedzającej). Algorytm Damma ma tę zaletę, że nie ma specjalnie konstruowanych permutacji i jego mocy specyficznych dla pozycji schematu Verhoeffa . Tablica odwrotności może być również zbędna, gdy wszystkie główne wpisy na przekątnej tabeli operacji są zerowe.
Algorytm Damm generuje tylko 10 możliwych wartości, unikając potrzeby stosowania znaku innego niż cyfra (takiego jak X w 10 -cyfrowym schemacie cyfr kontrolnych ISBN ).
Dodawanie wiodących zer na początku nie wpływa na cyfrę kontrolną (słabość kodów o zmiennej długości).
Istnieją całkowicie antysymetryczne quasigrupy, które wykrywają wszystkie błędy fonetyczne związane z językiem angielskim ( 13 ↔ 30 , 14 ↔ 40 , ..., 19 ↔ 90 ). Tabela użyta w ilustrującym przykładzie jest oparta na tego rodzaju egzemplarzu.
Słabości
W przypadku wszystkich algorytmów sum kontrolnych, w tym algorytmu Damma, dodawanie zer wiodących na początku nie wpływa na cyfrę kontrolną, więc 1, 01, 001 itd. Dają tę samą cyfrę kontrolną. W związku z tym kody o zmiennej długości nie powinny być weryfikowane razem.
Projekt
zasadniczą częścią jest quasigrupa rzędu 10 (tj. mająca kwadrat łaciński 10 × 10 jako korpus tabeli operacyjnej ) ze szczególną cechą bycia słabo całkowicie antysymetryczną . Damm ujawnił kilka metod tworzenia całkowicie antysymetrycznych kwazigrup rzędu 10 i podał kilka przykładów w swojej rozprawie doktorskiej. W ten sposób Damm obalił również stare przypuszczenie, że nie istnieją całkowicie antysymetryczne kwazigrupy rzędu 10.
Quasigrupę ( Q , ∗) nazywamy całkowicie antysymetryczną, jeśli dla wszystkich c , x , y ∈ Q zachodzą następujące implikacje:
- ( do ∗ x ) ∗ y = ( do ∗ y ) ∗ x ⇒ x = y
- x ∗ y = y ∗ x ⇒ x = y ,
i nazywa się to słabym całkowicie antysymetrycznym, jeśli zachodzi tylko pierwsza implikacja. Damm udowodnił, że istnienie całkowicie antysymetrycznej quasigrupy rzędu n jest równoznaczne z istnieniem słabej całkowicie antysymetrycznej quasigrupy rzędu n . Dla algorytmu Damma z równaniem kontrolnym 0 (...((0 ∗ x m ) ∗ x m −1 ) ∗ ...) ∗ x = 0 , słaba całkowicie antysymetryczna quasigrupa o właściwości x ∗ x = 0 jest potrzebne. Taką quasigrupę można zbudować z dowolnej całkowicie antysymetrycznej quasigrupy, przestawiając kolumny w taki sposób, aby wszystkie zera leżały na przekątnej. Z drugiej strony, z każdej słabej całkowicie antysymetrycznej quasigrupy można zbudować całkowicie antysymetryczną quasigrupę, przestawiając kolumny w taki sposób, aby pierwszy rząd był w naturalnym porządku.
Algorytm
Ważność sekwencji cyfr zawierającej cyfrę kontrolną jest zdefiniowana na quasigrupie. Gotową do użycia tabelę quasigrup można znaleźć w rozprawie Damma (str. 98, 106, 111). Jest to przydatne, jeśli każdy wpis głównej przekątnej wynosi 0, ponieważ upraszcza to obliczanie cyfry kontrolnej.
Walidacja numeru z dołączoną cyfrą kontrolną
- Ustaw cyfrę pośrednią i zainicjuj ją na 0.
- Przetwarzaj cyfrę po cyfrze: użyj cyfry numeru jako indeksu kolumny i cyfry pośredniej jako indeksu wiersza, weź wpis tabeli i zastąp go cyfrą pośrednią.
- Liczba jest ważna wtedy i tylko wtedy, gdy wynikowa cyfra pośrednia ma wartość 0.
Obliczanie cyfry kontrolnej
Warunek wstępny: Główne wpisy na przekątnej tabeli to 0.
- Ustaw cyfrę pośrednią i zainicjuj ją na 0.
- Przetwarzaj cyfrę po cyfrze: użyj cyfry numeru jako indeksu kolumny i cyfry pośredniej jako indeksu wiersza, weź wpis tabeli i zastąp go cyfrą pośrednią.
- Wynikowa cyfra pośrednia daje cyfrę kontrolną i zostanie dołączona jako cyfra końcowa do numeru.
Przykład
Zostanie użyta następująca tabela operacji. Można go otrzymać z całkowicie antysymetrycznej quasigrupy x ∗ y w rozprawie doktorskiej Damma, strona 111, przestawiając wiersze i zmieniając wpisy permutacją φ = (1 2 9 5 4 8 6 7 3) i definiując x ⋅ y = φ -1 ( φ ( x ) ∗ y ) .
| ⋅ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 3 | 1 | 7 | 5 | 9 | 8 | 6 | 4 | 2 |
| 1 | 7 | 0 | 9 | 2 | 1 | 5 | 4 | 8 | 6 | 3 |
| 2 | 4 | 2 | 0 | 6 | 8 | 7 | 1 | 3 | 5 | 9 |
| 3 | 1 | 7 | 5 | 0 | 9 | 8 | 3 | 4 | 2 | 6 |
| 4 | 6 | 1 | 2 | 3 | 0 | 4 | 5 | 9 | 7 | 8 |
| 5 | 3 | 6 | 7 | 4 | 2 | 0 | 9 | 5 | 8 | 1 |
| 6 | 5 | 8 | 6 | 9 | 7 | 2 | 0 | 1 | 3 | 4 |
| 7 | 8 | 9 | 4 | 5 | 3 | 6 | 2 | 0 | 1 | 7 |
| 8 | 9 | 4 | 3 | 8 | 6 | 1 | 7 | 2 | 0 | 5 |
| 9 | 2 | 5 | 8 | 1 | 4 | 3 | 6 | 7 | 9 | 0 |
Załóżmy, że wybieramy liczbę (sekwencję cyfr) 572 .
Obliczanie cyfry kontrolnej
| cyfra do przetworzenia → indeks kolumny | 5 | 7 | 2 |
|---|---|---|---|
| stara cyfra pośrednia → indeks wiersza | 0 | 9 | 7 |
| wpis w tabeli → nowa cyfra pośrednia | 9 | 7 | 4 |
Wynikowa cyfra pośrednia to 4 . To jest obliczona cyfra kontrolna. Dodajemy go do liczby i otrzymujemy 5724 .
Walidacja numeru z dołączoną cyfrą kontrolną
| cyfra do przetworzenia → indeks kolumny | 5 | 7 | 2 | 4 | |
|---|---|---|---|---|---|
| stara cyfra pośrednia → indeks wiersza | 0 | 9 | 7 | 4 | |
| wpis w tabeli → nowa cyfra pośrednia | 9 | 7 | 4 | 0 |
0 Wynikowa cyfra pośrednia to , stąd liczba jest prawidłowa .
Ilustracja graficzna
To jest powyższy przykład pokazujący szczegółowo algorytm generujący cyfrę kontrolną (niebieska przerywana strzałka) i weryfikujący liczbę 572 z cyfrą kontrolną.
