Moin,
ich habe Fragen zum Reed-Solome-Code. Hoffe richtiges Forenabteil, soll
ja auch aufn FPGA.
Bin grade dabei mich mit Kanalkodierungen zu beschäftigen.
Ich möchte eine Datenübertragung machen die Bits korrigieren kann. Die
Daten sollen von FPGA zu FPGA versendet werden. Fehler können einzeln
oder als Bündel auftreten.
Einer der bekanntesten bzw. oft eingesetzten RS-Codes ist wohl der
RS(255,223).
Das bedeutet aber ja auch, das erst 255 Bits übertragen werden muss,
damit ich die 223 Nutz-Bits nutzen kann? 16 Bits währen reparierbar?
Weiterhin frage ich mich ob dahinter wirklich eine große Look-Up-Table
stehen muss oder ob man dafür auch Algorithmus nutzen kann.
Für meinen Anwendungsfall sind nun 223 Nutz-Bits zur Übertragung
bisschen viel. Vorteil vom RS-Code soll ja auch sein diesen Individuell
anzupassen.
Ich dachte eher so etwas wie RS(68,64). 64 Nutz Bits und es können bis
zu 2 Bits in der Übertragung korrigiert werden. Aber war da nicht
irgendwas mit Primzahlen?
Bei RS(70,64) währen ja sogar 3 Bits korrigierbar?
Ein bisschen eingelesen habe ich mich dementsprechend schon, denke aber
um Fachliteratur komm ich nicht rum.
Aber bevor ich damit was machen will, was sowieso nicht funktioniert,
frage ich euch mal um Rat.
Evt. sind ja auch Fire-Codes, CRC-Codes etc besser geeignet.
Gruß
WW
WW schrieb:
Das DSP-Unterforum hier scheint mir geeigneter, weil dergleichen auch
beim CD-Playern vorkommt.
https://www.ti.com/lit/an/spra686/spra686.pdf> Ein bisschen eingelesen habe ich mich dementsprechend schon, denke aber> um Fachliteratur komm ich nicht rum.
Dann schau mal in die Lehrbücher für
Nachrichtentechnik(Codierungstheorie) oder technische Informatik. Die
FPGA-hersteller haben auch Applications note dazu. Der ist sehr
brauchbar ISBN: 978-3486721287
Schau dir mal "Punktierung" an, dass ist ein verfahren um codes an
Nutzdaten kleiner Wortbreite anzu passen.
https://www.math.uni-bielefeld.de/~baumeist/Codierungstheorie/hauck-Codierungstheorie-1.pdf> Evt. sind ja auch Fire-Codes, CRC-Codes etc besser geeignet.
Das musste halt selbst bewerten, welche Fehler (Einzeln- ( Unterteil
nach Hamming-Distanz), Burst) erkennbar sein müßen, welche Hardware zur
Verfügung steht (Gattergrab, CPLD,FPGA), bitrate, Blocvk oder Stream,
...
PS:
Nic primzahlen, schau eher nach Galois-Feldern.
PSS:
Wer das Archiv nicht ehrt ist die Auskunft nicht wert ;-)
https://www.google.de/search?q=site%3Amikrocontroller.net+Reed-Solomon&oq=site%3Amikrocontroller.net+Reed-Solomon
WW schrieb:> Weiterhin frage ich mich ob dahinter wirklich eine große Look-Up-Table> stehen muss oder ob man dafür auch Algorithmus nutzen kann.
Eine LUT wird für RS wahrscheinlich nicht ausreichen. Das ist
komplizierter.
WW schrieb:> Das bedeutet aber ja auch, das erst 255 Bits übertragen werden muss,> damit ich die 223 Nutz-Bits nutzen kann?
Man muss in der Tat den kompletten Block empfangen haben, um diesen zu
dekodieren.
Firecodes sind etwas einfacher, können aber auch weniger als RS.
CRC. "Frame prüfen und wiederholen" ist ein klassisches und einfaches
Verfahren, dem man einer FEC vorzieht, solange man kann. Aber du willst
dich ja mit FECs beschäftigen.
Ich empfehle dir noch Hamming-Codes, die u.a. in ECC-Memories verwendet
werden.
Bevor es in den FPGA geht, sollte der Algorithmus in Matlab/Python
stehen. Dann siehst du auch den Implementierungsaufwand.
Polyglotte schrieb:> medium advanced Pillepalle.
Der Encoder ja, aber der Decoder ist massiv komplizierter. Nicht ohne
Grund hat mein Arbeitgeber einen deutlich fünfstelligen Betrag für ein
RS Encoder/Decoder-Paar auf den Tisch gelegt (allerdings mit ein paar
Anpassungen an unsere Sonderwünsche)
schlappohr schrieb:> Polyglotte schrieb:>> medium advanced Pillepalle.>> Der Encoder ja, aber der Decoder ist massiv komplizierter. Nicht ohne> Grund hat mein Arbeitgeber einen deutlich fünfstelligen Betrag für ein> RS Encoder/Decoder-Paar auf den Tisch gelegt (allerdings mit ein paar> Anpassungen an unsere Sonderwünsche)
Naja, bei einem dreistelligen Stundensatz ist man schon vor Ablauf von 4
Wochen bei einem fünfstelligen Betrag. ;-) +MwSt.
Und zur Entwicklung kommt noch ausgiebiger Test, Doku und Laboraufwände
...
Das sehen manche Chef's nicht und setzen dann einen fachfremdes
Greenhorn an das Thema ... so wird dann auch aus Pillepalle ein
Jahresprojekt (unvollenset).
Polyglotte schrieb:> so wird dann auch aus Pillepalle ein> Jahresprojekt
Ja, das kommt vor. Aber ein RS-Decoder ist ziemlich nicht-trivial, auch
für einen erfahrenen Entwickler. Wir haben lange überlegt, ob wir die
Entwicklung selbst machen sollen un dann entschieden, dass wir das in
einer akzeptablen Zeit nicht hinbekommen und dann das Teil lieber
eingekauft.
Vancouver schrieb:> Ja, das kommt vor. Aber ein RS-Decoder ist ziemlich nicht-trivial, auch> für einen erfahrenen Entwickler. Wir haben lange überlegt, ob wir die> Entwicklung selbst machen sollen un dann entschieden, dass wir das in> einer akzeptablen Zeit nicht hinbekommen und dann das Teil lieber> eingekauft.
Falls ihr kein universell konfigurierbares Produkt, was Symbol- und
Datenwortbreiten, Anzahl korrigierbarer Symbole, Pipeline-Konfiguration
des Dekoders etc. angeht, eingekauft habt, müsst ihr beim nächsten
Projekt wieder Geld ausgeben. Gerade beim Dekodieren ist die Einbindung
in eine Pipeline-Architektur wichtig - das kann man kaum vorab
spezifizieren, bis der ganze Rest drumrum steht. Ohne Pipeline schafft
man bei großen Wortbreiten den Spagat zwischen Frequenz und
Gatterverbrauch kaum.
WW schrieb:> Einer der bekanntesten bzw. oft eingesetzten RS-Codes ist wohl der> RS(255,223).> Das bedeutet aber ja auch, das erst 255 Bits übertragen werden muss,> damit ich die 223 Nutz-Bits nutzen kann? 16 Bits währen reparierbar?
Ja. Du musst alle bits übertragen.
WW schrieb:> Ich dachte eher so etwas wie RS(68,64). 64 Nutz Bits und es können bis> zu 2 Bits in der Übertragung korrigiert werden. Aber war da nicht> irgendwas mit Primzahlen?> Bei RS(70,64) währen ja sogar 3 Bits korrigierbar?
Im Grunde kannst du dir das ganz so zusammenbasteln, wie du willst.
Das mit den Primzahlen bezieht sich auf das Galois Feld, auf dem die
Rechenoiperationen ausgeführt werden.
Vereinfacht gesagt funktioniert RS ja über einene Polynominterpolation
über deine Datenpunkte. Du hast bspw 5 Datenpunkte. Durch 5 Punkte
kannst du jetzt ein Polynom 5ter Ordnung setzen, das eindeutig bestimmt
ist. Da gibt es funktional zwei Ansätze: Entweder du legst deine Daten
d0 bis d4 in ein Koordinatensystem an die stellen (0, d0), (1, d1), ...
(4,d4) und interpolierst darüber ein Polynom. Oder du nutzt gleich die
Koeffizienten des Polynoms als Datenträger: also d0*x^5 + d1*x^4 etc...
Mathematisch erstmal egal. Du bekommst auf jedenfall mit beiden Methoden
ein eindeutiges Polynom (nicht das gleiche, aber eindeutig für jedes
Verfahren). Für die Redundanzdaten setzt du jetzt in dieses Polynom
einfach weitere Punkte ein und übermittelst die mit.
Egal welche bits jetzt verloren gehen bzw kaputt gehen, du kannst aus 5
beliebigen Punkten wieder eindeutlig das Polynom rückrechnen und deine
Daten rückgewinnen.
Das ist das grobe Prinzip. Das funktioniert so ganz ohne Galois Felder
und den ganzen Hokus-Pokus. Das Problem daran ist jetzt nur, dass je
nach Daten es schön wäre, wenn der Wertebereich dieser Koeffizienten
etc. irgendwie begrenzt wäre. Und da kommen jetzt Galois-Felder ins
Spiel. Man stellt jetzt fest, dass die ganze schöne Mathematik auch auf
einem endlichen Zahlenraum funktioniert, wenn man einfach alles mod p
rechnet. Also bspw. Auf dem Galois-Feld GF(3). Alles mod 3 rechnen und
gut ist. Wichtig hierbei ist, dass es nur funktioniert, wenn p eine
Primzahl ist. Leider sind jetzt Primzahlen etwas blöd, weil wir
theoretisch einen Zahlenraum von 0 bis 255 haben von einem Byte. Und
"mod 256" ist leider keine Primzahl. Man kann jetzt aber wunderbar
feststellen, dass die ganze Aktion auch (nahezu) funktioniert, wenn man
"mod p^n" rechnet. Also eine Potenz einer Primzahl. 2 Ist eine Primzahl
und 2^8= 256. Also kann man das auf diesem Feld rechnen. Es ändern sich
ein paar Dinge, damit das mathematisch mit der Modulo-Arithmetik
weiterhin komplett hinhaut. Aber es geht.
Das ist quasi schon die ganze Magie. Und eigentlich auch alles was du
brauchst um zu kodieren. Die Fehler-Erkennung ist deutlich aufwendiger,
da man vereinfacht nicht weiß, welche Punkt ein den Daten kaputt sind.
Wüsste man das, könnte man einfach schnell durch den Rest wieder ein
Polynom durchlegen und den kaputten Punkt rückrechnen. Um dieses Problem
anzugehen, ist im Dekoder bspw. dieses Verfahren notwendig:
https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Welch_algorithm
Diese Vorlesung ist imho ziemlich gut:
https://www.youtube.com/watch?v=AjJKl5rsTow
Das erklärt das rechnen auf dem endlichen Zahlenkörper und was man da
machen muss.
Polyglotte schrieb:>> Der Encoder ja, aber der Decoder ist massiv komplizierter. Nicht ohne>> Grund hat mein Arbeitgeber einen deutlich fünfstelligen Betrag für ein>> RS Encoder/Decoder-Paar auf den Tisch gelegt (allerdings mit ein paar>> Anpassungen an unsere Sonderwünsche)>> Naja, bei einem dreistelligen Stundensatz ist man schon vor Ablauf von 4> Wochen bei einem fünfstelligen Betrag. ;-) +MwSt.
Nun ja, es gibt auch Leute, die das in der Kiste haben und für die
Hälfte anbieten.
Was mich wundert:
Kein einziger hat bisher das Wichtigste nachgefragt, nämlich die
Bandbreite? Und was sonst noch so alles rein muss.
Erst wenn das feststeht, kann man entscheiden, ob das (wie
vorgeschlagen) ein Controller kann oder man einen fertigen Chip nimmt,
oder man einen FPGA mit Core oder einen FPGA mit selbst gebautem VHDL
nimmt.
Ich bin erstaunt, dass trotzdem jeder zu wissen scheint, wie die
optimale Lösung ist.
Jürgen S. schrieb:> Kein einziger hat bisher das Wichtigste nachgefragt, nämlich die> Bandbreite?
Für die reine Kodierung ist die Bandbreite nebensächlich, siehe (Audio-)
CompactDisc. Wobei bei der CD noch weitere Verfahren neben RS (bspw.
Interleave) hinzukommen, damit diese Fehler wie Löcher bis 2 mm ⌀
wegsteckt.
👴
Erstmal vielen Dank an alle. Hab mir mitlerweile auch schon viel dazu
durchgelesen und auch verstanden. Bin natürlich auch schon am Punkt der
Fehlerpunkterkennung und Gewichtung. (habs da auch nicht so eilig)
M. H. schrieb:> Das ist quasi schon die ganze Magie. Und eigentlich auch alles was du> brauchst um zu kodieren. Die Fehler-Erkennung ist deutlich aufwendiger,> da man vereinfacht nicht weiß, welche Punkt ein den Daten kaputt sind.> Wüsste man das, könnte man einfach schnell durch den Rest wieder ein> Polynom durchlegen und den kaputten Punkt rückrechnen. Um dieses Problem> anzugehen, ist im Dekoder bspw. dieses Verfahren notwendig:> https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Welch_algorithm
Jou, da bin ich dabei. Da gibts ja mehrere Dekoder um den Fehlerpunkt zu
bestimmen. Der BMA baut ja eher auf ein Schieberegister auf um mir das
Fehlerstellenpolynom zu geben. Bin aktuell am überlegen, auf ein anderes
auszuweichen, weil ich nicht bit für bit an Daten reinbekomme, sondern
direkt schon ein Stream an Bytes.
Der Peter-Ziegler wäre für viele Fehlerstellen zu aufwändig und der
erweiterte Euklidische Divisions Algorithmus hab ich noch nicht genau
verstanden. Etwas, was gut zu Pipelinen wäre, wäre praktisch, da mir die
Latenz nicht so wichtig ist.
M. H. schrieb:> Diese Vorlesung ist imho ziemlich gut:> https://www.youtube.com/watch?v=AjJKl5rsTow
Ja hat mir den Einstieg sehr vereinfacht, gibt auch noch ne Anschluss
Vorlesung (glaube aber nur auf deren HP), wird aber auch abgebrochen
wenn es zur Fehlerstellenerkennung geht.
alterweissermann schrieb:> Für die reine Kodierung ist die Bandbreite nebensächlich,
ich bezog mich auf den Umstand, dass hier u.a. Microcontroller empfohlen
wurden.
