www.manuel-einfalt.de

Hier gibt es eine interaktive Einführung in die Grundlagen des QR-Codes. Jedes ausgegebene Zwischenergebnis sowie das Endergebnis (am Ende dieser Seite) kann mit einem einfachen Mausklick auf das Bild heruntergeladen werden. Der Zoom definiert die Kantenlänge der QR-Module in Pixeln.

Eingabe: Fehlerkorrekturlevel:

Um den RS-Codes vollständig zu verstehen, sind einige mathematische Grundkenntnisse nötig. Einen vollständigen Einstieg in die Theorie liefert z.B. Algebra (Serge Lang). Nötig sind diese Grundlagen, weil RS-Codes aus Polynomen über endlichen Körpern berechnet werden. Die Addition und Multiplikation in Körpern mit 2 oder 256 Elementen unterscheidet sich von der Addition oder Multiplikation in reellen, komplexen oder rationalen Zahlen.

1. Grundgerüst

Dieser Teil eines QR-Codes ist immer gleich. Oben links, oben rechts und unten links befinden sich die Finder Pattern, die schwarzweißen Linien heißen timing Pattern, das schwarze Modul rechts der Finder Pattern unten ist das "dark Modul". Ab Version 2 kommen zusätzlich alignment Pattern hinzu.
Der blau markierte Teil ist der Bereich, in dem später Daten und Error Correction Code abgelegt werden und auf den grünen Linien werden die Versionsinformationen gespeichert. Dazu später mehr.

2. Benutzerdefinierte Daten

Die oben eingegebenen Zeichen werden mit folgenden Zahlenwerten kodiert:

Den Daten werden die 4 Bits 0100 vorangestellt, die das Datenpaket als Bytes kennzeichnen. Wollten wir numerische Daten kodieren (die Ziffern 0-9), wären die ersten Bits 0001. Für eine alphanumerische Zeichenfolge (hier gäbe es nur Großbuchstaben) die Bits 0010. Ein Kanji-Block würde mit den Bits 1000 beginnen und ein ECI-Header, mit dem man eine beliebige Kodierung definieren könnte, würde mit 0111 beginnen. In unserem Beispiel (Bytes) bleibt es dem Scanner überlassen, ob er die hinterlegten Daten als UTF-8 oder als ISO-8859-1 interpretiert.
Nach den ersten vier Bytes folgen 8 Bit, in denen die Länge der Daten kodiert werden. Dann folgen direkt die Daten. Die letzten 4 Bits sind '0000', damit man ein vielfaches von 8 Bits erhält und diese bequem in Bytes unterbringen kann. Insgesamt haben wir jetzt:

0100, , , 0000

3. Aufstellen der Polynome

Diese Bitfolge wird nun als Polynom aufgefasst. Jeder Koeffizient besteht aus einer Zahl, die aus 8 Bits kodiert wurde. Die obige Bitfolge wird dabei von links nach rechts gelesen.
Dieser QR-Code ist von der Version und besitzt Platz für Bytes (inkl Mode-Indicator, hier wie gesagt 0100 und der 8 Bits für die Datengröße). Wir brauchen also ein Polynom vom Grad . Wir beginnen damit, die Daten von links nach rechts in den jeweils größten noch nicht verwendeten Koeffizienten dieses Polynoms einzutragen. Sollte der Datenstring komplett in dem Polynom stehen, wird dieses noch mit Zusätzlichen Füllbytes (236, 17, 236, 17, ...) ergänzt, dass "ungenutzte" Koeffizienten nicht = 0 sind.

P (X) =

Das Polynom P muss nun in Blöcke zerteilt werden:

Nun betrachten wir das sogenannte Generatorpolynom:

G (X) =

Zu jedem der oben genannten Datenpolynome

P_{n}

existiert ein Error Correction Code Polynom

R_{n}

R_{n}

entstand durch die Division mit Rest,

P_{n} \cdot X^{} = Q_{n} \cdot G + R_{n}

und

Q_{n} \in 𝔽_{256} [X]

passend gewählt, G ist das Generatorpolynom.

Diese entstandenen Polynome

P_{n}

und

R_{n}

werden nun per Interlacing zu neuen Polynomen P und R zusammengefügt:

$P (X) =$

$R (X) =$

Werden diese Koeffizienten von sämtlichen

P_{n}

und

R_{n}

nun wieder in binäre Werte umgerechnet und in die QR-Matrix eingetragen (0 ist weiß, 1 ist schwarz), entsteht folgendes Bild.

Bewegen Sie die Maus über einen Koeffizienten um zu sehen, wo er in der Matrix eingetragen wurde.

4. Der Format String

Zuletzt müssen noch die oben eingezeichneten grünen Linien mit Inhalt gefüllt werden. Dazu betrachten wir sie zuerst etwas genauer:

Hier stellen die gewählten Farben die Fehlerkorrekturbits des Formatstrings, die Mask Pattern und die Angabe über das Errorcorrection Level dar.

Das Error Correction Level wird wie folgt kodiert:
L: 01 (1)
M: 00 (0)
Q: 11 (3)
H: 10 (2)

Die Mask wird definiert über eine Rechenregel in Form einer logischen Bedingung. Wenn der Term wahr ist, wird das Bit an der Koordinate geflippt (bit xor 1) ansonsten bleibt es unverändert.

000 (0): (x + y) mod 2 == 0
001 (1): y mod 2 == 0
010 (2): x mod 3 == 0
011 (3): (x + y) mod 3 == 0
100 (4): (floor(y/2) + floor(x/3)) mod 2 == 0
101 (5): ( ((x * y) mod 2) + ((x * y) mod 3) ) == 0
110 (6): ( ((y * x) mod 2) + ((y * x) mod 3) ) mod 2 == 0
111 (7): ( ((y + x) mod 2) + ((y * x) mod 3) ) mod 2 == 0

Wobei die (x, y) = (0, 0) wie so oft oben links und (x, y) = (x_max, y_max) unten rechts definiert sind.

Fassen wir die 2 Bits für das Error Correction Level

e_{1}, e_{2}

sowie die 3 Maskierungsbits

m_{1}, m_{2}, m_{3}

zu einem Polynom

e_{1} X^{4} + e_{2} X^{3} + m_{1} X^{2} + m_{2} X + m_{3}

, dann kann man mit dem Generatorpolynom

X^{10} + X^{8} + X^{5} + X^{4} + X^{2} + X + 1

die oben Erwähnten Fehlerkorrekturbits für den Formatstring berechnen.

Wir konstruieren einen Tupel, der versehen mit einer XOR-Operation den Formatstring ergibt:

(\neg e_{1}, e_{2}, \neg m_{1}, m_{2}, \neg m_{3}, f_{1}, f_{2}, f_{3}, f_{4}, f_{5}, \neg f_{6}, f_{7}, f_{8}, \neg f_{9}, f_{0})

wobei

\neg

wie gewohnt die Negation eines Bits, also eine XOR-Verknüpfung mit 1, ist.

5. Penalty-Score

Unten werden für jede eben beschriebene Maskierungs-Bedingung ein QR-Code erzeugt. Für diese Matrizen muss nun eine Zahl gefunden werden, die Auskunft über ihre jeweilige Qualität gibt. Ziel der zuvor erwähnten Maskierung ist, Muster zu vermeiden, die einen QR-Scanner evtl. verwirren könnten, wie mehrere Module der gleichen Farbe nebeneinander. Die Maskierungsfunktionen tauschen in bestimmten Mustern Periodisch den Wert des jeweiligen Moduls. Die Maskierung mit dem geringsten Penalty-Score wird ist dann der zu verwendende QR-Code. Theoretisch sind aber alle folgend aufgelisteten QR-Codes scanbar, manche besser und manche schlechter.

Nun die Evaluierungsbedingungen:

Berechnung 1: Überprüfe alle Zeilen und alle Spalten. Falls 5 Module mit dem gleichen Wert nebeneinader bzw. untereinander auftauchen, erhöhe den aktuellen Penalty-Score um 3, Tauchen danach weitere gleiche Module auf, addiere nochmal 1 zum Penalty-Score. ZB. würden 5 weiße Module zu einem Score von 3 führen, 6 weiße zu einem Score von 4. 7 schwarze liefern einen Wert von 5. usw.

Berechnung 2: Überprüfe die Matrix nach 2x2-Teilmatrizen, die den selben Wert haben, also komplett weiße oder komplett schwarze 2x2-Quadrate sind. Addiere für jedes solcher Quadrate 3 zum Penalty-Score. Die Quadrate können sich überlappen.

Berechnung 3: Überprüfe die Matrix nach der den Zeilen/Spalten 10111010000 oder 00001011101, wobei 1 ein schwarzes Modul und 0 ein weißes Modul repräsentiert.

Berechnung 4: Sei p der Prozentwert der in der Matrix schwarz gefärbten Module. und a das größte ganzzahlige Vielfache von 5 mit a < p sowie b das kleinste ganzzahlige Vielfache von 5 mit p < b.
Der Penalty-Score für diesen Schritt ist nun: min(|50 - a|, |50 - b|) * 10 / 5

Die Summe aller berechneten Penalty-Scores wird nun verglichen und die Maskierung mit der kleinsten Zahl wird als Endergebnis verwendet, siehe ganz unten.

Mask 0:

Mask 1:

Mask 2:

Mask 3:

Mask 4:

Mask 5:

Mask 6:

Mask 7:

Der QR-Code mit dem besten Penalty-Score ist: Mask_

nocookies html5
Impressum