Mit welchen Techniken können Sie Daten auf einem verlustbehafteten Einwegkanal kodieren?

https://stackoverflow.com/questions/1231489

22-07-2019
|

Frage

Stellen Sie sich vor, Sie hätten einen Kommunikationskanal von Natur aus verlustbehaftet und unidirektional.Das heißt, es gibt ein gewisses inhärentes Rauschen, das nicht entfernt werden kann und beispielsweise dazu führt, dass zufällige Bits umgeschaltet werden.Stellen Sie sich auch vor, dass es nur eine Möglichkeit gibt – Sie können keine erneute Übertragung beantragen.

Aber Sie müssen trotzdem Daten darüber senden.Mit welchen Techniken können Sie versenden? Zahlen Und Text über diesen Kanal?

Ist es möglich, Zahlen so zu kodieren, dass sie selbst bei zufälligem Bit-Twiddling immer noch als Werte interpretiert werden können, die dem Original nahe kommen (verlustbehaftet Übertragung)?
Gibt es eine Möglichkeit, eine Zeichenfolge (z. B. ASCII) in einem zu senden? verlustfrei Mode?

Das ist nur zum Spaß.Ich weiß, dass Sie Morsecode oder jede binäre Kommunikation mit sehr niedriger Frequenz verwenden können.Ich kenne mich mit Paritätsbits und Prüfsummen aus, um Fehler zu erkennen und es erneut zu versuchen.Ich weiß, dass Sie genauso gut ein analoges Signal verwenden können.Ich bin nur neugierig, ob es interessante computerwissenschaftliche Techniken gibt, um diese Dinge über einen verlustbehafteten Kanal zu senden.

Lösung

Abhängig von einigen Details, die Sie über Ihren verlustbehafteten Kanal nicht angeben, würde ich empfehlen, zunächst a zu verwenden Gray-Code um sicherzustellen, dass Einzelbitfehler zu kleinen Unterschieden führen (um Ihren Wunsch nach Verlustminderung bei verlustbehafteter Übertragung zu erfüllen), und dann möglicherweise auch den resultierenden Stream mit etwas „verlustfreiem“ (==versucht verlustfrei sein;-) Kodierung.

Reed-Solomon und Varianten davon eignen sich besonders gut, wenn Ihre Rauschepisoden dazu neigen, in kleinen Ausbrüchen (mehrere Bitfehler beispielsweise innerhalb eines einzelnen Bytes) aufzutreten, was gut mit der Gray-Codierung zusammenarbeiten sollte (da Mehrbitfehler die Ursache für den „Verlust“ sind). „Mitigation“-Aspekt von Gray, der für eine sanfte Beeinträchtigung bei Einzelbitfehlern auf der Leitung ausgelegt ist).Das liegt daran, dass R-S im Wesentlichen ein Blockschema ist und mehrere Fehler innerhalb eines Blocks aus der Sicht von R-S im Grunde dasselbe sind wie ein einzelner Fehler darin;-).

R-S ist besonders großartig, wenn viele der Fehler vorhanden sind Löschungen – Um es einfach auszudrücken: Eine Löschung ist ein Symbol, das höchstwahrscheinlich bei der Übertragung entstellt wurde, ABER Sie wissen die entscheidende Tatsache, dass es entstellt wurde.Die physikalische Schicht kann, abhängig davon, wie sie konzipiert ist, oft Hinweise auf diese Tatsache haben, und wenn es eine Möglichkeit gibt, die höheren Schichten zu informieren, kann das von entscheidender Hilfe sein.Lassen Sie mich das Löschen etwas erklären ...:

Nehmen wir als vereinfachtes Beispiel an, dass eine 0 als Pegel von -1 Volt und eine 1 als Pegel von +1 Volt gesendet wird (in Bezug auf eine Referenzwelle), aber es gibt Rauschen (physikalisches Rauschen lässt sich oft gut modellieren, fragen Sie). jeder kompetente Kommunikationstechniker;-);Abhängig vom Rauschmodell kann die Dekodierung so aussehen, dass alles, was -0,7 V und darunter liegt, als 0-Bit betrachtet wird, alles, was +0,7 V und darüber liegt, als 1-Bit betrachtet wird, alles dazwischen als Löschung betrachtet wird, d. h. die höhere Schicht wird mitgeteilt dass das fragliche Bit wahrscheinlich bei der Übertragung beschädigt wurde und daher außer Acht gelassen werden sollte.(Ich nenne dies manchmal als ein Beispiel meiner These, dass Abstraktionen manchmal „durchsickern“ sollten – auf kontrollierte und architektonische Weise:die Martelli-Folge zu Spolskys Gesetz der undichten Abstraktionen!-).

Ein R-S-Code mit einem beliebigen Redundanzverhältnis kann bei der Korrektur von Löschungen (Fehler, über die der Decoder informiert wird) etwa doppelt so effektiv sein wie bei der Korrektur ansonsten unbekannter Fehler. Es ist auch möglich, beide Aspekte zu mischen und sowohl einige Löschungen als auch zu korrigieren einige ansonsten unbekannte Fehler.

Als Sahnehäubchen können benutzerdefinierte R-S-Codes (ziemlich einfach) entworfen und angepasst werden, um die Wahrscheinlichkeit unkorrigierter Fehler auf unter jeden erforderlichen Schwellenwert θ zu reduzieren, vorausgesetzt ein genaues Modell der Eigenschaften des physischen Kanals in Bezug auf Löschungen und unentdeckte Fehler (einschließlich). sowohl Wahrscheinlichkeit als auch Burstigkeit).

Eigentlich würde ich diesen ganzen Bereich nicht als „Informatik“ bezeichnen:Als ich meinen Abschluss machte (MSEE, vor 30 Jahren), habe ich größtenteils versucht, „CS“-Sachen zugunsten von Chipdesign, Systemdesign, fortschrittlichen Funksystemen usw. zu vermeiden – und doch wurde mir dieses Zeug beigebracht (naja, die Teilmenge davon). war schon im Bereich der praktischen Ingenieurstauglichkeit ;-) Ziemlich gut.

Und um zu bestätigen, dass sich die Dinge in einer Generation nicht allzu sehr verändert haben:Meine Tochter hat gerade ihren Master in Telekommunikationstechnik gemacht (mit Schwerpunkt auf fortgeschrittenen Funksystemen) – sie kann kaum ernsthafte Programme, Algorithmen oder Datenstrukturen entwerfen (obwohl sie in den Pflichtkursen zu C und Java ganz gut abgeschnitten hat). In diesen Kursen und auch anderswo in ihrem Lehrplan gab es überhaupt keine Informatiktiefe – ihre tägliche Arbeitssprache ist es matlab...!-) – dennoch weiß sie mehr über Informations- und Codierungstheorie als ich jemals gelernt habe, und das ist es Vor irgendein Doktoratsstudium (sie bleibt für ihre Doktorarbeit, aber damit hat noch nicht begonnen).

Daher behaupte ich, dass diese Bereiche eher EE-lastig als CS-lastig sind (obwohl die Grenzen natürlich immer fließend sind – bezeugen Sie die Tatsache, dass ich, nachdem ich ein paar Jahre lang Chips entwickelt hatte, mehr oder weniger zufällig zum SW-Typ gelandet bin, und Das taten viele meiner Zeitgenossen auch ;-).

Andere Tipps

Diese Frage ist Gegenstand der Codierungstheorie .

Wahrscheinlich einer der besser bekannten Methoden ist Code Hamming. Es ist vielleicht nicht der beste Weg, von Fehlern auf großen Skalen zu korrigieren, aber es ist unglaublich einfach zu verstehen.

Es ist der redundante Codierung in optischen Medien verwendet das kann Bit-Verlust erholen.
- ECC wird auch verwendet, in Festplatten und RAM
Die TCP Protokoll ziemlich viel verarbeiten kann Datenverlust bei erneuten Übertragungen.

So oder Turbo Codes oder Low-Density-Codes Paritätsprüfung für die allgemeinen Daten , da diese am nächsten kommen, die Shannon-Grenze zu nähern - vgl. wikipedia

Sie können mit Reed-Solomon Codes.

Siehe auch die Sliding Window (die von TCP verwendet wird).

Obwohl dies schließt mit Paketen zu tun wird neu geordnet oder ganz verloren, was nicht Teil des Problems Definition war.

Wie Alex Martelli sagt, gibt es viel Codierungstheorie in der Welt, aber Reed-Solomon-Codes sind auf jeden Fall ein Sweet-Spot. Wenn Sie wirklich etwas aufbauen wollen, Jim Plank hat eine nettes Tutorial auf Reed-Solomon-Codierung . Plank hat ein professionelleres Interesse an der Codierung mit vielen praktischen Know-how um es wieder auf.

würde ich für einige dieser Vorschläge gehen, um mehrere Sendungen der gleichen Daten. So dass, wie Sie für verschiedene Fehler hoffen kann an verschiedenen Stellen in dem Strom eingeführt werden, und Sie können die gewünschte Anzahl viel einfacher folgern können.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow