Prüfziffer

A Prüfziffer ist eine Form der Redundanzprüfung für verwendet für Fehlererkennung Bei Identifikationsnummern wie Bankkontonummern, die in einer Anwendung verwendet werden, bei der sie zumindest manchmal manuell eingegeben werden. Es ist analog zu einem binären Paritätsbit, das verwendet wird, um Fehler in computergenerierten Daten zu überprüfen. Es besteht aus einem oder mehreren Ziffern (oder Buchstaben), die von einem Algorithmus aus den anderen Ziffern (oder Buchstaben) in der Sequenzeingabe berechnet werden.[1]

Mit einer Scheck -Ziffer kann man einfache Fehler in der Eingabe einer Reihe von Zeichen (normalerweise Ziffern) wie einer einzigen nebligen Ziffer oder einigen Permutationen von zwei aufeinanderfolgenden Ziffern erkennen.

Entwurf

Prüfziffer Algorithmen sind im Allgemeinen zum Erfassen entwickelt Mensch Transkriptionsfehler. In der Reihenfolge der Komplexität umfassen dies Folgendes:[2]

  • Buchstaben/Ziffernfehler wie L → 1 oder O → 0
  • Einstellige Fehler wie 1 → 2
  • Transpositionsfehler wie 12 → 21
  • Zwillingsfehler wie 11 → 22
  • Jump -Transpositionen Fehler wie 132 → 231
  • Twin -Fehler springen, wie 131 → 232
  • Phonetische Fehler wie 60 → 16 ("sechzig" bis "sechzehn")

Bei der Auswahl eines Systems wird eine hohe Wahrscheinlichkeit, Fehler aufzufangen, gegen Implementierungsschwierigkeiten ausgetauscht. Einfache Überprüfungs -Ziffernsysteme können von Menschen leicht verstanden und implementiert werden, fangen jedoch nicht so viele Fehler auf wie komplexe, für die ausgefeilte Programme erforderlich sind.

Eine wünschenswerte Funktion ist, dass die linke Paddierung mit Nullen die Überprüfung nicht ändern sollte. Auf diese Weise können Zahlen der variablen Länge verwendet und die Länge geändert werden. Wenn die ursprüngliche Nummer eine einzelne Prüfung hinzugefügt wird, wird das System nicht immer erfasst mehrere Fehler wie zwei Ersatzfehler (12 → 34) werden jedoch in der Regel in 90% der Fälle doppelte Fehler aufgenommen (beide Änderungen müssten die Ausgabe durch Aussetzen von Mengen ändern).

Eine sehr einfache Überprüfung der Ziffernmethode wäre, die Summe aller Ziffern zu übernehmen (Digitale Summe) Modulo 10. Dies würde einen einstelligen Fehler aufnehmen, da ein solcher Fehler die Summe immer ändern würde, jedoch keine Transpositionsfehler (zwei Ziffern schalten), da die Neuordnung die Summe nicht ändert.

Eine etwas komplexere Methode besteht darin, die zu nehmen gewichtete Summe der Ziffern, Modulo 10, mit unterschiedlichen Gewichten für jede Zahlenposition.

Um dies zu veranschaulichen, beispielsweise wenn die Gewichte für eine vierstellige Zahl 5, 3, 2, 7 waren und die zu codierte Zahl 4871 betrug, würde man 5 × 4 + 3 × 8 + 2 × 7 + 7 × 1 dauern = 65, d. H. 65 Modulo 10, und die Scheck -Ziffer wäre 5, was 48715 enthält.

Systeme mit Gewichten von 1, 3, 7 oder 9, wobei die Gewichte der benachbarten Zahlen unterschiedlich sind, werden häufig verwendet: Zum Beispiel 3111 31 Gewichte in UPC Codes, 13 13 Gewichte in Ean Zahlen (GS1 -Algorithmus) und die in der United States Bank verwendeten 371 371 371 Gewichte Routing -Transitzahlen. Dieses System erkennt alle einstelligen Fehler und rund 90% der Transpositionsfehler. 1, 3, 7 und 9 werden verwendet, weil sie es sind Coprime Mit 10 ändert sich die Ziffer ändern die Überprüfung der Ziffer. Die Verwendung eines durch 2 oder 5 teilnehmenden Koeffizienten würde Informationen verlieren (da 5 × 0 = 5 × 2 = 5 × 4 = 5 × 6 = 5 × 8 = 0 Modulo 10) und somit einige einstellige Fehler nicht aufnehmen. Die Verwendung unterschiedlicher Gewichte in benachbarten Zahlen bedeutet, dass die meisten Transpositionen die Überprüfung der Überprüfung ändern. Da sich jedoch alle Gewichte um eine gleichmäßige Zahl unterscheiden, fängt dies keine Transpositionen von zwei Ziffern auf 5 Multiplizieren Sie 10.

Der ISBN-10-Code verwendet stattdessen Modulo 11, das Prim- und alle Zahlenpositionen haben unterschiedliche Gewichte 1, 2, ... 10. Dieses System erkennt somit alle einstelligen Substitutions- und Transpositionsfehler (einschließlich Sprungtranspositionen), jedoch bei Die Kosten für die Schecks sind möglicherweise 10, dargestellt durch "x". (Eine Alternative besteht einfach darin, die Seriennummern zu vermeiden, die zu einer "x" -Prüfungsprüfung führen.) ISBN-13 verwendet stattdessen den in EAN-Zahlen verwendeten GS1-Algorithmus.

Kompliziertere Algorithmen umfassen die Luhn -Algorithmus (1954), die 98% der einstelligen Transpositionsfehler erfassen (es erkennt nicht 90 ↔ 09) und die noch anspruchsvolleren Verhoeff -Algorithmus (1969), das alle einstelligen Substitutions- und Transpositionsfehler und viele (aber nicht alle) komplexeren Fehler auffängt. Ähnlich ist ein anderer Zusammenfassung Algebra-basierte Methode die DAMM -Algorithmus (2004) erkennt auch alle einstelligen Fehler und alle benachbarten Transpositionsfehler. Diese drei Methoden verwenden eine einzelne Prüfung und erfassen daher nicht 10% der komplexeren Fehler. Um diese Ausfallrate zu reduzieren, muss mehr als eine Überprüfungsstelle verwendet werden (z. B. das unten verwiesene MODULO 97 -Überprüfungen, auf das zwei Ziffern verwendet werden - für den Algorithmus siehe Internationale Kontonummer) und/oder um einen breiteren Zeichenbereich in der Scheck -Ziffer zu verwenden, z. B. Buchstaben plus Zahlen.

Beispiele

UPC

Die letzte Ziffer von a Universeller Produkt Code ist eine Prüfung, die wie folgt berechnet wird:[3]

  1. Fügen Sie die Ziffern in den ungeraden Positionen von rechts (zuerst, dritter, fünfter usw. - nicht mit der Überprüfung der Prüfung zusammen) und multiplizieren Sie sie mit drei.
  2. Fügen Sie das Ergebnis (zweite, vierte, sechste usw.) die Ziffern (bis zu, aber nicht die Überprüfung der Überprüfung) in die geraden Positionen hinzu (zweite, vierte, sechste usw.).
  3. Nehmen Sie den Rest des Ergebniss geteilt durch 10 (dh der Modulo 10 -Operation). Wenn der Rest gleich 0 entspricht, verwenden Sie 0 als Überprüfungsstellen. Wenn nicht 0 den Rest von 10 subtrahieren, um die Überprüfung der Ziffer abzuleiten.

Zum Beispiel ist der UPC-A-Barcode für eine Schachtel mit Gewebe "036000241457". Die letzte Ziffer ist die Überprüfung "7", und wenn die anderen Zahlen korrekt sind, muss die Überprüfung der Ziffer -Berechnung 7 erzeugen.

  1. Fügen Sie die ungeraden Ziffern hinzu: 0+6+0+2+1+5 = 14.
  2. Multiplizieren Sie das Ergebnis mit 3: 14 × 3 = 42.
  3. Fügen Sie die gleichmäßigen Ziffern hinzu: 3+0+0+4+4 = 11.
  4. Fügen Sie die beiden Ergebnisse zusammen hinzu: 42 + 11 = 53.
  5. Um die Überprüfung der Überprüfung zu berechnen, nehmen Sie den Rest von (53 /10), der auch als (53 Modulo 10) bekannt ist, und falls nicht 0, von 10 subtrahieren ) = 5 Rest 3; 10 - 3 = 7.

Ein weiteres Beispiel: Berechnung der Überprüfung der folgenden Lebensmittel "01010101010x".

  1. Fügen Sie die ungeraden Ziffern hinzu: 0+0+0+0+0+0 = 0.
  2. Multiplizieren Sie das Ergebnis mit 3: 0 x 3 = 0.
  3. Fügen Sie die gleichmäßigen Ziffern hinzu: 1+1+1+1+1 = 5.
  4. Fügen Sie die beiden Ergebnisse zusammen hinzu: 0 + 5 = 5.
  5. Um die Überprüfung der Überprüfung zu berechnen, nehmen Sie den Rest von (5/10), der auch als (5 Modulo 10) bekannt ist, und falls nicht 0, von 10: d. H. (5/10) = 0 Rest 5; (10 - 5) = 5. Daher die Überprüfung der Überprüfung x Wert ist 5.

ISBN 10

Weitere Informationen: Internationale Standardbuchnummer § ISBN-10 Check-Ziffern

Der letzte Charakter eines zehnstelligen Charakters Internationale Standardbuchnummer ist eine prüfende Ziffer berechnet, die so berechnet wird, dass jede Ziffer mit ihrer Position in der Zahl (von rechts zählt) und die Summe dieser Produkte einnimmt Modulo 11 ist 0. Die Ziffer Die am weitesten rechts (was mit 1 multipliziert wird) ist die Prüfung, die für die korrekte Summe ausgewählt wurde. Es muss möglicherweise den Wert 10 haben, der als Buchstabe X dargestellt wird. Nehmen Sie zum Beispiel die ISBN0-201-53082-1: Die Summe der Produkte beträgt 0 × 10 + 2 × 9 + 0 × 8 + 1 × 7 + 5 × 6 + 3 × 5 + 0 × 4 + 8 × 3 + 2 × 2 + 1 × 1 = 99 ≡ 0 (Mod 11). Das ISBN ist also gültig. Beachten Sie, dass Positionen auch von links gezählt werden können. In diesem Fall wird die Überprüfung mit 10 multipliziert, um die Gültigkeit zu überprüfen: 0 × 1 + 2 × 2 + 0 × 3 + 1 × 4 + 5 × 5 + 3 × 6 + 0 × 7 + 8 × 8 + 2 × 9 + 1 × 10 = 143 ≡ 0 (Mod 11).

ISBN 13

Weitere Informationen: Internationale Standardbuchnummer § ISBN-13 Überprüfen Sie die Ziffernberechnung

ISBN 13 (im Januar 2007 in Gebrauch) entspricht dem EAN-13 Code unter dem Barcode eines Buches gefunden. Die Überprüfung wird genauso erzeugt wie das UPC, außer dass die gerade Ziffern mit 3 anstelle der ungeraden Ziffern multipliziert werden.[4]

EAN (GLN, GTIN, EAN -Nummern von GS1 verwaltet)

Ean (Europäische Artikelnummer) Ziffern überprüfen (verwaltet von GS1) werden berechnet, indem jede der ungeraden Positionsnummern mit 3 multipliziert und dann die Summe der gerade Positionsnummern hinzugefügt wird. Die Zahlen werden von rechts nach links untersucht, daher ist die erste ungerade Position die letzte Ziffer im Code. Die endgültige Ziffer des Ergebnisses wird von 10 abgezogen, um die Überprüfung der Ziffer zu berechnen (oder nach links is, wenn es bereits Null ist). Ein GS1 -Überprüfungs -Ziffernrechner und detaillierte Dokumentation finden Sie online unter GS1's Website.[5] Eine andere offizielle Taschenrechnerseite zeigt, dass der Mechanismus für GTIN-13 für gleich ist für Globale Standortnummer/Gln.[6]

NCDA

Der Noid Check -Ziffernalgorithmus (NCDA),[7] seit 2004 verwendet, ist für die Anwendung in konzipiert anhaltende Kennungen und arbeitet mit variablen Länge von Buchstaben und Ziffern, die als erweiterte Ziffern bezeichnet werden. Es wird häufig mit dem verwendet Arch -Kennung Schema und etwas mit Schemata verwendet, wie das System handhaben und Doi. Eine erweiterte Ziffer ist auf Betanumeric -Zeichen beschränkt, die alphanumerische abzüglich Vokale und den Buchstaben 'L' (Ell) sind. Diese Einschränkung hilft bei der Erzeugung von undurchsichtigen Saiten, die wahrscheinlich nicht aus Versehen Wörter bilden und nicht sowohl O als auch 0 oder L und 1 enthalten. Mit einem Prime-Radix von r = 29 ermöglicht das Betanumeric-Repertoire den Algorithmus, um die Erkennung von Single-Single zu garantieren. Charakter- und Transpositionsfehler[8] Für Zeichenfolgen weniger als r = 29 Zeichen lang (abgesehen davon, dass es eine etwas schwächere Prüfung liefert). Der Algorithmus verallgemeinert jedes Charakterrepertoire mit einem Prime -Radix R und den Zeichenfolgen, die weniger als R -Zeichen lang sind.

Andere Beispiele für Check -Ziffern

International

In den USA

In Mittelamerika

  • Die guatemaltekische Steuerzahl (NIT - Número de Identificación Tributaria) basierend auf Modulo 11.

In Eurasien

In Ozeanien

Algorithmen

Bemerkenswerte Algorithmen umfassen:

Siehe auch

Verweise

  1. ^ "Was ist Check Digit? - Definition von Techopedia". Techopedia.com. Abgerufen 2022-03-16.
  2. ^ Kirtland, Joseph (2001). Identifikationsnummern und Überprüfung der Ziffernschemata. Ressourcenmaterial im Klassenzimmer. Mathematische Vereinigung von Amerika. S. 4–6. ISBN 978-0-88385-720-5.
  3. ^ "GS1 Überprüfen Sie den Ziffernrechner". GS1 uns. 2006. archiviert von das Original am 2008-05-09. Abgerufen 2008-05-21.
  4. ^ "ISBN -Benutzerhandbuch". Internationale ISBN -Agentur. 2005. Abgerufen 2008-05-21.
  5. ^ "Ziffern Rechner überprüfen". GS1. 2005. Abgerufen 2008-05-21.
  6. ^ "Überprüfen Sie den Ziffernrechner, bei GS1 US Official Site". GS1 uns. Abgerufen 2012-08-09.
  7. ^ https://metacpan.org/pod/distribution/noid/noid#noid-check-digit-algorithm
  8. ^ David Bressoud, Stan Wagon, "Computational Number Theory", 2000, Key College Publishing
  9. ^ http://openfigi.com
  10. ^ "Eindeutige Ausweiskarte". Geek Gazette. IEEE Student Branch (Herbst 2011): 16. archiviert von das Original Am 2012-10-24. {{}}: Externer Link in |issue= (Hilfe)
  11. ^ Dr. Chong-yee Khoo (20. Januar 2014). "Neues Format für IP -Anwendungsnummern von Singapur bei iPos". Singapur Patentblog. Cantab ip. Abgerufen 6. Juli 2014.

Externe Links

  • Identifikationsnummern und Überprüfungsschemata (eine mathematische Erläuterung verschiedener Überprüfungs -Ziffernschemata)
  • UPC-, EAN- und SCC-14-Ziffernrechner prüfen
  • GS1 Überprüfen Sie den Ziffernrechner