Forum: PC-Programmierung Fehlerkorrekturverfahren


von Tasg (Gast)


Lesenswert?

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.

von Jörg E. (jackfritt)


Lesenswert?

Aus alten Modem Zeiten zmodem oder ymodem?

von Tasg (Gast)


Lesenswert?

Eins hatte ich vergessen: Es sollte sich um *Vorwärts*fehlerkorrektur 
handeln!

von Amateur (Gast)


Lesenswert?

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.

von Tasg (Gast)


Lesenswert?

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.

von (prx) A. K. (prx)


Lesenswert?

Sind das Massendaten, oder geht es um Kleinkram?

von Martin (Gast)


Lesenswert?

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

von Tasg (Gast)


Lesenswert?

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.

von (prx) A. K. (prx)


Lesenswert?

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
von Tasg (Gast)


Lesenswert?

.. Und ich suche eine Bibliothek, die das macht ..

von Mark B. (markbrandis)


Lesenswert?

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
von Route_66 H. (route_66)


Lesenswert?

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.

von (prx) A. K. (prx)


Lesenswert?

Tasg schrieb:
> .. Und ich suche eine Bibliothek, die das macht ..

Für die beteiligte CRC, oder fürs XOR?

von Tasg (Gast)


Lesenswert?

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.

von Tasg (Gast)


Lesenswert?

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.

von Mark B. (markbrandis)


Lesenswert?

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

von c-hater (Gast)


Lesenswert?

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

von Pandur S. (jetztnicht)


Lesenswert?

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 ?

von VHDL hotline (Gast)


Lesenswert?

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.

von Martin (Gast)


Lesenswert?

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

von Route_66 H. (route_66)


Lesenswert?

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.

von Peter (Gast)


Lesenswert?

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.

von bastel_ (Gast)


Lesenswert?

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
Noch kein Account? Hier anmelden.