Inhalt
Kurz gesagt: Ein QR-Code speichert nicht nur seine Nachricht. Er fügt Ersatzbytes hinzu, die aus ihr berechnet werden: Reed-Solomon-Fehlerkorrektur, dieselbe Mathematik wie auf Musik-CDs. So kann ein Leser Bytes wiederherstellen, die fehlen oder falsch sind. Wie viele, legst du fest: Vier Stufen, L, M, Q und H, stellen etwa 7, 15, 25 und 30 % der Codewörter wieder her, und mehr Ersatzbytes machen den Code größer. Deshalb kann ein Logo in der Mitte funktionieren: Für den Leser ist es ein Schaden. Die drei Eckquadrate sind etwas anderes: Sie sind keine Daten, sondern helfen dem Leser, den Code zu finden und gerade zu rücken, und die meisten Leser brauchen sie.
Zerrissen, verschmutzt, und er scannt
DENSO WAVE, das Unternehmen, das den QR-Code entwickelt hat: „QR Code has error correction capability to restore data if the code is dirty or damaged.“ (Der QR-Code kann Fehler korrigieren und Daten wiederherstellen, wenn der Code verschmutzt oder beschädigt ist.) Und in seiner Liste der Merkmale: „Data can be restored even if the symbol is partially dirty or damaged.“ (Daten lassen sich wiederherstellen, auch wenn das Symbol teilweise verschmutzt oder beschädigt ist.)
Der Code im Video ist echt: Er enthält oliverz.dev. An einer Ecke zerrissen, am Rand verschmutzt und in der Mitte von einem Logo verdeckt, sind 13 seiner 44 Codewörter falsch, und er lässt sich trotzdem dekodieren (getestet mit zwei Decodern, jsQR und ZXing).
Ersatzbytes, aus der Nachricht berechnet
DENSO WAVE: „The QR Code error correction feature is implemented by adding a Reed-Solomon Code… to the original data.“ (Die Fehlerkorrektur des QR-Codes entsteht, indem den ursprünglichen Daten ein Reed-Solomon-Code hinzugefügt wird.) Der Computer Science Field Guide der University of Canterbury sagt es einfacher: „it adds extra bits to the data so that errors can be corrected.“ (Er fügt den Daten zusätzliche Bits hinzu, damit sich Fehler korrigieren lassen.)
Die Einheit ist das Codewort. DENSO WAVE: „codeword is a unit that constructs the data area. One codeword of QR Code is equal to 8 bits.“ (Das Codewort ist eine Einheit, aus der der Datenbereich besteht. Ein Codewort des QR-Codes entspricht 8 Bit.) Und der CS Field Guide: „Each black or white square (“dot” or “module”) corresponds to one bit of data.“ (Jedes schwarze oder weiße Quadrat, „Punkt“ oder „Modul“, entspricht einem Bit an Daten.) Acht Module ergeben also ein Byte.
Die Mathematik ist nicht neu. DENSO WAVE: „Reed-Solomon Code is a mathematical error correction method used for music CDs etc. The technology was originally developed as a measure against communication noise for artificial satellites and planetary probes.“ (Der Reed-Solomon-Code ist ein mathematisches Fehlerkorrekturverfahren, das unter anderem bei Musik-CDs verwendet wird. Die Technik wurde ursprünglich gegen Kommunikationsrauschen bei künstlichen Satelliten und Planetensonden entwickelt.)
Zwei Ersatzbytes für jedes korrigierte Byte
DENSO WAVE: „Reed-Solomon Code requires twice the amount of codewords to be corrected.“ (Der Reed-Solomon-Code braucht doppelt so viele Codewörter, wie korrigiert werden sollen.) Der CS Field Guide: „The maximum number of errors that a Reed-Solomon code can correct is one half of the amount of extra error correcting data added to it.“ (Die höchste Zahl an Fehlern, die ein Reed-Solomon-Code korrigieren kann, ist die Hälfte der hinzugefügten Fehlerkorrekturdaten.)
Unser Code hat auf der höchsten Stufe 16 Codewörter für die Nachricht und 28 Ersatzcodewörter, zusammen 44. Die Hälfte von 28 ist 14, also kann er bis zu 14 falsche Codewörter reparieren: 14 von 44 sind etwa 32 % (unsere Rechnung), DENSOs „Approx. 30%“ (ca. 30 %). In unserem Test lag die Grenze genau dort: Mit 14 falschen Codewörtern wurde er gelesen, mit 15 kam kein Ergebnis.
Kein Ergebnis, kein falsches. Der CS Field Guide: „they won’t read the data incorrectly, instead they just refuse to give any data at all, rather than giving you incorrect data.“ (Sie lesen die Daten nicht falsch, sondern verweigern einfach jede Ausgabe, statt dir falsche Daten zu liefern.)
Vier Stufen: 7 bis 30 %
Aus DENSO WAVEs Überblick über den Standard (ISO/IEC 18004): „Level L Level M Level Q Level H Approx. 7% of codewords can be restored. Approx. 15% of codewords can be restored. Approx. 25% of codewords can be restored. Approx. 30% of codewords can be restored.“ (Stufe L, M, Q, H: ca. 7 % der Codewörter wiederherstellbar; ca. 15 %; ca. 25 %; ca. 30 %.)
Der Prozentsatz zählt Codewörter, nicht die sichtbare Fläche: „*Data restoration rate for total codewords“ … „QR Code therefore represents its error correction rate as a ratio of the total codewords.“ (*Wiederherstellungsrate bezogen auf alle Codewörter … Der QR-Code gibt seine Fehlerkorrekturrate daher als Anteil an allen Codewörtern an.)
Mehr Ersatzbytes brauchen Platz. DENSO WAVE: „Raising this level improves error correction capability but also increases the amount of data QR Code size.“ (Eine höhere Stufe verbessert die Fehlerkorrektur, erhöht aber auch die Datenmenge und die Größe des QR-Codes.) Und: „as the amount of data increases, more modules are required to comprise QR Code, resulting in larger QR Code symbols.“ (Mit wachsender Datenmenge braucht der QR-Code mehr Module, und die Symbole werden größer.) Unsere vier Codes von oliverz.dev, Codewörter für Nachricht + Ersatz:
- L: 19 + 7, 21 × 21 Module
- M: 16 + 10, 21 × 21 Module
- Q: 13 + 13, 21 × 21 Module
- H: 16 + 28, 25 × 25 Module (auf Stufe H passen die 11 Bytes von „oliverz.dev“ nicht mehr in 21 × 21)
Ein Logo ist ein Schaden, den er repariert
Deshalb kann ein Logo in der Mitte funktionieren: Der Leser behandelt es als Schaden und stellt wieder her, was es verdeckt. Auf unserem H-Code macht ein Logo von 7 × 7 Modulen 9 seiner 44 Codewörter falsch, innerhalb der Grenze von 14.
Umsonst ist das aber nicht: Es verbraucht die Ersatzbytes. DENSO WAVEs FAQ über Codes mit Farben oder einer eingefügten Illustration: „If it is deformed, the QR Code's error correction function is invoked where even a tiny missing or smeared part renders the reading operation impossible, or the response of the operation may become slow.“ (Ist er verformt, greift die Fehlerkorrektur des QR-Codes, und dann kann schon ein winziges fehlendes oder verschmiertes Stück das Lesen unmöglich machen oder es verlangsamen.)
Die Ecken nicht verdecken
Die drei großen Quadrate sind keine Daten. DENSO WAVE: „QR Code accomplishes this task through position detection patterns located at the three corners of the symbol.“ (Der QR-Code erreicht das mit Positionsmarkierungen an drei Ecken des Symbols.) Die Geschichte des Codes auf DENSO WAVEs Seite: Mit ihnen „the orientation of their code could be determined regardless of the angle of scanning, which could be any angle out of 360°“ (ließ sich die Ausrichtung des Codes bestimmen, egal aus welchem Winkel gescannt wurde, aus jedem der 360°).
Der CS Field Guide: „Don’t colour in near the three large squares in the corners, as most QR scanners need these to align the image.“ (Male nicht in der Nähe der drei großen Quadrate in den Ecken, denn die meisten QR-Scanner brauchen sie, um das Bild auszurichten.)
In unserem Test reichte ein kleiner Aufkleber von 3 × 3 Modulen auf der Mitte eines Eckquadrats, damit beide Decoder scheiterten, ohne dass ein einziges Datenbyte berührt wurde. Das Logo verdeckt 49 Module und scannt; der Aufkleber verdeckt 9 und scannt nicht.
Fazit
- Ein QR-Code speichert seine Nachricht plus daraus berechnete Ersatzbytes (Reed-Solomon), deshalb stellt ein Leser Bytes wieder her, die zerrissen, verschmutzt oder verdeckt sind.
- Wie viele, wählst du: L, M, Q, H, etwa 7 bis 30 % der Codewörter; mehr Ersatzbytes, ein größerer Code. Ein Logo in der Mitte ist ein Schaden, den die Ersatzbytes abdecken.
- Die drei Eckquadrate sind keine Daten: Sie helfen dem Leser, den Code zu finden und gerade zu rücken, und die meisten Leser brauchen sie.
Quellen
- DENSO WAVE: Error Correction Feature, QR Code Standardization, What is a QR Code?, Information capacity and versions of the QR Code, History of QR Code, FAQ
- University of Canterbury, Computer Science Field Guide, QR codes
Das Video ist mit Code animiert, und das Skript entstand mit KI-Unterstützung; jedes Zitat oben ist an seiner Quelle geprüft, und die mit „unsere Rechnung“ markierte Zahl stammt von uns. Die Codes sind echt (erzeugt, dann mit jsQR und ZXing dekodiert), ebenso ihre Bytes und die Zahl ihrer Codewörter. Illustrativ: der Riss, der Fleck und das Logo (ein neutrales Zeichen, genau auf die getesteten Module gezeichnet), der Kamerasucher und der gekippte Code, derselbe Code perspektivisch gezeichnet. Echte Abnutzung ist weniger ordentlich als ein Schaden, der den Modulen folgt. „QR Code“ ist eine eingetragene Marke der DENSO WAVE INCORPORATED. Das Video ist auf Englisch vertont. Gemacht mit Shotloop, meiner kostenlosen Mac-App für Erklärvideos aus Code, korrigiert Shot für Shot.
