QR-code codieren.

[Javatar]

Ihr wollet schon immer einmal wissen wie so ein QR-Code codiert wird? Dann geht es euch genau so wie mir.
Ich habe mich durch Google gewühlt und nur wenige Seiten gefunden die mit wirklich geholfen haben und außerdem waren alle auf englisch. Das will ich hiermit ändern.
Was ist ein QR-Code ?
.
Ein QR-Code ist ein zweidimensionaler Strich beziehungsweise Pixelcode mit dem Daten dargestellt werden können. Diese Daten werden in Binärcode übergeben, sprich durch 1en und 0en dargestellt. Ein schwarzes Kästchen steht für eine 1 und ein weißes Kästchen steht für eine 0. Je nach größe des Codes, können mehr oder weniger Daten gespeichert werden.
.
.
Was brauchen wir um uns selbst einen QR-Code zu codieren?
-Zuerst brauchen wir einen Text den wir Codieren wollen und Kenntnisse über Binärcode.
Wenn wir uns einen Text überlegt haben, wir nehmen “TEST”, müssen wir uns überlegen welcher Modus für unseren Text benötigt wird.
Für uns interessant sind nur 2 Modi.
Der Numeric Modus (Wenn der zu codierende Text nur aus Ziffern besteht) hat den Code: 0001,
und der Alphanummeric Modus ( Wenn der zu codierende Text aus Buchstaben, Zahlen und Sonderzeichen besteht (+,-,*,$,%,/,space))hat den Code: 0010
Da unser Text nur aus Buchstaben besteht müssen wir den Alphanummeric Modus wählen und haben somit den ersten Teil für unseren Binärcode.
Binärcode: 0010
Im nächsten Schritt übergeben wir die Länge des zu codierenden Textes.
Wir haben bei unserem Beispiel 4 Buchstaben. ( Wenn ihr Leerstellen in eurem Text habt, vergesst nicht sie mit zu zählen) der Binärcode für die Länge unseres Textes muss 9 Stellen haben (9 Bit)
Modus: 0010 + Textlänge: 000000100 = Binärcode: 0010000000100
Jetzt fangen wir an unseren Text zu codieren. Dazu müssen wir unseren Text in 2er Blöcke aufteilen.
Dies macht man immer dann, wenn man im Alphanumeric Modus codiert.
Im numeric Modus teilt man den String bzw. seine Zahl in 3er Blöcke und der der folgende Schritt des Wertezuweisens und Addierens wird übersprungen. Die Blöcke wir gleich in einen 11 stelligen Binärcode umgewandelt. Danach ist alles gleich.
Block 1 : TE Block 2 : ST
Jeder Buchstabe hat einen Wert:
0-0 | 1-1 | 2-2 | 3-3 | 4-4 | 5-5 | 6-6 | 7-7 | 8-8 | 9-9 | A-10 | B-11 | C-12 | D-13
E-14 | F-15 | G-16 | H-17 | I-18 | J-19 | K-20 | L-21 | M-22 | N-23 | O-24 | P-25 | Q-26 | R-27
S-28 | T-29 | U-30 | V-31 | W-32 | X-33 | Y-34 | Z-35 | (space) 36 | $ 37 | % 38 | * 39 | + 40 |
- 41 | . 42 | / 43 | : 44 |
Wandeln wir die Buchstaben um : Block 1 : 29 14 Block 2 : 28 29
Jetzt werden die Blöcke codiert, dazu wird der Erste Buchstabenwert mit 45 multipliziert und der Zweite Wert wird dann auf das Ergebnis addiert.
Block 1 : (29*45)+14 = 1319 Block 2 : (28*45)+29 = 1289
Jetzt haben wir für jeden Block den Wert errechent und wandeln diesen in einen 11 Stelligen (11 Bit) Binärcode um.(Wenn es euch zu aufwendig ist das Per hand zu machen benutz den Windows Rechner)
Block 1 : 10100100111 Block 2 : 10100001001
Diese beiden Blöcke hängen wir an unseren bisherigen Bnärcode.
Binärcode : 0010000000100 + Block 1 + Block 2 = 00100000001001010010011110100001001
Jetzt ist es Zeit sich eine geeignete Größe für seinen QR-Code zu wählen.
Die Größe wird auch als Version bezeichnen.
Es gibt 40 verschiedene Versionen deswegen verweise ich hier auf eine Seite, auf der ihr die Größe aller Versionen im Überblick habt.
QR-Code Versionstabelle
In der ersten Spalte könnt ihr die Version ablesen, in der Zweiten wie viele Module die Version hat, in der Dritten das Fehlerkorrektur LVL.
Dort gibt es 4 LVL L, M, Q und H. Dieses LVL entscheidet am Ende wie viel % eures QR-Codes beim Einscannen nicht lesbar sein müssen und der Scanner den Code trotzdem lesen kann. Die Wahl welches LVL ihr wählt liegt ganz bei euch, hat aber Auswirkungen darauf wie lang euer Text sein darf den ihr codieren wollt.
L -> 7% eures Codes dürfen beim scannen unkenntlich sein.
M -> 15% ——————–”————————� �
Q -> 25% ——————–”————————� �
H -> 30% ———————————————–
Unser bisheriger Binärcode hat 35 Stellen und ist somit 35 Bit lang.
Also brauchen wir Eine Version und ein Fehlerkorrektur LVL was eine Kapazität von 35 oder mehr Bits hat.
In der Tabele findet man die Kapazität in der Spalte “Data bits”.
Wir wollen das unser Code ein möglichst hohes Korrektur LVL hat, aber dennoch möglichst klein ist.
Da unser Binärcode nur 35 Bits umfasst nehmen wir Version 1 und Korrektur LVL H.
Das ist die kleinste Version die es gibt und trotz Korrektur LVL H kann der Binärcode den man darstellen möchte noch 72 Bit umfassen. Ihr könnt in der Tabelle sehen, dass wenn das Korrektur LVL sinkt die Anzahl der möglichen darzustellen Bits ( Data Bits) steigt.
Wenn der Binärcode kürzer ist als die maximale Kapazität ist, hängen wir an unseren Binärcode noch vier 0en.
Sollte das jedoch die maximale Kapazität überschreiten hängen wir nur so viele 0en dran bis die maximale Kapazität erreicht ist.
Bei uns ist der Binärcode deutlich kleiner als die maximale Kapazität also fügen wir vier weiter 0en hinzu. Diese 0en nennt man übrigens Terminator.
Binärcode + Terminator = 00100000001001010010011110100001001 + 0000 =
Neuer Binärcode 001000000010010100100111101000010010000
Als nächstes teilen wir den Binärcode in 8er Blöcke ( links beginnend )
Block1:00100000
Block2:00100101
Block3:00100111
Block4:10100001
Block5:0010000
Sollte der Letzte block kürzer als 8 Bits sein füllen wir ihn mit 0en auf bis er 8 Bits lang ist.
Block5:00100000
Diese Blöcke nennt man auch 8 Bit Wörter ich werde mich im Verlauf auf Wörter beschränken.
Jetzt haben wir 5 Wörter die jeweils 8 Bit lang sind also haben wir eine Binärcodelänge von 5*8 Bits
das enspricht einer Länge von 40 Bits.
Da damit die volle Kapazität noch nicht erreicht ist, müssen wir den Code weiter auffüllen.
Dazu gibt es 2 spezielle Wörter ( Blöcke )
Spezial1 : 11101100
Spezial2 : 00010001
Diese werden nun abwechselnd so lange an unseren Binärcode angefügt bis die maximale Kapazität erreicht ist. Wir habenn bis her 5 Wörter also brauchen wir 4 weitere Wörter mit 8 Bit um auf insgesammt 72 Bit zu kommen. ( 9 Wörter * 8 Bit = 72 Bit )
Block1 Block2 Block3 Block4 Block5 Spezial1 Spezial2 Spezial1 Spezial2
Das entspricht dem Binärcode
00100000 00100101 00100111 10100001 00100000 11101100 00010001 11101100 00010001
So unseren Text haben wir nun codiert, fehlt nur noch der code für die Fehlerkorrektur.
Dazu müssen wir unsere Wörter ( Blöcke ) in Dezimalzahlen umwandeln.
00100000 00100101 00100111 10100001 00100000 11101100 00010001 11101100 00010001
Diese Wörter entsprechen folgenden Dezimalzahlen.
32 37 39 161 32 236 17 236 17
Jetzt müssen wir herausfinden wie viele Korrekturwörtter wir benötigen. Dazu schauen wir in folgender Tabelle
Da wir Version 1 mit Fehlerkorrektur LVL H verwenden brauchen wir, wie in der Tabelle ersichtlich brauchen wir daher 17 Korrekturwörter.
Um jetzt den Code für die Fehlerkorrektur zu erhaltem, müssen wir unseren Ccdierten Text in Dezimalform zu einen Polynom umformen.
Dazu wird jeder Wert mit x Multipliziert
32x 37x 39x 161x 32x 236x 17x 236x 17x
Dann Bekommt jeder Wert noch einen Exponenten.
Dieser ergibt sich folgendermaßen
(Anzahl der Wörter)+(Anzahl der Korrekturwörter)-(Position -1)-1
23x^(25) 37x^(24) 39x^(23) 161x^(22) 32x^(21) 236x^(20) 17x^(19) 236x^(18) 17x^(17)
Diese Werden dann mit einen + verknüpft. Diese Polynom nennt man auch Nachrichtenpolynom
Unser Nachrichtenpolynom
23x^(25)+37x^(24)+39x^(23)+161x^(22)+32x^(21)+236x ^(20)+17x^(19)+236x^(18)+17x^(17)
Als zweites Brauchen wir ein Generatorpolynom.
Das Nachrichtenpolynom müssten wir dann mit dem Generatorpolynom dividieren.
Das würde den Ramen des Tut’s sprengen, deswegen verkürzen wir das ganze.
Benutzt einfach Folgendes Tool
In das erste Textfeld gebt ihr durch einen Kommergetrennt die Werte von euren Wörtern ein.
Bei uns wären es diese:
32 37 39 161 32 236 17 236 17
In das zweite Feld gebt ihr die Anzahl der Benötigten Korrekturwörter ein.
Dann auf den “Perform division” Button klicken und ganz nach unten scrollen.
Dort findet ihr die Werte für eure Korrekturwörter. Wenn ihr genau wissen wollt wie diese Werte entstehen könnt ihr jeden Schrit der Division auf der Seite des Tools finde
Für uns wären das die Werte:
208 147 120 235 20 36 10 42 73 162 140 142 217 162 207 0 62
Diese Fehlerkorrekturwerte fügen wir nun an unsere Textwerte an und erhalten somit unseren vollständigen Codewert.
32 37 39 161 32 236 17 236 17 208 147 120 235 20 36 10 42 73 162 140 142 217 162 207 0 62
Diese Werte müssen nun wieder in Binärcode umgewandelt werden
00100000 00100101 00100111 10100001 00100000 11101100 00010001 11101100 00010001 11010000 10010011 01111000 11101011 00010100 00100100 00001010 00101010 01001001 10100010 10001100 10001110 11011001
10100010 11001111 00000000 00111110
Das ist nun unser vollständiger Binärcode den wir in unsere QR-Matrix eintragen werden
Zuerst müssen wir uns eine QR-Matrix erstellen von der Version 1.
Diese Matrix ist 21×21 Pixel groß.

Diese Positionserkennungsfelder befinden sich in der oberen rechten, oberen linken und unteren linken Ecke eines jeden QR-Codes und dienen dazu das der Scanner die Ausrichtung des Codes erkennt.Sie sind 8×8 Pixel groß.
Die blau markierten felder (die schwarzen Pixel zwischen den erkennbar blau markierten felder gehören dazu) verbinden die Positionserkennungsfelder unzwar mit immer abwechselnden Bits ( schwarz, weiß, schwarz usw).
Der einzelne schwarze Pixel, rechts über dem unteren Positionserkennungsfelder, man könnte sagen er gehört zu dem unterem Positionserkennungsfeld dazu denn er befindet sich immer an der gleichen stelle rechts oben neben dem Positionserkennungsfeld.

Befor wir nun unseren Binärcode in die Matrix eintragen müssen wir uns noch eine von 8 mögliche Masken wählen. Eine Maske ist ein Schema welches an gibt an welchen stellen wir ein Gesetztes Bit umgedreht werden muss. Sprich ein schwarzez Bit wird zu einem Weißem und umgekehrt.
Maske————Wann ein Bit umgedreht wird
0 —————(y + x) mod 2 == 0
1 —————y mod 2 == 0
2 —————x mod 3 == 0
3 —————(y + x) mod 3 == 0
4 —————( (y / 2) + (x / 3) ) mod 2 == 0
5 —————((y * x) mod 2) + ((y * x) mod 3) == 0
6 —————( ((y * x) mod 2) + ((y * x) mod 3) ) mod 2 == 0
7 —————( ((y + x) mod 2) + ((y * x) mod 3) ) mod 2 == 0
(zahl) mod 2 gibt den Rest zurück wenn (zahl) durch 2 geteilt wird.
(zahl) ist bei Maske 0 (y+x)
x und y sind die Koordinaten des Pixels
Wir wählen Maske 0 für dieses beispiel.
Als erstes übergen wir der Matrix die Typinformation( Fehlerkorrektur LVL H / Maske 0 )
Dazu schauen wir in folgender Tabelle nach.
FK—Maske– Typinformation
L—-0———-111011111000100
L—-1———-111001011110011
L—-2———-111110110101010
L—-3———-111100010011101
L—-4———-110011000101111
L—-5———-110001100011000
L—-6———-110110001000001
L—-7———-110100101110110
M—-0———-101010000010010
M—-1———-101000100100101
M—-2———-101111001111100
M—-3———-101101101001011
M—-4———-100010111111001
M—-5———-100000011001110
M—-6———-100111110010111
M—-7———-100101010100000
Q—-0———-011010101011111
Q—-1———-011000001101000
Q—-2———-011111100110001
Q—-3———-011101000000110
Q—-4———-010010010110100
Q—-5———-010000110000011
Q—-6———-010111011011010
Q—-7———-010101111101101
H—-0———-001011010001001
H—-1———-001001110111110
H—-2———-001110011100111
H—-3———-001100111010000
H—-4———-000011101100010
H—-5———-000001001010101
H—-6———-000110100001100
H—-7———-000100000111011
Unsere Typinformation ist somit: 001011010001001
Typinformation werden in folgender Reihenfolge eingetragen. Zuerst von unten nach oben und nur neben den Positionserkennungsfeldern. Schon belegte Felder werden dabei übersprungen.

Und dann nochmal von links nach rechts. Dabei werden wieder die schon belegten Felder Übersprungen.

Jetzt können wir anfangen unseren Binärcode in die Matrix einzutragen. Dabei fängt man immer unten links in der Ecke an. Dabei müssen wir daran denken, eine 1 ist ein dukler Pixel und eine 0 ein heller Pixel.
Zur verdeutlichung habe ich alle nicht belegten Felder grau markiert.
Ob wir zuerst den Binärcode eintragen und dann nach dem Schema der Maske die Bits ändern oder ob wir schon beim Eintragen die Bits nach dem Schema ändern ist uns überlassen. In dem Beispiel werde ich die Bits schon beim Eintragen ändern. Es müssen alle Bits gänder werden bei denen die Summe der x- und y-Koordinate restlos durch 2 teilbar ist.( die gerade ist)
Die Bits werden folgendermaßen eingetragen
Das erste Bit ganz unten rechts.
Das Zeite Bit links daneben.
Dann geht man eine Zeile höher und setzt das dritte Bit genau über das erste Bit.
Das vierte Bit dann über das Zweite. Wieder eine Zeile höher und die Nächsten Bits nach dem gleichen Schema anordnen. Aber nicht vergessen alle Bits mit einer geraden Summe der x und y-Koordinate zu ändern.
Das erste Bit (X:21/Y:1) -> Summe ist gerade, Bitt wird geändert.
00100000 00100101 00100111 10100001 00100000 11101100 00010001 11101100 00010001 11010000 10010011 01111000 11101011 00010100 00100100 00001010 00101010 01001001 10100010 10001100 10001110 11011001
10100010 11001111 00000000 00111110

Das zweite Bit (X:20/Y:1)
00100000 00100101 00100111 10100001 00100000 11101100 00010001 11101100 00010001 11010000 10010011 01111000 11101011 00010100 00100100 00001010 00101010 01001001 10100010 10001100 10001110 11011001
10100010 11001111 00000000 00111110

Das dritte Bit (X:21/Y:2) D
00100000 00100101 00100111 10100001 00100000 11101100 00010001 11101100 00010001 11010000 10010011 01111000 11101011 00010100 00100100 00001010 00101010 01001001 10100010 10001100 10001110 11011001
10100010 11001111 00000000 00111110

Das vierte Bit (X:20/Y:2) -> Summe ist gerade, Bit wird geändert.
00100000 00100101 00100111 10100001 00100000 11101100 00010001 11101100 00010001 11010000 10010011 01111000 11101011 00010100 00100100 00001010 00101010 01001001 10100010 10001100 10001110 11011001
10100010 11001111 00000000 00111110

Das macht ihr jetzt weiter bis ihr oben angekommen seid.
00100000 00100101 00100111 10100001 00100000 11101100 00010001 11101100 00010001 11010000 10010011 01111000 11101011 00010100 00100100 00001010 00101010 01001001 10100010 10001100 10001110 11011001
10100010 11001111 00000000 00111110

Wenn ihr oben angekommen seid macht ihr das gleiche von oben nach unten.
00100000 00100101 00100111 10100001 00100000 11101100 00010001 11101100 00010001 11010000 10010011 01111000 11101011 00010100 00100100 00001010 00101010 01001001 10100010 10001100 10001110 11011001
10100010 11001111 00000000 00111110
Wieder zuerst das rechte Bit, dann das linke Bit, eine Zeile tiefer gehen und wieder das Bit rechts setzen.

Das führt ihr weiter bis ihr unten angekommen seid.( Nicht vergessen je nach Schema der Maske die Bits zu ändern.)
Danach fangt ihr wieder von unten an. Das macht ihr so lange bis die komplette Matrix ausgefüllt ist.
Dabei müsst ihr darauf achten, dass ihr schon belegte Felder einfach überspringt.
Komplette Matrix vollendet:

So, damit ist der QR-Code fertig und ihr könnt ihn scannen.
Das Tut. ist nur für kleinere QR-Codes
Bei größeren Versionen gibt es noch zusätzliche Elemente die in den QR-Code eingefügt werden müssen.
Es wäre schön wenn ihr einfach ein Kommentar als Rückmeldung hinterlassen würdet und ob ihr interesse an einer Erweiterung dieses Tut’s für größere QR-Codes habt.
MFG Javatar
Quellen:
http://www.denso-wave.com/qrcode/index-e.html
http://www.thonky.com/qr-code-tutorial/
http://www.swetake.com/qr/qr1_en.html