Warum GF für Reed-Solomon

[Steffen Hausinger (Gast)]

Hallo allerseits,

warum findet das Reed-Solomon Verfahren im Galoisfeld ab? Ich meine, es 
hat etwas mit der Abgeschlossenheit der Felder zu tun, bin mir aber 
nicht ganz sicher. Eine Modulo 2^m Berechnung wäre doch genauso 
abgeschlossen.

Kann mir jemand den Grund erklären?

Viele Grüße,
Steffen

[Alban (Gast)]

Deine Frage hat mich bewogen mal darüber was zu lesen, da ich bisher 
noch keine Ahnung davon hatte. Wahrscheinlich ist deine Frage 
tiefgreifender als ich es verstehe.

Ein Hamming code scheint z.B. so eine Modulo Berechnung zu sein, wie du 
sie zum Vergleich heranziehst. Wenn ich das richtig verstehe, kann mit 
dem Hamming Code in einem Datenwort ein einziger Bitfehler erkannt und 
behoben werden.

Der Vorteil des RS Code liegt darin, dass er mehrere Bitfehler in einem 
Datewort erkennen und beheben kann. Ein weiterer Vorteil scheint zu 
sein, dass eine Berechnung im Galois Feld sehr einfach zu implementieren 
ist.

Gruß,

Alban

[Steffen Hausinger (Gast)]

Hallo Alban

es stimmt, dass ein RS Code mehrere Bitfehler erkennen und korrigieren 
kann. Das liegt daran, dass er symbolorientiert arbeitet und damit 
mehrere Bits zusammenfasst. Es ist ihm dann egal, ob im Symbol ein Bit 
oder alle Bit falsch sind - eine falsches Symbol ist ein falsches Symbol 
und kann korrigiert werden.

Leider ist die Berechnung im Galoisfeld eben nicht einfach, so bin ich 
auch erst auf die Frage gekommen. Die Addition ist zwar ein simples XOR, 
allerdings ist die Multiplikation sehr aufwändig.

Grüße,
Steffen

[Detlef _. (detlef_a)]

Hallo Steffen,

RS Implementierung gibts z.b. bei Phil Karn: 
http://www.ka9q.net/code/fec/
Was willst Du denn wie korrigieren?


Cheers
Detlef

[Steffen Hausinger (Gast)]

Hallo Detlef,

den Code habe ich bereits implementiert und er läuft auch. Trotzdem 
Danke für den Link!

Steffen

[Alban (Gast)]

Hallo Steffen,

auf comp.dsp hatte gerade jemand eine ähnliche Frage gestellt. Auf jeden 
Fall scheint es da ein Papier zu geben das eine effiziente 
Multiplikation beschreibt:

http://www.eng.uwo.ca/people/areyhani/download%20Files/PB-TC-Aug04.pdf

Scheint starker Tabak zu sein, aber vielleicht hilft es ja.

Gruß,

Alban

[Steffen Hausinger (Gast)]

Hallo Alban,

der Text ist ziemlich mathematisch. Aber auch da steht (wieder einmal) 
nicht drin, warum überhaupt im GF gerechnet werden muss. Dabei wäre das 
doch die Rechtfertigung für das ganze Dokument. Also ist der Grund dafür 
entweder sonnenklar und bedarf keiner Erwähnung oder aber er wird 
stillschweigend hingenommen. Ich wüsste ihn trotzdem gerne...

Die Multiplikation und alles andere ist schon implementiert und läuft 
auch problemlos. Dennoch danke für den Link!

Welche Frage auf comp.dsp meinst Du genau? Ich kann nichts 
entsprechendes finden.

Steffen

[Holger K. (hkrueger)]

Schau mal unter dem Stichwort "Restklassenring" und "endlicher Körper" 
nach. Das sollte dir helfen zu verstehen was Modulo 2 mit dem 
Gauloisfeld zu tun hat.
Im Wesentlichen läuft es darauf hinaus, daß 2 eine Primzahl ist und es 
deshalb eine Inverse bezüglich der Multiplikation beim Rechnen mit 
modulo 2 gibt.
Eine Eigenschaft die äußerst wichtig für Kodierungsverfahren ist.

[Alban (Gast)]

@ Steffen

> Welche Frage auf comp.dsp meinst Du genau? Ich kann nichts
> entsprechendes finden.

Leider hat der Artikel keinen großen Tiefgang. Da fragt einfach jemand 
nach dem Dokument.

Der Betreff ist: "Who is able to help me with this article?" vom 22. 
Februar.

http://groups.google.de/group/comp.dsp/browse_frm/thread/d528b9526656f28a

[Hagen R. (hagen)]

Holger hat schon den mathematischen Grund genannt. Man könnte nun in 
jedem Restklassenring arbeiten der eine eindeutige multiplikative 
Inversion erlaubt, also zb. in Ganzzahlen N modulo einer Primzahl.
Aber die GF(2)'s haben den Vorteil das sie sehr effizient in 
Hard/Software zu implementieren sind, auch deren Multiplikation die im 
Grunde dann nicht häufig direkt verwendet wird. Zb. die Zyklischen 
Prüfsummen -> CRCs -> arbeiten per Shiftregister und das ist defakto 
eine Mul/Div in GF(2).

Gruß Hagen