Hallo. Ich möchte Binärdaten über einen rauschenden Kanal übertragen, bei dem es auch mal zu Übertragungsfehlern kommen kann. Auf der Suche nach Fehlerkorrekturverfahren bin ich auf das Reed-Solomon-Verfahren gestossen. Dieses ist allerdings nicht sonderlich effizient. Weiterhin habe ich das LDPC-Verfahren, sowie eine Bibliothek namens OpenFEC entdeckt. Allerdings ist die Dokumentation eher lückenhaft - mir ist nicht klar, wie man das benutzen soll. Konkret wären zwei Funktionen, die folgendes leisten, am besten: Eine Funktion zum encode(data) zum Encodieren, die Daten auf irgendeine Art und Weise mit einer Fehlerkorrektur versieht und eine Funktion decode(data), die, falls die Daten fehlerhaft übermittelt wurden, versucht, die Originaldaten wiederherzustellen und dann einen Fehlerwert zurückgibt, falls das nicht möglich sein sollte.
Eins hatte ich vergessen: Es sollte sich um *Vorwärts*fehlerkorrektur handeln!
Das A und sein Kumpel O bei solch einem Vorhaben sind: Wie häufig Fehler auftreten und wie viele Fehler Du korrigieren können willst. Eine einfache CRC-Prüfung ist ein bisschen Rechenarbeit, kann aber, in erster Näherung, nur die Erleuchtung: Stimmt oder Stimmt nicht, bringen. Braucht aber nicht viel Platz im Datenstrom. Es gibt aber Verfahren, die einen oder mehrere Fehler korrigieren können. Dabei wird dann aber der Korrekturblock recht aufwändig und auch schnell groß. In vielen Fällen ist dann das System aus einfacher Fehlerprüfung und einer Möglichkeit dem Sender zu sagen: Hä? Kannst Du das mal wiederholen? Einfacher, schneller und platzsparender. Such‘ mal im Netz. Da haben sich bestimmt Leute, mit dem Abwägen zur richtigen Balance, aus den beteiligten Parametern, beschäftigt.
Da es sich um unidirektionale bzw. Broadcast-Kommunikation handelt, ist eine Vorwärts(!)fehlerkorrektur notwendig. Ich dachte etwa an eine Redundanz von ca. 20% mit guter Performance (LDPC, Turbo, etc.). Ich suche auch konkret eine geeignete Library.
Reed-Solomon kann schon viele Fehler korrigieren. Aus meiner Sicht ist das damit schon effizient. Ich meine das aus einem Datenblock der aus Nutzdaten und Parity-Daten besteht fast die Hälfte verloren gehen und es kann immer noch die vollständige Nachricht erzeugt werden. Darüber hinaus ist RS schön dokumentiert und auch nicht so schrecklich schwierig zu verstehen. Mehr Informationen (auch source code): http://www.eccpage.com/ Martin
A. K. schrieb: > Sind das Massendaten, oder geht es um Kleinkram? Es sind Massendaten im GB-Bereich. Da ist RS nicht so wirklich effizient. Deswegen dachte ich auch eher an LDPC.
Mag komisch klingen, aber da geht vielleicht auch sowas wie RAID-3, alternierend angewandt, vorausgesetzt die Fehler sind keine häufigen kurzen Bitkipper, sondern sporadische aber teils längere Bursts. Frag mich jetzt nicht wie das Verfahren heisst. Trenne den Datenstrom in Gruppen zu 10 Blöcken, 8 Datenblöcke (1-8) und 2 Parity-Blöcke. Jeder Block ist mit CRC abgesichert. Der erste Parity-Block ist für die ungeraden, der zweite für die geraden Blöcke. Damit können 2 benachbarte Blöcke defekt sein, also ist ein Error-Burst innerhalb der Gruppe bis zur Blöckgrösse stets abgedeckt. Ist sicherlich nicht das beste Verfahren, aber auf beiden Seiten kinderleicht und performant implementiert, weil bloss eine einfache CRC und ein blockweises XOR erforderlich ist.
:
Bearbeitet durch User
Tasg schrieb: > A. K. schrieb: >> Sind das Massendaten, oder geht es um Kleinkram? > > Es sind Massendaten im GB-Bereich. Da ist RS nicht so wirklich > effizient. Deswegen dachte ich auch eher an LDPC. Deine Anforderungen sind etwas wirr. Du willst riesige Mengen an Daten übertragen, benutzt dafür aber keine etablierte Schnittstelle wie Ethernet oder FireWire mit den entsprechenden Protokollen, bei denen eine Fehlerkorrektur schon eingebaut ist? Sondern etwas selbst Gebasteltes? Bissi strange, das.
:
Bearbeitet durch User
Mark B. schrieb: > Deine Anforderungen sind etwas wirr. Solche Anforderungen sind üblich bei Sachen wie gegenwärtig bei der Mars-Mission. Der Kanal ist zwar prinzipiell bidirektional. Die Datenmengen sind groß und die Laufzeiten verbieten aber ein Hand-Shake.
Tasg schrieb: > .. Und ich suche eine Bibliothek, die das macht .. Für die beteiligte CRC, oder fürs XOR?
Mark B. schrieb: > Deine Anforderungen sind etwas wirr. Mag sein. > > Du willst riesige Mengen an Daten übertragen, benutzt dafür aber keine > etablierte Schnittstelle wie Ethernet oder FireWire mit den > entsprechenden Protokollen, bei denen eine Fehlerkorrektur schon > eingebaut ist? Sondern etwas selbst Gebasteltes? Ja. > > Bissi strange, das. Mag sein.
Genauer gesagt will ich die Daten als Backup auf einen Server hochladen. Der Server selbst besitzt keine Fehlerkorrektur, so dass die Daten dort auch mal verfälscht ankommen könnten oder mit der Zeit verfälscht werden. Da ich über den Server keine Kontrolle habe, möchte ich eine Fehlerkorrektur verwenden. Dazu gibt es bereits PAR2 (z.B. MultiPar), welches Reed-Solomon verwendet, aber halt extrem ineffizient und leistungshungrig ist, und daher auch nur für Monster-Prozessoren mit GPU empfehlenswert ist. Ich dachte da eher an etwas leichtere Kost. Es gibt Protokolle wie z.B. NNTP bei denen so etwas notwendig ist.
Route 6. schrieb: > Solche Anforderungen sind üblich bei Sachen wie gegenwärtig bei der > Mars-Mission. Der Kanal ist zwar prinzipiell bidirektional. Die > Datenmengen sind groß und die Laufzeiten verbieten aber ein Hand-Shake. So eine kleine Mission im Weltraum ist auch durchaus ein üblicher Anwendungsfall für einen Hobbybastler oder den durchschnittlichen Angestellten. :-)
Tasg schrieb: > .. Und ich suche eine Bibliothek, die das macht .. Klar. Und die mit Schleifchen bitte... Wie ich diese Typen hasse, die wirklich rein garnix selber können, nichtmal die Suche nach der passenden Wichsvorlage für's C&P-"Programmieren"...
Erst sollte mal eine Vorstellung der moeglichen Fehler vorhanden sein, sonst muss man die eben erarbeiten. Reed Solomon ist fuer Einzelbitfehler, hervorgerufen durch Spikes auf der elektrischen Leitung. Generell ist Vorwaertsfehlerkorrektur, hinzugepackte Redundanz, die nun eben die kaputten Bits wieder ausfuellen kann. Es gibt nun die Moeglichkeit das Bestehende zB Reed-solomon zu probieren. Vielleicht ist das Problem schon geloest. Vielleicht auch nicht. Dann nach eingehender Betrachtung der passenden Literatur, inklusive der wissenschftlichen Puplikationen, heisst es dann Zurueck zu den Wurzeln. Wie geht die Technologie uebrhaupt, und was muss ich machen, das nun fuer meinen Anwendungsfall passt. Vielleicht sollten wir etwas mehr von der Anwendung hoeren. Wieviele Bits am Stueck, und wie oft sollten denn repariert werden koennen ?
Oh D. schrieb: > Reed Solomon ist fuer > Einzelbitfehler Reed Solomon ist für Burstfehler geeignet. Der berühmte Kratzer auf der CD wird durch RS korrigiert.
Das Schöne an Reed-Solon ist, das der Anteil der Parity-Informationen eines Blocks festgelegt werden kann. Damit kann man mehr als nur einen Bitfehler korrigieren. Allerdings, und da gebe ich den TO Recht, steigt dann der Rechenaufwand. Generell funktioniert RS auch mit 16-bit Ganzzahlen, das führen moderne CPUs schon fix aus. Schau dir mal die Sourcen auf eccpage.com an. Martin
Mark B. schrieb: > So eine kleine Mission im Weltraum ist auch durchaus ein üblicher > Anwendungsfall für einen Hobbybastler oder den durchschnittlichen > Angestellten. :-) Vielleicht hat der Programmierer für die Landesoftware hier im Forum um Rat für seinen C-Quelltext gefragt? Das Ergebnis deutet darauf hin.
Nimm einen Reed Solomon Code. Die sind allemahl effizient, wohl definiert, funktionierende Software gibts überall. LDPC und Turbo sowie andere moderne Codes sind viel aufwändiger und brauchst du nur wenn es dir aufs allerletzte dB ankommt. Dafür brauchst du aber Softinformation, also Bitwahrscheinlichkeiten, sonst bringen die auch keinen Vorteil. Bei deinen Datenmengen z.B. LDPC DVB-S2, das wäre dann das beste. Das gibts dann aber nicht an jeder Ecke und wenn man sich nicht damit auskennt lässt man besser die Finger davon.
VHDL hotline schrieb im Beitrag #4763073: > Oh D. schrieb: >> Reed Solomon ist fuer >> Einzelbitfehler > > Reed Solomon ist für Burstfehler geeignet. Der berühmte Kratzer auf der > CD wird durch RS korrigiert. Die Daten auf ner CD liegen aber nicht linear vor sondern sind verteilt, damit ein Kratzer eben keinen Burst erzeugt, sonder viele Einzelfehler über eine größere Datenmenge. Cross interleaved Reed-Solomon.
Bitte 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.