Diskussion:Reed-Solomon-Code

Müsste mal überarbeitet werden. Wenn ich mal Zeit haben, dann übersetze ich aus dem Englischen. --MauriceKA 15:25, 23. Aug 2004 (CEST)

---

4

Wer als "einfacher" Techniker versucht, den Grundgedanken aus Lehrbüchern zu verstehen, wird Probleme bekommen. Ich jedenfalls hab's vergeblich versucht. Durch die volle Allgemeingültigkeit und Exaktheit und durch die Formalisierung wird der Grundgedanke verschleiert. Ein Lob für die Autoren der Uni Paderborn. Wetten, daß die Erfinder Reed und Solomon durch eine ähnliche Sichtweise wie dort dargestellt erstmal draufgekommen sind? Die Herren Theoretiker sollten sich mal dazu herablassen, ihre Darstellung mit einer anschaulichen, informellen Schilderung des Grundgedankens einzuleiten. Hermann Tropf. am 26. Sep. 2006

---

wat? wie funzt das teil? das versteht doch keiner wie das hier beschrieben ist... man sollte sich mal ein beispiel an der englischen beschreibung für den hamming code nehmen, das ist mal gut erklärt, aber das hier sollte man eher löschen. (nicht signierter Beitrag von 84.176.211.116 (Diskussion) 02:33, 14. Jan. 2007)

Dito. Dieser Artikel mag inhaltlich korrekt sein (ich kann es nicht beurteilen), verständlich ist er nicht. Der könnte genauso gut auf Chinesisch geschrieben sein.

(nicht signierter Beitrag von Sibarius (Diskussion | Beiträge) 04:32, 12. Jun. 2007)

Dem kann ich mich leider nur anschließen. Formale Definitionen dieser Art mögen korrekt sein haben jedoch keinen praktischen Nutzen. Wäre schön, wenn Jemand dies mal allgemeinverständlicher formulieren könnte.

--Vossa 20:37, 22. Nov. 2011 (CET)

Erkennbare Fehler

RS kann bis zu (n - k) / 2 Fehler in einem Segment korrigieren.

Anders ausgedrückt, für jedes korrigierbare Element in einem Segment benötigt der Algorithmus 2 Elemente an Parity Informationen.

Wie viele Fehler in einem Segment können noch 100% sicher erkannt werden?

Ist interessant da sehr viele Fehler in einem Segment übersehen werden könnten, da der Algorithmus wieder ein scheinbar korrigierbares Ergebnis erzeugen könnte. Deshalb müßten Informationen zusätzlich mit einer Checksumme gesichert werden und extrem hohe Fehlerraten die scheinbar korrigierbar sind doch noch zu erkennen. Zur Fehlererkennung eignen sich Checksummen wahrscheinlich besser als Korrekturalgorithmen.

(bis zu einem bestimmten Grad ist der Algorithmus fähig zu erkennen, wenn er nicht mehr korrigieren konnte, und die Fehleranzahl größer ist als (n - k) / 2. Wo liegt die Obergrenze noch erkennbarer unkorrigiertbarer Fehler in einem Segment?) (nicht signierter Beitrag von 85.5.235.196 (Diskussion) 13:08, 16. Mär. 2007)

Verstehe ich teilweise nicht, was da gefragt wird. Sind das Fragen, Feststellungen oder Zitate? Welche Quellen?

Die Aussagen zur Korrektur von Fehlern oder Quellen gehen auf den Hamming-Abstand zurück. Da ein Kodewort mit k Nullen vom Nullpolynom erzeugt sein müsste und damit das Nullkodewort ist, hat jedes andere Kodewort max. k-1 Nullen und damit Hamming-Abstand n-k+1 vom Nullwort. Durch Suche des kleinsten Hamming-Abstandes des empfangenen Blocks zu jedem Kodewort können n-k+1-1 Ausfälle und (n-k+1-1)/2 Fehler korrigiert werden. Wie man das effektiv macht, ist dann die andere Frage.

Beachte bitte, dass bei einer systematischen Kodierung die letzten n-k Symbole des Kodewortes eine Art Prüfsumme darstellen. Für mehr Sicherheit muss mehr an Redundanz investiert werden. Den Rest der Anmerkung bitte nochmal deutlicher formulieren.--LutzL 15:28, 15. Aug. 2007 (CEST)

Ein Zahlernbeispiel mit 8-Bit Einheiten (8-Bit Wort): Daraus ergibt sich ein Segment an Daten von 255 Einheiten.

Für jede korrigierbare Einheit, werden 2 Einheiten als RS vom Segment verwendet.

Angenommen es sollen 4 Einheiten korrigierbar sein, so werden 8 vom Segment als Korrektur-Einheiten (RS-Daten) verwendet.

Also: 247 Daten-Einheiten + 8 Korrektur-Einheiten = 255 Segmentgröße, und 4 korrigiertbare Einheiten.

RS kann so bis zu 4 zerstörte Dateneinheiten korrigieren (Egal wo sie im Segment auftreten).

Sind nun mehr als 4 Einheiten zerstört und ist das Segment somit unkorrigierbar, ist der RS immer noch bis zu einem gewissen Grad im Stande ein Fehler zu erkennen.

Die Frage ist nun, wie viele fehlerhafte Einheiten größer als 4 kann RS noch 100% sicher als Fehlerhaft wenn auch unkorrigierbar erkennen, wenn 8 Einheiten RS-Code hinzugefügt werden?

(Die Frage ist interessant, da bei sehr vielen Fehlern in einem Segment, ein scheinbar korroigierbares Resultat, oder sogar ein fehlerloses Segment entstehen kann, obwohl das Datensegment eigentlich zerstört ist. Die Frage ist also, wie sicher kann RS fehlerhafte Segmente erkennen wenn sie nicht zusätzlich z.b. durch eine Checksumme gesichert sind. Das gleiche kann ja auch bei einer Checksumme passieren. Da Checksummen immer kleiner sind als die zu Prüfenden Daten, treten Kollisionen auf. Dabei ist aber meistens exakt berechenbar, wie hoch die Wahrscheinlichkeit eines nicht erkannten aber zerstörten Datensegments sind. Im Idealfall ist die Warscheinlichkeit einer Kollision einer Checksumme von 16-Bit Länge = 1:65536 (jedes 65536ste vollkommen zerstörte Datensegment könnte fälschlicherweise als OK durchgehen. Hat der Algorithmus schwächen, sind es sogar mehr, z.b. wenn eine 16-bit Checksumme über 16-bit Daten erzeugt werden, und bereits da Kollisionen auftreten.). Bei Hash-Verfahren können diese Wahrscheinlichkeiten z.b. für bewußt erzeugte Kollisionen verwendet werden um Signaturen zu fälschen.)

Ein Beispiel bitte.

Der Artikel ist immer noch reichlich mathematisch-akademisch. Vor allem fehlen Beispiele und Aussagen, wie die Kodierung, Fehler-Erkennung und Fehlerbehebung konkret aussehen. Der englische Artikel könnte da als Vorbilsd dienen.---<(kmk)>- 13:01, 13. Jul. 2008 (CEST)

Unerklärliche Begrenzungen

1. Erkennen RS-Codes auch Fehler? Oder können sie nur bereits erkannte Fehler (die etwa durch andere Verfahren erkannt worden sind) korrigieren?
   Sprich: Muss man beim Dekodieren wissen, welche Datenblöcke defekt sind? (Programme wie 'par' oder 'ras' ergänzen die einzelnen Blöcke um Prüfsummen und erkennen so, welcher der Blöcke defekt ist)
   Einfaches Beispiel: Ein Paritätsbit gilt als simpler Fehlererkennungs-Algorithmus, welcher aber von sich aus keine Fehler korrigieren kann. Weiß man aber, welches der Bits defekt/unlesbar ist, kann man dieses dank des Paritätsbits problemlos "reparieren".
2. Warum kann man über einen endlichen Körper $F$ nur RS-Codes der Länge $|F|-1$ aufbauen?
3. Warum ist es z.B. nicht möglich, über $GF(2)$ einen Code mit "m zusätzlichen Bits" zu erzeugen, der m Fehler korrigiert, sofern bekannt ist, welche Bits defekt sind?

--Beiträge/82.83.126.246 11:28, 15. Jun. 2009 (CEST)

Das ist inzwischen etwas unleserlich geworden. Mit m extra Stellen können Fehler an m (oder doch nur m-1) vorher bekannten Positionen korrigiert werden. Das ergibt sich daraus, dass aus den anderen Stellen immer noch das zugrundeliegende Polynom interpoliert werden kann. Mit der gleichen Anzahl an extra Stellen können (m-1)/2 Fehler an beliebigen Positionen erkannt und korrigiert werden. Der Algorithmus dazu ist bisher hier nicht dargestellt und etwas kompliziert. Theoretisch könnte man aber auch alle zulässigen Code-Worte durchprobieren und den mit dem kleinsten Abstand wählen. Bitte für Weiterführendes die verlinkten Seiten, insb. zum Hamming-Abstand und den MDS-Codes, konsultieren.--LutzL 12:56, 15. Jun. 2009 (CEST)

Danke. Aber damit hast du nur meine 1. Frage beantwortet. ;-)

Ich hatte versucht, einen Code zu erstellen, der eben nur einzelne Bits betrachtet und mit n "Redundanzbits" beliebige n Bitfehler (an bekannten Positionen) korrigieren sollte. Das hat jedoch schon für n=2 nicht geklappt. Kannst du einen solchen Code angeben? --Beiträge/82.83.126.246 16:32, 15. Jun. 2009 (CEST)

Nochmal lesen, das war die Antwort auf die zweite Frage. Und es geht, mit einer angepassten Version der Polynominterpolation, ob nun Lagrange oder Newton. Die erste Frage verstehe ich nicht, so werden über F2 Codes beliebiger Länge erzeugt und verwendet.--LutzL 12:38, 24. Jun. 2009 (CEST)

Naja, ich meinte den ersten Stichpunkt oder "Fragenkomplex" von den dreien, die ich schrieb. --82.83.126.246 16:03, 24. Jun. 2009 (CEST)

Beispiel-Codetabelle

	Datenbits				Redundanzbits
	$d_{0}$	$d_{1}$	$d_{2}$		$r_{0}$	$r_{1}$	$r_{2}$	$r_{3}$
0	0	0	0		0	?	?	?
1	0	0	1		1	?	?	?
2	0	1	0		1	?	?	?
3	0	1	1		0	?	?	?
4	1	0	0		1	?	?	?
5	1	0	1		0	?	?	?
6	1	1	0		0	?	?	?
7	1	1	1		1	?	?	?

Mal ein Beispiel für den 3. Stichpunkt: Drei Datenbits sollen um n "Redundanz-Bits" erweitert werden, so dass man die Originaldatenbits wiederherstellen kann, solange mind. 3 der n übertragenen Bits intakt sind (und bekannt ist, welche Bits intakt sind). Das erste Redundanzbit kann ein einfaches XOR oder dessen Inverses sein (auch als EQU oder XOR bekannt).

Ich habe alle möglichen Belegungen für die Spalte $r_{2}$ durchprobiert, mit keiner ließen sich die Datenbits stets eindeutig wiederherstellen. :-| Darum meine Frage: Wieso klappt das nicht? Wie sähe die Tabelle für Doppelbits ($=GF_{4}$) – wo das ja möglich sein müsste – aus? Vielleicht wird meine Frage ja nun klarer... --82.83.126.246 16:23, 24. Jun. 2009 (CEST)

Nachtrag: Geht man systematisch vor, findet man:

1. $r_{1}$ in Zeile 0 sei $x$.
2. $r_{1}$ in Zeile 1 muss ­­${\bar {x}}$ sein, um Zeile 0 und 1 unterscheiden zu können, falls die Bits $d_{2}$ und $r_{0}$ zerstört sind.
3. Das gleiche gilt für $r_{1}$ in allen anderen Zeilen, wo 2 Spalten 0 sind, also Zeile 2, 3, 4, 5 und 6.
4. Damit sind aber z.B. die Zeilen 2 und 4 nicht mehr unterscheidbar, wenn die Bits $d_{0}$ und $d_{1}$ ausfallen!

Somit: Es gibt keinen Code, der in $GF_{2}$ diese Eigenschaften erfüllt. --82.83.126.246 16:43, 24. Jun. 2009 (CEST)

Wie sieht das nun mit $GF_{2\times 2}$ oder $GF_{4}$ aus? --RokerHRO 14:06, 17. Aug. 2011 (CEST)

Hi, die Frage hat aber offensichtlich nichts mit der Verbesserung dieses Artikels zu tun. Du möchtest vielleicht allgemein ein Buch zur Kodierungstheorie lesen oder das im Artikel verlinkte Skript.--LutzL 16:43, 18. Aug. 2011 (CEST)

Ich hätte gehofft, dass der Artikel mir diese Frage beantwortet, wie viele Auslöschungen ein RS-Code über einen gegebenen Körper K überhaupt beheben kann. Darüber steht aber leider nichts im Artikel. Oder finde ich es nur nicht?

Meine Beispiele sollten nur veranschaulichen, dass ein Code über $GF_{2}$ nur max. 1 Auslöschung beheben kann und ich mag das für andere Körper nicht händisch ausprobieren müssen, darum hab ich hier in den Artikel geschaut. Leider ohne Erfolg. :-( --RokerHRO 09:58, 19. Aug. 2011 (CEST)

Das war oben schon beantwortet. Im Artikel ist das nur implizit beantwortet, da nur der Mindestabstand bzw. das Gewicht des Codes angegeben ist, für den Rest wird auf die allgemeineren Artikel zu linearen Codes verwiesen. Müsste mal umsortiert und ergänzt werden. Bist Du identisch zu der IP oben? Ich hatte das bisher als zwei verschiedene Personen gelesen.

Der Code RS(p,m,n) hat die Einschränkungen n<=p, m<n, p eine Primzahlpotenz. Ist p=2^k, dann werden Nachrichten von m*k Bits in Codeworte von n*k Bits umgewandelt. Die Nachricht kann aus beliebigen m der n Symbole rekonstruiert werden, wenn diese als korrekt bekannt sind, also können n-m Ausfälle korrigiert werden. Es können c Fehler unbekannter Position korrigiert werden, wenn 2c<=n-m.

Da 3 eine Primzahl ist, müsste k=3 gewählt werden. Wegen m=1 wären alle vorkommenden Polynome konstant, der Code bestünde einfach aus Wiederholungen. Zwei Bitfehler können dann aber auch schon zu zwei Symbolfehlern führen, so dass oben genannte Frage nicht mit RS-Codes beantwortet werden kann.--LutzL 11:51, 19. Aug. 2011 (CEST)

Danke für deine Antwort. :-) Ich hoffe, ich hab es jetzt einigermaßen kapiert. Es wäre natürlich prima, wenn das in der Klarheit auch im Artikel stünde. Hm, wo würde das am besten reinpassen?

Die obige Codetabelle etc. waren von mir, ja. Schon eine Weile her, als ich mich fragte, wie Programme wie PAR funktionieren und wieso sie nur ein m+n<256 zulassen (ob es eine prinzipielle Begrenzung der Algorithmen oder nur ein Implementierungs-Limit ist). Durch Lesen des Quellcodes wurde ich jedenfalls nicht schlau, also habe ich versucht, mich ein wenig in die dahinterstehende Mathematik einzulesen, ohne gleich ein Mathe-Studium anfangen zu müssen. ;-( --RokerHRO 10:19, 20. Aug. 2011 (CEST)

Burstfehler Korrektur

Der Reed-Solomon-Code ist nur bedingt zur Burstfehler Korrektur geeignet.

Block- und Faltungscodes (wie der Reed-Solomon Code) arbeiten nur bei statistisch unabhängigen Fehlern gut. Um die Burstfehler statistisch unabhängig zu machen werden im Mobilfunk, der Satellitenübertragung und bei DVB Codespreizverfahren eingesetzt (Interleaving), da er nicht funktioniert wenn ganze Symbole betroffen sind. Im Anschluss wird dann der Reed-Solomon-Code verwendet um die über die einzelnen Symbole verteilten Fehler zu korrigieren. (nicht signierter Beitrag von 94.219.38.3 (Diskussion) 12:16, 14. Jul 2015 (CEST))