imported>Middle Distance Biker 39: /* Literatur */ Hinweis "Leerzeichen um Schrägstrich", Literaturangaben leicht verbessert, ISBN-13 erst ab 2007

2024-01-27T01:25:39Z

Literatur: Hinweis "Leerzeichen um Schrägstrich", Literaturangaben leicht verbessert, ISBN-13 erst ab 2007

Neue Seite

[[Datei:Binary symmetric channel (en).svg|mini|hochkant=2|Schema eines BSC]]
Ein '''binärer symmetrischer Kanal''' (englisch binary symmetric channel, kurz BSC) ist ein [[Kanal (Informationstheorie)|informationstheoretischer Kanal]], bei dem die [[Wahrscheinlichkeit]] einer Falschübermittlung (auch Fehlerwahrscheinlichkeit) von 1 genau so hoch ist wie die Wahrscheinlichkeit der Falschübermittlung einer 0. Das heißt, die Wahrscheinlichkeit, dass eine 1 empfangen wurde, falls eine 0 gesendet wurde und umgekehrt, beträgt die Wahrscheinlichkeit <math>p</math>. Für die verbleibenden Fälle, also der korrekten Übermittlung, ergibt sich damit eine Wahrscheinlichkeit von jeweils <math>1-p</math>:

:<math>\begin{align}
\operatorname {Pr} [ Y = 0 | X = 0 ] &= 1 - p \\
\operatorname {Pr} [ Y = 0 | X = 1 ] &= p \\
\operatorname {Pr} [ Y = 1 | X = 0 ] &= p \\
\operatorname {Pr} [ Y = 1 | X = 1 ] &= 1 - p
\end{align}</math>

Dabei gilt <math>0 \le p \le 1/2</math>, denn falls <math>p > 1/2</math> wäre, könnte der Empfänger alle empfangenen Bits invertieren und würde damit einen äquivalenten Kanal mit einer Fehlerwahrscheinlichkeit von <math>1 - p \le 1/2</math> erhalten.

== Kapazität ==
Die [[Kanalkapazität]] des binären symmetrischen Kanals ist
:<math>\ C_{\text{BSC}} = 1 - \operatorname H_\text{b}(p), </math>
wobei <math>\operatorname H_\text{b}(p)</math> die [[Bernoulli-Verteilung#Entropie|Entropie der Bernoulli-Verteilung]] mit Wahrscheinlichkeit <math>p</math> ist:

<math>\operatorname H_\text{b}(p) = -p\log_2(p)-(1-p)\log_2(1-p)</math>

'''Beweis:''' Die Kapazität ist definiert als die maximale [[Transinformation]] zwischen Eingang <math>X</math> und Ausgang <math>Y</math> für alle möglichen Wahrscheinlichkeitsverteilungen am Eingang <math>p_X(x)</math>:

:<math> C = \max_{p_X(x)} \left \{\, I(X;Y)\, \right \} </math>

Die Transinformation kann umformuliert werden zu

:<math>\begin{align}
I(X;Y) &= H(Y) - H(Y|X) \\
&= H(Y) - \sum_{x \in \{0,1\} }{p_X(x) H(Y|X=x)} \\
&= H(Y) - \sum_{x \in \{0,1\} }{p_X(x)} \operatorname H_\text{b}(p) \\
&= H(Y) - \operatorname H_\text{b}(p),
\end{align}</math>

wobei die ersten beiden Schritte aus der Definition von Transinformation bzw. der [[Bedingte Entropie|bedingten Entropie]] folgen. Die Entropie am Ausgang, bei gegebenem und festem Eingangsbit (<math>H(Y|X=x)</math>) gleicht der Entropie der Bernoulli-Verteilung, was zur dritten Zeile führt, welche weiter vereinfacht werden kann.

In der letzten Zeile ist nur der erste Term <math>H(Y)</math> von der Wahrscheinlichkeitsverteilung am Eingang <math>p_X(x)</math> abhängig. Außerdem ist von der Entropie einer binären Zufallsvariable bekannt, dass diese ihr Maximum von 1 bei einer Gleichverteilung besitzt. Die Gleichverteilung am Ausgang kann, bedingt durch die Symmetrie des Kanals, nur erreicht werden, wenn auch eine Gleichverteilung am Eingang vorliegt. Damit erhält man <math>C_{\text{BSC}}=1-\operatorname H_\text{b}(p)</math>.<ref>Thomas M. Cover, Joy A. Thomas: ''Elements of information theory'', S. 187, 2. Auflage, New York: Wiley-Interscience, 2006, ISBN 978-0471241959.</ref>

== Siehe auch ==
* [[Binärer Auslöschungskanal]]

== Literatur ==
* Bernd Friedrichs: ''Kanalcodierung. Grundlagen und Anwendungen in modernen Kommunikationssystemen.'' Springer Verlag, Berlin/Heidelberg 1995, ISBN 3-540-59353-5.
* [[Werner Lütkebohmert]]: ''Codierungstheorie. Algebraisch-geometrische Grundlagen und Algorithmen.'' Vieweg Verlag, Braunschweig u. a. 2003, ISBN 3-528-03197-2 (''Vieweg-Studium – Aufbaukurs Mathematik'').
* Rudolf Mathar: ''Informationstheorie. Diskrete Modelle und Verfahren.'' B.G. Teubner Verlag, Stuttgart 1996, ISBN 3-519-02574-4.

== Einzelnachweise ==
<references />

== Weblinks ==
* [http://www.ant.uni-bremen.de/sixcms/media.php/102/9490/kc1_top.pdf Vorlesungsskript Kanalcodierung I] (abgerufen am 22. Januar 2018)
* [http://page.mi.fu-berlin.de/juergen/WS0910/Codierungstheorie/codtheo3.pdf Kanalcodierung] (abgerufen am 22. Januar 2018)
* [https://web.archive.org/web/20180123072343/https://www.uni-salzburg.at/fileadmin/oracle_file_imports/556438.PDF SKRIPTUM zur Lehrveranstaltung INFORMATIONSTHEORIE] (abgerufen am 22. Januar 2018)

[[Kategorie:Informationstheorie]]

Binary Symmetric Channel - Versionsgeschichte

imported>Middle Distance Biker 39: /* Literatur */ Hinweis "Leerzeichen um Schrägstrich", Literaturangaben leicht verbessert, ISBN-13 erst ab 2007