Damm-Algorithmus - Damm algorithm
Bei Fehlererkennung , die Damm - Algorithmus ist eine Prüfziffer Algorithmus , der alle erkennt einziffrige Fehler und alle Fehler benachbarten Umsetzung . Es wurde von H. Michael Damm im Jahr 2004 vorgestellt.
Stärken und Schwächen
Stärken
Der Damm-Algorithmus ähnelt dem Verhoeff-Algorithmus . Es erkennt auch alle Vorkommen der beiden am häufigsten auftretenden Arten von Transkriptionsfehlern , nämlich das Ändern einer einzelnen Ziffer und das Transponieren von zwei benachbarten Ziffern (einschließlich der Transposition der nachfolgenden Prüfziffer und der vorhergehenden Ziffer). Der Damm-Algorithmus hat jedoch den Vorteil, dass er ohne die speziell konstruierten Permutationen und seine positionsspezifischen Kräfte auskommt, die dem Verhoeff-Schema inhärent sind . Darüber hinaus kann auf eine Inverstabelle verzichtet werden, sofern alle diagonalen Haupteinträge der Operationstabelle Null sind.
Der Damm-Algorithmus leidet nicht daran, die Anzahl von 10 möglichen Werten zu überschreiten, was dazu führt, dass ein nichtstelliges Zeichen verwendet werden muss (wie das X im 10-stelligen ISBN- Prüfziffernschema ).
Das Voranstellen führender Nullen wirkt sich nicht auf die Prüfziffer aus.
Es gibt völlig antisymmetrische Quasigruppen, die alle mit der englischen Sprache verbundenen phonetischen Fehler erkennen (13 ↔ 30, 14 ↔ 40, ..., 19 ↔ 90). Die im veranschaulichenden Beispiel verwendete Tabelle basiert auf einer solchen Instanz.
Schwächen
Da das Voranstellen führender Nullen die Prüfziffer nicht beeinflusst, sollten Codes mit variabler Länge nicht zusammen überprüft werden, da z. B. 0, 01 und 001 usw. dieselbe Prüfziffer erzeugen. Alle Prüfsummenalgorithmen sind hierfür jedoch anfällig.
Design
Sein wesentlicher Teil ist eine Quasigruppe der Ordnung 10 (dh mit einem lateinischen Quadrat von 10 × 10 als Hauptteil ihrer Operationstabelle ) mit dem besonderen Merkmal, dass sie schwach vollständig antisymmetrisch ist . Damm enthüllte verschiedene Methoden, um vollständig antisymmetrische Quasigruppen der Ordnung 10 zu bilden, und gab in seiner Dissertation einige Beispiele an. Damit widerlegte Damm auch eine alte Vermutung, dass es keine vollständig antisymmetrischen Quasigruppen der Ordnung 10 gibt.
Eine Quasigruppe ( Q , ∗) wird als vollständig antisymmetrisch bezeichnet, wenn für alle c , x , y ∈ Q die folgenden Implikationen gelten:
- ( c ∗ x ) ∗ y = ( c ∗ y ) ∗ x ⇒ x = y
- x ∗ y = y ∗ x ⇒ x = y ,
und es wird schwach total antisymmetrisch genannt, wenn nur die erste Implikation gilt. Damm hat bewiesen, dass die Existenz einer vollständig antisymmetrischen Quasigruppe der Ordnung n der Existenz einer schwachen vollständig antisymmetrischen Quasigruppe der Ordnung n entspricht . Für den Damm-Algorithmus mit der Prüfgleichung (... ((0 ∗ x m ) ∗ x m −1 ) ∗ ...) ∗ x 0 = 0 ist eine schwache, vollständig antisymmetrische Quasigruppe mit der Eigenschaft x ∗ x = 0 wird gebraucht. Eine solche Quasigruppe kann aus jeder vollständig antisymmetrischen Quasigruppe aufgebaut werden, indem die Spalten so neu angeordnet werden, dass alle Nullen auf der Diagonale liegen. Andererseits kann aus jeder schwachen, vollständig antisymmetrischen Quasigruppe eine vollständig antisymmetrische Quasigruppe aufgebaut werden, indem die Spalten so neu angeordnet werden, dass die erste Zeile in natürlicher Reihenfolge ist.
Algorithmus
Die Gültigkeit einer Ziffernfolge, die eine Prüfziffer enthält, wird über eine Quasigruppe definiert. Eine gebrauchsfertige Quasigruppentabelle kann Damms Dissertation entnommen werden (Seiten 98, 106, 111). Es ist nützlich, wenn jeder diagonale Haupteintrag 0 ist, da dies die Berechnung der Prüfziffer vereinfacht.
Validierung einer Nummer anhand der enthaltenen Prüfziffer
- Richten Sie eine Zwischenziffer ein und initialisieren Sie sie auf 0.
- Ziffer für Ziffer verarbeiten: Verwenden Sie die Ziffer der Zahl als Spaltenindex und die Zwischenziffer als Zeilenindex, nehmen Sie den Tabelleneintrag und ersetzen Sie die Zwischenziffer durch diese.
- Die Nummer ist nur dann gültig, wenn die resultierende Zwischenziffer den Wert 0 hat.
Berechnung der Prüfziffer
Voraussetzung: Die diagonalen Haupteinträge der Tabelle sind 0.
- Richten Sie eine Zwischenziffer ein und initialisieren Sie sie auf 0.
- Ziffer für Ziffer verarbeiten: Verwenden Sie die Ziffer der Zahl als Spaltenindex und die Zwischenziffer als Zeilenindex, nehmen Sie den Tabelleneintrag und ersetzen Sie die Zwischenziffer durch diese.
- Die resultierende Zwischenziffer gibt die Prüfziffer an und wird als nachfolgende Ziffer an die Nummer angehängt.
Beispiel
Die folgende Operationstabelle wird verwendet. Es kann aus der vollständig antisymmetrischen Quasigruppe x ∗ y in Damms Dissertation Seite 111 erhalten werden, indem die Zeilen neu angeordnet und die Einträge mit der Permutation φ = (1 2 9 5 4 8 6 7 3) geändert und x ⋅ y = definiert werden φ −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 |
Angenommen, wir wählen die Nummer (Ziffernfolge) 572 .
Berechnung der Prüfziffer
| zu verarbeitende Ziffer → Spaltenindex | 5 | 7 | 2 |
|---|---|---|---|
| alte Zwischenziffer → Zeilenindex | 0 | 9 | 7 |
| Tabelleneintrag → neue Zwischenziffer | 9 | 7 | 4 |
Die resultierende Zwischenziffer ist 4 . Dies ist die berechnete Prüfziffer. Wir hängen es an die Nummer an und erhalten 5724 .
Validierung einer Nummer anhand der enthaltenen Prüfziffer
| zu verarbeitende Ziffer → Spaltenindex | 5 | 7 | 2 | 4 |
|---|---|---|---|---|
| alte Zwischenziffer → Zeilenindex | 0 | 9 | 7 | 4 |
| Tabelleneintrag → neue Zwischenziffer | 9 | 7 | 4 | 0 |
Die resultierende Zwischenziffer ist 0 , daher ist die Nummer gültig .
Grafische Darstellung
Dies ist das obige Beispiel, das die Details des Algorithmus zeigt, der die Prüfziffer erzeugt (unterbrochener blauer Pfeil) und die Nummer 572 mit der Prüfziffer überprüft.
