QR Codes: Funktionsweise und Aufbau

Nachdem wir uns vorgestern damit beschäftigt haben, wie QR-Codes entstanden sind und uns gestern angesehen haben, was man alles mit ihnen machen kann und wie man sie erstellt, wollen wir uns heute mal der Frage widmen, wie sie technisch funktionieren. Auf diesem Wissen aufbauend, habe ich zudem noch ein paar wertvolle Tipps für euch, wie man bei der Generierung vieler QR-Codes mit variierender Datenmenge trotzdem zu optisch einheitlichen Ergebnissen kommt.

Wie ist ein QR-Code aufgebaut?

HIer ist eine schematische Darstellung des Aufbaus eines QR-Codes: Die kleinen Kacheln eines QR-Codes werden als Module bezeichnet. Sie können nur zwei Farben haben – entsprechend wird noch einmal klar, dass es sich beim QR-Code um eine Darstellung für einen Binärcode handelt. Jedes Modul zeigt den Zustand eines einzelnen Bits (0 oder 1), wobei sich je nach Position des Moduls unterscheiden kann, ob Schwarz bzw. Weiß für 1 oder 0 steht. (Dazu kommen wir gleich noch …)

Das Modul unten links, das hier pink markiert ist, heißt Dark Module und repräsentiert die verwendete Farbe für die dunklen Module. Wie man an den weiter unten folgenden Beispielgrafiken aber gut sehen kann, muss die Farbe eigentlich gar nicht einheitlich sein – wichtig ist vor allem ein ausreichender Kontrast.

Die vielen hellblau gefärbten Module sind die eigentlichen Nutzdaten des QR-Codes, die je nach verwendetem Fehlerkorrekturverfahren mit mehr oder weniger viel Redundanz eingebettet werden. (Auch dazu gleich noch mehr …)

Der Rahmen um den QR-Code (hier grau dargestellt) wird als Quiet Zone bezeichnet und dient der klaren Abgrenzung von anderen grafischen Elementen.

Die drei großen, rot markierten Felder an den äußeren Ecken heißen Finder und dienen der Positionsbestimmung. Alle drei Finder zusammen bilden das "Finder pattern".
Wie hier schon erläutert, wurden sie eingeführt, damit man QR-Codes von jeder Richtung aus einlesen kann und sich keine Gedanken darüber zu machen braucht, wie rum man sein Telefon oder Lesegerät halten muss. Anhand der Position des fehlenden Finders kann die korrekte Orientierung immer bestimmt werden.

Zur optischen Trennung der Finder vom Datenmuster dienen die als Separatoren bezeichneten weißen Linien, die hier grün hervorgehoben sind.

Ebenfalls zur (besseren) Positionsbestimmung dienen die türkis gefärbten Alignments, die im Datenmuster des QR-Codes untergebracht sind. Je nach QR-Code-Größe (Version) gibt es sie gar nicht (Version 1), nur einmal (Versionen 2-6) oder mehrfach (ab Version 7 in zunehmender Menge). Die Alignments sind vor allem dafür da, Verzerrungen bei schräg fotografierten QR-Codes zu erkennen. Auf Basis von Abstandsmessungen kann der Scanner dann (mithilfe von Algorithmen aus der Bildbearbeitung) versuchen, die Grafik wieder "geradezuziehen", bevor er das Datenmuster auswertet.

Zwischen den Findern verlaufen zwei Synchronisationslinien (lila eingefärbt), die die Matrixgröße definieren und immer abwechselnd dunkle und helle Module enthalten. Sie können von den Alignments überlagert werden, was aber zu keiner optischen Änderung führt, da die Alignments an den überlappenden Stellen immer die gleiche Farbe haben.

Der gelb markierte Datenbereich enthält die Version des QR-Codes. Sie ist zwei Mal vorhanden. Diese Dopplung dient dem Erhalt der Scanbarkeit des QR-Codes, wenn dieser an einer der Stellen beschädigt oder verdeckt wird.
Bei kleineren QR-Codes (mit einer Version < 7) fehlt die Versionsangabe. In diesem Fall muss sie der Scanner selbst aus der QR-Code-Größe ermitteln. Dabei werden die Größen der Finder sowie der Module erfasst und deren Abstände analysiert (es gibt hier je nach Scanner/Software unterschiedliche Verarbeitungsansätze). Insbesondere bei verzerrt eingelesenen QR-Codes sind hierbei die Synchronisationslinien wichtig, da sie durch die abwechselnde Farbgebung eine genaue Zählung erlauben.

Ist die Versionsangabe vorhanden, besteht sie aus 18 Bit. Sechs Bit werden für die Versionsnummer benötigt (Zahlen von 7 bis 40), die zusätzlichen 12 Bit dienen "nur" der Redundanz, damit sich die Versionsangabe auch bei vereinzelten Lesefehlern noch auswerten lässt. Hierfür (und auch für die Fehlerkorrektur der unten folgenden Datenformatangabe) werden in QR-Codes BCH-Codes genutzt. BCH-Codes basieren auf Polynomdivision und können in diesem konkreten Fall bis zu drei fehlerhaft eingelesene Bits (sog. "Bitflips") erkennen und korrigieren. (Um den Rahmen hier nicht zu sprengen, erkläre ich hier nicht mehr zu BCH-Codes, empfehle aber, sich diese einmal näher anzuschauen, weil es sich dabei um ein sehr schönes und leicht verständliches Fehlerkorrekturkonzept handelt.)

Es gibt 40 verschiedene QR-Code-Versionen. Version 1 hat ein Datenmuster aus 21 x 21 Modulen. In Version 40 sind es 177 x 177 Module. Die Modulanzahl lässt sich anhand der Formel

direkt aus der Versionsangabe ableiten.

Die orangefarbenen Module repräsentieren das verwendete Datenformat. Die Angabe umfasst bei kleineren QR-Codes (bis Version 6) 15 Bit. (Bei größeren QR-Codes sind es mehr Module mit mehr Redundanzinformationen.)
Auch dieser Datensatz ist doppelt im QR-Code abgelegt. Er enthält zwei Bit, welche die Fehlertoleranzklasse angeben und drei Bit, die das genutzte Maskenmuster definieren. Die verbleibenden zehn Bit sind wiederum Fehlerkorrekturinformationen (BCH-Code).

Schreibrichtung

Wie kommen die Daten nun in den QR-Code? Die einzubettenden Informationen werden byteweise zerlegt. Ein Byte umfasst acht Bit, also werden beim Befüllen des QR-Codes immer acht Module befüllt. Im Kontext von QR-Codes nennt man die Acht-Bit-Blöcke Codewörter. Sie werden von unten rechts beginnend in einem Zickzackmuster in den QR-Code eingetragen. Dieses verläuft primär vertikal, umfasst dabei aber immer zwei nebeineinanderliegende Module, zwischen denen es auch horizontal pendelt: Natürlich müssen beim Befüllen die oben genannten Strukturelemente, die nicht zum Nutzdatenbereich des QR-Codes gehören, übersprungen werden. Je nach QR-Code-Version, ist die zur Verfügung stehenden Modulanzahl nicht durch Acht teilbar, sodass sich am Ende kein ganzes Codewort (Byte) mehr eintragen ließe. Das Schema hier zeigt einen QR-Code in Version 2. Bei diesem bleiben am Ende (links) sieben Restbits übrig. Diese werden automatisch mit Nullen belegt – was aber nicht heißt, dass sie im Ergebnis weiß dargestellt werden, wie wir im nächsten Abschnitt sehen werden.

Bei größeren QR-Codes und stärkerer Fehlerkorrektur werden die Codewörter vor der Eintragung auf mehrere Gruppen (mit jeweils eigener Fehlerkorrektur) aufgeteilt und dann abwechselnd eingetragen – ähnlich wie beim Reißverschlussverfahren im Straßenverkehr. Das Verfahren wird als Interleaving bezeichnet. Dadurch liegen Codewörter, die im Text aufeinanderfolgen, im QR-Code nicht direkt nebeneinander. Eine partielle Beschädigung oder Verdeckung des QR-Codes verteilt sich so eher auf mehrere Gruppen, sodass der QR-Code mit einer höheren Wahrscheinlichkeit dennoch eingelesen werden kann.

Maskenmuster

Aus den drei Bit für das Maskenmuster ergeben sich 2³ = 8 verschiedene Varianten (000, 001, 010, 011, 100, 101, 110, 111). Das verwendete Maskenmuster legt fest, welche Farbe ein Bit an der jeweiligen Stelle im QR-Code in Abhängigkeit von seinem Wert (0 oder 1) haben soll: Konkret heißt das also, dass ein Bit mit dem Wert 1 an einer Stelle des QR-Codes hell ist und an einer anderen dunkel. Dies ist so umgesetzt, um Störfaktoren beim Einlesen des QR-Codes zu minimieren. Beispielsweise soll vermieden werden, das große einfarbige Flächen entstehen oder Modulmuster, die mit einem Finder oder Alignment verwechselt werden könnten. Es ist die Aufgabe des QR-Code-Generators, ein passendes Maskenmuster für den jeweiligen QR-Code zu finden, das solche Probleme minimiert.

Zu Demonstrationszwecken habe ich hier einmal vier weitere QR-Codes erstellt, die den gleichen Inhalt haben, wie der QR-Code oben in der Schema-Grafik. Diesen hatte ich mit Maskenmuster 2 generiert. Diese QR-Codes nutzen die Maskenmuster 0, 3, 4 und 5:

Fehlerkorrektur

Die Angabe für die Fehlerkorrektur umfasst zwei Bit. Da 2² = 4 ist, ergeben sich also vier mögliche Fehlerkorrekturstufen (00, 01, 10, 11). Je höher die gewählte Fehlerkorrekturstufe eingestellt ist, desto mehr redundante Informationen werden ins Datenmuster des QR-Codes eingebracht. Entsprechend vergrößert sich auch der Bereich des QR-Codes, den man beschädigen oder (zum Beispiel durch das Einfügen eines Logos) verdecken kann, ohne die Lesbarkeit des QR-Codes zu gefährden. Die Redundanzinformationen für die Nutzdaten werden hier übrigens nicht mit einem klassischen BCH-Code erzeugt, sondern mit einem Reed-Solomon-Code. (Erkläre ich jetzt auch nicht näher, die Beschäftigung damit lohnt sich aber ebenfalls.)

Die vier Fehlerkorrekturklassen heißen üblicherweise L, M, Q und H:

• Fehlerkorrektur Level L (Low): bis zu 7 % verdeckt
• Fehlerkorrektur Level M (Medium): bis zu 15 % verdeckt
• Fehlerkorrektur Level Q (Quartile): bis zu 25 % verdeckt
• Fehlerkorrektur Level H (High): bis zu 30 % verdeckt (oft für QR-Codes mit Logo genutzt)

Zur Verdeutlichung habe ich mal diese Grafik erstellt. Der goldene QR-Code nutzt die Fehlerkorrekturstufe L, der lila-orangefarbene QR-Code Fehlerkorrekturlevel M, der grüne QR-Code Level Q und der Regenbogen-QR-Code Level H. Man sieht deutlich die Zunahme an Datenpunkten, die zu einer schrittweisen Verkleinerung der einzelnen Module führt. Auch die Zunahme an Alignments ist sichtbar. Wenn wir noch mehr Daten in einen QR-Code packen, werden es noch mehr:

Warum ändert sich die Größe des Rahmens um den QR-Code?

Neben der Zunahme an Informationen, fällt oben in den vier Grafiken auch auf, dass sich die Größe der Quiet Zone verändert. Die vier QR-Codes enthalten die gleichen Daten und wurden mit dem gleichen QR-Code Generator von t1p.de erstellst. Warum ist das also so?

Es liegt daran, dass ich dem Generator eine Zielgröße (in Pixeln) mitgegeben habe, weil ich eine PNG-Grafik generieren wollte. Bedenkt man die mathematischen Zusammenhänge, wird schnell klar, warum das so sein muss: Beim Rendern des QR-Codes zu einer Pixelgrafik, ist ein Pixel die kleinstmögliche darstellbare Größe. Die Pixel geben ein Raster vor und dieses muss mit dem Raster des QR-Codes in Einklang gebracht werden. Für ein gleichmäßiges Bild, muss also anhand der Modulanzahl des QR-Codes und der Zielgröße der Pixelgrafik eine passende, einheitliche Pixelgröße für ein einzelnes QR-Code-Modul gefunden werden.
Diesem Mapping sind jedoch Grenzen gesetzt, da alle Module des QR-Codes die gleiche Pixelgröße haben müssen und man ein Pixel nicht weiter teilen kann. Um den entstehenden Versatz zwischen einer rechnerisch möglichen Grafikgröße und der vom Nutzer gewünschten Zielgröße zu kompensieren, erfolgt eine automatische Anpassung der Größe der Quiet Zone. In den allermeisten Fällen sind die Anpassungen aber so klein, dass sie nicht auffallen oder zumindest nicht stören.

Praxistipp: Wie kann ich die Rahmengröße des QR-Codes einheitlich halten?

Falls einen dieser Effekt doch stört, kann man entweder zur Erstellung von Vektorgrafiken (wie SVG) übergehen, bei der dieses Pixel-Mapping nicht notwendig ist, oder die gewünschte Zielgröße anpassen. Diese muss man reduzieren, wenn der Weißraum um den QR-Code zu groß wird oder sie anheben, falls er zu klein wird.

Ein anderer Hebel ist die Datenmenge des QR-Codes, welche sich ja durch die einzubettenden Daten und das verwendete Fehlerkorrekturlevel bestimmt. Wenn man keine bestimmte Fehlertoleranzstufe benötigt, kann man mit diesem Parameter spielen und schauen, ob ein besser passendes Ergebnis entsteht.

Wenn man für eine Publikation komplett einheitliche QR-Codes haben möchte, um ein harmonisches Gesamtbild zu erzeugen, geht es aber noch präziser. Denn zumindest bei der Einbettung von Internetadressen kann man leicht dafür sorgen, dass alle QR-Codes die gleiche Datensatzgröße bekommen:
Wie gestern schon erläutert, hat es einige Vorteile, Kurz-URLs statt langer Links in QR-Codes einzubetten. Mithilfe der Kurz-URLs kann man leicht erreichen, dass alle Links die gleiche Länge haben. Die aus unterschiedlich langen Zieladressen entstehende Variabilität wird somit eliminiert und alle QR-Codes erhalten die gleiche Geometrie und insbesondere auch gleich große Quiet Zones. Da t1p.de nicht nur QR-Codes, sondern auch Kurzlinks erzeugt und diese (wenn man keine selbst ausgewählten Kurz-URLs verwendet) immer gleich lang sind, lässt sich auch dieses Problem damit sehr bequem lösen.

Wie viele Daten passen in einen QR-Code?

Nachdem wir den Aufbau von QR-Codes nun analysiert und (hoffentlich) verstanden haben, möchte ich den Artikel mit der Beantwortung einer Frage abschließen, die sehr oft gestellt wird: Wie viele Daten passen denn nun eigentlich in so einen QR-Code?

Diese Tabelle liefert die Antwort. Sie zeigt die in Abhängigkeit von der gewählten Fehlertoleranz nutzbare Datengröße (in Byte) für die einzelnen QR-Code-Versionen.

Version	Module	Bytes in Low	Bytes in Medium	Bytes in Quartile	Bytes in High
1	21×21	17	14	11	7
2	25×25	32	26	20	14
3	29×29	53	42	32	24
4	33×33	78	62	46	34
5	37×37	106	84	60	44
6	41×41	134	106	74	58
7	45×45	154	122	86	64
8	49×49	192	152	108	84
9	53×53	230	180	130	98
10	57×57	271	213	151	119
11	61×61	321	251	177	137
12	65×65	367	287	203	155
13	69×69	425	331	241	177
14	73×73	458	362	258	194
15	77×77	520	412	292	220
16	81×81	586	450	322	250
17	85×85	644	504	364	280
18	89×89	718	560	394	310
19	93×93	792	624	442	338
20	97×97	858	666	482	382
21	101×101	929	711	509	403
22	105×105	1003	779	565	439
23	109×109	1091	857	611	461
24	113×113	1171	911	661	511
25	117×117	1273	997	715	535
26	121×121	1367	1059	751	593
27	125×125	1465	1125	805	625
28	129×129	1528	1190	868	658
29	133×133	1628	1264	908	698
30	137×137	1732	1370	982	742
31	141×141	1840	1452	1030	790
32	145×145	1952	1538	1112	842
33	149×149	2068	1628	1168	898
34	153×153	2188	1722	1228	958
35	157×157	2303	1809	1283	983
36	161×161	2431	1911	1351	1051
37	165×165	2563	1989	1423	1093
38	169×169	2699	2099	1499	1139
39	173×173	2809	2213	1579	1219
40	177×177	2953	2331	1663	1273

Ein QR-Code kann also bis zu 2.953 Byte transportieren. Und man sieht deutlich, wie teuer man sich die Fehlertoleranz erkaufen muss, wenn man einen QR-Code erstellen will, der Beschädigungen ausgesetzt sein könnte oder ein Logo beherbergen soll.

So, das war meine kleine Artikelserie zum Thema QR-Codes.

Geschnatter