Prüfziffer, Barcode

Analog zu den Teilbarkeitsregeln existiert für die wohlbekannten Barcodes, zum Beispiel auf Verpackungen, ein Prüfverfahren.

Bezahlt man in einem Geschäft seine Ware, so wird der Preis in aller Regel nicht von Hand eingegeben. Vielmehr wird der Strichcode, der sich auf jedem Artikel befindet, eingescannt. Selbst wenn dies aufgrund technischer Probleme nicht funktioniert, gibt der Kassierer nicht den Preis, sondern die zum Strichcode gehörende Ziffernfolge ein. Wie kommt es, dass ein Fehler beim Eingeben des Barcodes fast immer auffällt? Fallen Fehler wirklich immer auf?

Man braucht also eine Idee, wie man Fehler bei der Eingabe mit hoher Wahrscheinlichkeit bemerken kann – und diese Idee heisst Redundanz. Man hängt an den Teil des Codes, den man zur Identifikation des Produkts braucht, zusätzliche (redundante) Ziffern an, deren einziger Sinn es ist, den Code fehlerresistenter zu machen. Dabei sollten möglichst wenige zusätzliche Ziffern eine möglichst hohe Sicherheit bieten. Weshalb und wie man das mit nur einer Ziffer erreichen kann, hat mit Modulo-Arithmetik zu tun. Ähnliche Verfahren werden auch bei Kreditkarten, ISBN-Nummern, Seriennummern von Geldscheinen etc. verwendet.

Prüfziffer (Checksum)

Als kleines Beispiel betrachten wir das alte ISBN-System (International Standard Book Number). Dieses ist zwar nicht mehr aktuell, aber für unsere Zwecke instruktiver und einfacher verständlich als die inzwischen verwendete Variante. Die hier betrachteten Überlegungen gelten grundsätzlich auch für die meisten neueren Verfahren.

Zur Einordnung: Jedem Buch ist zur eindeutigen Identifikation eine zehnstellige ISBN-Nummer zugeordnet. Von diesen $10$ Ziffern sind die ersten $9$ die eigentliche Information; die zehnte ist eine Prüfziffer. Diese Prüfziffer, auch Checksum genannt, soll eine gewisse Sicherheit zur Vermeidung von Tipp- und Übertragungsfehlern gewährleisten.

Example 1

Wir nehmen als Beispiel das Buch

P. Hartmann, Mathematik für Informatiker, Vieweg, 2003. mit der (alten) ISBN-Nummer 3-8348-0096-1.

Dabei steht die erste Ziffer für die Länder- oder Sprachgruppe, die zweite Zifferngruppe für den Verlag und die dritte für die vom Verlag vergebene Titelnummer. Die 10. Ziffer, die 1, ist die Prüfziffer.

Eine ISBN-Nummer sei mit

a_1a_2a_3\dots a_9a_{10} =: Y

bezeichnet. Dabei ist $a_i\in\{0,1,2,\dots,9\}$ für $i=1,\dots,9$ und die Prüfziffer $a_{10}$ berechnet sich gemäss:

a_{10}\equiv a_1+2a_2+3a_3+\dots+9a_9\equiv\sum_{i=1}^9ia_i\mod11.

Dies ergibt für $a_{10}$ einen Wert zwischen $0$ und $10$ . Falls das Ergebnis $10$ lautet, schreibt man dafür römisch X.

Natürlich kann man nicht erwarten, dass so alle Fehler erkannt werden. Aber, wie wir gleich sehen werden, schützt diese Prüfziffer vor den alltäglichsten Fehlern.

Ziffer fehlerhaft eingetippt

Geschieht der Fehler in der Prüfziffer selbst, dann ist der Fall klar. Wir können also den Fehler zwischen den Stellen $1$ und $9$ annehmen und müssen zeigen, dass die Prüfziffer falsch ist. Sei also

Y'=a_1\dots a_i'\dots a_{10}

die fehlerhafte ISBN mit dem Fehler an der $i$ -ten Stelle, $1\leq i\leq9$ . Die Prüfziffer wäre so

a'_{10}=\sum_{j\neq i}ja_j+ia_i'\mod11

Wir haben aber $a_{10}$ und es gilt

a_{10}-a_{10}'=ia_i-ia_i'=i(a_i-a_i')\mod11

Wegen $a_i\neq a_i'$ ist $a_i-a_i'\neq0$ und wegen $1\leq i\leq9$ auch $i\neq0$ . Daraus folgt mit einer nicht ganz trivialen Überlegung, dass $i(a_i-a_i')\not\equiv0\mod11$ . Dabei ist die Wahl des Moduls wichtig. Entscheidend für die letzte Folgerung ist, dass $11$ eine Primzahl ist, denn für diese haben wir

Theorem 1: Lemma von Euklid

Sind $p$ prim und $a,b\in\mathbb{Z}$ mit $p\mid ab$ , so gilt $p\mid a$ oder $p\mid b$ .

Proof

Wir brauchen die Negation des obigen Satzes:

Teilt $p$ weder $a$ noch $b$ , dann teilt $p$ auch nicht $ab$ .

Wenn $p$ weder $a$ noch $b$ teilt, dann kommt $p$ nicht in der Primfaktorzerlegung von $a$ und $b$ vor, also auch nicht in der Primzahlzerlegung des Produkts $ab$ . Das heisst $p$ teilt $ab$ nicht.

Damit ist gezeigt, dass insbesondere für $p=11$ der letzte Schritt gilt und damit die Prüfziffer der ISBN eine fehlerhafte Ziffer erkennt.

Exercise 1: Vertipper

Früher wurde für die Buchklassifikation anstelle der heute gebräuchlichen ISBN13- die ISBN10-Nummer verwendet. Diese beiden Nummern unterscheiden sich nur durch das Präfix $978$ und die Prüfziffer, die restlichen $9$ Ziffern stimmen überein. Ich habe mich in diesem Beispiel für die ISBN10 entschieden, da sie rechnerisch etwas handlicher ist.

Das Buch Mathematik für Informatiker hat die ISBN-10 Nummer 3-8348-0096-1, wobei die letzte Ziffer, 1, als Prüfziffer (Checksum) fungiert. Diese letzte Ziffer $a_{10}$ wird in der ISBN10-Variante aus den vorangehenden Ziffern wie folgt berechnet:

a_{10}\equiv\sum_{k=1}^9k\cdot a_k\mod11.

a) Überprüfe, ob die Checksum 1 korrekt ist.

b) Wähle eine beliebige Position in der ISBN-Nummer aus und vertippe dich (absichtlich). Berechnen nun die Prüfziffer der "vertippten" Nummer.

c) Angenommen, man vertippe sich an genau $2$ Stellen, sagen wir Positionen $2$ und $5$ . Registriert die Prüfziffer die Vertipper? Finde ein Beispiel für einen "Doppelvertipper", der nicht erkannt wird.

Solution

a) Es ist $1\cdot3+2\cdot8+3\cdot3+4\cdot4+5\cdot8+6\cdot0+7\cdot0+8\cdot9+9\cdot6=210\equiv1\mod11.$

b) Wenn ich mich zum Beispiel an der Stelle $5$ vertippe, $3834\textcolor{red}{9}00961$ , dann kriege ich als Checksum $6\not\equiv1$ .

c) Wenn man sich an den Stellen $2$ und $5$ vertippt, dann hat man als Differenz der Checksums

a_{10}-a'_{10}=2(a_i-a'_i)+5(a_j-a'_j).

Nun probiert man für $a_i$ , $a_j$ , $a'_i$ , $a'_j\in\{0,1,\dots9\}$ alle Kombinationen aus, die $\mod11\equiv 0$ ergeben. Denn in diesem Fall werden die Vertipper nicht bemerkt. Das ist im Allgemeine aufwändig und von den konkreten Ziffern abhängig. Für die vorliegende Nummer klappt dies beispielsweise für $3\textcolor{red}{7}34\textcolor{red}{4}00961$ , da $2\cdot(8-7)+5\cdot(8-4)=22\equiv0\mod11$ .

Note 1

All die Erkennung der "einfachen" Vertipper würde nicht funktionieren, wenn wir anstelle von $11$ beispielsweise $10$ als Modul verwendet hätten. Denn wegen $10=2\cdot5$ , also $2\cdot5\equiv0\mod10$ würde etwa ein Fehler an der $i=5$ -ten Stelle nicht erkannt, wenn die fehlerhafte Ziffer um $2$ von der korrekten Ziffer abweicht. Die Prüfziffer Modulo $10$ bliebe dann unverändert.

Exercise 2: Vertauscher

Schreibe eine Python-Funktion, die zu gegebenem Input einer ISBN10-Nummer als Output angibt, ob die Nummer korrekt ist oder nicht.

Verwende anschliessend das Programm, um zu testen, dass die Prüfziffer bemerkt, falls man zwei Ziffern vertauscht hat.

Solution

Ein Beispiel ist

def isbncheck(isbnnr):
    # Einzelne Ziffern aus der Nummer listen
    isbnls = [int(num) for num in str(isbnnr)]
    summod = 0
    # Ziffern gewichten, zusammenzaehlen und mod 11 rechnen
    for k in range(1,10):
        summod = (summod + (k)*isbnls[k-1]) % 11
    # Checksum vergleichen mit Pruefziffer
    if summod == isbnls[9]:
        return print("ok")
    else:
        return print("bärääh")

Robuster und ausführlicher wäre:

# Akzeptiert einen String, der Bindestriche ignoriert
def is_isbn10_valid(isbn_str):
    # Entfernt mögliche Bindestriche und Leerzeichen
    digits = isbn_str.replace("-", "").replace(" ", "")
    
    if len(digits) != 10:
        return False
        
    # Prüfen, ob alle Zeichen (ausser evtl. 'X' am Ende) Ziffern sind
    if not digits[:9].isdigit():
        return False

    checksum = 0
    for i in range(9):
        checksum += (i + 1) * int(digits[i])
    
    # Prüfziffer validieren (kann 'X' sein)
    last_char = digits[9].upper()
    if last_char == 'X':
        correct_checksum = 10
    elif last_char.isdigit():
        correct_checksum = int(last_char)
    else:
        return False # Ungültiges Zeichen an letzter Stelle

    return (checksum % 11) == correct_checksum

# -- So würde man die Funktion verwenden --
my_isbn = "3-8348-0096-1"
if is_isbn10_valid(my_isbn):
    print(f"Die ISBN '{my_isbn}' ist gültig! ✔️")
else:
    print(f"Die ISBN '{my_isbn}' ist fehlerhaft. ❌")

Zahlenvertauscher

Die ISBN erkennt nicht nur einzelne fehlerhafte Ziffern, sondern auch den am häufigsten auftauchende Fehlertyp: das Vertauschen zweier aufeinanderfolgender Ziffern. In der Tat erkennt die Prüfziffer sogar Vertauschen von nicht unmittelbar aufeinanderfolgenden Ziffern, was zwar weniger vorkommt, aber für den folgenden Beweis ohne Mehraufwand mit einbezogen werden kann.

Exercise 3: Vertauscher testen

Teste einen Zahlendreher anhand von 3-8348-0069-0.

Solution

Brauche dein Python-Programm von oben.

Exercise 4: Beweis Vertauscher

Zeige, dass obige Checksum einen Vertauscher bemerkt. Zeige dies für $2$ Ziffern, die nicht zwingend aufeinander folgen.

Solution

Seien $i,j\in\{1,2,\dots,9\}$ mit $i\neq j$ die vertauschten Positionen. Die involvierten Ziffern unterschieden sich natürlich auch, $a_i\neq a_j$ , da sonst der Vertauscher gar nicht bemerkt würde. Betrachten Sie die korrekte, $a_{10}$ , versus die inkorrekte, $a'_{10}$ , Checksum. Die Differenz ist

\begin{align*} a_{10}-a'_{10}&= i\cdot a_i+j\cdot a_j-(i\cdot a_j+j\cdot a_i)\\ &=i\cdot(a_i-a_j)+j\cdot(a_j-a_i)\\ &=i\cdot(a_i-a_j)-j\cdot(a_i-a_j)\\ &=(i-j)\cdot(a_i-a_j)\\ &\not\equiv0\mod11 \end{align*}

wobei man beim letzten Schritt gleich argumentiert wie im vorangegangenen Beweis: teilt die Primzahl $11$ weder den einen noch den andern Faktor, dann sicher auch nicht das Produkt; also teilt $11$ nicht $a_{10}-a'_{10}$ und damit unterscheiden sich die Prüfziffern Modulo $11$ .

(Zahlendreher kommentiert)

Wie oben gesehen, ist also die Wahl des Moduls entscheidend. Bei $9$ informationstragenden Ziffern braucht man also eine Primzahl grösser oder gleich $10$ , und $11$ ist dafür die kleinstmögliche Wahl.

Exercise 5: 🧩

Bei der ISBN13 berechnet sich die Prüfziffer $a_{13}$ via

a_{13}\equiv10-\left(\sum_{k=1}^{12}a_k\cdot 3^{(k+1)\mod2}\mod10\right).

Überprüfe die Korrektheit der ISBN13 Prüfziffer.

Hier kann man noch für die oben verwendete ISBN10 die zugehörige ISBN13 Checksum nachrechnen:

Solution

Wir berechnen zuerst die gewichtete Summe:

\begin{align*} S &= 9\cdot1 + 7\cdot3 + 8\cdot1 + 3\cdot3 + 0\cdot1 + 3\cdot3 + 3\cdot1 + 0\cdot3 + 2\cdot1 + 5\cdot3 + 8\cdot1 + 6\cdot3 \\ &= 9 + 21 + 8 + 9 + 0 + 9 + 3 + 0 + 2 + 15 + 8 + 18 \\ &= 102 \end{align*}

Nun berechnen wir den Modulo 10 der Summe: $102 \equiv 2 \pmod{10}$ . Die Prüfziffer $a_{13}$ ist dann:

a_{13} = (10 - 2) \pmod{10} = 8.

Das Ergebnis 8 stimmt mit der Prüfziffer der ISBN überein.