Grafische Codes

In vielen praktischen Anwendungen werden digitale Codes grafisch dargestellt, beispielsweise als Aufdruck auf Artikeln, Tickets oder Postern, so dass sie mit optischen Lesegeräten (z. B. Barcode-Scanner) oder Kameras eingelesen und automatisch interpretiert werden können.

Die in der Praxis am häufigsten verwendeten maschinenlesbaren grafischen Codes sind Barcodes (auch Strich-Code oder Balken-Code) und Matrix-Codes (auch 2D-Barcode oder Pixel-Code), die auch mit dem Smartphone mit Hilfe bestimmter Apps gescannt werden können.

Barcodes

Ein Barcode ist ein grafischer Code, der aus parallelen Balken und Lücken unterschiedlicher Breite besteht (in der Regel einfarbig und vertikal). Die digitalen Daten werden hier also als Binärfolgen (= Zeilenpixel) codiert, aus den sich die Darstellung der vertikalen Balken ergibt. Als Beispiel für einen Barcode, dem wir im Alltag sehr häufig begegnen, wird hier der EAN-Barcode behandelt, der für Artikelnummern verwendet wird.

EAN-Barcode

Der EAN-Barcode (EAN ist kurz für European Article Number) spezifiziert einen Barcode zur grafischen Codierung von global eindeutigen Artikelnummern (GTIN, kurz für Global Trade Item Number), der im Einzelhandel und anderen Branchen sehr verbreitet ist.¹ Der Standard-EAN-Barcode hat 13 Ziffern (EAN-13), für kürzere Artikelnummern gibt es auch eine Variante mit 8 Ziffern (EAN-8). Oft ist die Artikelnummer zusätzlich als Klartext unterhalb des Barcodes abgebildet, so dass sie auch manuell erfasst werden kann, wenn das Einscannen nicht funktionieren sollte, beispielsweise weil der Barcode beschädigt ist.

Hier ein dekoratives Beispiel:²

GTIN/ISBN

Eine Artikelnummer im Format GTIN-13 ist immer nach dem folgenden Muster aufgebaut (ähnlich z. B. dem Erzeugercode auf Hühnereiern): Sie besteht aus 13 Ziffern, wobei üblicherweise die ersten 2–3 Ziffern das Länderpräfix³ darstellen, die folgenden 4–5 Ziffern den Hersteller des Produkts kennzeichnen und die folgenden 5 Stellen das Produkt selbst kennzeichnen. Die letzte Ziffer stellt eine Prüfziffer dar, die aus den restlichen 12 Stellen berechnet wird und anhand derer sich überprüfen lässt, ob die GTIN-13 eventuell falsch gelesen wurde (dazu unten mehr).

Eine ISBN (International Standard Book Number) bzw. ISBN-13 ist eine Sonderform der GTIN-13, die speziell zur Kennzeichnung von Büchern verwendet wird und ebenfalls mit dem EAN-Barcode dargestellt wird. Hier wird zu Beginn als Länderpräfix immer die Ziffernfolge 978 oder 979 verwendet (“Bookland”). Die Stellen 4–12 geben hier die Ländergruppe, Verlagsnummer und Titelnummer des Buches an.

Struktur

Der EAN-Barcode stellt die Ziffern der Artikelnummer durch vertikale schwarz-weiße Streifenmuster dar. Dabei werden nur die Stellen 2 bis 13 durch Streifenmuster dargestellt, die Ziffer an der ersten Stelle wird nur indirekt codiert (darauf kommen wir später zurück). Zur Codierung der Ziffern in Streifenmuster werden drei verschiedene Codetabellen verwenden, die hier “Code A”, “Code B” und “Code C” genannt werden.

Der Barcode ist folgendermaßen aufgebaut:

• Der Barcode besteht aus vertikalen Streifen gleicher Breite, die entweder schwarz oder weiß sind, und unterschiedlich breite “Balken” bilden.
• Insgesamt enthält der Barcode je 7 Streifen für jede der 12 dargestellten Ziffern, sowie je 3 abwechselnd schwarze und weiße Streifen als Randzeichen links und rechts und 5 als Trennzeichen in der Mitte.
• Links vom Trennzeichen werden die Stellen 2 bis 7 der Artikelnummer durch Streifenmuster dargestellt, rechts vom Trennzeichen die Stellen 8 bis 13.
• Die sechs Ziffern in der linken Hälfte werden mit den Streifenmustern aus den Tabellen “Code A” und “Code B” dargestellt.
• Die sechs Ziffern in der rechten Hälfte werden dagegen nur mit den Streifenmustern aus Tabelle “Code C” dargestellt (Invertierung von Code A).

Jede Ziffer wird also quasi durch einen 7-stelligen Binärcode codiert, so dass durch die schwarzen und weißen Streifen je zwei schwarze und zwei weiße Balken unterschiedlicher Breite pro Ziffer entstehen. Die Streifenmuster sind dabei so gewählt, dass erkannt werden kann, ob der Barcode von links oder von rechts gescannt wurde, so dass es dadurch nicht zu Verwechslungen kommen kann.

Codevarianten

Welche der beiden Codevarianten A oder B für eine Ziffer aus der linken Hälfte verwendet wird, hängt von der Position der Ziffer, sowie von der ersten Ziffer der Artikelnummer ab. Die Tabelle auf der rechten Seite stellt dar, in welcher Reihenfolge die beiden Codevarianten für die 6 Ziffern in der linken Hälfte in Abhängigkeit von der ersten Ziffer der Artikelnummer gewählt werden.

Die erste Ziffer ist im Barcode also indirekt über die Ziffern in der linken Hälfte codiert: Je nachdem, welchen Wert die 1. Ziffer hat, wird für jede der Ziffern an den Stellen 2–7 ein Streifenmuster aus Codetabelle A oder B gewählt. Beim Decodieren werden die Ziffern in der linken Hälfte mit den beiden Codetabelle A und B decodiert und aus der Reihenfolge der Codevarianten die 1. Ziffer decodiert.

Der Grund für diese umständliche Codierung der ersten Ziffer liegt darin, dass der EAN-Barcode den in den USA verbreiteten 12-stelligen UPC-Barcode (Universal Product Code) erweitert, so dass Lesegeräte für EAN-Barcodes auch UPC-Barcodes lesen können. Der UPC-Barcode verwendet dabei für die Ziffern in der linken Hälfte nur die Codevariante A, entspricht also einer GTIN-13 mit führender Null.

Interaktiver EAN-Barcode

Tool: Im folgenden interaktiven EAN-Barcode können Sie austesten, wie sich der Barcode für verschiedene Eingabewerte ändert. Klicken Sie auf eine Ziffer, um sie zu ändern oder tragen Sie eine GTIN über das Eingabefeld ein (ohne Bindestriche oder Leerzeichen). Mit den Schaltflächen können Sie die verwendeten Codierungen (A/B/C) anzeigen, Hilfslinien ein-/ausblenden und die Prüfziffer der Eingabe überprüfen.

Erkunden Sie den Aufbau des Barcodes beispielsweise folgendermaßen:

• Klicken Sie auf “Codierung anzeigen” und anschließend mehrmals auf die erste Ziffer, um zu sehen, wie sich die Codierungen in der linken Hälfte in Abhängigkeit von der ersten Ziffer ändern (Code A/B), während die Codierungen in der rechten Hälfte gleich bleiben (Code C).
• Klicken Sie auf “Prüfziffer anzeigen” und anschließend mehrmals auf Ziffern an geraden oder ungeraden Stellen, um zu sehen, wie sich die erwartete Prüfziffer ändert.
  Im folgenden Abschnitt wird erläutert, wie die Prüfziffer zustandekommt.

Prüfziffer

Beim Einscannen des Barcodes kann es passieren, dass die GTIN-Artikelnummer falsch eingelesen wird, beispielsweise aufgrund von Verdeckungen, Deformationen oder Beschädigungen des Barcodes. Um solche Situationen zu erkennen, enthält die GTIN redundante Information: Konkret codieren nur die ersten 12 Ziffern die relevanten Informationen über das Produkt, während die letzte Ziffer (“Prüfziffer”) nach einer bestimmten Formel aus den übrigen Daten berechnet wird. So kann anhand der gelesenen Ziffern überprüft werden, ob bestimmte Fehler beim Einlesen aufgetreten sind.

Die Prüfziffer der GTIN wird also mit dem folgenden Algorithmus berechnet:

• Summiere die ersten 12 Ziffern der GTIN. Multipliziere dabei alle Ziffern an geraden Stellen mit 3.
• Die Prüfziffer ist die Differenz der Summe zur nächstgrößeren Zahl, die ohne Rest durch 10 teilbar ist (oder 0 wenn die Summe selbst ohne Rest durch 10 teilbar ist).

Formel: Wenn also die einzelnen Ziffern der GTIN mit z₁ bis z₁₃ bezeichnet werden, ergibt sich die Prüfziffer z₁₃ durch die folgende Formel:⁴

$$z_{13} = (10 - ((z_1 + 3 \cdot z_2 + z_3 + 3 \cdot z_4 + … + 3 \cdot z_{12}) \ mod \ 10)) \ mod \ 10$$

Beispiel: Für die ISBN 978-3-486-71751-? soll die Prüfziffer berechnet werden. Die Quersumme mit dreifacher Gewichtung der geraden Stellen ergibt:

$$9 + 8 + 4 + 6 + 1 + 5 + 3 \cdot (7 + 3 + 8 + 7 + 7 + 1) = 33 + 3 \cdot 33 = 132$$

Also lautet die Prüfziffer 8, nämlich die Differenz zu 140 bzw. das Ergebnis von:

$$z_{13} = (10 - (132 \ mod \ 10)) \ mod \ 10 = (10 - 2) \ mod \ 10 = 8$$

Die vollständige ISBN lautet also 978-3-486-71751-8.

Um eine gegebene GTIN zu überprüfen, wird einfach die gewichtete Quersumme inkl. Prüfziffer berechnet und geprüft, ob das Ergebnis ohne Rest durch 10 teilbar ist.

Beispiel: Der Barcode-Scanner liest aus einem EAN-Barcode die ISBN 978-1-234-56789-1. Die Quersumme mit dreifacher Gewichtung der geraden Stellen ergibt:

$$9 + 8 + 2 + 4 + 6 + 8 + 1 + 3 \cdot (7 + 1 + 3 + 5 + 7 + 9) = 38 + 3 \cdot 32 = 134$$

Das Ergebnis ist nicht ohne Rest durch 10 teilbar. Der EAN-Barcode ist also vom Barcode-Scanner falsch gelesen worden, er muss entweder erneut gescannt werden oder die Artikelnummer wird manuell eingegeben.

Matrix-Codes

Ein Matrix-Code stellt Binärdaten als zweidimensionale Muster dar, meist als schwarze und weiße quadratische Pixel innerhalb eines Rasters (einer Matrix). Im Gegensatz zu Barcodes können Matrix-Codes deutlich größere Datenmengen speichern und eignen sich so für verschiedenste Anwendungsfälle. Das erlaubt es auch, größere Mengen an redundanter Zusatzinformation zu speichern, so dass die Daten im Zweifelsfall auch dann noch korrekt ausgelesen werden können, wenn Teile des Codes verdeckt oder zerstört sind. Dadurch werden die Codierverfahren aber auch deutlich komplizierter als bei Barcodes.

Bekannte Beispiele sind der Actec-Code (z. B. auf Bahntickets), DataMatrix-Code (z. B. auf Briefmarken) und der QR-Code (vielseitig einsetzbar, u. a. zum Codieren von Internetadressen). Der folgende QR-Code codiert beispielsweise die URL dieses Online-Skripts – wird dieser QR-Code mit einer geeignete Smartphone-App gescannt, kann die URL im Browser geöffnet werden:

Fachkonzept: Prüfsumme

Bei den oben beschriebenen GTINs wurde eine zusätzliche Ziffer angehängt, so dass die (auf eine bestimmte Weise gewichtete) Quersumme ein Vielfaches von 10 ist. So konnte beim Lesen einer GTIN aus einem EAN-Barcode ggf. erkennt werden, ob die Daten falsch decodiert wurden. Hier wird also eine spezielle Prüfsumme zur Fehlererkennung verwendet.

Eine Prüfsumme (engl. checksum) ist allgemein ein Wert, der aus den Daten und zusätzlicher redundanter Information berechnet wird. Die redundante Information (hier die Prüfziffer) wird dabei so gewählt, dass die Prüfsumme eine bestimmte Eigenschaft hat. Das Lesegerät kann dann durch Berechnen der Prüfsumme und Überprüfen der erwarteten Eigenschaft die Daten validieren, also auf Fehler überprüfen, und bei Abweisungen eventuell sogar erkannte Fehler zu korrigieren.

Prüfsummenbasierte Verfahren stellen eine der einfacheren Möglichkeiten zur Fehlererkennung für digitale Daten dar, die eingelesen oder übertragen werden und dienen oft als Grundlage für komplexere Verfahren. Ziel ist es, typische Fehler zu erkennen, z. B. dass einzelne Werte oder Bits durch widrige Umstände vertauscht, ausgelassen, verdoppelt oder invertiert werden.

Als Prüfsumme für Sequenzen von Ziffern oder Ganzzahlen wird oft die Quersumme (= Summe über alle Elemente der Sequenz) oder die gewichtete Quersumme (mit fest vorgegebenen Gewichtungsfaktoren) verwendet und als Eigenschaft überprüft, ob diese ein ganzzahlig Vielfaches einer vorgegebenen Zahl M darstellt. Um diese Eigenschaft zu erreichen, werden ein oder mehrere Werte zur Sequenz hinzugefügt (Prüfziffern/-zahlen).

Beispiel: Bei der GTIN-13 wird eine zusätzliche Ziffer zur Sequenz aus 12 Ziffern hinzugefügt, so dass die mit den Faktoren 1, 3, 1, … gewichtete Quersumme ein ganzzahlig Vielfaches von 10 ergibt.

Parität

Für binäre Daten wird als Prüfsumme üblicherweise die Parität verwendet (= Quersumme modulo 2), die anschaulich angibt, ob die Anzahl der 1-Bits in einer Bitsequenz gerade (= 0) oder ungerade (= 1) ist. Hier wird an die Daten meist ein zusätzliches Bit angehängt (Paritätsbit), so dass die Parität der Bitsequenz inkl. Paritätsbit gerade ist.

Beispiel: Die Bitsequenz 0110 0010 soll um ein Paritätsbit ergänzt werden, so dass die Gesamtparität gerade ist. Da die Bitsequenz 3 1-Bits enthält, muss das Paritätsbit auch den Wert 1 bekommen.

Ist die Parität einer gelesenen Bitsequenz ungerade, muss ein Fehler vorlegen. Mit einfacher Parität bleiben viele Fehler allerdings unentdeckt, beispielsweise wenn ein 0- und ein 1-Bit vertauscht werden oder wenn gleich viele 0- und 1-Bits “gekippt” sind (hier rot dargestellt):

Als Ausblick: Werden mehrere Paritätsbits für eine Bitsequenz verwendet, lässt sich die Fehlererkennung verbessern und Fehler ggf. sogar beheben.