So funktioniert die Fehlerkorrektur von QR-Codes: die Reed-Solomon-Mathematik erklärt

1. Was ist die Reed-Solomon-Fehlerkorrektur?

Die Reed-Solomon-Fehlerkorrektur (RS) wurde 1960 von den Mathematikern Irving S. Reed und Gustave Solomon erfunden. Sie ist ein nicht-binärer zyklischer Fehlerkorrekturalgorithmus, der in der Raumfahrt-Telekommunikation (NASA Voyager), auf optischen CDs und DVDs, im Satellitenfernsehen und im Standard ISO/IEC 18004 für QR-Codes weit verbreitet ist.

Statt Fehler nur zu erkennen (wie ein einfaches Paritätsbit oder eine CRC-Prüfsumme), erzeugt der Reed-Solomon-Code redundante mathematische Paritätsblöcke, die die genaue Position beschädigter Byte-Module bestimmen und die ursprünglichen Nutzdaten rekonstruieren können, ohne dass die Übertragung erneut angefordert werden muss.

2. Die 4 Fehlerkorrekturstufen von QR-Codes

Der Standard ISO/IEC 18004 legt vier wählbare Fehlerkorrekturstufen (ECC, Error Correction Code) fest. Jede Stufe gibt an, welcher Anteil aller Codewörter zerstört oder verdeckt sein darf, bevor der Code unlesbar wird:

3. Wie eingebettete Logos die Fehlerkorrektur nutzen

Wenn Sie ein Logo oder Symbol in die Mitte eines QR-Codes setzen, interpretiert der optische Sensor des Scanners das Logo als physische Beschädigung der Oberfläche oder als fehlende Module.

Da Fehlerkorrekturstufe Q bis zu 25 % und Stufe H bis zu 30 % beschädigter Daten wiederherstellen kann, berechnet der mathematische Reed-Solomon-Decoder die fehlenden Module unter dem Logo und rekonstruiert die ursprüngliche URL in Millisekunden.

4. Die mathematische Verarbeitung im Galois-Körper GF(256)

Der Encoder, der in Ihrem Browser läuft, rechnet in einem endlichen Körper mit 256 Elementen, geschrieben GF(2⁸) oder GF(256). Jedes Byte ist ein Element dieses Körpers, und die Multiplikation ist modulo des folgenden primitiven Polynoms definiert:

Die Datenbytes werden als Koeffizienten eines Polynoms D(x) behandelt. Die Engine multipliziert es mit x^E, wobei E die Anzahl der Fehlerkorrektur-Codewörter ist, die die Stufe vorsieht, und teilt das Ergebnis durch ein festes Generatorpolynom G(x) für diese Stufe. Der Rest dieser Division ist die Parität: E Bytes, die im Symbol hinter den Daten platziert werden.

5. Die 8 ISO-Maskenmuster & die Strafpunktbewertung

Sind die Fehlerkorrektur-Codewörter berechnet, könnte das bloße Einsetzen der binären Bytes in das Raster versehentlich große rein schwarze oder rein weiße Flächen erzeugen oder falsche „Positionsmarkierungen“, die optische Kamerasensoren verwirren.

Um das zu verhindern, legt der Standard ISO/IEC 18004 8 mathematische XOR-Maskenmuster als Kandidaten über das Raster. Die Engine bewertet jeden maskierten Kandidaten mit einer strengen Strafpunktformel:

• Strafe 1 (Folgen benachbarter Module): Zusammenhängende Folgen von 5 oder mehr gleichfarbigen Modulen ergeben 3 Punkte plus 1 Punkt für jedes Modul über fünf hinaus.
• Strafe 2 (Blöcke aus 2x2 Modulen): Jedes einfarbige 2x2-Quadrat ergibt 3 Strafpunkte.
• Strafe 3 (falsche Positionsmarkierungen): Jede Modulfolge im Verhältnis 1:1:3:1:1 ergibt 40 Strafpunkte.
• Strafe 4 (Ungleichgewicht zwischen Dunkel und Hell): Eine Abweichung vom Verhältnis 50/50 ergibt proportional Strafpunkte.

Das Maskenmuster mit der niedrigsten Gesamtpunktzahl wird ausgewählt und in den Formatinformationsbits rund um die Positionsmarkierungen codiert.

6. Widerstandsfähigkeit gegen reale Umwelteinflüsse

Die richtige Fehlerkorrekturstufe ist entscheidend für Materialien, die Witterung oder Abnutzung ausgesetzt sind:

7. Daten- und Fehlerkorrektur-Codewörter nach Version

Jede Version hat eine feste Anzahl von Codewörtern zu je acht Bit, und die Stufe entscheidet, wie viele davon Ihre Daten und wie viele Wiederherstellungsdaten tragen. Die ersten drei Versionen sehen so aus.

Die Datencodewörter bestehen nicht vollständig aus Nutzdaten. Die ersten Bits enthalten den Modusindikator und die Zeichenanzahl, die im Byte-Modus bis Version 9 zwölf Bit und ab Version 10 zwanzig Bit belegen. Deshalb fasst ein Symbol der Version 1 auf Stufe L 17 Bytes Ihrer Daten statt 19.

Auf Stufe H überwiegen die Wiederherstellungsdaten bereits ab Version 1 die Nutzdaten. Genau diesen Tausch geht die Logo-Option ein, wenn sie die Stufe anhebt: weniger Bytes Platz, dafür ein Symbol, das sich auch dann noch lesen lässt, wenn ein Teil davon übermalt ist.