Ursprung und weitere Verbreitung
Reed-Solomon-Codes wurden 1960 von Irving S. Reed und Gustave Solomon beschrieben. Sie arbeiten mit ganzen Symbolen, meist Bytes, statt mit einzelnen Bits, weshalb sie gut mit Schadensbündeln wie einem Kratzer oder einem Fleck umgehen.
Dieselbe Code-Familie schützt Daten auf CDs, DVDs und Blu-ray-Discs, in einigen digitalen Fernseh- und Satellitenverbindungen und in anderen 2D-Barcodes wie Data Matrix ECC 200, Aztec-Code und PDF417.
Wie QR-Codes sie nutzen
Ein QR-Code behandelt jedes 8-Bit-Codewort als Element des endlichen Körpers GF(256), aufgebaut mit dem primitiven Polynom x^8 + x^4 + x^3 + x^2 + 1 (hex 0x11D). Die Datencodewörter werden durch ein Generatorpolynom geteilt, und der Rest wird zu den angehängten Fehlerkorrekturcodewörtern.
Größere Codes teilen ihre Daten in mehrere Blöcke auf, jeder mit eigenen Fehlerkorrekturcodewörtern. Die Blöcke werden beim Platzieren der Codewörter im Raster verschränkt, sodass sich eine einzelne beschädigte Stelle auf viele Blöcke verteilt, statt einen zu überfordern.
Wie viel sie beheben kann
Bei n Fehlerkorrekturcodewörtern in einem Block kann ein Decoder bis zu n/2 Codewörter korrigieren, deren Position unbekannt ist, oder bis zu n Codewörter, deren Position bekannt ist, sogenannte Auslöschungen. Für gemischte Fälle gilt die Regel, dass jeder Fehler doppelt und jede Auslöschung einfach zählt.
Deshalb lässt sich ein Code mit einer sauberen, flachen Fläche unter einem Logo noch scannen: Ein kluges Lesegerät kann die verdeckte Region als Auslöschungen behandeln, während zufällige Schäden schwerer zu beheben sind, weil der Decoder sie erst finden muss.
- Unbekannte Fehler: bis zur Hälfte der Anzahl der EC-Codewörter
- Auslöschungen (bekannte Positionen): bis zur Anzahl der EC-Codewörter
- Körper: GF(256), Polynom 0x11D
- Blöcke werden verschränkt, um Schadensbündel zu verteilen