Einführung in QR Codes
Martin Stoev

Zurück Weiter

Funktionen und Algorithmen

Masking

Beim Masking wird eine XOR-Maske über alle Datenmodule gelegt, die bestimmte Muster, wie das Finder Pattern, in Datenmodulen unterdrücken soll. Dadurch wird eine schnelle Erkennung des Symbols garantiert.

Eine Maske ist eine Funktion mit zwei Parametern f(x,y), die einzelne Koordinaten von Datenmodulen erwartet. Ihr Rückgabewert ist ein Boolean. Nacheinander werden die Koordinaten aller Datenmodule abgefragt, bei True wird die Farbe des Moduls umgekehrt (hell wird zu dunkel und umgekehrt), bei False passiert nichts.

Da nur die Datenmodule davon betroffen sind, werden Metainformationen, Finder-, Alignment- und Timing Patterns nicht maskiert.

Im Standard sind acht solche Funktionen für die XOR-Maske vorgesehen und alle sind in Tabelle 1 dargestellt. Zusätzlich zum eigentlichen Maskierungsvorgang wird die Mask Pattern Referenz in den Formatinformationen abgelegt, sodass eindeutig feststeht welche Funktion für ein Symbol gewählt wurde.

Mask Pattern Referenz Bedingung
000 (i + j) mod 2 = 0
001 i mod 2 = 0
010 j mod 3 = 0
011 (i + j) mod 3 = 0
100 ((i div 2) + (j div 3)) mod 2 = 0
101 (i j) mod 2 + (i j) mod 3 = 0
110 ((i j) mod 2 + (i j) mod 3 = 0
111 ((i j) mod 3 + (i + j) mod 2) mod 2 = 0

Tab. 1: Mask Pattern Referenzen zu Masking Funktionen (vgl. [ISO] S. 50)

Prinzipiell ist es egal welche der Funktionen beim Masking verwendet wird, solange die Referenz richtig ist. Trotzdem sind im Standard bestimmte Kriterien hinterlegt, die helfen sollen die optimale Funktion herauszusuchen.

Ausgangsmatrix wird mit allen Masken kombiniert

Abb. 1: Die Ausgangsmatrix wird mit allen Masken kombiniert

Bei der Auswahl der Maske wird zunächst eine Ausgangsmatrix mit den zu maskierenden Datenmodulen erzeugt (siehe Abbildung 1). Diese wird dann nacheinander mit allen acht Funktionen maskiert und jede maskierte Matrix wird anschließend bewertet. Die Bewertung erfolgt auf Grundlage der Tabelle 2. Wenn ein Bewertungskriterium zutrifft, werden die dazugehörigen Strafpunkte für die jeweilige Matrix hinzugezählt.

Es wird die Referenz der Maske / Funktion ausgewählt, die die wenigsten Strafpunkte hat.

Eigenschaft Bewertungskriterium Punkte
Hintereinander liegende Module in Zeile / Spalte haben die gleiche Farbe Anzahl der gleichfarbigen Module = (5 + i) 3 + i
Block mit Modulen in gleicher Farbe Blockgröße = m * n 3 * (m - 1) * (n - 1)
1:1:3:1:1 Muster in Zeile / Spalte 40
Verhältnis helle zu dunkle Module im gesamten Symbol 50 (5*k)% zu 50±(5*(k+1))% 10 * k

Tab. 2: Bewertungskriterien mit Strafpunkten (vgl. [ISO] S. 52)

Fehlerkorrektur

Für die Fehlerkorrektur in QR Codes wird immer ein Reed-Solomon Code (RS Code) mit Erzeugerpolynom verwendet. Dafür sind insgesamt 4 Fehlerkorrektur Niveaus vorgesehen, die zu jeder Version existieren. Sie können stets über den Indicator referenziert werden (siehe Tabelle 3). Zu einer Version muss das Fehlerkorrektur Niveau ausgewählt werden. L hat die geringste Fehlerkorrekturrate, aber es passen auch die meisten Informationen in das Symbol.

Fehlerkorrektur NiveauWiederherstellungs Kapazität %
L7
M15
Q25
H30

Tab. 3: Fehlerkorrektur Niveau

RS Codes werden auch in anderen bekannten Standards, wie CD (Compact Disk) oder DVB (Digital Video Broadcasting) eingesetzt. Das liegt an ihren vielfältigen Einsatzmöglichkeiten und der variablen Fehlerkorrekturrate.

Bei RS Codes wird mit Koeffizienten von Polynomen über Galois Felder gerechnet. Das bedeutet, dass zunächst ein Symbolalphabet  über ein Galois Feld definiert werden muss. Im Falle der QR Codes wird immer ein Galoisfeld der Größe 2^8 (bzw. 256) verwendet. So entspricht jedes Codewort einem Element dieses Alphabets. Ein solches Element wird häufig auch Symbol genannt, sodass von Daten- und Fehlerkorrektursymbolen gesprochen wird. Diese dürfen jedoch nicht mit den QR Code Symbolen verwechselt werden.

Die notwendigen Erzeugerpolynome sind im Standard definiert und können direkt übernommen werden. Mit dem Erzeugerpolynom wird die Nachricht encodiert und um die Fehlerkorrektursymbole erweitert. Das bedeutet die Nachricht steht in Klartext da, aber zusätzlich gibt es weitere redundante Fehlerkorrekturinformationen. Diese können bei Bedarf herangezogen werden.

Beim decodieren werden die Nachricht und die Fehlerkorrektursymbole ausgelesen. Mit Hilfe mehrerer verschiedener Gleichungssysteme können zunächst die Positionen der Fehler bestimmt und diese dann anschließend verbessert werden.

Die Fehlerkorrekturrate kann bei RS Codes einfach festgelegt werden. Als Faustregel gilt, dass 2t Fehlerkorrektursymbole garantiert t Fehler korrigieren können. Dabei ist die Verteilung der Fehler irrelevant. Sogenannte Burstfehler, also längere Fehlerfolgen, können auch erkannt und behoben werden. Das ist wichtig, denn ein Fleck (z.B. Dreck oder Kaffee) auf einem QR Code verfälscht viele hintereinanderliegende Codewörter.

Es ist jedoch nicht möglich eine 100%ige Fehlerkorrekturrate zu erlangen, da auch die Korrektursymbole ebenfalls Fehler enthalten können.

Für des Generieren und Auslesen von QR Codes ist es nicht wichtig RS Codes im Detail zu verstehen, hier können auch existierende Bibliotheken genutzt werden. Es ist wichtig zu verstehen, dass RS Codes Möglichkeiten bieten Daten robust abzulegen, sodass diese auch bei Fehlern noch korrekt ausgelesen werden können. Trotzdem soll ein kleines Beispiel zumindest das Erzeugen der Fehlerkorrekturdaten bei Reed-Solomon Codes verdeutlichen.

RS Encoding

Für das Beispiel erzeugen wir ein Galoisfeld der Größe 8 mit dem Primitivpolynom Primitivpolynom Die einzelnen Elemente sind in Tabelle 3 dargestellt.

Galois Feld der
                                                  Größe 8

Tab. 3: GF(8) des Erzeugerpolynoms (vgl. [ECC] S. 156)

Nachdem das GF(8) bekannt ist, kann im Folgenden damit gerechnet werden. Es muss bestimmt werden wie hoch die Anzahl der zu korrigierenden Fehler (bzw. die Fehlerkorrekturrate bezogen auf die Nachricht) sein soll. 2t Fehlerkorrektursymbole können t Fehler verbessern. In dem Beispiel werden 4 Fehlerkorrektursymbole berechnet, deswegen können auch garantiert mindestens 2 Fehler korrigiert werden.

Dafür wird ein Polynom benötigt, welches aus 4 Einheitswurzeln des Galoisfeldes besteht. In dem Beispiel berechnen wir das Erzeugerpolynom g(X) mit den vier Einheitswurzeln Einheitswurzeln a0 bis a3. Nach ausmultiplizieren bekommen wir das Erzeugerpolynom g(X) aus Formel 1.

g(x)
                                                           ausrechnen

For. 1: Berechnung für Erzeugerpolynom

Wie schon erwähnt werden jedoch nur die Koeffizienten der Polynome betrachtet. In Koeffizientendarstellung ist g = Erzeugerpolynom in Koeffizentendarstellung.

In dem Beispiel möchten wir die Datensequenz 111001111 encodieren (vgl. [ECC] S. 157). Diese Daten entsprechen dem Polynom Datenpolynom in
                                                                                                            Koeffizentendarstellung in Koeffizientendarstellung.

Beim encodieren wird das Datenpolynom um so viele 0en erweitert, wie es Korrektursymbole gibt. Das erweiterte Datenpolynom wird anschließend durch das Erzeugerpolynom dividiert. Wir verwenden 4 Fehlerkorrektursymbole, also rechnen wir wie in Formel 2.

Polynomdivision zur Berechnung der Korrektursymbole

For. 2: Polynomdivision zur Berechnung der Korrektursymbole

Der Rest enthält die Fehlerkorrektursymbole. Das Ergebnis des Encodings setz sich zusammen aus dem Datenpolynom konkateniert mit dem Rest in Koeffizientendarstellung.

  • Polynomdivision zur Berechnung der Korrektursymbole =111001111101111001010

RS Decoding

Das Decodieren ist wesentlich komplizierter als das Encodieren, da nun die erwähnten Gleichungssysteme ins Spiel kommen. Das Vorgehen wird aufgrund der vielen unübersichtlichen Rechnungen von Polynomen über Galoisfeldern nur skizziert.

Wir erhalten die Nachricht R (siehe Formel 3) mit Fehlerkorrektursymbolen. R ist optimaler Weise Polynomdivision zur Berechnung der Korrektursymbole, aber die Symbole könnten auch falsch sein.

Empfangene Daten

For. 3: Empfangene Daten

Dann berechnen wir die Syndrome indem wir für R(x) nacheinander die Elemente das Galoisfeldes einsetzen. Das wiederholen wir solange bis die Anzahl der Polynome den Fehlerkorrektursymbolen entspricht, so wie in Formel 4.

Syndrome für das
                                                      Beispiel

For. 4: Syndrome für das Beispiel

Dann stellen wir das Gleichungssystem zur Ermittlung der Fehlerpositionen auf. Da in unserem Beispiel bis zu 2 Fehlerkorrekturen möglich sind, muss das Gleichungssystem aus 2 Gleichungen bestehen.

Gleichungssystem zur Ermittlung der Fehlerpositionen

For. 5: Gleichungssystem zur Ermittlung der Fehlerpositionen

Mit der Berechnung von Sigma1 und Sigma2 können wir eine Funktion Fehlerfunktion aufstellen, die uns die Positionen der Fehler liefert, denn für jeden Fehler gilt der Sachverhalt Fehlergleichung.

Die Fehlerpositionen werden für ein weiteres Gleichungssystem (siehe Formel 6) verwendet, in dem die jeweiligen Fehlergrößen Y1 und Y2 bestimmt werden.

Gleichungssystem zur Ermittlung der Fehlergrößen

For. 6: Gleichungssystem zur Ermittlung der Fehlergrößen

Für die Korrektur eines Fehlers wird das Komplement der Fehlergröße zu dem Symbol an der Fehlerposition hinzuaddiert. Anschließend ist die ursprüngliche Nachricht wiederhergestellt.

Encoding

Jetzt da alle Grundlagen bekannt sind, soll ein Beispiel den Encodingprozess verdeutlichen. Dabei werden nacheinander die folgenden sechs Schritte durchlaufen.

  1. Daten encodieren
  2. Fehlerkorrektur Codewörter berechnen
  3. Anfangsmatrix erstellen
  4. Masking Pattern auswählen und anwenden
  5. Formatinformationen und Versionsinformationen hinzufügen
  6. QR Code generieren

In diesem Beispiel werden die Daten "01234567" in einen QR Code mit dem Fehlerkorrektur Niveau M (Referenz 00 -- siehe Tabelle 3) abgelegt. Dafür analysieren wir zunächst die Daten. Es handelt sich nur um Ziffern, deswegen ist der Numeric Mode (Mode Indicator = 0001 -- siehe [Informationen in QR Code Symbolen: Tabelle 2]) optimal. Der Character Count Indicator beträgt 8, da die Daten aus 8 Ziffern bestehen (CCI = 8 bzw. 000000100).

Anschließend suchen wir die optimale Version für das Symbol. Dabei wird immer die kleinste Version herausgesucht, die mehr oder genauso viele Daten enthalten kann, wie durch das Fehlerkorrektur Niveau und den Modus vorgegeben sind. In diesem Fall kann schon Version 1-M 34 (>= 8) Ziffern enthalten (siehe [Informationen in QR Code Symbolen: Tabelle 1]).

Als nächstes müssen wir die Versionsinformationen berechnen, aber unser Symbol der Größe 1-M benötigt diese nicht (Versionen < 7).

Dann encodieren wir die Daten analog zum Beispiel im Kapitel Numeric Mode.

  • Daten: 01234567 -> (012, 345, 67) -> 00000011000101011001I000011

Der Terminator kann in Informationen in QR Code Symbolen: Tabelle 2 nachgelesen werden und hat die Referenz 0000.

Wir konkatenieren die Daten und ergänzen 3 Füllbits (0en), um auf die Größe des nächsthöheren Codeworts zu kommen.

  • Mode Indicator +CCI + Daten + Terminator + Füllbits (6 CW): 00010000 00100000 00001100 01010110 01100001 10000000

Anschließend müssen die 10 (16 CW - 6 CW) verbleibenden Codewörter der Version 1-M aufgefüllt werden. Dafür können wir eine beliebige Bitfolge verwenden.

  • Zufallsdaten (10 CW): 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001

Für die Datencodewörter werden noch die Fehlerkorrekturdaten berechnet und konkateniert.

  • Fehlerkorrektur (10 CW): 10100101 00100100 11010100 11000001 11101101 00110110 11000111 10000111 00101100 01010101

So ergeben sich alle Codewörter, die im Symbol gespeichert werden müssen.

  • Alle Codewörter (26 CW): 00010000 00100000 00001100 01010110 01100001 10000000 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 10100101 00100100 11010100 11000001 11101101 00110110 11000111 10000111 00101100 01010101

Jetzt füllen wir eine Anfangsmatrix mit diesen Daten und wenden alle Masking Patterns darauf an. Wie im Masking Kapitel beschrieben, wählen wir die beste Masking Pattern Referenz, in diesem Fall 011, aus.

Mit diesen Informationen können wir dann die Formatinformationen wie in dem Beispiel des entsprechenden Kapitels errechnen und einfügen. Das ganze ist schematisch in Abbildung 2 dargestellt.

Ausgangsmatrix wird mit allen Masken kombiniert

Abb.2: Die Ausgangsmatrix wird mit allen Masken kombiniert

Daraus resultiert der endgültige Code (siehe Abbildung 3).

Endgültiger Code

Abb.3: Endgültiger Code

Decoding

Um ein QR Code Symbol zu decodieren muss dieses als Bild vorliegen. Dann gibt es eine kurze Erkennungsphase in der das Symbol gefunden, normalisiert und digitalisiert wird. Anschließend wird das Bild nicht mehr benötigt, da die weitere Analyse auf den Daten aufbaut.

Der Decodingprozess ist viel komplizierter als das Encodingprozess und wird im Standard nur als Pseudocode beschrieben. Die konkrete Implementation der einzelnen Funktionen bleibt offen. In Abbildung 3 ist der Ablauf in Form eines Flussdiagrammes abgebildet.

Flussdiagramm
                                                        des
                                                        Decoding-Prozesses

Abb. 3: Flussdiagramm des Decoding-Prozesses

Es folgt eine ausführlichere Beschreibung des Decodings.

  • Zuerst wird der Kontrast des Bildes erhöht, sodass die hellen und dunklen Module leichter erkannt werden können.
  • Dann werden die Finder Pattern anhand ihres charakteristischen Musters (1:1:3:1:1) lokalisiert.
  • Wenn alle Drei gefunden wurden, steht die Orientierung des Symbols fest und es kann richtig ausgerichtet werden.
  • Anschließend werden die Breite der Finder Patterns W_UL, W_UR und die Distanz D zwischen ihnen abgelesen (siehe Abbildung 4), sodass die Modulgröße Modulgröße und die vorläufige Version Vorläufige Versionberechnet werden kann.
  • Wenn die ermittelte Version größer als 6 ist, muss die Version zusätzlich über die Versionsinformationen ausgelesen werden.
  • Bei Versionen > 1, muss das Bild entzerrt werden. Dafür werden die tatsächlichen und die mathematischen Positionen der Alignment Patterns bestimmt. Die daraus resultierende Abweichung wird für die Interpolation der einzelnen Module herangezogen. Bei diesem Vorgang werden zunächst die Alignment Patterns entlang des Timing Patterns vorgezogen, da diese leichter ausgelesen werden können. Das konkrete Vorgehen ist im Kapitel Alignment Patterns beschrieben.
  • Das entzerrte Bild wird in eine Binärmatrix überführt. Dafür wir die Ausprägung aller Module nacheinander festgestellt. Dunkle Module bekommen den binären Wert 1 und Helle den Wert 0.
  • Aus dieser Matrix werden dann die Formatinformationen extrahiert. Die darin enthaltene Mask Pattern Referenz wird verwendet um die Masking Funktion wiederholt anzuwenden. Dann liegt die Matrix unmaskiert vor.
  • Aus dieser Matrix werden die Codewörer sequentiell nach den Richtungsregeln ausgelesen. Diese Informationen werden in Daten und Fehlerkorrektur Codewörter zerlegt.
  • Die Daten werden korrigiert indem das Reed-Solomon Decoding darauf angewendet wird. Resultat sind die ursprünglichen binären Daten der Nachricht.
  • Um die eigentliche Nachricht zu extrahieren müssen die Interpetationsregeln des Modus angewendet werden. Dafür muss der Bitstrom in seine Bestandteile zerlegt werden (Mode Indicator, CCI, Daten, Terminator usw.).
  • Die Daten werden nach den Regeln des Modus interpretiert. Das Resultat ist die ursprüngliche Nachricht.
Auszulesende Größen

Abb. 4: Breite der Finder Patterns und Distanz zwischen ihnen


Zurück Weiter