Welcher Algorithmus für extrem hohe non-burst-Fehler?

Question

Ich habe einen binären Datenstrom, der eine sehr hohe Fehlerquote.Die Fehler rate ist 50% Bedeutung jedes bit hat eine 50% chance of being flipped.Der Fehler tritt nicht in bursts und ist komplett zufällig, so Reed–Solomon-codes nicht gut funktionieren würde.

Die Schema oder Algorithmus sollte ich anwenden, um den stream???I don ' T care über die Zuschläge auf alle.

Das ist alles theoretisch, also hat es keinen Sinn zu Fragen, ob ich könnte nur reduzieren die Fehler der stream.

BEARBEITEN

Nicht sagen, dass es nicht möglich ist, die erste Antwort, die es Ihnen sagt, dass es möglich ist, mit laut Kanal Codierung theorem.

Answer 1

Das noisy-channel coding theorem besagt, dass können Sie wirklich erreichen die Shannon-Kapazität für den Kanal.Es tut nicht sagen Sie dem Kanal einen Wert ungleich null Kapazität!

Wenn Sie randomize 100% der bits in den Kanal, 50% unverändert, so dass Sie nur flip eine zufällige 50% der bits.Es sollte offensichtlich sein, dass Sie können nicht senden Daten über diesen Kanal-die Shannon-Kapazität ist gleich null.

Answer 2

Wenn der Fehler rate ist 50%, dann ist das im Grunde das Rauschen, ist es nicht?Ich meine, sollten Sie nur versuchen, ein einzelnes bit übertragen.Wenn Sie senden ein unendlich Strom von der Recht wenig, mit einem 50% - Fehler-rate, die Sie erhalten die Hälfte 1s und die Hälfte 0s, ob Sie die richtige bit ist 1 oder 0.

Wenn es ist tatsächlich weniger als 50% (z.B.50% der bit wird "random" anstatt "gespiegelt"), dann könnten Sie wiederholen Sie einfach die Daten zu übertragen jedes bit der 128 mal und arbeiten Sie heraus, welche Sie bekommen mehr für jedes 100 bits empfangen.Das ist der einfache code, enorm ineffizient, nicht sich an alle mathematischen Lösung :)

Answer 3

Gut, die ganze Punkt der Reed-Solomon-Fehlerkorrektur ist, dass die meisten realen Welt auftreten von Fehlern in bursts, so dass Sie verschachteln und de-interleave-der Daten.Wenn Ihr Fehler sind völlig zufällig, d.h.Poisson-verteilt, dann nur das hinzufügen von Redundanz, um den Strom in eine einfache, mathematisch effiziente Weise funktionieren wird.Eine Sache, die Sie sich auf irgendeine Art von versteckten Markov-Modell, wie trellis-code. Das ist im Grunde nur eine rechnerisch effiziente Möglichkeit, das hinzufügen von Redundanz.

Außerdem haben Sie einen Blick auf die laut Kanal Codierung theorem. Streng genommen, Sie bezieht sich nicht auf digitale Daten, aber wenn Sie die Quelle dieser bits ist etwas analoges Verfahren, oder wenn Sie könnte als Modell für die bits als ob Sie waren das Ergebnis einiger analoger Prozess, es konnte Ihnen einen kleinen Einblick in das, was das beste, was Sie tun konnte sein könnte.Dies würde verhindern, dass Sie verschwenden Zeit versuchen, zu tun besser als mathematisch möglich.

Answer 4

Als der Kanal nähert sich 50% real noise rate, es wird nicht mehr übertragen keine Informationen an alle.Jon Skeet ' s Antwort, wenn die Fehlerrate wird weniger als 50% Lärm, dann können Sie die Daten durch längere platzt der vorgesehenen Daten Redundant und statistisch Blick auf das Ergebnis, um ein gewisses Maß an Vertrauen in die original Wert.Die benötigte burst-Länge und das Vertrauen für eine gegebene Länge würde dann abgeleitet werden, basierend auf einer Charakterisierung des Rauschens.Aber verstehen, was Sie hier tun, ist eine wirksame Senkung der Datenrate zu verbessern die net Signal-Rausch-Verhältnis der übermittelten stream.

In Ihrer Frage, die Sie haben könnten, entschieden dies als eine option, aber eine bessere encoding-Schema basieren möglicherweise auf die relative Existenz (oder nicht) von der Datenstrom selbst.In anderen Worten, zu übermitteln, eine binäre eins....senden einer wechselnden stream-1/0.Senden Sie eine null, senden nichts oder vielleicht schicken Sie ein konstantes Niveau.Die Idee ist, dass das senden (und empfangen) etwas stellt eine Staatliche und senden (und empfangen) nichts stellt dem anderen Staat hat.Dies würde effektiv ähneln einer Art von bipolar encoding der Daten.

Answer 5

Wenn Ihr Fehler rate ist 50% der bit stream IST zufällig und steht in KEINER KORRELATION zu den original-Bitstream.Es ist wie Sie sind XORing den stream mit einem komplett-random-bit-stream, und das Ergebnis ist völlig zufällig.Und es gibt nichts, was Sie dagegen tun können.

Die flip-Preis muss unter 50%, damit die Regelung funktioniert.Es könnte natürlich sein, ÜBER 50%, aber dann können Sie zuerst umkehren, die Strom und dann verarbeiten Sie es mögen, wenn der Fehler rate unter 50% lag.

Wenn die Fehler sind völlig zufällig, und sehr Häufig (z.B.25% von die bits gespiegelt), es ist sehr schwer zu kommen mit einem robusten error detection System.Sie müssen hinzufügen eine erhebliche Menge an Redundanz.

Answer 6

Haben Sie schaute in den turbo-codes?

-- MarkusQ

Doh!I misread, dass als 50% randomisierte, nicht 50% gespiegelt.

Answer 7

Wenn genau 50% der bits umgedreht werden, in jedem gegebenen übertragung, anstatt jedes bit umgedreht mit 50% - Wahrscheinlichkeit, die Sie senden können, ein bisschen von Informationen durch senden einer übertragung von zwei bits -- senden Sie eine 0, 00 und 1 als 01.Wenn das erste bit des empfangenen Codewort ist 1, dann ist die andere bit ist unflipped.