So wird ein QR-Code gelesen

Ein Code, den Sie mit der Hand abdecken können

Hält man ein Telefon vor einen QR-Code, ist er im Nu gelesen, selbst wenn ein Aufkleber sich löst, eine Ecke geknickt ist oder ein Daumen im Weg liegt. Versucht man dasselbe mit dem Strichcode auf einer Müslipackung, piept die Kasse nur. Der Unterschied liegt nicht an der Kamera. Ein QR-Code trägt zusätzliche Codewörter, mit denen ein Lesegerät rekonstruieren kann, was es nicht sieht, und er trägt drei Markierungen, mit denen das Lesegerät ihn in jedem Winkel findet, noch bevor es zu lesen beginnt.

Die Bühne beginnt mit Ihrem eigenen Text oder der Adresse dieser Seite, als QR-Code in Stufe H, Version 9 dargestellt: ein Quadrat aus 53 mal 53 Modulen, das auf einem Galerietisch liegt. Eine Schaufensterpuppenhand schiebt sich vom Rand darüber und hält an, wenn sie 16 der 53 Spalten bedeckt. Das sind 848 der 2809 Module, 30,2 % des Symbols. Die Anzeige meldet unverändert „Gelesen“, und das Telefon rechts findet den Code weiter und gibt Ihren Text aus. Jeder der 8 Fehlerkorrekturblöcke des Symbols steht damit genau an seiner Grenze: je 12 falsche Codewörter, und 12 ist das Meiste, was ein Block dieser Größe beheben kann. Schieben Sie die Abdeckung um eine Spalte weiter, auf 32,1 %, und das Lesen bricht ab.

Reißen Sie dann eine Ecke ab. Das abgerissene Dreieck macht nur 3,2 % des Symbols aus, viel weniger als die Hand bedeckt hat, und trotzdem lässt sich der Code überhaupt nicht mehr lesen. Der Rest dieser Seite erklärt, warum beides geschieht, mit den Zahlen, die die Bühne verwendet. Sie stammen aus den Regeln der ISO/IEC 18004, der internationalen Norm für den QR-Code, und aus dem, was DENSO WAVE, die Firma, die ihn 1994 entwickelt hat, über seinen Entwurf veröffentlicht hat.

Das Symbol auf dem Tisch ist kein Bild eines QR-Codes. Es wird auf der Seite aus dem Text im Eingabefeld Modul für Modul erzeugt, mit derselben Reed-Solomon-Arithmetik, die auch ein Druckertreiber verwenden würde, und es wird von einem Decoder zurückgelesen, der den Referenzschritten der Norm folgt. Sie können das saubere Symbol als Bild speichern und mit Ihrem eigenen Telefon lesen. Der Encoder wurde mit zwei unabhängigen Lesegeräten und einem zweiten Encoder geprüft: Für 160 Kombinationen aus Version und Stufe waren die Matrizen Modul für Modul identisch.

So benutzen Sie die Bühne

Tippen Sie in das Feld am unteren Rand der Bühne, und das Symbol wird beim Tippen neu aufgebaut. Die Anzeige in der linken oberen Ecke nennt zuerst das Ergebnis („Gelesen“ oder „Nicht gelesen“ mit dem Grund), dann die Version und die Größe, die Fehlerkorrekturstufe, die Maske und ihre Strafpunkte, den Modus und die Zahl der Bits, die Ihr Text braucht, die Codewörter, wie viel abgedeckt ist und wie viele Codewörter jetzt falsch sind. Die kleinen Balken darunter sind die Fehlerkorrekturblöcke: Jeder füllt sich, wenn sich die Zahl seiner falschen Codewörter dem nähert, was er beheben kann, und wird rot, wenn er darüber liegt.

Der Telefonbildschirm rechts zeigt, was eine Kamera mit dem Bild machen würde: Eine rote Linie wandert über das Bild nach unten, grüne Markierungen zeigen jede Zeile, in der die Streifen im Verhältnis 1:1:3:1:1 passen, und Kreise zeigen, ob die drei Positionsmuster gefunden wurden. Darunter gibt das Telefon den Text aus oder den Grund, aus dem es aufgegeben hat.

Bei den Reglern legt Version die kleinste zu verwendende Version fest (der Encoder vergrößert das Symbol, wenn Ihr Text nicht hineinpasst), Fehlerkorrektur wählt L, M, Q oder H, und Maske erzwingt eine der acht Masken anstelle derjenigen mit den wenigsten Strafpunkten. Breite der Abdeckung und Lage der Abdeckung bewegen die Hand, und Abdeckung tauscht sie gegen einen Papierstreifen oder schwarzes Klebeband. Nach Aufgabe heben hebt die Module nach ihrer Aufgabe in Schichten an; Nach Aufgabe färben färbt sie, ohne sie anzuheben. Reihenfolge der Platzierung zeichnet den Weg, dem die Bits folgen, und färbt die Codewörter nach Blöcken. Maske einfärben tönt die Module, die die Maske umkehrt. Drehen dreht das Symbol auf dem Tisch. Vergleich stellt einen EAN-13-Strichcode oder ein Micro-QR-Symbol auf die Staffelei oder hängt die Versionen 1 bis 40 an die Wand. Ruhezone entfernt den weißen Rand.

Mit Malen ziehen Sie mit Tinte, Korrekturflüssigkeit, einem Loch oder einem Radiergummi über das Symbol. Mit Ecke abreißen und Ölflecken lässt es sich schnell beschädigen. Uhrzeit füllt das Symbol mit der aktuellen Zeit und zeichnet es jede Sekunde neu. Klicken Sie auf ein beliebiges Modul, um zu sehen, was es ist: seine Zeile und Spalte, seine Aufgabe und bei Datenmodulen den Block, das Codewort und das Bit, zu dem es gehört. Manche Module und manche Gegenstände auf dem Tisch öffnen versteckte Karten.

Unter den Reglern finden Sie Ihren Text als Bits ausgeschrieben, die Codewörter jedes Blocks hexadezimal, eine Tabelle der vier Stufen für die aktuelle Version, die acht Masken nebeneinander, eine Tabelle der Versionen, 12 Aufgaben, 46 Fälle, Karten, die mit „Eigentlich“ beginnen, eine Sammlung und Links zu verwandten Exponaten.

Quadrate in drei Ecken

Der schwierigste Teil beim Lesen eines zweidimensionalen Codes sind nicht die Daten. Schwierig ist es, den Code in einem Kamerabild voller anderer Dinge zu finden, herauszufinden, wo oben ist, und zu bestimmen, wie groß jedes Modul ist. Ein Strichcode ist leicht zu finden: Ein Laser oder eine Pixelzeile muss ihn nur kreuzen. Ein Matrixcode muss in zwei Dimensionen gefunden werden.

Die Antwort von DENSO WAVE waren die drei Quadrate in den Ecken, die die Norm Positionsmuster nennt. Jedes misst 7 mal 7 Module: ein dunkler Ring, ein heller Ring und ein dunkles Zentrum von 3 mal 3. Eine Linie durch die Mitte in beliebiger Richtung kreuzt dunkel, hell, dunkel, hell, dunkel in den Breiten 1, 1, 3, 1 und 1. Das Verhältnis ändert sich nicht, wenn der Code gedreht, skaliert oder schräg gesehen wird. Ein Lesegerät kann daher Pixelzeilen abtasten, sich die letzten fünf zusammenhängenden dunklen und hellen Abschnitte merken und prüfen, ob ihre Breiten diesem Verhältnis entsprechen.

Warum dieses Verhältnis? Laut DENSO WAVE haben die Entwickler Bilder und Schriftzeichen auf Prospekten, Zeitschriften und Pappkartons auf schwarz-weiße Muster reduziert und gezählt, welche Verhältnisse auftraten. Das seltenste auf Drucksachen war 1:1:3:1:1. In einem 2024 von DENSO veröffentlichten Interview sagte Masahiro Hara, der die Arbeit leitete, die Suche danach habe etwa sechs Monate gedauert, mit Zeitungen und Zeitschriften, die Seite für Seite fotografiert wurden, und Messsoftware, die über Nacht weiterlief.

Das Telefon auf der Bühne tut genau das mit den Pixeln, die es sieht. Es geht jede Zeile entlang, zählt Läufe und akzeptiert fünf Läufe, deren Breiten höchstens ein halbes Modul von 1:1:3:1:1 abweichen. Bei jedem Treffer prüft es dasselbe Verhältnis senkrecht durch die Mitte des mittleren Laufs. Treffer, die übereinstimmen, werden zu Kandidaten für Mittelpunkte. Dann braucht es drei davon, und derjenige, der zwischen den beiden anderen im rechten Winkel liegt, ist die Ecke oben links. Dieser Winkel verrät dem Lesegerät auch, wie weit der Code gedreht ist. Drehen Sie das Symbol mit Drehen und sehen Sie zu, wie die Kreise den Ecken folgen.

Ein Stück Daten kann zufällig dieselben Streifen bilden. Lesegeräte verwerfen solche Ausreißer, weil das Raster, das sie nahelegen, nicht passt. Die Bühne zählt ein Positionsmuster nur dann als gefunden, wenn die Erkennung auf dem echten landet.

Trennstreifen, Rand und der dunkle Tisch

Der Test auf 1:1:3:1:1 funktioniert nur, wenn der äußere dunkle Ring auf beiden Seiten Helligkeit hat. Innerhalb des Symbols garantieren das die Trennstreifen: ein heller Ring von einem Modul Breite um jedes Positionsmuster. Außerhalb des Symbols ist es die Aufgabe der Ruhezone, eines hellen Rands, den die Norm auf jeder Seite vier Module breit vorschreibt.

Auf der Bühne ist das Symbol auf ein Blatt Papier gedruckt, dessen Rand genau vier Module misst. Der Tisch darunter ist dunkler Schiefer. Schalten Sie Ruhezone aus, und der Papierrand verschwindet, sodass der äußere Ring jedes Positionsmusters direkt in den dunklen Tisch übergeht. Eine Zeile durch ein Positionsmuster ergibt nun einen langen dunklen Lauf, gefolgt von hell, dunkel, hell und dunkel: Der erste Lauf ist viele Module breit, und das Verhältnis stimmt nicht. Das Telefon findet keine Positionsmuster, und die Anzeige meldet „Nicht gelesen“, ein Positionsmuster fehlt. An den Daten hat sich nichts geändert.

Die Druckhinweise von DENSO WAVE rechnen den Rand in die Größe des Etiketts ein. Das Beispiel ist 50 alphanumerische Zeichen in Stufe M, wofür Version 3 nötig ist (29 Module; Version 2 fasst in Stufe M nur 38). Bei einem Drucker mit 400 dpi und 4 Punkten je Modul misst das Modul 0,254 mm, das Symbol 7,366 mm, und mit 8 Modulen Rand ist die Etikettenfläche 9,398 mm im Quadrat. Micro-QR-Codes, die nur ein Positionsmuster haben, brauchen statt vier nur zwei Module Rand.

Ein Lineal, im Code mitgedruckt

Zeile 6 und Spalte 6 jedes QR-Codes verlaufen von einem Positionsmuster zum nächsten und wechseln dabei zwischen dunkel und hell. Das sind die Taktmuster. Sie sagen dem Lesegerät, wo jede Spalte und Zeile liegt, was wichtig ist, wenn der Druck gedehnt, das Papier wellig oder der Code schräg zu sehen ist. Ein Lesegerät, das die Lagen der Positionsmuster kennt, kann die Modulgröße schätzen, aber das Abzählen der wechselnden Module liefert die genaue Zahl der Module zwischen den Positionsmustern.

Die Zahl der Module verrät auch die Version. Die Version V hat auf jeder Seite 17 + 4V Module, Version 1 ist also 21 mal 21 Module groß; bei Version 40 sind es 177 mal 177. Auf der Bühne füllt das Symbol immer dieselben 30 cm Papier, sodass das Modul mit wachsender Version schrumpft: 5,7 mm bei Version 9, 1,7 mm bei Version 40.

Weil die Taktmuster im Symbol liegen, belegen sie auch Module, die Daten aufnehmen könnten. In Version 1 lassen die Funktionsmuster (Positionsmuster, Trennstreifen, Takt, Formatinformation und das dunkle Modul) 208 Module für Codewörter übrig: 26 Codewörter zu je 8 Bit.

Zielmarken für gebogenes Papier

Der erste QR-Code von 1994, heute Model 1 genannt, hatte keine weiteren Hilfen. Laut DENSO WAVE reichte Model 1 bis Version 14, 73 mal 73 Module und 1167 Ziffern. Model 2, der heute verwendete QR-Code, fügte Ausrichtungsmuster hinzu, damit auch Codes auf gekrümmten Flächen oder unter steilem Blickwinkel noch gelesen werden. Es erweiterte den Bereich außerdem bis Version 40 und 7089 Ziffern.

Ein Ausrichtungsmuster ist eine kleine Zielmarke von 5 mal 5: ein dunkler Ring, ein heller Ring und ein dunkles Mittelmodul. Version 1 hat keines. Die Versionen 2 bis 6 haben eines nahe der Ecke unten rechts, die Versionen 7 bis 13 haben sechs, und die Zahl wächst bis auf 46 in den Versionen 35 bis 40. Ihre Mittelpunkte liegen auf einem Raster aus Zeilen und Spalten, das in der Norm aufgelistet ist; für Zeilen und Spalten gelten dieselben Positionen, und die drei Stellen, an denen sie ein Positionsmuster überlappen würden, bleiben leer. Die Bühne berechnet diese Positionen aus der Version: Für Version 9 sind es 6, 26 und 46, was 3 x 3 = 9 Plätze minus 3 = 6 Muster ergibt.

Ein Lesegerät, das die drei Positionsmuster gefunden hat, kennt drei Ecken des Codes. Die vierte Ecke ist nicht markiert, also schätzt das Lesegerät sie und sucht dann das nächste Ausrichtungsmuster, um die Schätzung zu korrigieren. Mit diesem vierten Punkt kann es die Perspektive eines schräg aufgenommenen Fotos rückgängig machen. Bei einem großen Symbol erlauben mehrere Ausrichtungsmuster dem Lesegerät, einer Seite zu folgen, die sich wölbt.

Fünfzehn Bits, die sagen, wie der Rest zu lesen ist

Bevor ein Lesegerät irgendwelche Daten lesen kann, muss es zwei Dinge wissen: die Fehlerkorrekturstufe und welche der acht Masken angewendet wurde. Sie nehmen 5 Bits ein: 2 für die Stufe (L ist 01, M ist 00, Q ist 11 und H ist 10) und 3 für die Maskennummer.

Diese 5 Bits sind weit stärker geschützt als die Daten. Sie werden mit einem BCH-Code auf 15 Bits erweitert. BCH-Codes sind fehlerkorrigierende Codes, die Bose und Ray-Chaudhuri 1960 und unabhängig davon Hocquenghem 1959 gefunden haben. Die 10 Prüfbits sind der Rest der um 10 Stellen nach links verschobenen 5 Bits, geteilt durch das Polynom x^10 + x^8 + x^5 + x^4 + x^2 + x + 1. Zwei beliebige der 32 möglichen 15-Bit-Codewörter unterscheiden sich in mindestens 7 Bits, sodass ein Lesegerät das nächstliegende wählen kann, selbst wenn 3 Bits falsch sind.

Die 15 Bits werden dann mit dem festen Muster 101010000010010 per XOR verknüpft. Ohne dieses Muster bestünde die Formatinformation bei Stufe M mit Maske 0 aus 15 hellen Modulen, und das Lesegerät könnte sie nicht von leerem Papier unterscheiden.

Die Formatinformation wird zweimal geschrieben: einmal um das Positionsmuster oben links und einmal aufgeteilt auf die beiden anderen, 8 Bits neben dem Positionsmuster oben rechts und 7 neben dem unten links. Verdeckt eine Abdeckung die eine Kopie, funktioniert die andere noch. Klicken Sie auf der Bühne auf ein Formatmodul, und die versteckte Karte öffnet sich; reißen Sie die Ecke oben links ab, bleibt nur eine Kopie erhalten, aber dann ist auch das Positionsmuster schon weg.

Neben der Kopie unten links sitzt ein Modul, das in jedem QR-Code dunkel ist: das dunkle Modul, in Zeile 4V + 9 und Spalte 8. Es gehört zum Formatbereich und trägt keine Information.

Die Versionen 1 bis 40

Kleine Symbole müssen ihre Version nicht angeben: Das Lesegerät zählt die Module. In einem großen Symbol würde ein kleiner Fehler bei der geschätzten Modulgröße die falsche Zahl ergeben, daher wird die Version ab Version 7 ausgeschrieben. Sechs Bits Versionsnummer werden mit einem weiteren BCH-Code, erzeugt durch x^12 + x^11 + x^10 + x^9 + x^8 + x^5 + x^2 + 1, auf 18 erweitert und zweimal platziert, als Block von 6 mal 3 neben dem Positionsmuster oben rechts und als Block von 3 mal 6 neben dem unten links. Version 7 wird als 000111110010010100 geschrieben und Version 40 als 101000110001101001. Auch hier lassen sich 3 falsche Bits korrigieren.

Wie viel eine Version fasst, hängt von der Stufe und der Art der Zeichen ab. Die Tabellen von DENSO WAVE nennen für Version 1 in Stufe L 41 Ziffern, 25 alphanumerische Zeichen, 17 Bytes oder 10 Kanji und für Version 1 in Stufe H 17 Ziffern, 10 alphanumerische Zeichen, 7 Bytes oder 4 Kanji. Am anderen Ende fasst Version 40 in Stufe L 7089 Ziffern, 4296 alphanumerische Zeichen, 2953 Bytes oder 1817 Kanji. Der Encoder auf dieser Seite gibt diese Zahlen wieder, und die Tabelle im Labor nennt sie für jede Version in der aktuellen Stufe, mit der gedruckten Breite für jede Modulgröße, die Sie eingeben.

DENSO WAVE rät, Telefonen nicht zu viel zum Lesen zuzumuten: Es nennt etwa 271 Bytes, Version 10 in Stufe L, als praktischen Richtwert für Telefonkameras, je nach Modell. Hängen Sie mit Vergleich die Versionen an die Wand, um zu sehen, warum. Bei der Modulgröße des Tisches ist Version 40 mehr als einen Meter breit.

Vom Text zu Bits

Der Text, den Sie tippen, kommt nicht als Buchstaben in den Code. Er kommt als Bitstrom hinein, der aus Segmenten aufgebaut ist, und jedes Segment beginnt mit einer Modusangabe von 4 Bit.

Der Ziffernmodus (0001) packt Ziffern zu je drei in 10 Bits, weil 1000 Kombinationen in 1024 passen. Eine letzte Gruppe aus zwei Ziffern braucht 7 Bits und eine einzelne Ziffer 4. Der alphanumerische Modus (0010) deckt 45 Zeichen ab: die Ziffern, die Großbuchstaben, das Leerzeichen und $ % * + - . / :. Er packt zwei Zeichen in 11 Bits als 45 x erstes + zweites, weil 45 x 45 = 2025 in 2048 passt, und ein letztes einzelnes Zeichen in 6 Bits. Der Bytemodus (0100) verwendet 8 Bits je Byte. Der Kanjimodus (1000) nimmt ein Shift-JIS-Zeichen aus zwei Bytes und presst es in 13 Bits, weshalb der QR-Code von Anfang an japanischen Text kompakt tragen konnte.

Nach der Modusangabe folgt eine Zeichenzahl. Ihre Länge hängt vom Modus und von der Version ab: Für die Versionen 1 bis 9 sind es 10 Bits für numerisch, 9 für alphanumerisch, 8 für Byte und 8 für Kanji; größere Versionen verwenden längere Zahlen. Dann folgen die Zeichen. Am Ende fügt der Encoder bis zu 4 Nullbits als Abschluss an, Nullen bis zur nächsten Bytegrenze und dann abwechselnd die Füllbytes 11101100 und 00010001 (236 und 17), bis die Datenkapazität gefüllt ist.

Die Norm gibt ein durchgerechnetes Beispiel: die acht Ziffern 01234567 in Version 1, Stufe M. Modus 0001, Zeichenzahl 0000001000 (acht), dann 012 als 0000001100, 345 als 0101011001 und 67 als 1000011. Mit Abschluss und Füllung lauten die 16 Datencodewörter hexadezimal 10 20 0C 56 61 80 EC 11 EC 11 EC 11 EC 11 EC 11. Der Encoder auf dieser Seite erzeugt genau diese Bytes und die Fehlerkorrektur-Codewörter, die die Norm danach aufführt.

Der Bytemodus sagt nicht, in welchem Zeichensatz die Bytes stehen. Ausgaben der Norm ab 2006 machen ISO 8859-1 zum Standard; die erste Ausgabe von 2000 verwendete einen japanischen 8-Bit-Satz. Für anderen Text kann der Encoder einen ECI-Kopf (Extended Channel Interpretation, Modus 0111) mit der Nummer 26 hinzufügen, die UTF-8 bedeutet. Die Bühne fügt ihn immer dann hinzu, wenn Ihr Text mehr als reines ASCII enthält, sodass Koreanisch oder Emoji unversehrt ankommen. Tippen Sie japanische Kana, schaltet der Encoder stattdessen in den Kanjimodus, 13 Bits je Zeichen statt 24 in UTF-8.

Das Labor zeigt Ihren eigenen Text in diese Segmente zerlegt, mit ihren Bitzahlen. Eine Adresse in Großbuchstaben kann den alphanumerischen Modus nutzen und fast ein Drittel der Bits sparen, was ein Grund dafür ist, dass manche gedruckten Codes Adressen in Großbuchstaben verwenden.

Reed-Solomon im QR-Code

Auf die Datencodewörter folgen Fehlerkorrektur-Codewörter aus einem Reed-Solomon-Code, den Irving Reed und Gustave Solomon 1960 auf fünf Seiten beschrieben haben. DENSO WAVE beschreibt ihn als mathematisches Verfahren, das bei Musik-CDs verwendet wird, zuerst gegen Störungen bei der Kommunikation mit Satelliten und Planetensonden entwickelt wurde, auf der Ebene von Bytes korrigiert und sich für Fehler eignet, die gebündelt auftreten.

Gerechnet wird in einem Körper mit 256 Elementen, einem für jeden Bytewert. Zwei Bytes zu addieren ist XOR. Beim Multiplizieren dient eine Tabelle, die aus dem Polynom x^8 + x^4 + x^3 + x^2 + 1 aufgebaut ist, das die Norm für den QR-Code festlegt. Ein Block von Datencodewörtern wird als Koeffizienten eines Polynoms gelesen, mit x^n multipliziert und durch ein Generatorpolynom geteilt, das die n Nullstellen 1, a, a^2 bis a^(n-1) hat. Der Rest liefert die n Fehlerkorrektur-Codewörter. Der ganze Block, Daten plus Rest, ist dann ein Vielfaches des Generators und hat deshalb an jeder der n Nullstellen den Wert null.

Ein Lesegerät wertet den empfangenen Block an diesen Nullstellen aus. Ist jedes Ergebnis, Syndrom genannt, null, ist der Block sauber. Wenn nicht, enthalten die Syndrome genug Information, um bis zu n/2 falsche Codewörter und ihre richtigen Werte zu finden. Der Decoder auf dieser Seite macht das in drei Schritten, die in der Codierungstheorie üblich sind: Der Berlekamp-Massey-Algorithmus findet das kürzeste Fehlerlokalisierungspolynom (Massey, 1969), eine Chien-Suche probiert jede Position durch, um seine Nullstellen zu finden (Chien, 1964), und die Formel von Forney liefert die Größe jedes Fehlers (Forney, 1965).

Es gibt noch eine Regel. In den kleinsten Symbolen würde ein Decoder, der die vollen n/2 Fehler korrigiert, zu oft bei einem falschen, aber gültigen Block landen. Die Norm hält deshalb einige Codewörter als Schutz vor Fehldekodierung zurück: Version 1 hält in Stufe L 3 zurück, in M 2, in Q 1 und in H 1, Version 2-L hält 2 zurück und Version 3-L hält 1 zurück. Ein Block kann dann (n - p)/2 Codewörter korrigieren, wobei p die Zahl der zurückgehaltenen ist. Version 1-L hat 7 Fehlerkorrektur-Codewörter, korrigiert aber 2, nicht 3. Das Labor führt p neben der Zahl auf, die jeder Block beheben kann.

Ein Codewort ist falsch, ob eines seiner Bits falsch ist oder alle acht. Deshalb passen Reed-Solomon-Codes zu Flecken und Rissen: Ein Schaden, der ein Stück Module bedeckt, ruiniert einige ganze Codewörter statt vieler verstreuter Bits.

Blöcke und Verschränkung

Bei allen Versionen oberhalb der kleinsten werden die Codewörter in Blöcke aufgeteilt, und jeder Block bekommt seine eigenen Fehlerkorrektur-Codewörter. Version 9 in Stufe H hat 292 Codewörter in 8 Blöcken. Vier Blöcke haben 12 Datencodewörter und vier haben 13, jeweils mit 24 Fehlerkorrektur-Codewörtern, das sind 100 Datencodewörter und 192 für die Fehlerkorrektur. Jeder Block kann 12 falsche Codewörter beheben, das Symbol als Ganzes also 96 seiner 292 Codewörter.

Die Blöcke werden nicht hintereinander platziert. Zuerst kommt das erste Datencodewort jedes Blocks, dann das zweite jedes Blocks und so weiter, danach in gleicher Weise die Fehlerkorrektur-Codewörter. Schalten Sie Reihenfolge der Platzierung ein, dann zeigen es die Farben: Auf dem Papier benachbarte Codewörter gehören zu verschiedenen Blöcken. Ein Fleck von der Größe einiger Codewörter kostet deshalb mehrere Blöcke je ein oder zwei Codewörter, statt einem Block alle zu kosten.

Das ist es, was die Hand am Anfang zeigt. Die 16 Spalten unter der Hand verändern 96 Codewörter, 12 in jedem der 8 Blöcke. Die Verschränkung verteilt den Schaden so gleichmäßig, dass alle 8 Blöcke im selben Augenblick ihre Grenze erreichen. Eine weitere Spalte fügt jedem Block falsche Codewörter hinzu, und alle versagen gemeinsam.

Malen Sie einen einzelnen Tintenfleck und beobachten Sie die Balken unter der Anzeige: Meist steigen mehrere Blöcke ein wenig. Die Aufgabe Einen Block überlasten verlangt, genau einen Block versagen zu lassen, während die anderen durchhalten, was mehr Sorgfalt erfordert, als es klingt, weil die Verschränkung gegen Sie arbeitet.

Die Codewörter platzieren

Sind die Daten- und Fehlerkorrektur-Codewörter verschränkt, werden ihre Bits entlang eines festen Wegs in das Symbol gelegt. Er beginnt in der Ecke unten rechts und führt an einem Spaltenpaar aufwärts, erst das rechte Modul, dann das linke, dann die nächste Zeile darüber. Oben wendet er und kommt am nächsten Spaltenpaar wieder herunter, und so weiter durch das ganze Symbol. Jedes Funktionsmuster wird übersprungen, und das senkrechte Taktmuster in Spalte 6 wird ganz übersprungen, damit die Paare im Gleichschritt bleiben.

Der Weg erklärt einiges, was Sie auf der Bühne sehen können. Die ersten vier Bits, die Modusangabe, liegen immer in der Ecke unten rechts. Die meisten Codewörter nehmen einen Block von 2 mal 4 Modulen ein, aber wo der Weg oben oder unten wendet oder um ein Ausrichtungsmuster läuft, wird ein Codewort zu anderen Formen verbogen. Klicken Sie auf ein Modul nahe der Ecke unten rechts, und seine Karte sagt Ihnen, dass es Teil der Modusangabe ist.

Wenn die Codewörter den Datenbereich nicht genau füllen, sind die übrigen Module Restbits: 7 in den Versionen 2 bis 6, 3 in den Versionen 14 bis 20 und 28 bis 34, 4 in den Versionen 21 bis 27 und keine in den übrigen. Sie sind vor dem Maskieren hell, und das Lesegerät ignoriert sie.

Masken und Strafpunkte

Ein Symbol direkt aus der Platzierung kann große dunkle Flächen, lange Läufe oder durch Pech ein Stück Daten haben, das wie ein Positionsmuster aussieht. Jedes davon erschwert das Lesen. Deshalb wendet der Encoder eine Maske an: Er kehrt jedes Datenmodul um, bei dem eine Regel über seine Zeile i und Spalte j zutrifft. Es gibt acht Regeln, von (i + j) mod 2 = 0, einem Schachbrett, bis ((i + j) mod 2 + (i j) mod 3) mod 2 = 0. Funktionsmuster werden nie maskiert.

Der Encoder probiert alle acht und bewertet jedes Ergebnis mit vier Arten von Strafpunkten aus der Norm. Jeder Lauf von 5 oder mehr Modulen derselben Farbe in einer Zeile oder Spalte kostet 3 Punkte, plus 1 für jedes Modul über 5 hinaus. Jeder Block von 2 mal 2 in einer Farbe kostet 3. Jedes Muster, das wie ein Positionsmuster aussieht, 1011101 mit 4 hellen Modulen auf einer Seite, kostet 40. Und für jeweils 5 Prozentpunkte, um die der Anteil dunkler Module von der Hälfte abweicht, fallen 10 Strafpunkte an. Die Maske mit den wenigsten Punkten gewinnt, und ihre Nummer geht in die Formatinformation ein.

Das Labor zeichnet alle acht Fassungen Ihres Symbols nebeneinander mit ihren Wertungen. Wählen Sie mit dem Regler Maske eine andere Maske, und der Code lässt sich weiterhin lesen, weil das Lesegerät die Maskennummer der Formatinformation entnimmt. Deshalb können auch zwei Generatoren aus demselben Text verschieden aussehende Codes machen, und beide sind richtig. Die FAQ von DENSO WAVE weisen auf dasselbe hin: Gleiche Daten können je nach Modus und anderen Entscheidungen verschiedene Muster ergeben.

Maske einfärben tönt jedes Modul, das die aktuelle Maske umkehrt, orange. Vergleichen Sie es mit der Regel im Labor: Es ist dieselbe Regel, auf den gesamten Datenbereich angewendet.

Was 30 % wirklich bedeutet

DENSO WAVE gibt die vier Stufen mit der Wiederherstellung von etwa 7 %, 15 %, 25 % und 30 % der Codewörter an und merkt an, dass Stufe M die gebräuchlichste ist. Zwei Wörter in diesem Satz sind wichtig: etwa und Codewörter.

Etwa, weil der Anteil von Version zu Version abweicht. Gerechnet als die Zahl der Codewörter, die alle Blöcke zusammen beheben können, geteilt durch die Gesamtzahl, reicht Stufe L über die Versionen 1 bis 40 von 7,7 % bis 10,5 %, M von 15,4 % bis 19,2 %, Q von 23,1 % bis 28,0 % und H von 30,8 % bis 33,2 %. Die Tabelle im Labor nennt den genauen Wert für die Version auf der Bühne.

Codewörter, weil eine Abdeckung in Fläche gemessen wird und sich Fläche nicht einfach in Codewörter umrechnen lässt. Eine Abdeckung, die den Rand eines Codeworts bedeckt, ruiniert es so sicher wie eine, die es ganz bedeckt. Eine Abdeckung, die auf helle Module fällt, ändert nichts, weil eine Hand oder ein Papierstreifen als hell gelesen wird: Auf der Bühne ändert die Hand über 30,2 % der Module nur etwa 16 % davon. Eine Abdeckung über Funktionsmustern kostet keine Codewörter, kann aber die Positionsmuster, den Takt oder die Formatinformation kosten.

Die ehrliche Zusammenfassung lautet also: In Stufe H kann das Symbol eine Abdeckung von etwa 30 % seiner Fläche überstehen, wenn die Abdeckung quer über den Daten liegt und die Blöcke den Schaden gleichmäßig teilen, wie es die 16 Spalten der Hand tun. Wird dieselbe Fläche über Zeilen statt Spalten abgedeckt, also 16 Zeilen bei 30,2 %, lässt sich der Code in Version 9 nicht lesen. Eine Abdeckung von 3,2 % an der falschen Stelle stoppt es. Die Aufgabe Mit weniger als 10 % kaputt machen ist dazu da, diese Stelle zu finden.

DENSO WAVE beschreibt die Wahl der Stufe in praktischen Begriffen: Q oder H für Fabriken, in denen Codes schmutzig werden, L für saubere Orte mit vielen Daten. Für ein Bahnsteigtür-System auf Tokioter Linien, wo Codes an Zugtüren Sonne und Regen ausgesetzt sind, entwickelte DENSO nach eigener Aussage einen Spezialcode, tQR, der 50 % Beschädigung verträgt.

Wie ein Telefon den Code findet und liest

Die Norm beschreibt einen Referenz-Dekodieralgorithmus, und echte Lesegeräte folgen seiner Reihenfolge, auch wenn ihre Einzelheiten abweichen. Das Quiz im Labor bittet Sie, die Schritte in die richtige Reihenfolge zu bringen.

Zuerst wird das Bild in Schwarz und Weiß umgewandelt. Echte Lesegeräte wählen für jeden Bildteil einen Schwellenwert, weil ein Code auf einer glänzenden Dose oder unter einer Schreibtischlampe nicht gleichmäßig beleuchtet ist. Dann kommen die Positionsmuster, gefunden durch die oben beschriebene Abtastung auf 1:1:3:1:1. Aus den drei Mittelpunkten schätzt das Lesegerät die Modulgröße und die Ausrichtung, dann die Version aus dem Abstand der Positionsmuster. Ab Version 7 liest es zur Bestätigung die Versionsinformation. Es sucht in der Nähe der erwarteten Lage der vierten Ecke nach einem Ausrichtungsmuster und passt eine perspektivische Transformation an, die jedes Modul des Rasters auf das Bild abbildet.

Dann tastet es die Mitte jedes Moduls ab und liest die Formatinformation. Von den 32 gültigen Format-Codewörtern nimmt es dasjenige, das dem Gelesenen am nächsten kommt, und probiert bei Bedarf beide Kopien. Das ergibt die Stufe und die Maske. Es entfernt die Maske, indem es dieselben Module erneut umkehrt, folgt dem Platzierungsweg, um die Codewörter einzusammeln, sortiert sie wieder in Blöcke, korrigiert jeden Block und dekodiert schließlich den Bitstrom: Modus, Zeichenzahl, Zeichen, bis es auf den Abschluss trifft oder die Daten zu Ende sind.

Die Bühne vereinfacht zwei dieser Schritte. Das Telefon führt die Suche nach den Positionsmustern auf echten Pixeln aus, gedreht mit dem Regler Drehen und mit oder ohne Rand, aber es verbiegt oder kippt das Bild nicht, und das Lesegerät tastet das Raster dann an bekannten Positionen ab, statt eine Perspektive anzupassen. Außerdem werden Abdeckungen als hell behandelt: Eine Hand wird wie weißes Papier gelesen, schwarzes Klebeband wie dunkel. Eine echte Kamera würde den Schatten einer Hand und die Struktur von Haut sehen und kann besser oder schlechter abschneiden.

DENSO WAVE nennt eine weitere praktische Grenze, die nichts mit dem Code zu tun hat: die Farbe. Seine Scanner beleuchten den Code mit rotem Licht, sodass ein roter Code auf weißem Papier ebenso viel Rot reflektiert wie das Papier und verschwindet. Es empfiehlt Schwarz auf Weiß.

Strichcodes, Micro QR und rMQR

Der Strichcode, den der QR-Code verbessern sollte, ist der Strichcode im Einzelhandel: UPC in Nordamerika, EAN-13 anderswo. Norman Woodland und Bernard Silver meldeten 1949 das erste Patent für einen optisch gelesenen Code an, erteilt am 7. Oktober 1952. Nach Angaben des Europäischen Patentamts war der erste UPC-Scan an einer Kasse eine Packung Kaugummi in einem Supermarkt in Ohio im Jahr 1974, und ein solcher Strichcode fasst höchstens etwa 20 Zeichen.

Ein EAN-13-Strichcode ist 95 Module breit: ein Begrenzungsmuster von 3 Modulen an jedem Ende und 5 in der Mitte sowie 12 Ziffern zu je 7 Modulen. Die dreizehnte Ziffer wird nicht als Striche gedruckt; sie ist durch die Wahl zwischen zwei Mustern für die linken Ziffern codiert. Die letzte Ziffer ist eine Prüfziffer: Die Ziffern werden abwechselnd mit 1 und 3 gewichtet, und die Prüfziffer macht die Summe zu einem Vielfachen von 10. Das erkennt die meisten Fehler, kann aber keinen korrigieren. Stellen Sie mit Vergleich den Strichcode auf die Staffelei und decken Sie seine obere Hälfte ab, und er lässt sich weiterhin lesen, weil ein Scanner nur eine saubere Linie über alle Striche braucht. Decken Sie einen senkrechten Streifen ab, lässt er sich nicht lesen.

Micro QR, im November 2004 als JIS-Norm genehmigt, geht den anderen Weg. Es lässt zwei Positionsmuster weg und behält eines, verwendet einen Rand von zwei Modulen und kommt in vier Größen: M1 ist 11 mal 11 Module groß und fasst 5 Ziffern, M4 ist 17 mal 17 und fasst bis zu 35. Es hat nur vier Masken, seine Formatinformation trägt statt der Stufe eine Symbolnummer von 3 Bit, und in M1 und M3 ist das letzte Datencodewort nur 4 Bit lang. Die Staffelei zeigt eine Micro-QR-Fassung Ihres Textes, wenn er hineinpasst, in derselben Modulgröße wie das Symbol auf dem Tisch. Selbst M4 fasst weniger als Version 1 des vollen Codes.

Im Mai 2022 veröffentlichte die ISO den rechteckigen Micro-QR-Code, rMQR, für lange schmale Etiketten. DENSO WAVE beschreibt ihn als einen Code mit eineinhalb Positionsmustern, ab 7 mal 43 Modulen, mit bis zu 361 Ziffern in 17 mal 139 Modulen. DENSO WAVE hat außerdem iQR veröffentlicht, eine größere Familie mit rechteckigen Symbolen, Frame QR mit einem leeren Platz für ein Bild und SQRC, das einschränkt, wer einen Teil der Daten lesen kann. Forscher sind weiter gegangen: Chu und Kollegen zeigten 2013, wie man einen Code macht, der wie ein Halbtonbild aussieht und sich dennoch lesen lässt, indem man die Bilddetails innerhalb jedes Moduls platziert und sich auf die Fehlerkorrektur stützt.

Wie sich das Modell von echten Codes und Lesegeräten unterscheidet

Der Encoder deckt das, was die Norm Model 2 nennt, vollständig ab, für numerische, alphanumerische, Byte- und ECI-Segmente, die Versionen 1 bis 40, alle vier Stufen und alle acht Masken. Er verwendet pro Text ein Segment statt gemischter Modi, was ein sorgfältiger Encoder tun würde, um Bits zu sparen. Der Kanjimodus ist auf Kana beschränkt, weil die vollständige Shift-JIS-Tabelle groß ist; für diese Zeichen sind die Bits dieselben wie bei einem vollständigen Encoder. Structured Append, das eine Nachricht auf bis zu 16 Symbole verteilt, ist nicht umgesetzt.

Das Lesegerät auf der Bühne liest das Raster an bekannten Positionen. Es prüft die Positionsmuster danach, wie viele ihrer Module erhalten sind, und verlangt alle drei, wie es die meisten Telefon-Lesegeräte tun. Es dekodiert Format- und Versionsinformation genau so, wie die Norm es sagt, entfernt die Maske, korrigiert jeden Block mit Reed-Solomon-Dekodierung einschließlich des Schutzes vor Fehldekodierung und zerlegt den Bitstrom. Ein echtes Lesegerät muss außerdem mit Unschärfe, Blendung, Perspektive und einem Druck zurechtkommen, der dunkle Module in helle verlaufen lässt; die Bühne hat nichts davon.

Die Positionsmustersuche des Telefons läuft auf Pixeln und dreht sich mit dem Symbol, aber das Bild ist sauber und flach. Die Mal- und Fleckenwerkzeuge markieren ganze Module. Das Symbol ist auf dem Tisch immer 30 cm breit, damit man es sehen kann; echte Codes messen meist einige Zentimeter.

Die Zahlen in der Anzeige stammen alle aus dem Code auf dem Tisch. Die beiden unabhängigen Lesegeräte, die bei der Prüfung verwendet wurden (eine Open-Source-Bibliothek in JavaScript und eine weitere in C++), lasen alle 320 Testsymbole der Versionen 1 bis 10 in jeder Stufe und Maske, alle 120 Symbole der Versionen 11 bis 40, Micro-QR-Symbole aller acht Größen und Stufen und EAN-13-Strichcodes.

Eine kurze Geschichte

DENSO WAVE, damals eine Abteilung von DENSO, begann 1992 mit der Entwicklung des QR-Codes. Autofabriken stellten auf viele Modelle in kleinen Serien um, und Teile wurden mit etwa 10 Strichcodes je Produkt verschickt; Etiketten, die mit Öl verschmiert waren, ließen sich nicht lesen. DENSO sagt, das Entwicklungsteam habe aus zwei Personen bestanden. Es dauerte etwa anderthalb Jahre. Der Code wurde 1994 vorgestellt und konnte nach Angaben von DENSO WAVE etwa 7000 Ziffern fassen, Kanji codieren und mehr als 10-mal schneller gelesen werden als andere Codes. Das Europäische Patentamt bezifferte die Geschwindigkeit auf etwa das 20-Fache früherer Matrixcodes, als es dem Team 2014 den Publikumspreis des Europäischen Erfinderpreises verlieh.

Der Name steht für „quick response“, also „schnelle Antwort“, aber DENSO WAVE sagt, der offizielle Name sei QR Code und kein Akronym. Das Patent wurde am 14. März 1994 in Japan angemeldet und unter der Nummer 2938338 erteilt; das entsprechende US-Patent 5,726,435 nennt Masahiro Hara, Motoaki Watabe, Tadao Nojiri, Takayuki Nagaya und Yuji Uchiyama als Erfinder. DENSO WAVE behält das Patent, erklärt aber, die Rechte daraus bei genormten QR-Codes nicht geltend zu machen; nach eigener Aussage galt diese Regelung von Anfang an. QR Code ist eine eingetragene Marke von DENSO WAVE für das Wort, nicht für das Muster.

Die Autoindustrie übernahm den Code zuerst, für das elektronische Kanban, die Karten, die Teile abrufen. Nach Lebensmittelskandalen wie BSE nutzten Hersteller von Lebensmitteln, Arzneimitteln und Kontaktlinsen ihn, um Produkte zurückzuverfolgen. Normen folgten: AIM International im Oktober 1997, JEIDA-55 im März 1998, JIS X 0510 im Januar 1999 und ISO/IEC 18004 im Juni 2000. Die aktuelle, vierte Ausgabe erschien im August 2024.

Telefone, die QR-Codes lesen konnten, kamen 2002 in Japan auf den Markt und holten den Code aus den Fabriken. Im Dezember 2011 genehmigte ihn GS1, die Organisation hinter den Strichcodes im Einzelhandel, für Mobiltelefone. EMVCo veröffentlichte im Juli 2017 QR-Zahlungsspezifikationen; Singapur fasste am 17. September 2018 27 Zahlungssysteme in einem SGQR-Etikett zusammen; Brasilien startete Pix am 16. November 2020 mit 734 Instituten. Während COVID-19 nutzte Korea QR-Codes für Besucherlisten ab dem 10. Juni 2020, England und Wales hängten ab dem 24. September 2020 NHS-QR-Plakate an die Türen von Lokalen, und das digitale COVID-Zertifikat der EU, ein signierter QR-Code, war vom 1. Juli 2021 bis zum 30. Juni 2023 in Gebrauch. Händler planen inzwischen, dass Kassen bis Ende 2027 2D-Codes lesen.