Reed-Solomon oder RS ist ein leistungsfähiger Fehlerkorrekturalgorithmus (ECC Error-Correcting-Code) über den es möglich ist in Daten auftretende Fehler zu korrigieren, und ist eine Erweiterung des BCH-Code Verfahrens. Ein solcher Algorithmus versucht dabei möglichst viele Fehler zu korrigieren mit möglichst wenigen zusätzlichen Korrekturdaten. Dabei Spielt es keine Rolle ob die Fehler in den Daten selbst, oder in den zusätzlichen Fehlerkorrektur-Daten auftreten. Der Algorithmus funktioniert so das Bitgruppen korrigiert werden können, deshalb werden meistens 8 Bit verwendet. Aus einer Bit-Wortlänge ergibt sich eine feste Größe an Daten die korrigiert werden können, also ein Datensegment in dem je nachdem wie viel Fehler korrigiert werden könnten sollen mehr oder weniger Daten zur Fehlerkorrektur verwendet werden. Dabei gilt für jedes Wort (8-Bit Gruppe) das korrigiert werden soll, müssen 2 Worte an Fehlerkorrektur-Daten im Datensegment verwendet werden. Bei einer Wortlänge von 8 Bit ergibt sich einem feste Segmentlänge von 255 Worten in dem man 2 fehlerhafte Worte korrigieren können will müssen also 4 Worte reserviert werden wodurch noch 251 Worte für die tatsächlichen Daten übrig bleiben. Wird ein Segment nicht komplett mit Daten gefüllt bleiben die restlichen Worte leer (0).
Reed-Solomon wird als Fehlerkorrektur auf CD-Rom DVD und Harddisks und auch in der Datenübertragung verwendet. Bei Datenmedien müssen die Daten gegen Zerstörung geschützt werden, bei Kommunikation reicht oft auch eine Checksumme zur Prüfung der Daten, und falls diese nicht korrekt ist kann das Kommunikationsprotokoll die Daten einfach noch einmal anfordern. Ein Nachteil des Algorithmus ist es nämlich das die Brechungen relativ aufwendig sind und deshalb Zeit brauchen. Reed-Solomon kann bis zu einem bestimmten Grad auch erkennen das Fehler stattgefunden haben auch wenn diese zu schwerwiegend sind um sie korrigieren zu können da nicht genügend Korrekturdaten vorhanden sind. Spezielle Checksummen Verfahren die keine Korrektur ermöglichen müssen sind dann allerdings leistungsfähiger oder platzsparender.
In der Praxis gibt es Situationen in welchen auf Grund der Datenübertragung oder Speicherung meistens nicht nur einzelne Worte zerstört werden sonder eine Kette von Wörtern. Bei der Datenübertragung kann zB. ein Knacken mehrere Worte hintereinander zerstören, das gleiche gilt für ein Kratzer auf einer CD. Um solche langen Datenfehler korrigieren zu können, kann man ein sogenanntes Cross-Interleave-Reed-Solomon Verfahren verwenden. Es funktioniert so das man die Daten in ein zweidimensionales Feld aufteilt, und dann die Daten einmal in der X und einmal in der Y Achse mit Fehlerkorrektur-Daten versieht. Auf diese Weise kann man die Daten doppelt und über kreuz schützen. Und dies läßt sich noch einmal verstärken in dem man mehrere Felder verschachtelt übereinander legen kann. Auf diese weise wird die Fehlerkorrektur sehr stark. Für CD und DVD verwendet man dieser verstärkte Variante um die Daten ausreichend gegen zerstörte Informationen durch Oberflächenfehler oder Kratzer zu schützen.
Im schlimmsten Fall kann es sein das so viele Fehler auftreten das daraus wieder ein scheinbar sinnvolles aber falsches Ergebnis berechenbar erscheint. Um dies zu verhindern können die Datensegmente zusätzlich mit einer Checksumme geschützt werden damit auch eine falsche Rekonstruktion der Daten erkennbar ist. Das dann noch ein Fehler in einer Daten übersehen wird ist zwar nicht unmöglich aber extrem unwahrscheinlich.
Besonders bei Cross-Interleave-Reed-Solomon ist die Korrektur zeitaufwendig da es notwendig ist die Daten mehrmals kreuz und quer zu vergleichen biss entweder alle Fehler beseitigt werden konnten oder eine Korrektur als unmöglich erkannt wurde.
Reed-Solomon wird schwach wenn Informationen nicht einzeln zerstört wurden sondern eine Information aus den Daten entfernt wird und sich so die Position der Worte ändert. Dies tritt aber im Normalfall weder bei Datenspeichern wie CD noch bei Datenübertragung auf, da die Position der Worte meistens unveränderlich ist.
Dies ist nur ein simples Test-Programm, und um die Zahlen von Hand eingeben zu können wurde eine Wortlänge von nur 4 Bit gewählt um eine Segmentlänge von 15 zu erhalten. Um aber zB. Dateien gegen Zerstörung schützen zu können werden 8 Bit verwendet und je nach Bedarf können die Parity-Informationen entweder in der Datei selbst untergebracht oder auch in einer zweiten Datei gespeichert werden.
Das Programm ist Freeware und liegt im Download.
