Prüfziffer

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

${\displaystyle x=(x_{1},x_{2},\dotsc ,x_{9},x_{10})}$

in ${\displaystyle \mathbb {Z} _{11}^{10}=\mathbb {Z} _{11}\times \dotsm \times \mathbb {Z} _{11}}$ (kartesisches Produkt mit 10 Faktoren), das analog die Kontrollgleichung

${\displaystyle {\overline {1}}\cdot x_{1}+{\overline {2}}\cdot x_{2}+\dotsm +{\overline {9}}\cdot x_{9}+{\overline {10}}\cdot x_{10}={\overline {0}}}$

in ${\displaystyle \mathbb {Z} _{11}}$ erfüllt. Beispielsweise entspricht die Nummer 3-528-16419-0 des Buches dem 10-Tupel

${\displaystyle x={\bigl (}\!\ {\overline {3}},{\overline {5}},{\overline {2}},{\overline {8}},{\overline {1}},{\overline {6}},{\overline {4}},{\overline {1}},{\overline {9}},{\overline {0}}{\bigr )}\in \mathbb {Z} _{11}^{10},}$

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

${\displaystyle {\overline {3}}+{\overline {10}}+{\overline {6}}+{\overline {10}}+{\overline {5}}+{\overline {3}}+{\overline {6}}+{\overline {8}}+{\overline {4}}+{\overline {0}}}$ ${\displaystyle ={\overline {55}}={\overline {0}}}$

in ${\displaystyle \mathbb {Z} _{11}}$ (etwa der vierte Summand zu ${\displaystyle {\overline {4}}\cdot {\overline {8}}={\overline {32}}={\overline {10}}}$). Der Code soll nun die Menge ${\displaystyle C}$ sämtlicher 10-Tupel in ${\displaystyle \mathbb {Z} _{11}^{10}}$ 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

${\displaystyle x=(x_{1},x_{2},\dotsc ,x_{12},x_{13})\in \mathbb {Z} _{10}^{13},}$

das die Kontrollgleichung

${\displaystyle x_{1}+{\overline {3}}\cdot x_{2}+x_{3}+\dotsm +{\overline {3}}\cdot x_{12}+x_{13}={\overline {0}}}$

in ${\displaystyle \mathbb {Z} _{10}}$ erfüllt. Der entsprechende Code, also die Menge sämtlicher 13-Tupel in ${\displaystyle \mathbb {Z} _{10}^{13},}$ 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 ${\displaystyle n\in \mathbb {N} }$ über einer endlichen Gruppe ${\displaystyle (G,*)}$ versteht man eine Menge der Form

${\displaystyle C={\Big \{}(x_{1},x_{2},\dotsc ,x_{n})\in G^{n}\,{\Big |}}$ ${\displaystyle \,f_{1}(x_{1})*f_{2}(x_{2})*\dotsm *f_{n}(x_{n})=a{\Big \}}}$

mit ${\displaystyle n}$ bijektiven Abbildungen ${\displaystyle f_{1},f_{2},\dotsc ,f_{n}\colon \,G\to G}$ und einem Element ${\displaystyle a\in G.\,}$ Solch ein Code ${\displaystyle C\subseteq G^{n}}$ lässt jeden Einzelfehler erkennen.

Beispielsweise ist der ISBN-10-Code ${\displaystyle C\subseteq \mathbb {Z} _{11}^{10}}$ ein Prüfzeichen-Code der Länge 10 über der Gruppe ${\displaystyle (\mathbb {Z} _{11},+).}$ Dazu nimmt man das Element ${\displaystyle a={\overline {0}}}$ und die zehn Abbildungen ${\displaystyle f_{k}\colon \,\mathbb {Z} _{11}\to \mathbb {Z} _{11},}$

${\displaystyle f_{k}(z)={\overline {k}}\cdot z\;\;\ (z\in \mathbb {Z} _{11})}$

mit ${\displaystyle k=1,2,\dotsc ,10.}$ Diese sind bijektiv, weil jeweils die inverse Restklasse ${\displaystyle {\overline {k}}{\vphantom {|}}^{\,-1}}$ wegen ${\displaystyle \mathrm {ggT} (11,k)=1}$ existiert.

Der EAN-13-Code ${\displaystyle C\subseteq \mathbb {Z} _{10}^{13}}$ ist ein Prüfzeichen-Code der Länge 13 über der Gruppe ${\displaystyle (\mathbb {Z} _{10},+)}$ mit den 13 bijektiven Abbildungen ${\displaystyle f_{k}\colon \,\mathbb {Z} _{10}\to \mathbb {Z} _{10},}$

${\displaystyle f_{k}(z)=z\ {\text{ für ungerades }}k,\quad }$ ${\displaystyle f_{k}(z)={\overline {3}}\cdot z\ {\text{ für gerades }}k}$

${\displaystyle (z\in \mathbb {Z} _{10},\ k=1,2,\dotsc ,13)}$ sowie dem Element ${\displaystyle a={\overline {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 ${\displaystyle n\geq 2}$ über der (abelschen) Gruppe ${\displaystyle (\mathbb {Z} _{10},+),}$ der jede Nachbar-Vertauschung erkennen lässt.

II. Es gibt eine nichtabelsche Gruppe ${\displaystyle (G,*)}$ der Ordnung 10 und eine bijektive Abbildung ${\displaystyle f\colon \,G\to G}$ derart, dass für jede ganze Zahl ${\displaystyle n\geq 2}$ und jedes Element ${\displaystyle a\in G}$ der Prüfzeichen-Code

${\displaystyle C={\Big \{}(x_{1},x_{2},\dotsc ,x_{n})\in G^{n}\,{\Big |}}$ ${\displaystyle \,f(x_{1})*f^{2}(x_{2})*\dotsm *f^{n}(x_{n})=a{\Big \}}}$

jede Nachbar-Vertauschung erkennen lässt.

In Satz II muss man die Diedergruppe ${\displaystyle D_{5}}$ 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 ${\displaystyle e,r,s\in D_{5}}$ ihr neutrales Element bzw. die Drehung um 72° bzw. eine Spiegelung bezeichnet. Es gilt dann ${\displaystyle \textstyle r^{5}=e=s^{2}}$ und ${\displaystyle \textstyle sr^{k}=r^{-k}\!s}$ für alle ganzen Zahlen ${\displaystyle k}$ sowie

${\displaystyle D_{5}={\bigl \{}e,r,r^{2},r^{3},r^{4},s,rs,r^{2}\!s,r^{3}\!s,r^{4}\!s{\bigr \}}.}$

Als bijektive Abbildung ${\displaystyle f\colon \;}$${\displaystyle D_{5}\to D_{5}}$ kann man die durch die Skizze gegebene nehmen. In der Kontrollgleichung erscheinen noch ihre Iterierten wie etwa ${\displaystyle \textstyle f^{2}=f\circ f.}$

Bei den Nummern der DM-Banknoten der vierten/letzten Serie wurde allerdings in der Kontrollgleichung vergessen, ${\displaystyle x_{n}}$ mit ${\displaystyle f^{n}}$ abzubilden (mehr dazu im Artikel Diedergruppe #Codierung).