Prüfziffern

[geringfügig geändertes Referat von Tanja Hoertling, Berufsakademie Mosbach]

Prüfziffern sind unscheinbar und allgegenwertig: Banken setzen sie ein, um falsch erfaßte Kontonummern zu entdecken, der Buchhandel erkennt mit ihrer Hilfe falsche ISBNs, und schließlich weiß der Laserscanner an der Kasse im Supermarkt dank einer Prüfziffer, ob er den Strichcode der Artikelnummer richtig erkannt hat.

Um die Qualität der Fehlererkennung verschiedener Prüfziffernverfahren bewerten zu können, kann auf eine Statistik von Verhoeff zu Fehlertypen und Fehlerhäufigkeiten zurückgegriffen werden. Diese Fehlerstatistik beruht allerdings auf einer Untersuchung sechsstelliger Zahlen Ende der sechziger Jahre. Deshalb sind die darin genannten Fehlerhäufigkeiten nur als Anhaltswerte zu sehen, denn mit zunehmender Stellenzahl der verwendeten Zahlen nimmt die Häufigkeit von Fehlern zu.

Eine besondere Fehlerklasse bildet das Einfügen oder Weglassen von Ziffern. Die Häufigkeit derartiger Fehler liegt immerhin zwischen 10% und 20 %.

Fehler wie z. B. die Verwechslungen von Kunden und Telefonnummern oder eine irrtümlich eingegebene Kontonummer, die jedoch zum falschen Kunden gehört, können von den im folgenden beschriebenen Verfahren nicht erkannt werden.

Prüfziffernverfahren auf Modulo-Basis

Modulo 10 - die erste

Das einfachste Prüfverfahren besteht darin, alle Ziffern zu addieren (also die Quersumme zu bilden) und den 10er Rest als Prüfziffer anzuhängen. Mit dieser Methode können sämtliche Einzelfehler erkannt werden; schließlich wirkt jede einzelne fehlerhafte Ziffer eine Änderung der Prüfziffer. Aber diese einfache Prüfsumme ist nicht von der Reihenfolge der Ziffern abhängig, deshalb werden keine Vertauschungen erkannt.

Beispiel: Zahl: 4711

Gewichtheben

Eine Erweiterung des ersten Verfahrens besteht darin, die Prüfziffer nicht aus einer einfachen, sondern einer gewichteten Summe der anderen Ziffern zu berechen. Die Gewicht (ganzzahlig) sind frei wählbar; Randbedingung: möglichst gute Fehlererkennung.

Beispiel: Alle Ziffern sind vor der Addition abwechselnd mit 1 und 2 zu multiplizieren. Weil sich nun bei der Vertauschung zweier Ziffern die Prüfziffer ändert, lassen sich damit sämtliche Nachbarvertauschungen erkennen.

Zahl: 391415 ® Prüfziffer 1 (1 * 3 + 2 * 9 + 1 * 1 + 2 * 4 + 1 * 1 + 2 * 5 = 41 ; 41 : 10 = 4 Rest 1)

Zahl inklusive Prüfziffer: 3914151

bei Eingabe von 3941151 ® fehlerhafte Eingabe (1 * 3 + 2 * 9 + 1 * 4 + 2 * 1 + 1 * 1 + 2 * 5 = 38 ; 38 : 10 = 3 Rest 8 ® 8 ¹ 3

Aber: Weil der Vorfaktor 2 ein Teiler von 10 ist, werden jedoch an allen geraden Positionen Vertauschungen von 0 mit 5, 1 mit 6 usw. nicht erkannt. ® es werden nicht mehr alle Einzelfehler erkannt; außerdem wird weiterhin keine einzige Sprungtransposition erkannt.

Es gibt kein Modulo-10-Verfahren, bei dem sämtliche Einzelfehler und Nachbarvertauschungen erkannt werden. Für die Einzelfehler müssen sämtliche Vorfaktoren teilerfremd zu 10 sein; dies gilt nur für die Gewichte 1, 3, 7 und 9. Um alle Nachbarvertauschungen zu erkennen, müssen aber die Differenzen benachbarter Gewichte teilerfremd zu 10 sein. Beides zusammen geht nicht.

11 = 10++

(Verwendung einer Primzahl als Modulus)

Die Bedingungen zum Erkennen sämtlicher Einzelfehler und Nachbarvertauschungen erledigen sich bei Modulo 11 praktisch von selbst; jede Zahl von 1 bis 10 ist natürlich teilerfremd zur Primzahl 11 und kann somit als Vorfaktor genommen werden. Zur Erkennung aller Nachbarvertauschungen müssen je zwei aufeinanderfolgende Gewichte voneinander verschieden sein.

Bekannte Modulo-11-Prüfung: ISBN (Internationale Standardbuchnummer)

Eine ISBN hat zehn Ziffern und setzt sich aus vier Abschnitten zusammen, von denen der erste das Land, der zweite den Verlag und der dritte das Buch kennzeichnet. Zuletzt folgt eine Prüfziffer.

Prüfzifferbestimmung: Jede Ziffer wird vor der Summenbildung mit ihrer Position mulipliziert. Da der Faktor 11 nicht als Multiplikator in Frage kommt, funktioniert das Verfahren nur für maximal zehnstellige Zahlen.

Bei der ISBN-Prüfung werden alle Einzelfehler und bis auf einen Teil der Zwillingsvertauschungen und phonetische Fehler auch alle Doppelfehler erkannt.

Beispiel: ISBN 0-517-11864-5

Eine Verbesserung des Modulo-11-Verfahrens wird erreicht durch: Gewichtung der Reihe nach mit den Potenzen von 2

® Erkennung sämtlicher Einzel- und Doppelfehler

Nachteil: es kann sich der Rest 10 ergeben, der sich nicht mehr als normale Ziffer speichern läßt:

Eine weitere Alternative zu den beiden oben genannten Möglichkeiten, ist das Arbeiten mit Diedergruppen, was auch eine sehr gute Fehlererkennung ermöglicht. Seriennummern bundesdeutscher Geldscheine werden auf diese Weise gesichert.

Ein weiteres Diederverfahren findet sich bei Verhoeff.

Die einfachste Diederprüfung besteht darin, alle Ziffern der Multiplikationstabelle für die Diedergruppe D₅ zu multiplizieren und die Prüfziffer ist so zu wählen, daß das Ergebnis Null ist.

® Erkennung aller Einzelfehler und ca. 2/3 der Nachbarvertauschungen

Erweiterung des Verfahrens: Transformation aller Ziffern vor der Multiplikation, um die Erkennung von Nachbarvertauschungen zu verbessern.

Beispiel: Prüfung der Seriennummer bundesdeutscher Geldscheine

Die Prüfziffer bei den elfstelligen Seriennummern bundesdeutscher Geldscheine beruht auf Permutationen.

Die Nummern an den Positionen 1, 2 und 10 enthalten Ziffern statt Buchstaben. Diese müssen vor der Prüfung nach folgendem Schema umgesetzt werden:

Zum anderen geht die Prüfziffer, die an letzter (elfter) Stelle steht, ohne Permutation in die Prüfbedingung ein.

Beispielsweise ergibt sich für den 20-DM-Schein mit der Seriennummer AD53396605 folgendes:

Seriennummer: AD53396605

codierte Zahl : 0153396605 (s. Schema)

t₁ (0), t₂ (1) ... t₁₀ (4), 5

=18436536175 (s. Permutationstabelle)

Dieder-Multiplikation: 1 * 8 * 4 * 3 * 6 * 5 * 3 * 6 * 1 * 7 * 5 = 0

Dieder-Verfahren nach Verhoeff

Verfahren unbekannt, da Verhoeff nur die Permutationstabelle angegeben hat, nicht jedoch den zugehörigen Algorithmus.

Quellen: c´t 4/97, S. 448 ff ; c´t 7/96, S. 265 ff