Binary Symmetric Channel

Scheme of a BSC

A binary symmetric channel (BSC for short) is an information-theoretic channel in which the probability of a false transmission (also error probability) of 1 is exactly as high as the probability of false transmission of a 0. That is, the probability that a 1 was received, if a 0 was sent and vice versa, the probability is . For the remaining cases, i.e. the correct transmission, there is a probability of : ${\displaystyle p}$ ${\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}}}$

The following applies here , because if it were, the receiver could invert all the bits received and would thus receive an equivalent channel with an error probability of . ${\displaystyle 0\leq p\leq 1/2}$ ${\displaystyle p>1/2}$ ${\displaystyle 1-p\leq 1/2}$

capacity

The channel capacity of the binary balanced channel is

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

where the entropy of the Bernoulli distribution is with probability : ${\displaystyle \operatorname {H} _{\text{b}}(p)}$ ${\displaystyle p}$

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

Proof: The capacity is defined as the maximum transinformation between input and output for all possible probability distributions at the input : ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle p_{X}(x)}$

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

The transinformation can be reformulated to

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

The first two steps follow from the definition of transinformation or the conditional entropy . The entropy at the output, with a given and fixed input bit ( ), equals the entropy of the Bernoulli distribution, which leads to the third line, which can be further simplified. ${\displaystyle H(Y|X=x)}$

In the last line, only the first term depends on the probability distribution at the input . In addition, the entropy of a binary random variable is known to have its maximum of 1 if it is uniformly distributed. Due to the symmetry of the channel, even distribution at the output can only be achieved if there is also an even distribution at the input. So you get . ${\displaystyle H(Y)}$ ${\displaystyle p_{X}(x)}$ ${\displaystyle C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p)}$

See also

• Binary extinction channel

literature

• Bernd Friedrichs: Channel coding. Basics and applications in modern communication systems. Springer Verlag, Berlin / Heidelberg 1995, ISBN 3-540-59353-5 .
• Werner Lütkebohmert : Coding Theory. Algebraic-geometric basics and algorithms. Vieweg Verlag, Braunschweig u. a. 2003, ISBN 3-528-03197-2 ( Vieweg course - advanced course in mathematics ).
• Rudolf Mathar: Information Theory. Discrete models and processes, BG Teubner Verlag, Stuttgart 1996, ISBN 978-3-519-02574-0 .

Individual evidence

1. ^ Thomas M. Cover, Joy A. Thomas: Elements of information theory , p. 187, 2nd edition, New York: Wiley-Interscience, 2006, ISBN 978-0471241959 .

Web links

• Lecture notes Kanalcodierung I (accessed January 22, 2018)
• Channel coding (accessed January 22, 2018)
• SCRIPTUM for the course INFORMATION THEORY (accessed on January 22, 2018)