Binary Symmetric Channel

Ein binärer symmetrischer Kanal (englisch binary symmetric channel, kurz BSC) ist ein 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 ${\displaystyle p}$. Für die verbleibenden Fälle, also der korrekten Übermittlung, ergibt sich damit eine Wahrscheinlichkeit von jeweils ${\displaystyle 1-p}$:

${\displaystyle {\begin{aligned}\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{aligned}}}$

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

Die Kanalkapazität des binären symmetrischen Kanals ist

${\displaystyle \ C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p),}$

wobei ${\displaystyle \operatorname {H} _{\text{b}}(p)}$ die Entropie der Bernoulli-Verteilung mit Wahrscheinlichkeit ${\displaystyle p}$ ist:

${\displaystyle \operatorname {H} _{\text{b}}(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)}$

Beweis: Die Kapazität ist definiert als die maximale Transinformation zwischen Eingang ${\displaystyle X}$ und Ausgang ${\displaystyle Y}$ für alle möglichen Wahrscheinlichkeitsverteilungen am Eingang ${\displaystyle p_{X}(x)}$:

${\displaystyle C=\max _{p_{X}(x)}\left\{\,I(X;Y)\,\right\}}$

Die Transinformation kann umformuliert werden zu

${\displaystyle {\begin{aligned}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{aligned}}}$

wobei die ersten beiden Schritte aus der Definition von Transinformation bzw. der bedingten Entropie folgen. Die Entropie am Ausgang, bei gegebenem und festem Eingangsbit (${\displaystyle H(Y|X=x)}$) 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 ${\displaystyle H(Y)}$ von der Wahrscheinlichkeitsverteilung am Eingang ${\displaystyle p_{X}(x)}$ 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 ${\displaystyle C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p)}$.^[1]

• Binärer Auslöschungskanal

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

1. ↑ Thomas M. Cover, Joy A. Thomas: Elements of information theory, S. 187, 2. Auflage, New York: Wiley-Interscience, 2006, ISBN 978-0471241959.

• Vorlesungsskript Kanalcodierung I (abgerufen am 22. Januar 2018)
• Kanalcodierung (abgerufen am 22. Januar 2018)
• SKRIPTUM zur Lehrveranstaltung INFORMATIONSTHEORIE (abgerufen am 22. Januar 2018)