Reed-Solomon-Fehlerkorrektur in QR-Codes
Wie Reed-Solomon-Codes in QR-Codes funktionieren: Galois-Feld-Arithmetik, Generatorpolynome und Codewort-Interleaving.
Reed-Solomon-Fehlerkorrektur in QR-Codes
Fehlerkorrektur ist das, was QR-Codes bemerkenswert widerstandsfähig macht. Die mathematische Antriebskraft hinter dieser Widerstandsfähigkeit ist die Reed-Solomon-Fehlerkorrektur (RS), ein Blockcode, der auf Arithmetik über endlichen Körpern basiert.
Was Reed-Solomon leistet
RS-Codes fügen Ihren Daten redundante Codewörter hinzu. Sind einige Codewörter beschädigt — durch Schmutz, Kratzer, Verblassen oder absichtliche Logo-Platzierung — kann der Decoder die beschädigten Positionen lokalisieren und die Originaldaten rekonstruieren. Ein RS-Code, der 2t Fehlerkorrektur-Codewörter hinzufügt, kann bis zu t beschädigte Codewörter korrigieren.
Galois-Feld-Arithmetik
RS-Codes in QR-Codes operieren über GF(256) — dem Galois-Körper mit 256 Elementen. Jedes Element entspricht einem Byte (0-255), und der Körper definiert spezielle Additions- (XOR) und Multiplikationsoperationen (unter Verwendung eines primitiven Polynoms). Das primitive Polynom für QR-Codes lautet:
x^8 + x^4 + x^3 + x^2 + 1 (dezimal 285)
Alle Codewort-Arithmetik — Kodierung, Syndromberechnung und Fehlerkorrektur — verwendet GF(256)-Operationen.
Generatorpolynome
Der Encoder erstellt ein Generatorpolynom, dessen Wurzeln aufeinanderfolgende Potenzen des primitiven Elements sind. Für n Fehlerkorrektur-Codewörter hat das Generatorpolynom den Grad n. Das Datenpolynom wird durch das Generatorpolynom geteilt, und der Rest wird zu den Fehlerkorrektur-Codewörtern.
Codewort-Interleaving
Große QR-Codes teilen Daten in mehrere Blöcke auf, jeder mit eigener RS-Fehlerkorrektur. Die Codewörter aus verschiedenen Blöcken werden dann im finalen Bitstrom interleaved (verschachtelt). Dies verteilt die Auswirkung lokalisierter Beschädigung auf mehrere Blöcke und verbessert die Wiederherstellung bei großen zusammenhängenden Schadensbereichen.
Die Decoder-Seite
Beim Dekodieren geht der Scanner wie folgt vor:
- Berechnet Syndrome — sind alle Syndrome null, liegen keine Fehler vor
- Verwendet den Berlekamp-Massey-Algorithmus, um das Fehlerlokator-Polynom zu finden
- Wendet die Chien-Suche an, um Fehlerpositionen zu finden
- Verwendet Forneys Algorithmus, um Fehlergrößen zu berechnen
- Korrigiert die fehlerhaften Codewörter
Praktische Auswirkungen
| EC-Stufe | EC-Codewörter (%) | Korrigierbare Codewörter (%) |
|---|---|---|
| L | ~20 % | ~7 % |
| M | ~38 % | ~15 % |
| Q | ~55 % | ~25 % |
| H | ~65 % | ~30 % |
Der „korrigierbare“ Prozentsatz beträgt etwa die Hälfte des EC-Codewort-Prozentsatzes, da jeder Fehler zwei EC-Codewörter benötigt, um lokalisiert und behoben zu werden. Sind die Fehlerpositionen bereits bekannt (Auslöschungen), genügt ein EC-Codewort pro Position.
Wichtige Erkenntnisse
- Reed-Solomon-Codes fügen redundante Codewörter für Fehlererkennung und -korrektur hinzu
- Die Arithmetik erfolgt in GF(256) unter Verwendung des primitiven Polynoms x^8+x^4+x^3+x^2+1
- Jeder korrigierbare Fehler verbraucht zwei EC-Codewörter
- Interleaving über Blöcke hinweg verteilt lokalisierte Beschädigung
- Die RS-Dekodierung verwendet Syndrome, den Berlekamp-Massey-Algorithmus, die Chien-Suche und Forneys Algorithmus