Reed Solomon Fehlerkorrektur?
-
In allwissenden Internet lassen sich zwar jede Menge Seiten ergooglen, die erklären, was das ist und wofür es gut ist, aber irgendwie finde ich den Wald vor lauter Bäumen nicht. Jedenfalls keine konkreten Hinweise wie es funktioniert bzw. gemacht wird. Hat jemand eine Ahnung wie der Algorithmus der Reed-Solomon Fehlerkorrektur konkret aussieht oder wo man sich darüber schlau machen kann
-
hast du die mathematische basis dahinter schon intus? wenn nein, würd ich mal nach nem vorlsungsskript suchen, das das behandelt. wenn ja: http://www.eccpage.com/rs.c (hab ich grad gefunden)
noch die seite von meim mathe prof: http://www.mi.uni-erlangen.de/~kurzweil/ (der macht sowas haupsächlich)
und da das skript: http://www.mi.uni-erlangen.de/~kurzweil/inf1.pdf (such nach reed oder codes)
-
Au weia - da habe ich ja voll in die merde gegriffen. Die Zauberwörter zum Googlen heißen "Galois fields", "Welch-Berlekamp", "Guruswami-Sudan", "Feng-Zeng" und "Roth-Ruckenstein". Und schon findet sich bei der NASA z.B. ein 60-Seiten PDF, wo's umfassend - aber sowas von gründlich - ähm - erklärt wird...
In dem Script von Prof. Kurzweil ist die RS-De/Kodierung leider nur kurz und oberflächlich angeschnitten. OK, dass die zu kodierenden Daten im Prinzip als Durchlaufpunkte einer Polynomkurve betrachtet werden und statt der Daten die Koeffizienten des Polynoms übertragen werden, aus denen die komplette Kurve rekonstruiert werden kann, auch wenn einzelne Stützpunkte daneben liegen, habe ich soweit kapiert. Die etwas merkwürdige Logik dieser Galois Felder zur Vermeidung langwieriger Gauss-Elimination will mir aber noch nicht so recht einleuchten. Da wird halt immer nur bewiesen, warum es funktionieren muss - aber nicht wie es funktioniert. Typisch Mathematiker. Aber bei dem relativ geringen Datenumfang von Data Matrix Codes mit maximal 144x144bit wird's letztendlich im Wesentlichen auf Lookup-Tabellen hinauslaufen.
Diverse C-Sourcen für Berlekamp-Massey- und euklidischen Algorithmus finden sich bei the-art-of-ecc.com. Allerdings mit horrendem Programmierstil - selten zuvor so ein saumäßiges Geschmiere gesehen. Womit mal wieder bewiesen wäre, das gute Mathematiker nie gute Programmierer sind. OK, Hauptsache der Algorithmus funktioniert, aber irgendwie ekelt's mich, diesen Code aufzuräumen, damit er lesbar und kompilierbar wird.
Über eccpage fanden sich auf Phil's home page auch noch ein paar C++ Sourcen, die interessant sein könnten. Das muss ich mir alles nochmal durch den Kopf gehen lassen ...