Ein binärer symmetrischer Kanal (oder BSC) ist ein allgemeines Kommunikationskanalmodell, das im Codieren der Theorie und Informationstheorie verwendet ist. In diesem Modell möchte ein Sender wenig (eine Null oder eine) senden, und der Empfänger erhält wenig. Es wird angenommen, dass das Bit gewöhnlich richtig übersandt wird, aber dass es mit einer kleinen Wahrscheinlichkeit (die "Überkreuzungswahrscheinlichkeit") "geschnipst" wird. Dieser Kanal wird oft in der Informationstheorie verwendet, weil es einer der einfachsten Kanäle ist, um zu analysieren.

Beschreibung

Der BSC ist ein binärer Kanal; d. h. es kann nur ein von zwei Symbolen übersenden (gewöhnlich hat 0 und 1 gerufen). (Ein nichtbinärer Kanal würde dazu fähig sein, mehr als 2 Symbole, vielleicht sogar eine unendliche Zahl von Wahlen zu übersenden.) Ist die Übertragung nicht vollkommen, und gelegentlich bekommt der Empfänger das falsche Bit.

Dieser Kanal wird häufig von Theoretikern verwendet, weil es einer der einfachsten lauten Kanäle ist, um zu analysieren. Viele Probleme in der Nachrichtentheorie können auf einen BSC reduziert werden. Umgekehrt kann das Imstandesein, effektiv über den BSC zu übersenden, Lösungen für mehr komplizierte Kanäle verursachen.

Definition

Ein binärer symmetrischer Kanal mit der Überkreuzungswahrscheinlichkeit p angezeigt dadurch, ist ein Kanal mit dem binären Eingang und der binären Produktion und der Wahrscheinlichkeit des Fehlers p; d. h. wenn X die übersandte zufällige Variable und Y die erhaltene Variable ist, dann wird der Kanal durch die bedingten Wahrscheinlichkeiten charakterisiert

: Pr (Y = 0 | X = 0) = 1 − p

: Pr (Y = 0 | X = 1) = p

: Pr (Y = 1 | X = 0) = p

: Pr (Y = 1 | X = 1) = 1 − p

Es wird dass 0  p  1/2 angenommen. Wenn p> 1/2, dann kann der Empfänger die Produktion tauschen (dolmetschen 1, wenn es 0, und umgekehrt sieht), und einen gleichwertigen Kanal mit der Überkreuzungswahrscheinlichkeit 1 &minus erhalten; p  1/2.

Kapazität von BSC

Die Kapazität des Kanals ist 1 − H (p), wo H (p) die binäre Wärmegewicht-Funktion ist.

Das gegenteilige kann von einem Bereich gezeigt werden, der Argument einpackt. In Anbetracht eines Kennwortes gibt es ungefähr 2 typische Produktionsfolgen. Es gibt 2 mögliche Gesamtproduktionen, und der Eingang wählt von einem codebook der Größe 2. Deshalb würde der Empfänger beschließen, den Raum in "Bereiche" mit 2 / 2 = 2 potenzielle Produktionen jeder zu verteilen. Wenn R> 1 − H (p) dann werden die Bereiche zu dicht asymptotisch gepackt sein, und der Empfänger wird nicht im Stande sein, das richtige Kennwort mit der verschwindenden Wahrscheinlichkeit zu identifizieren.

Der Kanalhöchstlehrsatz von Shannon für BSC

Der laute Codierlehrsatz von Shannon ist für alle Arten von Kanälen allgemein. Wir ziehen einen speziellen Fall dieses Lehrsatzes für einen binären symmetrischen Kanal mit einer Fehlerwahrscheinlichkeit p in Betracht.

Lauter Codierlehrsatz für BSC

Wir zeigen an (und würde fortsetzen anzuzeigen) Geräusch von als "". Das Geräusch ist im Wesentlichen eine zufällige Variable mit jedem seiner Indizes, die mit der Wahrscheinlichkeit und mit der Wahrscheinlichkeit sind.

Lehrsatz 1

Für alle und ganzes das

Was dieser Lehrsatz wirklich einbezieht, ist eine Nachricht, wenn aufgepickt, von, verschlüsselt mit einer zufälligen Verschlüsselungsfunktion, und senden Sie über einen lauten, es gibt eine sehr hohe Wahrscheinlichkeit, die ursprüngliche Nachricht durch die Entzifferung wieder zu erlangen, wenn oder tatsächlich die Rate des Kanals durch die Menge begrenzt wird, hat im Lehrsatz festgesetzt. Die Entzifferungsfehlerwahrscheinlichkeit ist exponential klein.

Wir werden jetzt Lehrsatz 1 beweisen.

Beweis

Wir werden zuerst die Verschlüsselungsfunktion und die im Lehrsatz verwendete Entzifferungsfunktion beschreiben. Sein Nutzen, um hier festzustellen, dass wir die probabilistic Methode verwenden würden, diesen Lehrsatz zu beweisen. Der Lehrsatz von Shannon war eine der frühsten Anwendungen dieser Methode.

Verschlüsselung der Funktion: Die Verschlüsselungsfunktion: Wird aufs Geratewohl ausgewählt. Das bedeutet in Anbetracht jeder Nachricht, wir wählen gleichförmig und unabhängig aufs Geratewohl.

Entzifferung der Funktion: Die Entzifferungsfunktion: Wird jedes erhaltene Kennwort gegeben, wir finden die Nachricht solch, der (mit Banden gebrochen willkürlich) minimal ist. Diese Art einer Entzifferungsfunktion wird eine Funktion der maximalen Wahrscheinlichkeitsentzifferung (MLD) genannt.

Jetzt zuerst zeigen wir uns, für einen festen und gewähltes zufällig, die Wahrscheinlichkeit des Misserfolgs über das Geräusch ist exponential klein. An diesem Punkt arbeitet der Beweis für eine feste Nachricht. Als nächstes erweitern wir dieses Ergebnis, für alle zu arbeiten. Wir erreichen das, indem wir Hälfte der Kennwörter aus dem Code mit dem Argument beseitigen, dass der Beweis für die Entzifferungsfehlerwahrscheinlichkeit für die mindestens Hälfte der Kennwörter hält. Die letzte Methode wird Zensierung genannt. Das gibt dem Gesamtprozess den Namen das zufällige Codieren mit der Zensierung.

Ein hoher Beweis: In Anbetracht einer festen Nachricht müssen wir einschätzen, dass der erwartete Wert der Wahrscheinlichkeit des erhaltenen Kennwortes zusammen mit dem Geräusch auf der Entzifferung nicht zurückgibt. Das heißt, müssen wir schätzen:.

Lassen Sie, das erhaltene Kennwort zu sein. In der Größenordnung vom decodierten Kennwort, um der Nachricht nicht gleich zu sein, muss eines der folgenden Ereignisse vorkommen:

• liegt innerhalb des Balls von Hamming des Radius für etwas größeren nicht als, in den Mittelpunkt gestellt daran. Diese Bedingung wird hauptsächlich verwendet, um die Berechnungen leichter zu machen.
• Es gibt eine andere solche Nachricht dass. Mit anderen Worten nehmen die Fehler wegen des Geräusches das übersandte an einer anderen verschlüsselten Nachricht nähere Kennwort.

Wir können Chernoff anwenden, der verpflichtet ist, das nicht Ereignis des ersten Ereignisses zu sichern. Durch die Verwendung von Chernoff hat gebunden wir haben. So, für irgendwelchen, können wir aufpicken, um groß genug zu sein, um die obengenannte Wahrscheinlichkeit exponential klein zu machen.

Bezüglich des zweiten Ereignisses bemerken wir, dass die Wahrscheinlichkeit, die ist, wo der Ball von Hamming des Radius ist, der am Vektoren in den Mittelpunkt gestellt ist, und sein Volumen ist. Mit der Annäherung, um die Zahl von Kennwörtern im Ball von Hamming zu schätzen, haben wir. Folglich beläuft sich die obengenannte Wahrscheinlichkeit darauf. Jetzt hat verwendende Vereinigung gebunden, wir können ober hat die Existenz von solch einem gebunden, durch den, wie gewünscht, durch die Wahl dessen ist.

Ein ausführlicher Beweis: Von der obengenannten Analyse berechnen wir die Wahrscheinlichkeit des Ereignisses, dass das decodierte Kennwort plus das Kanalgeräusch nicht dasselbe als die ursprüngliche gesandte Nachricht ist. Wir werden einige Symbole hier einführen. Lassen Sie zeigen die Wahrscheinlichkeit an, gegebenes Kennwort zu erhalten, dass Kennwort gesandt wurde. Zeigen Sie dadurch an.

Wir bekommen die letzte Ungleichheit durch unsere Analyse mit dem Chernoff, der oben gebunden ist. Jetzt Einnahme der Erwartung an beiden Seiten haben wir,

[[]..

Jetzt haben wir. Das sagt gerade, dass die Menge wieder von der Analyse im höheren Niveau-Beweis oben. Folglich alles zusammen nehmend, haben wir

, durch die passende Auswahl des Werts dessen. Da das obengenannte bestimmte für jede Nachricht hält, haben wir. Jetzt können wir die Ordnung der Summierung der en general in Bezug auf die Nachricht und die Wahl der Verschlüsselungsfunktion ohne Verlust der Allgemeinheit ändern. Folglich haben wir. Folglich schließlich durch die probabilistic Methode, haben wir etwas Verschlüsselungsfunktion und eine entsprechende solche Entzifferungsfunktion dass.

An diesem Punkt arbeitet der Beweis für eine feste Nachricht. Aber wir müssen sicherstellen, dass das obengenannte bestimmte für alle Nachrichten gleichzeitig hält. Dafür, lassen Sie uns die Nachrichten durch ihre Entzifferungsfehlerwahrscheinlichkeiten sortieren. Jetzt, indem wir die Ungleichheit von Markov anwenden, können wir die Entzifferungsfehlerwahrscheinlichkeit für die ersten Nachrichten zeigen, um höchstens zu sein. So, um zu bestätigen, dass das obengenannte bestimmte, um für jede Nachricht zu halten, wir gerade von den letzten Nachrichten aus der sortierten Ordnung zurechtmachen konnten. Das gibt uns im Wesentlichen eine andere Verschlüsselungsfunktion mit einer entsprechenden Entzifferungsfunktion mit einer Entzifferungsfehlerwahrscheinlichkeit höchstens mit derselben Rate. Als wir genommen haben, um dem gleich zu sein, haben uns die Entzifferungsfehlerwahrscheinlichkeit dazu gebunden. Dieser Zensierungsprozess vollendet den Beweis des Lehrsatzes 1.

Sprechen Sie vom Höchstlehrsatz von Shannon

Der gegenteilige vom Höchstlehrsatz stellt im Wesentlichen fest, dass das die beste Rate ist, die man über einen binären symmetrischen Kanal erreichen kann. Formell die Lehrsatz-Staaten:

Lehrsatz 2

Wenn dann der folgende für jede Verschlüsselung und Entzifferung der Funktion wahr ist: und: beziehungsweise: [.

Für einen ausführlichen Beweis dieses Lehrsatzes wird der Leser gebeten, sich auf die Bibliografie zu beziehen. Die Intuition hinter dem Beweis zeigt jedoch die Zahl von Fehlern, schnell zu wachsen, als die Rate außer der Kanalkapazität wächst. Die Idee ist der Absender erzeugt Nachrichten der Dimension, während der Kanal Übertragungsfehler einführt. Wenn die Kapazität des Kanals ist, ist die Zahl von Fehlern normalerweise für einen Code der Block-Länge. Die maximale Zahl von Nachrichten ist. Die Produktion des Kanals hat andererseits mögliche Werte. Wenn es Verwirrung zwischen irgendwelchen zwei Nachrichten gibt, ist es das wahrscheinlich. Folglich würden wir, ein Fall haben, den wir gern vermeiden würden, um die Entzifferungsfehlerwahrscheinlichkeit exponential klein zu halten.

Codes für BSC

Sehr kürzlich ist viel Arbeit getan worden und wird auch getan, um ausführliche Fehlerkorrekturcodes zu entwerfen, um die Kapazitäten von mehreren Standardnachrichtenkanälen zu erreichen. Die Motivation hinter dem Entwerfen solcher Codes soll die Rate des Codes mit dem Bruchteil von Fehlern verbinden, die es korrigieren kann.

Die Annäherung hinter dem Design von Codes, die die Kanalkapazitäten dessen entsprechen, ist gewesen, eine kleinere Zahl von Fehlern mit einer hohen Wahrscheinlichkeit zu korrigieren, und die höchstmögliche Rate zu erreichen. Der Lehrsatz von Shannon gibt uns die beste Rate, die über a erreicht werden konnte, aber es gibt uns keine Idee von keinen ausführlichen Codes, die diese Rate erreichen. Tatsächlich werden solche Codes normalerweise gebaut, um nur einen kleinen Bruchteil von Fehlern mit einer hohen Wahrscheinlichkeit zu korrigieren, aber eine sehr gute Rate zu erreichen. Der erste derartige Code war wegen George D. Forneys 1966. Der Code ist ein verketteter Code durch das Verketten zwei verschiedener Arten von Codes. Wir werden den Baucode von Forney für den Binären Symmetrischen Kanal besprechen und seine Rate und Entzifferungsfehlerwahrscheinlichkeit kurz hier analysieren. Verschiedene ausführliche Codes, für die Kapazität des binären Ausradierungskanals zu erreichen, sind auch kürzlich heraufgekommen.

Der Code von Forney für BSC

Forney hat einen verketteten Code gebaut, um die Kapazität des Lehrsatzes 1 dafür zu erreichen. In seinem Code,

• Der Außencode ist ein Code der Block-Länge und Rate über das Feld, und. Zusätzlich haben wir einen Entzifferungsalgorithmus, für den bis zum Bruchteil von Grenzfall-Fehlern und Läufen rechtzeitig korrigieren kann.
• Der innere Code ist ein Code der Block-Länge, Dimension und einer Rate dessen. Zusätzlich haben wir einen Entzifferungsalgorithmus für mit einer Entzifferungsfehlerwahrscheinlichkeit höchstens und Läufe rechtzeitig.

Für den Außencode wäre ein Code des Rohres-Solomon der erste Code gewesen, um im Sinn gekommen zu sein. Jedoch würden wir sehen, dass der Aufbau solch eines Codes in der polynomischen Zeit nicht getan werden kann. Das ist, warum ein binärer geradliniger Code dafür verwendet wird.

Weil der innere Code codiert, finden wir einen geradlinigen Code, indem wir aus dem geradlinigen Code der Block-Länge und Dimension erschöpfend suchen, deren Rate die Kapazität, durch den Lehrsatz 1 entspricht.

Die Rate, die fast die Kapazität entspricht. Wir bemerken weiter, dass die Verschlüsselung und Entzifferung dessen in der polynomischen Zeit in Bezug darauf getan werden können. Eigentlich nimmt Verschlüsselung Zeit in Anspruch. Weiter nimmt der beschriebene Entzifferungsalgorithmus so lange Zeit in Anspruch; und.

Die Entzifferung der Fehlerwahrscheinlichkeit für C

Ein natürlicher Entzifferungsalgorithmus dafür ist zu:

• Nehmen Sie an
• Führen Sie auf durch

Bemerken Sie, dass jeder Block des Codes dafür als ein Symbol dafür betrachtet wird. Jetzt, da die Wahrscheinlichkeit des Fehlers an jedem Index dafür höchstens ist und die Fehler darin unabhängig sind, ist die erwartete Zahl von Fehlern dafür höchstens durch die Linearität der Erwartung. Jetzt hat sich wendender Chernoff gebunden, wir haben Fehlerwahrscheinlichkeit mehr verpflichtet als Fehler, die vorkommen zu sein. Da der Außencode an den meisten Fehlern korrigieren kann, ist das die Entzifferungsfehlerwahrscheinlichkeit dessen. Das, wenn ausgedrückt, in asymptotischen Begriffen, gibt uns eine Fehlerwahrscheinlichkeit dessen. So ist die erreichte Entzifferungsfehlerwahrscheinlichkeit dessen als Lehrsatz 1 exponential klein.

Wir haben eine allgemeine Technik gegeben, um zu bauen. Für detailliertere Beschreibungen darauf und lesen Sie bitte die folgenden Verweisungen. Kürzlich haben einige andere Codes auch gebaut zu werden, für die Kapazitäten zu erreichen. Sein, den sich es lohnt zu erwähnen, dass LDPC-Codes jetzt für diesen Zweck für ihre schnellere Entzifferungszeit betrachtet werden. Verweisen Sie bitte auf das Buch von Richardson und in der Verweisung zitiertem Urbanke, mehr über solche Codes zu wissen.

Siehe auch

• Z Kanal
• David J. C. MacKay. Informationstheorie, Schlussfolgerung und das Lernen von Algorithmen Cambridge: Universität von Cambridge Presse, 2003. Internationale Standardbuchnummer 0-521-64298-1
• Thomas M. Cover, Joy A. Thomas. Elemente der Informationstheorie, 1. Ausgabe. New York: Wiley-Zwischenwissenschaft, 1991. Internationale Standardbuchnummer 0-471-06259-6.
• Der Kurs von Atri Rudra über den Fehler, der Codes Korrigiert: Combinatorics, Algorithmen und Anwendungen (Fall 2007), Vorträge 9, 10, 29, und 30.
• Madhu-Kurs von Sudan über die Algorithmische Einführung ins Codieren der Theorie (Fall 2001), Vortrag 1 und 2.
• G. David Forney. Verkettete Codes. MIT Presse, Cambridge, Massachusetts, 1966.
• Der Kurs von Venkat Guruswamy über Fehlerkorrekturcodes: Aufbauten und Algorithmen, Herbst 2006.
• Eine mathematische Theorie der Kommunikation C. E Shannon, ACM SIGMOBILE Mobile EDV und Kommunikationsrezension.
• Moderne Codiertheorie von Tom Richardson und Rudiger Urbanke., Universität von Cambridge drücken

Außenverbindungen

• Java applet das Einführen Binären Symmetrischen Kanals