mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Warum GF für Reed-Solomon


Autor: Steffen Hausinger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Alban (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Steffen Hausinger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Steffen,

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


Cheers
Detlef

Autor: Steffen Hausinger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Detlef,

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

Steffen

Autor: Alban (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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%20F...

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

Gruß,

Alban

Autor: Steffen Hausinger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Holger K. (hkrueger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Alban (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ 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/...

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.