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.
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.
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.
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.
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.
