QR-Code

Die QR-Codes erfahren gerade einen nie dagewesenen Hype. Nicht nur in Deutschland wird eine aktuelle Corona-Impfung per QR-Code nachgewiesen. In der ganzen Welt hat das Virus für einen neuen Höhenflug der inzwischen fast 30 Jahre alten Erfindung geführt. Zeit, einmal genauer hinzusehen.

Der QR-Code ist ein zweidimensionaler Code. Auf einer Fläche (zwei Dimensionen) sind unzählige schwarze und weiße Quadrate untergebracht, von denen (fast) jedes ein Bit, also eine 1 oder 0 repräsentiert (schwarz oder weiß). Allein hierdurch wird deutlich, dass das System geschaffen ist, um von Maschinen gelesen zu werden und nicht etwa von Menschen. Vorläufer des QR-Codes war eine Armada aus unterschiedlichen eindimensionalen Codes, den Strichcodes oder Barcodes, wie man sie auch heute noch vom EAN-Code aus dem Einzelhandel kennt oder vom ISBN-Code auf jeder Buch-Rückseite. Auch Strichcodes erstrecken sich über eine Fläche, jedoch sind die eigentlichen Informationen (die Bits) nur in einer Richtung (Dimension) codiert (quer zu den Strichen).

Wer den QR-Code verstehen will, muss vorher den Strichcode verstehen. Das ist Gott sei Dank nicht so schwer. Auch der Strichcode codiert die Daten durch schwarze und weiße Abschnitte. Anders als beim QR-Code stellen diese Abschnitte aber nicht direkt binäre Bits dar. Stattdessen entsprechen bestimmte Schwarz-Weiß-Folgen bestimmten Zeichen, manchmal rein numerischen Zeichen (0-9, z.B. beim EAN-Code) manchmal auch alphanumerische. Um diese Schwarz-Weiß-Folgen zu lesen, wird ein Barcode-Scanner benötigt. In der einfachsten Form ist dies eine Art Stift, der per Hand mit der Scanner-Spitze über den Code gezogen werden muss. An dieser Spitze befindet sich neben einer Leuchtdiode als Lichtquelle ein Phototransistor. Dieser erkennt die schwarzen und weißen Bereiche als dunkle und helle Abschnitte. Schafft man es, den Stift mit relativ gleichförmiger Geschwindigkeit über den Code zu führen, dann scannt er ein genaues Abbild des Codes, das nun im elektronischen Format vorliegt. Die nachgeschaltete Elektronik kann diese Daten dann analysieren, in die codierten Zahlen und/oder Buchstaben umsetzen und diese an den angeschlossenen Computer senden.

Dies war die erste funktionierende Barcode-Technik aus den 70er Jahren. Das gleichförmig-über-den-Barcode-Führen des Stifts war damals die eigentliche Challenge beim Scannen. Daher folgten bald CCD-Scanner, die diese Bewegung überflüssig machten, da sie den Code aus kurzer Entfernung „in einem Rutsch“ einlesen konnten. Später wurden sie durch Laser-Scanner ersetzt, bei denen ein Laserstrahl mit mehr oder weniger komplizierten Spiegel- und Linsensystemen über den Code geführt wurde. All diesen Methoden gemeinsam war, dass der Mensch den Scanner passend zum Barcode ausrichten musste – durch Ziehen des Stiftes quer zu den Linien oder durch korrektes Ausrichten des Laser-Scanners. Man könnte auch sagen, der Mensch musste sich um die Lage der informationstragenden Dimension auf der bedruckten Fläche kümmern. Das war nicht sonderlich schwer, führte aber dennoch immer wieder zu Verrenkungen. Daher kamen schließlich Laser-Scanner auf den Markt, die diese Aufgabe selbst übernahmen: Blitzschnell tasteten sie den fraglichen Bereich selbsttätig in verschiedensten Richtungen ab, bis sie etwas Verwertbares erfassen konnten. Auf diese Weise funktioniert noch heute jede Scanner-Kasse im Supermarkt.

Was heute im Supermarkt niemand mehr hinterfragt, wurde in den 70er Jahren weltweit eingeführt. Tatsächlich aber tüftelten Norman Joseph Woodland und Bernard Silver, Studenten und später Dozenten an der Drexel University in Philadelphia, schon ab 1949 an der Barcode-Technologie und erhielten 1952 auch ein Patent darauf. Auch wenn die allerersten Ideen zu diesem Thema schon aus den 1930er Jahren stammen, gelten Woodland und Silver als die Erfinder des Barcodes. Es dauerte anschließend aber noch etwa 20 Jahre, bis alle technischen Probleme soweit gelöst waren, bis der erste Barcode an einer Kasse gelesen werden konnte (eine Packung Wrigley's-Kaugummis in Ohio). Der UPC war geboren, der Universal Product Code (Vorlage für den europäischen EAN-Code), an dem auch Norman Joseph Woodland maßgeblich mitgearbeitet hatte und wofür er von George Bush mit dem National Medal of Technology ausgezeichnet wurde. Die Drexel University berichtet ausführlich über diese Zeit in ihrem Blog.

Barcodes wurden mit der Zeit immer perfekter. Durch bessere Druckmethoden und Scanner enthielten sie immer mehr Daten und konnten schneller und zuverlässiger gelesen werden. Doch natürlich bestand dennoch der Wunsch nach mehr. Die ersten zweidimensionalen Codes wurden Ende der 80er eingeführt. Voraussetzung hierfür waren Scanner mit einer Kamera, die spätestens in den 90ern zur Verfügung standen. Durchgesetzt haben sich 2D-Code nur in speziellen Bereichen in der Logistik (z.B. der MaxiCode bei UPS oder der Aztec-Code bei der Deutschen Bahn).

Dann kam schließlich das Jahr 1992. Masahiko Hara, Ingenieur beim japanischen Toyota-Zulieferer Denso Wave, wurde beauftragt, einen neuen Code mit besonders großer Datendichte und sehr schneller Lesefähigkeit zu entwickeln. In einem Interview sagte er: „We will develop a compact code that can store more information, including kanji and kana characters, and at the same time can be read at higher speed“ („Wir entwickeln einen kompakten Code, der mehr Informationen speichern kann, einschließlich Kanji und Kana [japanische Schriftsysteme], und gleichzeitig schneller lesbar ist“). Anderthalb Jahre dauerte die Entwicklung. Genaueres kann auf der Denso-Wave-Webpräsenz nachgelesen werden. Das Ergebnis ist jedenfalls eine zweidimensionale Rastermatrix aus schwarzen und weißen Quadraten. Wie andere 2D-Codes wird der QR-Code beim Scannen von einer Kamera erfasst. Die größte Hürde beim Dekodieren ist die Erkennung der Ausrichtung des Codes, also wo "oben" ist. Gelöst wurde das Problem beim QR-Code durch markante Muster innerhalb des Codes, die fest vorgegeben sind. Um eine geeignete Form für diese Muster zu finden, untersuchte das nur zweiköpfige Team von Masahiro Hara unzählige Drucksachen auf verschiedenen Untergründen und hob schließlich die drei prominenten Quadrat-Muster aus der Taufe, die seitdem jeder QR-Code enthält: Ein schwarzes Quadrat mit weißem Rand, den wiederum ein schwarzer Rand umgibt. Bei besonders großen Codes kommen weitere, kleinere Muster hinzu, die insbesondere bei verzerrten Scans (durch unebene Untergründe) die Ausrichtung erleichtern. Weiterhin sind zwei Linien aus streng abwechselnden schwarzen und weißen Feldern fest vorgegeben, aus denen sich das Raster der Matrix genau ergibt. Zu guter Letzt ist ein vollständig weißer Rand um den gesamten QR-Code wichtig, um den Code klar in einer bedruckten Umgebung zu erkennen.

Aber wie funktioniert nun das Lesen eines QR-Codes?

• Der Code und seine unmittelbare Umgebung werden mit einer Kamera aufgenommen – heute z.B. mit einer einfachen Handy-Kamera.
• Das Bild wird von einer Software untersucht, die zunächst die drei großen Quadrat-Muster in den Ecken finden muss. Mit ihrer Hilfe erkennt die Software nicht nur die Ausdehnung des Codes, sondern auch seine genaue Ausrichtung (da die Muster nur in drei der vier Ecken vorhanden sind). Die kleineren Ausrichtungsmuster helfen dabei, insbesondere bei besonders großen Codes oder einer unebenen Druckfläche (Verzerrung des Bildes).
• Die Software betrachtet das Bild ab jetzt in korrekter Ausrichtung, also mit streng horizontalem und vertikalem Raster.
• Die Auflösung des Rasters kann anschließend exakt durch die beiden Linien aus abwechselnden schwarzen und weißen Feldern bestimmt werden. Dieses Raster steht eigentlich schon durch die Form der drei großen Quadrat-Muster fest (diese haben ein Schwarz-Weiß-Verhältnis von 1:1:3:1:1), doch durch die Linien ist eine genauere und robustere Bestimmung möglich.
• Jetzt kann das Programm die eigentlichen Daten bitweise auslesen. Dabei muss es bestimmte Bereiche beachten, in denen verschiedene Datenabschnitte liegen. Dies sind: Die Code-Version, das Datenformat und letztlich die reinen Nutzdaten (inkl. Fehlerkorrekturdaten).
• Wenn alles gut läuft, liegen die Nutzdaten nun im Klartext als Bitfolge vor. Bei beschädigten Codes oder schlechten Lesebedingungen aber können einzelne Bits verloren oder uneindeutig sein. In diesen Fällen hilft eine weitreichende Fehlerkorrektur, auf die hier nicht weiter eingegangen werden soll. Beim QR-Code ist es möglich, die kompletten Daten auch dann zu rekonstruieren, wenn bis zu 30% unlesbar sind.

Neben einer hohen Datendichte sind die großen Vorteile des QR-Codes die sehr schnelle Lesbarkeit und die Robustheit gegen Verschmutzung oder Beschädigung. Mit diesen Merkmalen gelang es dem QR-Code ab 1994 schnell, im industriellen Bereich Fuß zu fassen. Doch nicht nur im Produktionsumfeld von Toyota konnte sich der QR-Code etablieren. Zwar ist der QR-Code als Markenzeichen von Denso Wave eingetragen, die Spezifikationen aber wurden von der Firma offengelegt und der Gebrauch ist weltweit lizenz- und kostenfrei möglich. So ist es zu erklären, warum sich der Code so weit ausbreitete. Heute ist er auf jedem Konzert-Ticket zu sehen, auf jedem Werbeplakat und – wie angedeutet – auf jeder Impfbescheinigung.

Spätestens seit ihn jedes Handy lesen kann, hat dieser skurrile Labyrinth-Muster-Code unsere Gesellschaft durchdrungen. Wir alle benutzen ihn heute auf die eine oder andere Weise, doch – lesen können wir ihn nicht. Das habe ich nun geändert :-)