Zum Inhalt springen

Prüfziffer

aus Wikipedia, der freien Enzyklopädie

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.

Skriptfehler: Ein solches Modul „Vorlage:Anker“ ist nicht vorhanden. Beispiel: Identcode der Deutschen Post[Bearbeiten]

Die Berechnung der Prüfziffer erfolgt beim Identcode der Deutschen Post im Modulo-11-Verfahren<ref>[Skriptfehler: Ein solches Modul „Vorlage:Internetquelle“ ist nicht vorhanden. Skriptfehler: Ein solches Modul „Vorlage:Internetquelle“ ist nicht vorhanden.] (PDF, 554 kB) S. 8, archiviert vom Vorlage:Referrer (nicht mehr online verfügbar) am 2015-04-02;.Skriptfehler: Ein solches Modul „Vorlage:Internetquelle“ ist nicht vorhanden.Skriptfehler: Ein solches Modul „TemplatePar“ ist nicht vorhanden.</ref> 

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
Datei:Identcode.gif
Identcode der Deutschen Post / DHL

Berechnung der Prüfziffer:

  • Von links nach rechts werden die Stellen mit 8, 6, 4, 2, 3, 5, 9 und 7 gewichtet. Im Unterschied zu einer einfachen Summierung der Code-Ziffern können so auch Vertauschungen von zwei Ziffern erkannt werden.<ref>In anderen Verfahren zur Prüfsummenberechnung werden andere Gewichtungen genutzt, bei ISBN beispielsweise die Folge 10, 9, 8, 7, 6, 5, 4, 3, 2.</ref>
  • Die einzelnen Code- und Gewichtungsziffern werden multipliziert und die Produkte dann addiert.
  • Die Summe wird Modulo 11 berechnet, sprich es wird nur der Rest der Division durch 11 (also nur eine Ziffer) berücksichtigt. Die Restbildung kann auch unmittelbar nach der Produktbildung erfolgen.
  • Die Prüfziffer ergibt sich aus der Differenz des Restes zu 11 (Ausnahmen siehe oben).

Berechnung des Identcodes in einer Formel am Beispiel Excel:

  • Der achtstellige Code steht in Zelle A1
  • Formel<syntaxhighlight lang="text">
=A1&TEIL("012345678905";12-REST(TEIL(A1;1;1)*8+TEIL(A1;2;1)*6+TEIL(A1;3;1)*4+TEIL(A1;4;1)*2+TEIL(A1;5;1)*3+TEIL(A1;6;1)*5+TEIL(A1;7;1)*9+TEIL(A1;8;1)*7;11);1)

</syntaxhighlight>

Weitere Beispiele[Bearbeiten]

Prüfzeichen-Code über einer Gruppe[Bearbeiten]

Häufig ist eine Beschreibung durch einen Prüfzeichen-Code über einer Gruppe möglich, etwa über der Restklassen-Gruppe <math>(\Z_{11},+)</math> bei der ISBN-10 bzw. <math>(\Z_{10},+)</math> bei der EAN-13 oder über der Diedergruppe <math>D_5</math> bei den Nummern der DM-Banknoten der vierten/letzten Serie.<ref name="Schulz2003">Skriptfehler: Ein solches Modul „Vorlage:Literatur“ ist nicht vorhanden.</ref><ref name="Beutelspacher1995">Skriptfehler: Ein solches Modul „Vorlage:Literatur“ ist nicht vorhanden.</ref>

ISBN-10[Bearbeiten]

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

<math>

x = (x_1,x_2,\dotsc,x_9,x_{10}) </math> in <math>\Z_{11}^{10} = \Z_{11}\times\dotsm\times\Z_{11}</math> (kartesisches Produkt mit 10 Faktoren), das analog die Kontrollgleichung

<math>

\overline1\cdot x_1 + \overline2\cdot x_2 + \dotsm + \overline9\cdot x_9 + \overline{10}\cdot x_{10} = \overline0 </math> in <math>\Z_{11}</math> erfüllt. Beispielsweise entspricht die Nummer 3-528-16419-0 des Buches<ref name="Schulz2003"/> dem 10-Tupel

<math>

x = \bigl(\!\ \overline3,\overline5,\overline2,\overline8,\overline1,\overline6,\overline4,\overline1,\overline9,\overline0 \bigr) \in \Z_{11}^{10}, </math> und dieses erfüllt tatsächlich die Kontrollgleichung. Denn deren linke Seite wird zu

<math>

\overline3 + \overline{10} + \overline6 + \overline{10} + \overline5 + \overline3 + \overline6 + \overline8 + \overline4 + \overline0</math> <math>= \overline{55} = \overline0 </math> in <math>\Z_{11}</math> (etwa der vierte Summand zu <math>\overline4\cdot\overline8 = \overline{32} = \overline{10}</math>). Der Code soll nun die Menge <math>C</math> sämtlicher 10-Tupel in <math>\Z_{11}^{10}</math> sein, welche die Kontrollgleichung erfüllen. Er lässt jeden Einzelfehler erkennen, ebenso jede Vertauschung zweier Zeichen.

EAN-13[Bearbeiten]

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

<math>

x = (x_1,x_2,\dotsc,x_{12},x_{13}) \in \Z_{10}^{13}, </math> das die Kontrollgleichung

<math>

x_1 + \overline3\cdot x_2 + x_3 + \dotsm + \overline3\cdot x_{12} + x_{13} = \overline0 </math> in <math>\Z_{10}</math> erfüllt. Der entsprechende Code, also die Menge sämtlicher 13-Tupel in <math>\Z_{10}^{13},</math> 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[Bearbeiten]

Unter einem Prüfzeichen-Code der Länge <math>n \in \N</math> über einer endlichen Gruppe <math>(G,*)</math> versteht man eine Menge der Form

<math>

C = \Big\{ (x_1,x_2,\dotsc,x_n) \in G^n \,\Big|</math> <math>\, f_1(x_1)*f_2(x_2)*\dotsm*f_n(x_n) = a \Big\} </math> mit <math>n</math> bijektiven Abbildungen <math>f_1,f_2,\dotsc,f_n\colon\, G\to G</math> und einem Element <math>a \in G.\,</math> Solch ein Code <math>C \subseteq G^n</math> lässt jeden Einzelfehler erkennen.<ref name="Schulz2003"/>

Beispielsweise ist der ISBN-10-Code <math>C \subseteq \Z_{11}^{10}</math> ein Prüfzeichen-Code der Länge 10 über der Gruppe <math>(\Z_{11},+).</math> Dazu nimmt man das Element <math>a = \overline0</math> und die zehn Abbildungen <math>f_k\colon\, \Z_{11}\to\Z_{11},</math>

<math>

f_k(z) = \overline{k}\cdot z\;\;\ (z \in \Z_{11}) </math> mit <math>k = 1,2,\dotsc,10.</math> Diese sind bijektiv, weil jeweils die inverse Restklasse <math>\overline{k}\vphantom|^{\,-1}</math> wegen <math>\mathrm{ggT}(11,k) = 1</math> existiert.

Der EAN-13-Code <math>C \subseteq \Z_{10}^{13}</math> ist ein Prüfzeichen-Code der Länge 13 über der Gruppe <math>(\Z_{10},+)</math> mit den 13 bijektiven Abbildungen <math>f_k\colon\, \Z_{10}\to\Z_{10},</math>

<math>

f_k(z) = z\ \text{ für ungerades } k,\quad</math> <math>f_k(z) = \overline{3}\cdot z\ \text{ für gerades } k </math> <math>(z \in \Z_{10},\ k = 1,2,\dotsc,13)</math> sowie dem Element <math>a = \overline0.</math>

Prüfzeichen-Codes über Gruppen der Ordnung 10[Bearbeiten]

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:<ref name="Schulz2003"/>

I. Es gibt keinen Prüfzeichen-Code mit einer Länge <math>n \ge 2</math> über der (abelschen) Gruppe <math>(\Z_{10},+),</math> der jede Nachbar-Vertauschung erkennen lässt.

II. Es gibt eine nichtabelsche Gruppe <math>(G,*)</math> der Ordnung 10 und eine bijektive Abbildung <math>f\colon\, G\to G</math> derart, dass für jede ganze Zahl <math>n \ge 2</math> und jedes Element <math>a \in G</math> der Prüfzeichen-Code

<math>

C = \Big\{ (x_1,x_2,\dotsc,x_n) \in G^n \,\Big|</math> <math>\, f(x_1)*f^2(x_2)*\dotsm*f^n(x_n) = a \Big\} </math> jede Nachbar-Vertauschung erkennen lässt.

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

<math>

D_5 = \bigl\{e,r,r^2,r^3,r^4,s,rs,r^2\!s,r^3\!s,r^4\!s\bigr\}. </math>

Permutation f der Diedergruppe D₅
Permutation f der Diedergruppe D₅

Als bijektive Abbildung <math>f\colon\;</math><math>D_5\to D_5</math> kann man die durch die Skizze gegebene nehmen. In der Kontrollgleichung erscheinen noch ihre Iterierten wie etwa <math>\textstyle f^2 = f\circ f.</math>

Bei den Nummern der DM-Banknoten der vierten/letzten Serie wurde allerdings in der Kontrollgleichung vergessen, <math>x_n</math> mit <math>f^n</math> abzubilden<ref name="Beutelspacher1995"/> (mehr dazu im Artikel Diedergruppe #Codierung).

Siehe auch[Bearbeiten]

Hinweise und Einzelnachweise[Bearbeiten]

<references />

Weblinks[Bearbeiten]

Commons: Prüfziffer – Sammlung von Bildern, Videos und Audiodateien

Vorlage:Wikidata-Registrierung

[[wikt:Skriptfehler: Ein solches Modul „WLink“ ist nicht vorhanden.|Wiktionary: Skriptfehler: Ein solches Modul „WLink“ ist nicht vorhanden.]] – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Skriptfehler: Ein solches Modul „TemplatePar“ ist nicht vorhanden.

Abgerufen von „https://wiki.kertz.ch/index.php?title=Prüfziffer&oldid=34609“