Prüfziffer

Eine Prüfziffer ist die einfachste Form einer Prüfsumme. Die Prüfziffer einer mehrstelligen Zahl wird nach einer festgelegten Rechenvorschrift aus den einzelnen Ziffern der zu prüfenden Zahl berechnet. Durch Berechnung und Vergleich der Prüfziffer werden Eingabefehler erkannt.

Wenn die Prüfziffer zehn Werte annehmen kann, tritt eine zufällige Übereinstimmung auch bei ungültigen Zahlen mit 10 % Wahrscheinlichkeit auf. Bei Verwendung von zwei Prüfziffern liegt diese Fehlerwahrscheinlichkeit nur noch bei 1 %.

Prüfziffern können bei manueller Eingabe über Tastatur und auch bei automatischer Datenerfassung, z. B. OCR oder Barcodelesern, verwendet werden. In einem Datenerfassungsgerät kann bei einer abweichenden Prüfziffer die Eingabe annulliert werden.

Beispiel: Identcode der Deutschen Post

Die Berechnung der Prüfziffer erfolgt beim Identcode der Deutschen Post im Modulo-11-Verfahren

Code        : 4  7  3  1  2  4  8  2
Gewichtung  : 8  6  4  2  3  5  9  7
Produkte    : 32 42 12 2  6  20 72 14
Summe       : 200
Modulo 11   : 200 / 11 = 18 Rest 2
Prüfziffer  : Differenz zu 11 = 11 - 2 = 9
Ausnahmen   :
Wenn Differenz zu 11 = 10: Prüfziffer wird zu 0
Wenn Differenz zu 11 = 11: Prüfziffer wird zu 5
Identcode der Deutschen Post / DHL

Berechnung der Prüfziffer:

Berechnung des Identcodes in einer Formel am Beispiel Excel:

Weitere Beispiele

Prüfzeichen-Code über einer Gruppe

Häufig ist eine Beschreibung durch einen Prüfzeichen-Code über einer Gruppe möglich, etwa über der Restklassen-Gruppe (ℤ11,+) bei der ISBN-10 bzw. (ℤ10,+) bei der EAN-13 oder über der Diedergruppe D5 bei den Nummern der DM-Banknoten der vierten/letzten Serie.

ISBN-10

Werden bei einer zehnstelligen ISBN-10 die zehn Ziffern der Reihe nach mit den Zahlen 1, 2,…, 10 multipliziert und diese Produkte addiert, so muss sich eine durch 11 teilbare Summe ergeben. Denn so ist das Prüfzeichen an der letzten Stelle festgelegt, für das sich allerdings auch die „Ziffer“ 10 ergeben kann, die durch ein X symbolisiert wird.

Geht man von den zehn Ziffern einer ISBN-10 zu ihren jeweiligen Restklassen modulo 11 über, so ergibt sich ein 10-Tupel

x=(x1,x2,…,x9,x10)

in ℤ1110=ℤ11×⋯×ℤ11 (kartesisches Produkt mit 10 Faktoren), das analog die Kontrollgleichung

1‾⋅x1+2‾⋅x2+⋯+9‾⋅x9+10‾⋅x10=0‾

in ℤ11 erfüllt. Beispielsweise entspricht die Nummer 3-528-16419-0 des Buches dem 10-Tupel

x=( 3‾,5‾,2‾,8‾,1‾,6‾,4‾,1‾,9‾,0‾)∈ℤ1110,

und dieses erfüllt tatsächlich die Kontrollgleichung. Denn deren linke Seite wird zu

3‾+10‾+6‾+10‾+5‾+3‾+6‾+8‾+4‾+0‾ =55‾=0‾

in ℤ11 (etwa der vierte Summand zu 4‾⋅8‾=32‾=10‾). Der Code soll nun die Menge C sämtlicher 10-Tupel in ℤ1110 sein, welche die Kontrollgleichung erfüllen. Er lässt jeden Einzelfehler erkennen, ebenso jede Vertauschung zweier Zeichen.

EAN-13

Werden bei einer 13-stelligen EAN-13 die 13 Ziffern abwechselnd mit den Zahlen 1 und 3 multipliziert und diese Produkte addiert, so muss sich eine durch 10 teilbare Summe ergeben. Geht man also von den 13 Ziffern zu ihren Restklassen modulo 10 über, so ergibt sich ein 13-Tupel

x=(x1,x2,…,x12,x13)∈ℤ1013,

das die Kontrollgleichung

x1+3‾⋅x2+x3+⋯+3‾⋅x12+x13=0‾

in ℤ10 erfüllt. Der entsprechende Code, also die Menge sämtlicher 13-Tupel in ℤ1013, welche die Kontrollgleichung erfüllen, lässt jeden Einzelfehler erkennen – ebenso wie der ISBN-10-Code. Aber im Unterschied zu diesem wird nicht jede Vertauschung zweier Zeichen erkannt, nicht einmal jede Nachbar-Vertauschung („Zahlendreher“).

Allgemein

Unter einem Prüfzeichen-Code der Länge n∈ℕ über einer endlichen Gruppe (G,∗) versteht man eine Menge der Form

C={(x1,x2,…,xn)∈Gn| f1(x1)∗f2(x2)∗⋯∗fn(xn)=a}

mit n bijektiven Abbildungen f1,f2,…,fn:G→G und einem Element a∈G. Solch ein Code C⊆Gn lässt jeden Einzelfehler erkennen.

Beispielsweise ist der ISBN-10-Code C⊆ℤ1110 ein Prüfzeichen-Code der Länge 10 über der Gruppe (ℤ11,+). Dazu nimmt man das Element a=0‾ und die zehn Abbildungen fk:ℤ11→ℤ11,

fk(z)=k‾⋅z (z∈ℤ11)

mit k=1,2,…,10. Diese sind bijektiv, weil jeweils die inverse Restklasse k‾|−1 wegen ggT(11,k)=1 existiert.

Der EAN-13-Code C⊆ℤ1013 ist ein Prüfzeichen-Code der Länge 13 über der Gruppe (ℤ10,+) mit den 13 bijektiven Abbildungen fk:ℤ10→ℤ10,

fk(z)=z  für ungerades k, fk(z)=3‾⋅z  für gerades k

(z∈ℤ10, k=1,2,…,13) sowie dem Element a=0‾.

Prüfzeichen-Codes über Gruppen der Ordnung 10

Eine Gruppe der Ordnung 10 hat den Vorteil, dass ihre Elemente durch die Ziffern 0, 1,…, 9 symbolisiert werden könnten. Zwei Sätze sind nun zentral:

I. Es gibt keinen Prüfzeichen-Code mit einer Länge n≥2 über der (abelschen) Gruppe (ℤ10,+), der jede Nachbar-Vertauschung erkennen lässt.

II. Es gibt eine nichtabelsche Gruppe (G,∗) der Ordnung 10 und eine bijektive Abbildung f:G→G derart, dass für jede ganze Zahl n≥2 und jedes Element a∈G der Prüfzeichen-Code

C={(x1,x2,…,xn)∈Gn| f(x1)∗f2(x2)∗⋯∗fn(xn)=a}

jede Nachbar-Vertauschung erkennen lässt.

In Satz II muss man die Diedergruppe D5 nehmen. Das ist die Symmetriegruppe eines regelmäßigen Fünfecks, bestehend aus fünf Drehungen und fünf Achsenspiegelungen sowie der Verkettung als Verknüpfung. Im Folgenden wird sie multiplikativ geschrieben und das Verknüpfungssymbol weggelassen. Außerdem werden mit e,r,s∈D5 ihr neutrales Element bzw. die Drehung um 72° bzw. eine Spiegelung bezeichnet. Es gilt dann r5=e=s2 und srk=r−ks für alle ganzen Zahlen k sowie

D5={e,r,r2,r3,r4,s,rs,r2s,r3s,r4s}.
Permutation f der Diedergruppe D₅
Permutation f der Diedergruppe D₅

Als bijektive Abbildung f:D5→D5 kann man die durch die Skizze gegebene nehmen. In der Kontrollgleichung erscheinen noch ihre Iterierten wie etwa f2=f∘f.

Bei den Nummern der DM-Banknoten der vierten/letzten Serie wurde allerdings in der Kontrollgleichung vergessen, xn mit fn abzubilden (mehr dazu im Artikel Diedergruppe #Codierung).

Siehe auch

Hinweise und Einzelnachweise

  1. ↑ Technische Spezifikation Briefzusatzleistungen. (PDF, 554 kB) S. 8, archiviert vom Original (nicht mehr online verfügbar) am 2. April 2015; abgerufen am 4. März 2015.  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
  2. ↑ In anderen Verfahren zur Prüfsummenberechnung werden andere Gewichtungen genutzt, bei ISBN beispielsweise die Folge 10, 9, 8, 7, 6, 5, 4, 3, 2.
  3. ↑ Structure of the ORCID Identifier (ORCID, abgerufen am 26. Juni 2017)
  4. 1 2 3 4 Ralph-Hardo Schulz: Codierungstheorie. Eine Einführung. 2., aktualisierte und erweiterte Auflage. Vieweg, Wiesbaden 2003, ISBN 3-528-16419-0, S. 55–66.
  5. 1 2 Albrecht Beutelspacher: Vertrauen ist gut, Kontrolle ist besser! Vom Nutzen elementarer Mathematik zum Erkennen von Fehlern. In: Jahrbuch Überblicke Mathematik. 1995, ISSN 0172-8512, DNB 011466979, S. 27–37.
  6. ↑ Nicht erkannt werden die Nachbar-Vertauschungen 0‾↔5‾, 1‾↔6‾, 2‾↔7‾, 3‾↔8‾ und 4‾↔9‾.
  7. ↑ Mit dem Luhn-Algorithmus kann für jede natürliche Zahl n≥2 ein Code C⊆ℤ10n auf ähnliche Weise gebildet werden. Bei ihm wird sogar nur die Nachbar-Vertauschung 0‾↔9‾ nicht erkannt.