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.
Tim schrieb: > Eine LUT wird für RS wahrscheinlich nicht ausreichen. Das ist > komplizierter. Grösser, nicht unbedingt komplizierter. Da was für lattice-FPGA: https://www.latticesemi.com/~/media/LatticeSemi/Documents/UserManuals/RZ/ReedSolomonEncoderUsersGuide.PDF?document_id=5930 Es braucht dort ein paar hundert LUT's und ein paar hundert FF, also nix besonders grosses, eher medium advanced Pillepalle.
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.