Die ISBN-Codierung und Allgemeines über Prüfzeichencodierungen

Ein Beispiel für einen fehlererkennenden Code ist die Codierung mit Hilfe der ISBN (International Standard Book Number). ,,Von westlichen Verlagen herausgegebene Bücher werden seit einiger Zeit mit Nummern versehen, aus denen Land, Verlag und Buch zu identifizieren sind.`` ([9] S.56) Das Buch [9] von Ralph Hardo Schulz zum Beispiel hat die ISBN $3-528-06419-6$, wobei die $3$ für das Land, die $528$ für den Verlag und die $06419$ für den Artikel stehen. Die $6$ ist eine Prüfziffer, die es uns (unter Umständen) erlaubt, eine Aussage über die Richtigkeit der Nummer zu machen: Erfüllt die Prüfziffer eine bestimmte Kontrollgleichung nicht, so können wir uns sicher sein, dass ein Fehler aufgetreten ist, erfüllt sie diese aber, dann können wir immer noch keine genaue Aussage darüber treffen, ob sie richtig ist. Eine gültige ISBN-Nummer $a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}a_{7}a_{8}a_{9}a_{10}$ muss die Prüfgleichung

$$a_{10}\equiv {\sum_{i=1}^{9}}i\cdot a_{i}\pmod{11}$$

erfüllen. Man verwendet hier die Summe modulo $11$, was zur Folge hat, dass auch der Fall $a_{10}=10$ auftreten kann; wir müssen also unser Alphabet $\{0,1,2,3,4,5,6,7,8,9\}$, aus dem wir die endgültige Nummer bilden wollen, um eine Stelle erweitern. Man hat als Symbol für die $10$ den Buchstaben $X$ gewählt. Es stellt sich nun die Frage, ob die Verwendung der Summe modulo $11$, die uns zwingt, unser Alphabet zu erweitern, uns auch irgendwelche Vorteile verschafft. Dies tut sie, da bei einem Einzelfehler in der $j$-ten Stelle die Summe folgendermaßen aussieht (vgl. auch [9], S. 59):

$$\sum_{i=1,i\neq j}^{9}i\cdot a_{i}+j\cdot a^{\prime}_{j}=\sum_{i=... ...{j}+j\cdot a^{\prime}_{j}\equiv a_{10} +j\cdot(a^{\prime}_{j}-a_{j}){\pmod{11}}$$ (4)

Damit ein solcher Fehler erkannt werden kann, darf der Term $j\cdot(a^{\prime}_{j}-a_{j})$ allerdings nicht durch $11$ teilbar sein. Dieser Fall kann jedoch gar nicht eintreten, da $11$ eine Primzahl ist: Das Produkt $j\cdot(a^{\prime}_{j}-a_{j})$ besteht aus den Faktoren $j$ und $a^{\prime}_{j}-a_{j}$; $j$ kann sich ja nur zwischen $1$ und $9$ bewegen, hat also auf jeden Fall keinen Teiler $t\neq 1$ mit $11$ gemeinsam und auch der Betrag des zweiten Faktors kann sich zwischen $1$ und $9$ bewegen (wir gehen davon aus, dass $a^{\prime}_{j}\neq a_{j}$, also dass ein Fehler aufgetreten ist) und wir wissen, dass $-a{\pmod{n}}=n-a\pmod{n}$. Also kann das gesamte Produkt gar kein Vielfaches von $11$ sein, da $11$ keinen Teiler $t\neq 1$ mit einem Faktor gemeinsam hat. Ein einzelner Fehler der ersten neun Stellen wird also auf diese Weise erkannt, was bei Verwendung von $\pmod{10}$ nicht gewährleistet hätte sein können, zum Beispiel wenn der Fall $j=2$ und $a^{\prime}_{j}-a_{j}=5$ eintritt. Allgemein können wir aus Gleichung 5.1 erkennen, dass es, wenn wir nicht modulo $11$ rechnen, sondern allgemein modulo $k$ (wobei $k$ allerdings größer sein sollte als das größte $a_{i}$) notwendig für die Erkennung von Einzelfehlern ist, dass alle $i$ teilerfremd zu $k$ sind und diese Forderung auch hinreichend für die Erkennung von Einzelfehlern ist (vgl. auch [9], S. 59).

Die Prüfgleichung kann nun auch anders formuliert und verallgemeinert werden:

$${\sum_{i=1}^{9}i\cdot a_{i}}-a_{10}\equiv 0\pmod{11}\hbox{,}$$ (5)

und noch allgemeiner können wir, da wir ja die Teilerfremdheit zu einem allgemeinen $k$ nicht für alle $i\in \{1,\cdots,n\}$ garantieren können, die folgende Gleichung

$${\sum_{i=1}^{n}\omega_{i}\cdot a_{i}}\equiv c \pmod{k}$$ (6)

als Prüfgleichung wählen. (vgl. [9], S. 59)

In unserem Fall ist $\omega_{i}=i$ für $i\neq 10$ und $\omega_{10}=-1$. Wir können nun von Gleichung 5.2 ausgehend (analog zur ersten Form) erkennen, dass Einzelfehler auch in der zehnten Stelle erkannt werden können.

Unsere allgemeine Gleichung 5.3 findet in der Praxis vor allem für $k=10$ (mit $\omega_{i}$ ungerade und $\omega_{i}\neq 5$) und $k=11$ Anwendung, wobei sich allerdings gezeigt hat, dass für $k=11$ mehr Fehlertypen erkannt werden können als mit $k=10$, dass hier jedoch, wie wir schon gesehen haben, eine Erweiterung des Alphabets notwendig ist (vgl. [9], S. 61).

Man kann die Abbildung von $i$ auf den Rest von $\omega_{i}\cdot i$ bei Division (in unserem Fall) durch $11$ als eine Permutation auffassen (vgl. auch [9] S.59) und den Begriff der Prüfzeichencodierung auf Gruppen ausweiten; den Nachweis, dass wir es hier mit Permutationen zu tun haben, werden wir hier allerdings nicht erbringen, die Tatsache, dass hier wieder $11$ verschiedene Reste auftreten und für keine zwei $i$ aus unserem Alphabet gleiche Reste auftreten, könnten wir aber wieder ähnlich zu dem Beweis, dass $\langle d^{m}\rangle =\langle d^{a}\rangle$ für den Fall, dass $a$ der größte gemeinsame Teiler von $n$ und $m$ ist, den wir bei unserer Untergruppensuche geführt haben, und auch allgemein für den Fall, dass $w_{i}$ teilerfremd zu $k$ ist, zeigen.

In unserem Beispiel haben wir für $\omega_{i}=8$ die folgenden Reste bei Division mit $11$ und erkennen sofort, dass wir es hier mit einer Permutation zu tun haben, wobei wir allerdings das Alphabet um die $10$ erweitern. $P=\left(\begin{array}{ccccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & 8 & 5 & 2 & 10 & 7 & 4 & 1 & 9 & 6 & 3 \end{array}\right)$