Binary Symmetric Channel

Schema eines BSC

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 $p$. Für die verbleibenden Fälle, also der korrekten Übermittlung, ergibt sich damit eine Wahrscheinlichkeit von jeweils $1-p$:

$\begin{array}{cc}\mathrm{Pr}[Y=0|X=0]& =1-p\\ \mathrm{Pr}[Y=0|X=1]& =p\\ \mathrm{Pr}[Y=1|X=0]& =p\\ \mathrm{Pr}[Y=1|X=1]& =1-p\end{array}$

Dabei gilt $0\le p\le 1/2$, denn falls $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 $1-p\le 1/2$ erhalten.

Kapazität

Die Kanalkapazität des binären symmetrischen Kanals ist

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

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

${\mathrm{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 $X$ und Ausgang $Y$ für alle möglichen Wahrscheinlichkeitsverteilungen am Eingang $p_X(x)$:

$C=\underset{p_X(x)}{\max }\{I(X;Y)\}$

Die Transinformation kann umformuliert werden zu

$\begin{array}{cc}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){\mathrm{H}}_{\text{b}}(p)\\ & =H(Y)-{\mathrm{H}}_{\text{b}}(p),\end{array}$

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

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.

Weblinks

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