View source for Information Theory/Application to Digital Signal Transmission

 
{{Header
|Untermenü=Mutual Information Between Two Discrete Random Variables
|Vorherige Seite=Verschiedene Entropien zweidimensionaler Zufallsgrößen
|Nächste Seite=Differentielle Entropie
}}

==Information-theoretical model of digital signal transmission == 	
<br>
The entropies defined so far in general terms are now applied to digital signal transmission, whereby we assume a discrete memoryless channel&nbsp; $\rm (DMC)$&nbsp; according to the graphic:

[[File:P_ID2779__Inf_T_3_3_S1a_neu.png|right|frame|Digital signal transmission model under consideration]]

*The set of source symbols is characterized by the discrete random variable&nbsp; $X$&nbsp;, where&nbsp; $|X|$&nbsp; indicates the source symbol set size:
 
:$$X = \{\hspace{0.05cm}x_1\hspace{0.05cm}, \hspace{0.15cm} x_2\hspace{0.05cm},\hspace{0.15cm} \text{...}\hspace{0.1cm} ,\hspace{0.15cm} x_{\mu}\hspace{0.05cm}, \hspace{0.15cm}\text{...}\hspace{0.1cm} , \hspace{0.15cm} x_{|X|}\hspace{0.05cm}\}\hspace{0.05cm}.$$

*Correspondingly,&nbsp; $Y$&nbsp; characterizes the set of sink symbols with the symbol set size&nbsp; $|Y|$:
 
:$$Y = \{\hspace{0.05cm}y_1\hspace{0.05cm}, \hspace{0.15cm} y_2\hspace{0.05cm},\hspace{0.15cm} \text{...}\hspace{0.1cm} ,\hspace{0.15cm} y_{\kappa}\hspace{0.05cm}, \hspace{0.15cm}\text{...}\hspace{0.1cm} , \hspace{0.15cm} Y_{|Y|}\hspace{0.05cm}\}\hspace{0.05cm}.$$

*Usually&nbsp; $|Y| = |X|$is valid.&nbsp; Also possible is&nbsp; $|Y| > |X|$, for example with the&nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|$\text{Binary Erasure Channel}$]]&nbsp; (BEC): 
:$$X = \{0,\ 1\},\hspace{0.5cm} Y = \{0,\ 1,\ \ \text{E}\}\    ⇒  \ |X| = 2, \ |Y| = 3.$$

*The sink symbol&nbsp; $\rm E$&nbsp; indicates an&nbsp; "erasure".&nbsp; The event&nbsp; $Y=\text{E}$&nbsp; indicates that a decision for&nbsp; $0$&nbsp; or for&nbsp; $1$&nbsp; would be too uncertain.

*The symbol probabilities of the source and sink are accounted for in the graph by the probability mass functions&nbsp; $P_X(X)$&nbsp; and&nbsp; $P_Y(Y)$:
:$$P_X(x_{\mu}) = {\rm Pr}( X = x_{\mu})\hspace{0.05cm}, \hspace{0.3cm}
P_Y(y_{\kappa}) = {\rm Pr}( Y = y_{\kappa})\hspace{0.05cm}.$$

*Let it hold:&nbsp; The prtobability mass functions&nbsp; $P_X(X)$&nbsp; and&nbsp; $P_Y(Y)$&nbsp; contain no zeros &nbsp; ⇒ &nbsp; $\text{supp}(P_X) = P_X$ &nbsp;and&nbsp; $\text{supp}(P_Y) = P_Y$.&nbsp; This prerequisite facilitates the description without loss of generality.

*All transition probabilities of the discrete memoryless channel &nbsp; $\rm (DMC)$&nbsp; are captured by the&nbsp; conditional probability function&nbsp; $P_{Y|X}(Y|X)$.&nbsp;. With&nbsp; $x_μ ∈ X$&nbsp; and&nbsp; $y_κ ∈ Y$,&nbsp; the following definition applies to this:
 
:$$P_{Y\hspace{0.01cm}|\hspace{0.01cm}X}(y_{\kappa}\hspace{0.01cm} |\hspace{0.01cm} x_{\mu}) = {\rm Pr}(Y\hspace{-0.1cm} = y_{\kappa}\hspace{0.03cm} | \hspace{0.03cm}X \hspace{-0.1cm}= x_{\mu})\hspace{0.05cm}.$$


The green block in the graph marks&nbsp; $P_{Y|X}(⋅)$&nbsp; with&nbsp; $|X|$&nbsp; inputs and&nbsp; $|Y|$&nbsp; outputs.&nbsp; Blue connections mark transition probabilities&nbsp; $\text{Pr}(y_i | x_μ)$&nbsp; starting from&nbsp; $x_μ$&nbsp; with&nbsp; $1 ≤ i ≤ |Y|$,&nbsp; while all red connections end at&nbsp; $y_κ$:&nbsp; &nbsp; $\text{Pr}(y_κ | x_i)$&nbsp; with&nbsp; $1 ≤ i ≤ |X|$.

Before we give the entropies for the individual probability functions, viz.
:$$P_X(X) ⇒ H(X),\hspace{0.5cm}  P_Y(Y) ⇒ H(Y), \hspace{0.5cm} P_{XY}(X) ⇒ H(XY), \hspace{0.5cm} P_{Y|X}(Y|X) ⇒ H(Y|X),\hspace{0.5cm} P_{X|Y}(X|Y) ⇒ H(X|Y),$$
the above statements are to be illustrated by an example.

[[File:P_ID2780__Inf_T_3_3_S1b_neu.png|right|frame|Channel model&nbsp; "Binary Erasure Channel"&nbsp; $\rm (BEC)$]]
{{GraueBox|TEXT=
$\text{Example 1}$:&nbsp; In the book&nbsp; "Channel Coding"&nbsp; we also deal with the&nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|$\text{Binary Erasure Channel}$]]&nbsp; $\rm (BEC)$, which is sketched in a somewhat modified form on the right. &nbsp; The following prerequisites apply:
*Let the input alphabet be binary&nbsp; &rArr; &nbsp; $X = \{0,\ 1 \}$  &nbsp; ⇒  &nbsp; $\vert X\vert = 2$&nbsp; while three values are possible at the output &nbsp; &rArr; &nbsp; $Y = \{0,\ 1,\ \text{E} \}$  &nbsp; ⇒  &nbsp; $\vert Y\vert = 3$.
*The symbol&nbsp; $\text{E}$&nbsp;  indicates the case that the receiver cannot decide for one of the binary symbols&nbsp; $0$&nbsp; or&nbsp; $1$&nbsp; due to too much channel interference.&nbsp; "E"&nbsp; stands for erasure.
*With the&nbsp; $\rm BEC$&nbsp; according to the above sketch, both a transmitted&nbsp; $0$&nbsp; and a&nbsp; $1$&nbsp; are erased with probability&nbsp; $λ$&nbsp; while the probability of a correct transmission is&nbsp; $1 – λ$&nbsp; in each case.
*In contrast, transmission errors are excluded by the BEC model  &nbsp; <br>⇒  &nbsp; the conditional probabilities &nbsp;$\text{Pr}(Y = 1 \vert X = 0)$ &nbsp;and&nbsp; $\text{Pr}(Y = 0 \vert X = 1)$ &nbsp;are both zero.


At the transmitter, the&nbsp; "zeros"&nbsp; and&nbsp; "ones"&nbsp; would not necessarily be equally probable.&nbsp; Rather, we use the probability mass functions
:$$\begin{align*}P_X(X)  & =  \big ( {\rm Pr}( X = 0)\hspace{0.05cm},\hspace{0.2cm} {\rm Pr}( X = 1) \big )\hspace{0.05cm},\\
P_Y(Y) & = \big ( {\rm Pr}( Y = 0)\hspace{0.05cm},\hspace{0.2cm} {\rm Pr}( Y = 1)\hspace{0.05cm},\hspace{0.2cm} {\rm Pr}( Y = {\rm E}) \big )\hspace{0.05cm}.\end{align*}$$

From the above model we then get:
 
:$$\begin{align*}P_Y(0)  & =    {\rm Pr}( Y \hspace{-0.1cm} = 0) = P_X(0) \cdot ( 1 - \lambda)\hspace{0.05cm}, \\
P_Y(1) & =  {\rm Pr}( Y \hspace{-0.1cm} = 1) = P_X(1) \cdot ( 1 - \lambda)\hspace{0.05cm}, \\
P_Y({\rm E})  & =   {\rm Pr}( Y \hspace{-0.1cm} = {\rm E}) = P_X(0) \cdot \lambda \hspace{0.1cm}+\hspace{0.1cm} P_X(1) \cdot \lambda \hspace{0.05cm}.\end{align*}$$

If we now take&nbsp; $P_X(X)$&nbsp; and&nbsp; $P_Y(Y)$&nbsp; to be vectors, the result can be represented as follows:
 
:$$P_{\hspace{0.05cm}Y}(Y) = P_X(X) \cdot P_{\hspace{0.05cm}Y\hspace{-0.01cm}\vert \hspace{-0.01cm}X}(Y\hspace{-0.01cm} \vert \hspace{-0.01cm} X) \hspace{0.05cm},$$

where the transition probabilities &nbsp;$\text{Pr}(y_κ\vert x_μ)$&nbsp; are accounted for by the following matrix:
 
:$$P_{\hspace{0.05cm}Y\hspace{-0.01cm} \vert \hspace{-0.01cm}X}(Y\hspace{-0.01cm} \vert \hspace{-0.01cm} X) = 
\begin{pmatrix} 
		1 - \lambda  & 0 & \lambda\\
		0 & 1 - \lambda  & \lambda
		\end{pmatrix}\hspace{0.05cm}.$$

Note:
*We have chosen this representation only to simplify the description. 
*$P_X(X)$&nbsp; and&nbsp; $P_Y(Y)$&nbsp; are not vectors in the true sense and&nbsp; $P_{Y \vert X}(Y\vert X)$&nbsp; is not a matrix either.}}


==Directional diagram for digital signal transmission ==
<br>
All entropies defined in the&nbsp; [[Information_Theory/Verschiedene_Entropien_zweidimensionaler_Zufallsgrößen|"last chapter"]]&nbsp; also apply to digital signal transmission.&nbsp; However, it is expedient to choose the right-hand diagram instead of the diagram used so far, corresponding to the left-hand diagram, in which the direction from source&nbsp; $X$&nbsp; to sink&nbsp; $Y$&nbsp; is recognizable.

[[File:EN_Inf_T_3_3_S2_vers2.png|center|frame|Two information-theoretical models for digital signal transmission]]

Let us now interpret the right graph starting from the general&nbsp; [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung#Information-theoretical_model_of_digital_signal_transmission|$\text{DMC model}$]]:
*The&nbsp; &raquo;'''source entropy'''&laquo;&nbsp; $H(X)$&nbsp; denotes the average information content of the source symbol sequence. &nbsp; With the symbol set size&nbsp; $|X|$&nbsp; applies:
 
:$$H(X) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_X(X)}\right ] \hspace{0.1cm}
= -{\rm E} \big [ {\rm log}_2 \hspace{0.1cm}{P_X(X)}\big ] \hspace{0.2cm}
=\hspace{0.2cm} \sum_{\mu = 1}^{|X|} 
 P_X(x_{\mu}) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_X(x_{\mu})} \hspace{0.05cm}.$$

*The&nbsp; &raquo;'''equivocation'''&laquo;&nbsp; $H(X|Y)$&nbsp;  indicates the average information content that an observer who knows exactly about the sink&nbsp; $Y$&nbsp; gains by observing the source&nbsp; $X$&nbsp;:
 
:$$H(X|Y) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{\hspace{0.05cm}X\hspace{-0.01cm}|\hspace{-0.01cm}Y}(X\hspace{-0.01cm} |\hspace{0.03cm} Y)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^{|X|} \sum_{\kappa = 1}^{|Y|} 
 P_{XY}(x_{\mu},\hspace{0.05cm}y_{\kappa}) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{\hspace{0.05cm}X\hspace{-0.01cm}|\hspace{0.03cm}Y}
(\hspace{0.05cm}x_{\mu}\hspace{0.03cm} |\hspace{0.05cm} y_{\kappa})}
 \hspace{0.05cm}.$$

*The equivocation is the portion of the source entropy&nbsp; $H(X)$&nbsp; that is lost due to channel interference&nbsp; (for digital channel: transmission errors).&nbsp; The&nbsp; &raquo;'''mutual information'''&laquo;&nbsp; $I(X; Y)$&nbsp; remains, which reaches the sink:
 
:$$I(X;Y) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_{XY}(X, Y)}{P_X(X) \cdot P_Y(Y)}\right ] \hspace{0.2cm} = H(X) - H(X|Y) \hspace{0.05cm}.$$

*The&nbsp; &raquo;'''irrelevance'''&laquo;&nbsp; $H(Y|X)$&nbsp; indicates the average information content that an observer who knows exactly about the source&nbsp; $X$&nbsp; gains by observing the sink&nbsp; $Y$:
 
:$$H(Y|X) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{\hspace{0.05cm}Y\hspace{-0.01cm}|\hspace{-0.01cm}X}(Y\hspace{-0.01cm} |\hspace{0.03cm} X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^{|X|} \sum_{\kappa = 1}^{|Y|} 
 P_{XY}(x_{\mu},\hspace{0.05cm}y_{\kappa}) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{\hspace{0.05cm}Y\hspace{-0.01cm}|\hspace{0.03cm}X}
(\hspace{0.05cm}y_{\kappa}\hspace{0.03cm} |\hspace{0.05cm} x_{\mu})}
 \hspace{0.05cm}.$$

*The&nbsp; &raquo;'''sink entropy'''&laquo;&nbsp; $H(Y)$, the mean information content of the sink.&nbsp; $H(Y)$&nbsp; is the sum of the useful mutual information&nbsp; $I(X; Y)$&nbsp; and the useless irrelevance&nbsp; $H(Y|X)$, which comes exclusively from channel errors:
  	
:$$H(Y) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_Y(Y)}\right ] \hspace{0.1cm}
= -{\rm E} \big [ {\rm log}_2 \hspace{0.1cm}{P_Y(Y)}\big ] \hspace{0.2cm} =I(X;Y) + H(Y|X) 
 \hspace{0.05cm}.$$
 
==Calculation of the mutual information for the binary channel== 
<br>
These definitions will now be illustrated by an example. &nbsp; We deliberately avoid simplifying the calculations by exploiting symmetries.

[[File:P_ID2782__Inf_T_3_3_S3a.png|right|frame|General model of the binary channel]]
{{GraueBox|TEXT=
$\text{Example 2}$:&nbsp; We consider the general binary channel without memory according to the sketch.&nbsp; Let the falsification probabilities be:
  
:$$\begin{align*}\varepsilon_0  & =  {\rm Pr}(Y\hspace{-0.1cm} = 1\hspace{0.05cm}\vert X \hspace{-0.1cm}= 0) = 0.01\hspace{0.05cm},\\
\varepsilon_1  & = {\rm Pr}(Y\hspace{-0.1cm} = 0\hspace{0.05cm} \vert X \hspace{-0.1cm}= 1) = 0.2\hspace{0.05cm}\end{align*}$$

:$$\Rightarrow \hspace{0.3cm}  P_{\hspace{0.05cm}Y\hspace{-0.01cm} \vert \hspace{-0.01cm}X}(Y\hspace{-0.01cm}  \vert \hspace{-0.01cm} X) = 
\begin{pmatrix} 
		1 - \varepsilon_0  & \varepsilon_0\\
		\varepsilon_1 & 1 - \varepsilon_1
		\end{pmatrix} =
		\begin{pmatrix} 
		0.99  & 0.01\\
		0.2 & 0.8
		\end{pmatrix} \hspace{0.05cm}.$$

Furthermore, we assume source symbols that are not equally probable:
 
:$$P_X(X) = \big ( p_0,\ p_1 \big )=
\big ( 0.1,\ 0.9 \big )
\hspace{0.05cm}.$$

With the&nbsp; [[Information_Theory/Gedächtnislose_Nachrichtenquellen#Binary_entropy_function|$\text{binary entropy function}$]]&nbsp; $H_{\rm bin}(p)$,&nbsp; we thus obtain for the source entropy:
 
:$$H(X) = H_{\rm bin} (0.1) = 0.4690 \hspace{0.12cm}{\rm bit}
\hspace{0.05cm}.$$

For the probability mass function of the sink as well as for the sink entropy we thus obtain:
   
:$$P_Y(Y) = \big [ {\rm Pr}( Y\hspace{-0.1cm} = 0)\hspace{0.05cm}, \ {\rm Pr}( Y \hspace{-0.1cm}= 1) \big ] = \big ( p_0\hspace{0.05cm},\ p_1 \big ) \cdot 
\begin{pmatrix} 
		1 - \varepsilon_0  & \varepsilon_0\\
		\varepsilon_1 & 1 - \varepsilon_1
		\end{pmatrix} $$

:$$\begin{align*}\Rightarrow \hspace{0.3cm}  {\rm Pr}( Y \hspace{-0.1cm}= 0)& =  
p_0 \cdot (1 - \varepsilon_0) + p_1 \cdot \varepsilon_1 =
0.1 \cdot 0.99 + 0.9 \cdot 0.2 = 0.279\hspace{0.05cm},\\
{\rm Pr}( Y \hspace{-0.1cm}= 1) & =  1 - {\rm Pr}( Y \hspace{-0.1cm}= 0) = 0.721\end{align*}$$

:$$\Rightarrow \hspace{0.3cm}
H(Y) = H_{\rm bin} (0.279) = 0.8541 \hspace{0.12cm}{\rm bit}
\hspace{0.05cm}. $$

The joint probabilities&nbsp; $p_{\mu \kappa} = \text{Pr}\big[(X = μ) ∩ (Y = κ)\big]$&nbsp; between source and sink are:
 
:$$\begin{align*}p_{00} & =   p_0 \cdot (1 - \varepsilon_0) = 0.099\hspace{0.05cm},\hspace{0.5cm}p_{01}= p_0 \cdot \varepsilon_0 = 0.001\hspace{0.05cm},\\
p_{10} & =  p_1 \cdot (1 - \varepsilon_1) = 0.180\hspace{0.05cm},\hspace{0.5cm}p_{11}= p_1 \cdot \varepsilon_1 = 0.720\hspace{0.05cm}.\end{align*}$$

From this one obtains for
*the&nbsp; &raquo;'''joint entropy'''&laquo;:
 
:$$H(XY) =  p_{00}\hspace{-0.05cm} \cdot \hspace{-0.05cm}{\rm log}_2 \hspace{0.05cm} \frac{1}{p_{00} \rm } +
p_{01} \hspace{-0.05cm} \cdot \hspace{-0.05cm}{\rm log}_2 \hspace{0.05cm} \frac{1}{p_{01} \rm } +
p_{10}\hspace{-0.05cm} \cdot \hspace{-0.05cm} {\rm log}_2 \hspace{0.05cm} \frac{1}{p_{10} \rm } +
p_{11} \hspace{-0.05cm} \cdot \hspace{-0.05cm} {\rm log}_2\hspace{0.05cm} \frac{1}{p_{11}\rm } = 1.1268\,{\rm bit} \hspace{0.05cm},$$

*the&nbsp; &raquo;'''mutual information'''&laquo;:
 
:$$I(X;Y) = H(X) + H(Y) - H(XY)  = 0.4690 + 0.8541 - 1.1268 = 0.1963\hspace{0.12cm}{\rm bit}
 \hspace{0.05cm},$$

[[File:EN_Inf_T_3_3_S3b_vers2.png|right|frame|Information theoretic model of the binary channel under consideration]]
*the&nbsp; &raquo;'''equivocation'''&laquo;:
 
:$$H(X \vert Y) \hspace{-0.01cm} =\hspace{-0.01cm}  H(X) \hspace{-0.01cm} -\hspace{-0.01cm}  I(X;Y) \hspace{-0.01cm}  $$
:$$\Rightarrow \hspace{0.3cm}  H(X \vert Y) \hspace{-0.01cm}  = \hspace{-0.01cm}  0.4690\hspace{-0.01cm}  -\hspace{-0.01cm}  0.1963\hspace{-0.01cm} =\hspace{-0.01cm}  0.2727\hspace{0.12cm}{\rm bit}
 \hspace{0.05cm},$$

*the &raquo;'''irrelevance'''&laquo;:
 
:$$H(Y \vert X) = H(Y) - I(X;Y) $$
:$$\Rightarrow \hspace{0.3cm}  H(Y \vert X) = 0.8541 - 0.1963 = 0.6578\hspace{0.12cm}{\rm bit}
 \hspace{0.05cm}.$$

The results are summarized in the graph.}}


''Notes'': 
*The equivocation and irrelevance could also have been calculated directly (but with extra effort) from the corresponding probability functions. 
*For example, the irrelevance:
  
:$$H(Y|X) = \hspace{-0.2cm} \sum_{(x, y) \hspace{0.05cm}\in \hspace{0.05cm}XY} \hspace{-0.2cm} P_{XY}(x,\hspace{0.05cm}y) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{\hspace{0.05cm}Y\hspace{-0.01cm}|\hspace{0.03cm}X}
(\hspace{0.05cm}y\hspace{0.03cm} |\hspace{0.05cm} x)}= p_{00} \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1\hspace{-0.08cm} - \hspace{-0.08cm}\varepsilon_0} +
p_{01} \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{\varepsilon_0} +
p_{10} \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1\hspace{-0.08cm} - \hspace{-0.08cm}\varepsilon_1} +
p_{11} \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{\varepsilon_1} = 0.6578\,{\rm bit} \hspace{0.05cm}.$$

==Definition and meaning of channel capacity == 
<br>
We further consider a discrete memoryless channel&nbsp; $\rm (DMC)$&nbsp; with a finite number of source symbols &nbsp; ⇒ &nbsp; $|X|$&nbsp; and also only finitely many sink symbols &nbsp;  ⇒  &nbsp; $|Y|$,&nbsp; as shown in the first section of this chapter.
*If one calculates the mutual information&nbsp; $I(X, Y)$&nbsp; as explained in&nbsp; $\text{Example 2}$,&nbsp;  it also depends on the source statistic   &nbsp;  ⇒  &nbsp;  $P_X(X)$.
* Ergo: &nbsp; '''The mutual information'''&nbsp; $I(X, Y)$&nbsp;''' is not a pure channel characteristic'''.


{{BlaueBox|TEXT=
$\text{Definition:}$&nbsp; The&nbsp; &raquo;'''channel capacity'''&laquo;&nbsp; introduced by&nbsp; [https://en.wikipedia.org/wiki/Claude_Shannon $\text{Claude E. Shannon}$]&nbsp; according to his standard work&nbsp; [Sha48]<ref name = Sha48>Shannon, C.E.:&nbsp; A Mathematical Theory of Communication. In:&nbsp; Bell Syst. Techn. J. 27 (1948), S. 379-423 und S. 623-656.</ref> reads:
 
:$$C = \max_{P_X(X)} \hspace{0.15cm}  I(X;Y)  \hspace{0.05cm}.$$

The additional unit&nbsp; "bit/use"&nbsp; is often added.&nbsp; Since according to this definition the best possible source statistics are always the basis:
*$C$&nbsp; depends only on the channel properties &nbsp; ⇒ &nbsp; $P_{Y \vert X}(Y \vert X)$,
*but not on the source statistics &nbsp; ⇒ &nbsp; $P_X(X)$.&nbsp; }}


Shannon needed the quantity&nbsp; $C$&nbsp; to formulate the&nbsp; "Channel Coding Theorem" – one of the highlights of the information theory he founded.

{{BlaueBox|TEXT=
$\text{Shannon's Channel Coding Theorem: }$&nbsp; 
*For every transmission channel with channel capacity&nbsp; $C > 0$,&nbsp; there exists (at least) one&nbsp; $(k,\ n)$–block code,&nbsp; whose (block) error probability approaches zero&nbsp; as long as the code rate&nbsp; $R = k/n$&nbsp; is less than or equal to the channel capacity: &nbsp; 
:$$R ≤ C.$$
*The prerequisite for this, however,&nbsp;  is that the following applies to the block length of this code: &nbsp; $n → ∞.$}}


The proof of this theorem,&nbsp; which is beyond the scope of our learning tutorial,&nbsp; can be found for example in&nbsp; [CT06]<ref name="CT06">Cover, T.M.; Thomas, J.A.:&nbsp; Elements of Information Theory.&nbsp; West Sussex: John Wiley & Sons, 2nd Edition, 2006.</ref>,&nbsp;  [Kra13]<ref name="Kra13">Kramer, G.:&nbsp; Information Theory.&nbsp; Lecture manuscript, Chair of Communications Engineering, Technische Universität München, 2013.</ref>&nbsp; and&nbsp; [Meck09]<ref name="Meck09">Mecking, M.:&nbsp; Information Theory.&nbsp; Lecture manuscript, Chair of Communications Engineering, Technische Universität München, 2009.</ref>. 

As will be shown in&nbsp; [[Aufgaben:Exercise_3.13:_Code_Rate_and_Reliability|"Exercise 3.13"]],&nbsp; the reverse is also true.&nbsp; This proof can also be found in the literature references just mentioned.
 
{{BlaueBox|TEXT=
$\text{Reverse of Shannon's channel coding theorem: }$&nbsp;
 
If the rate&nbsp;  $R$&nbsp; of the&nbsp; $(n,\ k)$–block code used is greater than the channel capacity&nbsp; $C$,&nbsp; then an arbitrarily small block error probability is not achievable.}}


In the chapter&nbsp;  [[Information_Theory/AWGN_Channel_Capacity_for_Discrete_Input#AWGN_model_for_discrete-time_band-limited_signals|"AWGN model for discrete-time band-limited signals"]]&nbsp; it is explained in connection with the continuous&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_binary_input|$\text{AWGN channel model}$]]&nbsp; &nbsp; what phenomenally great significance Shannon's theorem has for the entire field of information technology,&nbsp; not only for those interested exclusively in theory,&nbsp; but also for practitioners.

 	 
==Channel capacity of a binary channel==  	
<br>
[[File:P_ID2786__Inf_T_3_3_S3a.png|right|frame|General model of the binary channel]]
The mutual information of the general&nbsp; (asymmetrical)&nbsp; binary channel according to this sketch was calculated in&nbsp; [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung#Transinformationsberechnung_f.C3.BCr_den_Bin.C3.A4rkanal|$\text{Example 2}$]].&nbsp;  In this model, the input symbols&nbsp; $0$&nbsp; and&nbsp; $1$&nbsp; are distorted to different degrees:
 
:$$P_{\hspace{0.05cm}Y\hspace{-0.01cm}|\hspace{-0.01cm}X}(Y\hspace{-0.01cm} |\hspace{-0.01cm} X) = 
\begin{pmatrix} 
		1 - \varepsilon_0  & \varepsilon_0\\
		\varepsilon_1 & 1 - \varepsilon_1
		\end{pmatrix}  \hspace{0.05cm}.$$

The mutual information can be represented with the probability mass function&nbsp; $P_X(X) = (p_0,\ p_1)$&nbsp; as follows:
 
:$$I(X  ;Y) =  \sum_{\mu = 1}^{2} \hspace{0.1cm}\sum_{\kappa = 1}^{2} \hspace{0.2cm}
 {\rm Pr} (\hspace{0.05cm}y_{\kappa}\hspace{0.03cm} |\hspace{0.05cm} x_{\mu}) \cdot 
{\rm Pr} (\hspace{0.05cm}x_{\mu}\hspace{0.05cm})\cdot {\rm log}_2 \hspace{0.1cm} \frac{{\rm Pr}
(\hspace{0.05cm}y_{\kappa}\hspace{0.03cm} |\hspace{0.05cm} x_{\mu})}{{\rm Pr}
(\hspace{0.05cm}y_{\kappa})} $$
:$$\begin{align*}\Rightarrow \hspace{0.3cm}  I(X  ;Y) &=    \hspace{-0.01cm}  (1  \hspace{-0.08cm}- \hspace{-0.08cm}\varepsilon_0) \cdot p_0 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1  \hspace{-0.08cm}- \hspace{-0.08cm}\varepsilon_0}{(1  \hspace{-0.08cm}- \hspace{-0.08cm}\varepsilon_0) \cdot p_0 + \varepsilon_1 \cdot p_1} +
\varepsilon_0 \cdot p_0 \cdot {\rm log}_2 \hspace{0.1cm} \frac{\varepsilon_0}{(1  \hspace{-0.08cm}- \hspace{-0.08cm}\varepsilon_0) \cdot p_0 + \varepsilon_1 \cdot p_1} \ + \\
& +  \hspace{-0.01cm} \varepsilon_1 \cdot p_1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{\varepsilon_1}{\varepsilon_0 \cdot p_0 + (1  \hspace{-0.08cm}- \hspace{-0.08cm}\varepsilon_1) \cdot p_1} +  (1  \hspace{-0.08cm}- \hspace{-0.08cm}\varepsilon_1) \cdot p_1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1  \hspace{-0.08cm}- \hspace{-0.08cm}\varepsilon_1}{\varepsilon_0 \cdot p_0 + (1  \hspace{-0.08cm}- \hspace{-0.08cm}\varepsilon_1) \cdot p_1}
 \hspace{0.05cm}.\end{align*}$$

[[File:EN_Inf_T_3_3_S4a.png|right|frame|Mutual information for the <br>"asymmetrical binary channel"]]
{{GraueBox|TEXT=
$\text{Example 3}$:&nbsp; 
In the following we set&nbsp; $ε_0 = 0.01$&nbsp; and&nbsp; $ε_1 = 0.2$. 

Column 4 of the adjacent table shows&nbsp; (highlighted in green)&nbsp; the mutual information&nbsp; $I(X; Y)$&nbsp; of this asymmetrical binary channel depending on the source symbol probability&nbsp; $p_0 = {\rm Pr}(X = 0)$&nbsp; .&nbsp; One can see:
*The mutual information depends on the symbol probabilities&nbsp; $p_0$&nbsp; and&nbsp; $p_1 = 1 - p_0$.
*Here the maximum value of&nbsp; $I(X; Y)$&nbsp;  results in &nbsp;$p_0 ≈ 0.55$&nbsp;  &nbsp; ⇒  &nbsp; &nbsp;$p_1 ≈ 0.45$.
*The result&nbsp; $p_0 > p_1$&nbsp; follows from the relation&nbsp; $ε_0 < ε_1$&nbsp; (the&nbsp; "zero"&nbsp; is less distorted).
*The capacity of this channel is&nbsp; $C = 0.5779 \ \rm bit/use$.}}
<br clear=all>
In the above equation, the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|$\text{Binary Symmetric Channel}$]]&nbsp; $\rm (BSC)$&nbsp; with parameters&nbsp; $ε = ε_0 = ε_1$&nbsp; is also included as a special case.&nbsp; Hints: 
*In&nbsp; [[Aufgaben:Exercise_3.10:_Mutual_Information_at_the_BSC|"Exercise 3.10"]]&nbsp; the mutual information of the BSC is calculated for the system parameters&nbsp; $ε = 0.1$ &nbsp;and&nbsp; $p_0 = 0.2$&nbsp; .
*In&nbsp;  [[Aufgaben:Exercise_3.10Z:_BSC_Channel_Capacity|"Exercise 3.10Z"]]&nbsp; its channel capacity is given as follows:
  	 
:$$C_{\rm BSC} = 1 - H_{\rm bin} (\varepsilon) \hspace{0.05cm}.$$

==Properties of symmetrical channels == 
<br>
The capacity calculation of the (general)&nbsp; [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung#Information-theoretical_model_of_digital_signal_transmission|$\text{discrete memoryless channel}$]]&nbsp; $\rm (DMC)$&nbsp; is often complex.&nbsp; It simplifies decisively if symmetries of the channel are exploited. &nbsp; 

[[File:EN_Inf_T_3_3_S6a_vers2.png|right|frame|Examples of symmetrical channels]]

<br>The diagram shows two examples:

*In the case of the&nbsp; <u>uniformly dispersive channel</u>&nbsp; all source symbols&nbsp; $x ∈ X$&nbsp; result in exactly the same set of transition probabilities  &nbsp; ⇒  &nbsp;  $\{P_{Y\hspace{0.03cm}|\hspace{0.01cm}X}(y_κ\hspace{0.05cm}|\hspace{0.05cm}x)\}$&nbsp; with &nbsp;$1 ≤ κ ≤ |Y|$.&nbsp; Here &nbsp;$q + r + s = 1$&nbsp; must always apply here&nbsp; (see left graph).

*In the case of the&nbsp; <u>uniformly focusing channel</u>&nbsp;, the same set of transition probabilities&nbsp; ⇒  &nbsp; $\{P_{Y\hspace{0.03cm}|\hspace{0.01cm}X}(y\hspace{0.05cm}|\hspace{0.05cm}x_μ)\}$&nbsp; with &nbsp;$1 ≤ μ ≤ |X|$ results for all sink symbols&nbsp; $y ∈ Y$&nbsp;. &nbsp; Here, &nbsp;$t + u + v = 1$&nbsp; need <u>not</u> necessarily hold&nbsp; (see right graph).
<br clear=all>
{{BlaueBox|TEXT=
$\text{Definition:}$&nbsp; If a discrete memoryless channel is both uniformly dispersive and uniformly focusing,&nbsp; it is a&nbsp; &raquo;'''strictly symmetric channel'''&laquo;.&nbsp; 
*With an equally distributed source alphabet, this channel has the capacity 
:$$C = {\rm log}_2 \hspace{0.1cm} \vert Y \vert  + \sum_{y \hspace{0.05cm}\in\hspace{0.05cm} Y} \hspace{0.1cm} P_{\hspace{0.03cm}Y \vert \hspace{0.01cm} X}(y\hspace{0.05cm} \vert \hspace{0.05cm}x) \cdot
{\rm log}_2 \hspace{0.1cm}P_{\hspace{0.01cm}Y \vert  \hspace{0.01cm} X}(y\hspace{0.05cm}\vert\hspace{0.05cm} x)
 \hspace{0.05cm}.$$
*Any&nbsp; $x ∈ X$&nbsp; can be used for this equation.}}


This definition will now be clarified by an example.

{{GraueBox|TEXT=
$\text{Example 4}$:&nbsp; In the channel under consideration, there are connections between all&nbsp; $ \vert X \vert  = 3$&nbsp; inputs and all&nbsp; $ \vert Y \vert  = 3$&nbsp; outputs:
[[File:P_ID2794__Inf_T_3_3_S6b.png|right|frame|Strongly symmetrical channel&nbsp; $\vert X \vert = \vert Y \vert= 3$]]
*A red connection stands for&nbsp; $P_{Y \hspace{0.03cm}\vert\hspace{0.01cm} X}(y_κ \hspace{0.05cm} \vert \hspace{0.05cm} x_μ) = 0.7$.
*A blue connection stands for&nbsp; $P_{Y \hspace{0.03cm}\vert\hspace{0.01cm} X}(y_κ \hspace{0.05cm}\vert \hspace{0.05cm} x_μ) = 0.2$.
*A green connection stands for&nbsp; $P_{Y \hspace{0.03cm}\vert\hspace{0.01cm} X}(y_κ \hspace{0.05cm}\vert\hspace{0.05cm} x_μ) = 0.1$.


According to the above equation, the following applies to the channel capacity:
 
:$$C = {\rm log}_2 \hspace{0.1cm} (3) + 0.7 \cdot {\rm log}_2 \hspace{0.1cm} (0.7) 
+ 0.2 \cdot {\rm log}_2 \hspace{0.1cm} (0.2) + 0.1 \cdot {\rm log}_2 \hspace{0.1cm} (0.1) = 0.4282 \,\,{\rm bit} \hspace{0.05cm}.$$

Notes: 
*The addition of&nbsp; "the same set of transition probabilities”&nbsp; in the above definitions does not mean that it must apply: 
:$$P_{Y \hspace{0.03cm}\vert\hspace{0.01cm} X}(y_κ  \hspace{0.05cm}\vert\hspace{0.05cm} x_1) = P_{Y \hspace{0.03cm}\vert\hspace{0.01cm} X}(y_κ  \hspace{0.05cm}\vert\hspace{0.05cm} x_2) = P_{Y \hspace{0.03cm}\vert\hspace{0.01cm} X}(y_κ \hspace{0.05cm}\vert\hspace{0.05cm} x_3).$$ 
*Rather, here a red, a blue and a green arrow leaves from each input and a red, a blue and a green arrow arrives at each output. 
*The respective sequences permute: &nbsp; R – G – B, &nbsp; &nbsp;  B – R – G, &nbsp; &nbsp; G – B – R.}}


An example of a strictly symmetrical channel is the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|$\text{Binary Symmetric Channel}$]]&nbsp; $\rm (BSC)$.&nbsp; In contrast, the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC|$\text{Binary Erasure Channel}$]]&nbsp; $\rm (BEC)$&nbsp;  is not strictly symmetric,&nbsp; because,
*although it is uniformly dispersive,
*but it is not uniformly focusing.


The following definition is less restrictive than the previous one of a strictly symmetric channel.

{{BlaueBox|TEXT=
$\text{Definition:}$&nbsp; A&nbsp; &raquo;'''symmetric channel'''&laquo;&nbsp; exists,
*if it can be divided into several&nbsp; $($generally $L)$&nbsp; strongly symmetrical sub-channels,
*by splitting the output alphabet&nbsp; $Y$&nbsp; into&nbsp; $L$&nbsp; subsets&nbsp; $Y_1$, ... , $Y_L$&nbsp;.


Such a&nbsp; "symmetric channel"&nbsp; has the following capacity:
 
:$$C = \sum_{l \hspace{0.05cm}=\hspace{0.05cm} 1}^{L} \hspace{0.1cm} p_{\hspace{0.03cm}l} \cdot C_{\hspace{0.03cm}l} \hspace{0.05cm}.$$

The following designations are used here:
* $p_{\hspace{0.03cm}l}$&nbsp;indicates the probability that the&nbsp; $l$–th  sub-channel is selected.
* $C_{\hspace{0.03cm}l}$&nbsp; is the channel capacity of this&nbsp; $l$–th sub-channel.}}


[[File:EN_Inf_T_3_3_S6c_v2.png|right|frame|Symmetrical channel consisting of two strongly symmetrical <br>sub-channels&nbsp;  $\rm A$&nbsp; and&nbsp; $\rm B$]]
The diagram illustrates this definition for&nbsp; $L = 2$&nbsp; with the sub-channels&nbsp; $\rm A$&nbsp; and&nbsp; $\rm B$.
*The differently drawn transitions&nbsp; (dashed or dotted)&nbsp; show that the two sub-channels can be different,&nbsp; so that&nbsp; $C_{\rm A} ≠ C_{\rm B}$&nbsp; will generally apply.
*For the capacity of the total channel one thus obtains in general:
 
:$$C = p_{\rm A} \cdot C_{\rm A} +  p_{\rm B} \cdot C_{\rm B}  \hspace{0.05cm}.$$

*No statement is made here about the structure of the two sub-channels.


The following example will show that the&nbsp; "Binary Erasure Channel"&nbsp; $\rm (BEC)$&nbsp; can also be described in principle by this diagram.  &nbsp; However, the two output symbols&nbsp; $y_3$&nbsp; and&nbsp; $y_4$&nbsp; must then be combined into a single symbol.
<br clear=all>
[[File:EN_Inf_T_3_3_S6d.png|right|frame|$\rm BEC$&nbsp; in two different representations]]
{{GraueBox|TEXT=
$\text{Example 5}$:&nbsp; The left figure shows the usual representation of the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC|$\text{Binary Erasure Channel}$]]&nbsp; $\rm (BEC)$&nbsp; with input&nbsp; $X = \{0,\ 1\}$&nbsp; and output&nbsp; $Y = \{0,\ 1,\ \text{E} \}$. 

If one divides this according to the right grafic into
*an&nbsp; "ideal channel"&nbsp; $(y = x)$&nbsp; for
:$$y ∈ Y_{\rm A} = \{0, 1\} \ \ ⇒  \ \ C_{\rm A} = 1 \ \rm bit/use,$$
*an&nbsp; "erasure channel"&nbsp; $(y = {\rm E})$&nbsp; for
:$$y ∈ Y_{\rm B} = \{\rm E \} \ \ ⇒  \ \ C_{\rm B} = 0,$$

then we get with the sub-channel weights&nbsp; $p_{\rm A} = 1 – λ$&nbsp; and&nbsp; $p_{\rm B} = λ$:
 
:$$C_{\rm BEC} = p_{\rm A} \cdot C_{\rm A} = 1 - \lambda \hspace{0.05cm}.$$

Both channels are strongly symmetrical. &nbsp; The following applies equally for the (ideal) channel&nbsp; $\rm A$&nbsp;
*for&nbsp; $X = 0$&nbsp; and&nbsp; $X = 1$: &nbsp; &nbsp;   $\text{Pr}(Y = 0 \hspace{0.05cm}\vert \hspace{0.05cm} X) = \text{Pr}(Y = 1 \hspace{0.05cm} \vert\hspace{0.05cm} X) = 1 - λ$  &nbsp;  ⇒  &nbsp;  uniformly dispersive,
*for&nbsp; $Y = 0$ &nbsp;and&nbsp;&nbsp; $Y = 1$: &nbsp;  &nbsp;   $\text{Pr}(Y  \hspace{0.05cm} \vert \hspace{0.05cm} X= 0) = Pr(Y \hspace{0.05cm}\vert\hspace{0.05cm} X = 1) = 1 - λ$  &nbsp; ⇒  &nbsp;  uniformly focusing.


The same applies to the erasure channel&nbsp; $\rm B$.}}


In&nbsp; [[Aufgaben:Exercise_3.12:_Strictly_Symmetrical_Channels|"Exercise 3.12"]]&nbsp; it will be shown that the capacity of the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Error_.26_Erasure_Channel_.E2.80.93_BSEC|$\text{Binary Symmetric Error & Erasure Channel}$]]&nbsp; $\rm (BSEC)$&nbsp; model can be calculated in the same way.&nbsp; One obtains:

:$$C_{\rm BSEC}  = (1- \lambda) \cdot \left [ 1 - H_{\rm bin}(\frac{\varepsilon}{1- \lambda}) \right ]$$

*with the crossover probability&nbsp; $ε$ 
*and the erasure probability&nbsp; $λ$.



==Some basics of channel coding == 	 
<br>
In order to interpret the channel coding theorem correctly, some basics of&nbsp; &raquo;'''channel coding'''&laquo;.&nbsp;  This extremely important area of Communications Engineering is covered in our learning tutorial&nbsp; $\rm LNTwww$&nbsp; in a separate book called&nbsp;  [[Channel_Coding|"Channel Coding"]].

[[File:EN_Inf_T_3_3_S7a.png|center|frame|Model for binary&ndash;coded communication]]

The following description refers to the highly simplified model for&nbsp; [[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes|$\text{binary block codes}$]]:
*The infinitely long source symbol sequence&nbsp; $\underline{u}$&nbsp; (not shown here)&nbsp; is divided into blocks of&nbsp; $k$&nbsp; bits.&nbsp; We denote the information block with the serial number&nbsp; $j$&nbsp; by&nbsp; $\underline{u}_j^{(k)}$.
*Each information block&nbsp; $\underline{u}_j^{(k)}$&nbsp; is converted into a code word&nbsp; $\underline{x}_j^{(n)}$&nbsp; by the channel encoder with a yellow background, where&nbsp; $n > k$&nbsp; is to apply.&nbsp; The ratio&nbsp; $R = k/n$&nbsp; is called the&nbsp; &raquo;'''code rate'''&laquo;.
*The&nbsp; "Discrete Memoryless Channel"&nbsp; $\rm (DMC)$&nbsp;  is taken into account by transition probabilities&nbsp; $P_{Y\hspace{0.03cm}|\hspace{0.03cm}X}(⋅)$&nbsp;.&nbsp; This block with a green background causes errors at the bit level.&nbsp; The following can therefore apply:  &nbsp; $y_{j, \hspace{0.03cm}i} ≠ x_{j,\hspace{0.03cm} i}$.
*Thus the received blocks&nbsp; $\underline{y}_j^{(n)}$&nbsp; consisting of &nbsp; $n$&nbsp; bits can also differ from the code words&nbsp; $\underline{x}_j^{(n)}$ .&nbsp; Likewise, the following generally applies to the blocks after the decoder:&nbsp;
:$$\underline{v}_j^{(k)} ≠ \underline{u}_j^{(k)}.$$


{{GraueBox|TEXT=
$\text{Example 6}$:&nbsp; 
The diagram is intended to illustrate the nomenclature used here using the example of&nbsp;  $k = 3$ &nbsp;and&nbsp; $n = 4$.&nbsp; The first eight blocks of the information sequence&nbsp; $\underline{u}$&nbsp; and the&nbsp; encoded sequence $\underline{x}$ are shown. 

[[File:EN_Inf_T_3_3_S7b_vers2.png|right|frame|Bit designation of information block and code word]]
One can see the following assignment between the blocked and the unblocked description:
*Bit 3 of the 1st information block &nbsp; ⇒ &nbsp; $u_{1,\hspace{0.08cm} 3}$&nbsp; corresponds to the symbol&nbsp; $u_3$&nbsp; in unblocked representation.
*Bit 1 of the 2nd information block &nbsp; ⇒ &nbsp; $u_{2, \hspace{0.08cm}1}$&nbsp; corresponds to the symbol&nbsp; $u_4$&nbsp; in unblocked representation.
*Bit 2 of the 6th information block &nbsp; ⇒ &nbsp; $u_{6, \hspace{0.08cm}2}$&nbsp; corresponds to the symbol&nbsp; $u_{17}$&nbsp; in unblocked representation.
*Bit 4 of the 1st code word &nbsp; ⇒ &nbsp; $x_{1, \hspace{0.08cm}4}$&nbsp; corresponds to the symbol&nbsp; $x_4$&nbsp; in unblocked representation.
*Bit 1 of the 2nd code word &nbsp; ⇒ &nbsp; $x_{2, \hspace{0.08cm}1}$&nbsp; corresponds to the symbol&nbsp; $x_5$&nbsp; in unblocked representation.
*Bit 2 of the 6th code word &nbsp; ⇒ &nbsp; $x_{6, \hspace{0.08cm}2}$&nbsp; corresponds to the symbol&nbsp; $x_{22}$&nbsp; in unblocked representation.}}

==Relationship between block errors and bit errors==
<br>
To interpret the channel coding theorem, we still need various definitions for error probabilities.&nbsp; Various descriptive variables can be derived from the above system model:

{{BlaueBox|TEXT=
$\text{Definitions:}$
*In the present channel model, the&nbsp; $\text{channel error probability}$&nbsp; is given by
 
:$$\text{Pr(channel error)} = {\rm Pr} \left ({y}_{j,\hspace{0.05cm} i} \ne {x}_{j,\hspace{0.05cm} i}
\right )\hspace{0.05cm}.$$

:For example, in the BSC model&nbsp;  $\text{Pr(channel error)} = ε$&nbsp;  für alle&nbsp; $j = 1, 2$, ... &nbsp;and&nbsp; $1 ≤ i ≤ n$.
*The&nbsp; $\text{block error probability}$&nbsp; refers to the allocated information blocks at the encoder input &nbsp; ⇒  &nbsp; $\underline{u}_j^{(k)}$&nbsp; and the decoder output  &nbsp; ⇒   &nbsp; $\underline{v}_j^{(k)}$,&nbsp; each in blocks of&nbsp; $k$&nbsp; bits:
 
:$$\text{Pr(block error)} = {\rm Pr} \left (\underline{\upsilon}_j^{(k)} \ne \underline{u}_j^{(k)}
\right )\hspace{0.05cm}.$$

*The&nbsp; $\text{bit error probability}$&nbsp; also refers to the input and the output of the entire coding system under consideration, but at the bit level:
 
:$$\text{Pr(bit error)} = {\rm Pr} \left ({\upsilon}_{j,\hspace{0.05cm} i} \ne {u}_{j,\hspace{0.05cm} i}
\right )\hspace{0.05cm}.$$

:For simplicity, it is assumed here that all&nbsp; $k$&nbsp; bits&nbsp; $u_{j,\hspace{0.08cm}i}$&nbsp;  $(1 ≤ i ≤ k)$&nbsp; of the information block&nbsp; $j$&nbsp; are falsified with equal probability. 
:Otherwise, the&nbsp; $k$&nbsp; bits would have to be averaged.}}


There is a general relationship between the block error probability and the bit error probability:
 
:$${1}/{k} \cdot \text{Pr(block error)} \le \text{Pr(bit error)} \le \text{Pr(block error)} 
 \hspace{0.05cm}.$$

*The lower bound results when all bits are wrong in all faulty blocks.
*If there is exactly only one bit error in each faulty block, then the bit error probability   is identical to the block error probability:
:$$ \text{Pr(bit error)} \equiv \text{Pr(block error)}  \hspace{0.05cm}.$$

[[File:EN_Inf_T_3_3_S7c.png|frame|Definition of different error probabilities]]
{{GraueBox|TEXT=
$\text{Example 7:}$&nbsp; The upper graph shows the first eight  received blocks&nbsp; $\underline{y}_j^{(n)}$&nbsp; with&nbsp; $n = 4$&nbsp; bits each.&nbsp;  Here channel errors are shaded green. 

Below, the initial sequence&nbsp; $\underline{v}$&nbsp; after decoding is sketched, divided into blocks&nbsp; $\underline{v}_j^{(k)}$&nbsp; with&nbsp; $k = 3$&nbsp; bits each. Note:

*Bit errors are shaded red in the lower diagram.
*Block errors can be recognized by the blue frame.


For this, some&nbsp; (due to the short sequence)&nbsp; only very vague information about the error probabilities:
*Half of the received bits are shaded green.&nbsp; From this follows:  &nbsp; 
:$$\text{Pr(channel error)} = 16/32 = 1/2.$$

*The bit error probability with the exemplary encoding and decoding is:   &nbsp; 
:$$\text{Pr(bit error)} = 8/24 = 1/3.$$

*In contrast, with uncoded transmission would be: &nbsp; 
:$$\text{Pr(bit error)} = \text{Pr(channel error)}  = 1/2.$$

*Half of the decoded blocks are outlined in blue. From this follows:   &nbsp; 
:$$\text{Pr(block error)} = 4/8 = 1/2.$$

*With &nbsp;$\text{Pr(block error)}= 1/2$&nbsp; and &nbsp;$k = 3$&nbsp; the bit error probability is in the following range:   &nbsp; 
:$$1/6  \le \text{Pr(bit error)} \le 1/2 
 \hspace{0.05cm}.$$

#The upper bound with respect to bit errors is obtained when all bits in each of the four falsified blocks are wrong:    &nbsp;  $\text{Pr(bit error)} = 12/24 = 1/2.$
#The lower bound indicates that only one bit is wrong in each of the four falsified blocks:  &nbsp;    $\text{Pr(bit error)} = 4/24 = 1/6$.}}


==Rate, channel capacity and bit error probability==  
<br>
{{BlaueBox|TEXT=
$\text{Basically:}$&nbsp;
*Channel coding increases the reliability of data transmission from the source to the sink. 
*If the code rate&nbsp; $R = k/n$&nbsp; is reduced and the added redundancy&nbsp; $(1 - R)$&nbsp; is increased, the data reliability is generally improved and the bit error probability is reduced, which we will refer to as&nbsp; $p_{\rm B}$&nbsp; in the following:
 
:$$p_{\rm B} = \text{Pr(bit error)} = {\rm Pr} \left ({\upsilon}_{j,\hspace{0.05cm} i} \ne {u}_{j,\hspace{0.05cm} i}
\right )\hspace{0.05cm}.$$}}


The following theorem is based on the&nbsp; "Data Processing Theorem"&nbsp; and&nbsp; "Fano's Lemma".&nbsp; The derivation can be found in standard works on information theory, for example in&nbsp; [CT06]<ref name="CT06" />:

{{BlaueBox|TEXT=
$\text{Inversion of Shannon's Channel Coding Theorem:}$&nbsp;
 
If one uses a channel with too small a capacity&nbsp; $R$&nbsp; for data transmission at rate&nbsp; $C < R$, the bit error probability&nbsp; $p_{\rm B}$&nbsp;   cannot fall below a lower bound even with the best possible channel coding:
 
:$$p_{\rm B} \ge H_{\rm bin}^{-1} \cdot \left ( 1 - {C}/{R}\right ) > 0\hspace{0.05cm}.$$

Here&nbsp; $H_{\rm bin}(⋅)$&nbsp; denotes the&nbsp; [[Information_Theory/Discrete_Memoryless_Sources#Binary_entropy_function|$\text{binary entropy function}$]].}}


Since the probability of the block errors can never be smaller than that of the bit errors,&nbsp; the block error probability "zero" is also not possible for&nbsp; $R > C$&nbsp;.&nbsp; <br>From the given bounds for the bit errors,
 
:$$ {1}/{k} \cdot {\rm Pr}({\rm block\ error}) \le  {\rm Pr}({\rm bit\ error}) \le   {\rm Pr}({\rm block\ error})\hspace{0.05cm},$$

a range for the block error probability can also be given:
 
:$$ {\rm Pr}({\rm bit\ error})  \le   {\rm Pr}({\rm block\ error}) \le  k \cdot  {\rm Pr}({\rm bit\ error})\hspace{0.05cm}.$$

{{GraueBox|TEXT=
$\text{Example 8:}$&nbsp; For a channel with capacity&nbsp; $C = 1/3$&nbsp; (bit), error-free data transmission &nbsp; $(p_{\rm B} = 0)$&nbsp; with code rate&nbsp; $R < 1/3$&nbsp; is possible in principle.  
*However, from the channel coding theorem the special&nbsp; $(k$,&nbsp;  $n)$–block code is not known which makes this desired result possible. &nbsp;  Shannon also makes no statements on this.
*All that is known is that such a best possible code works with blocks of infinite length.&nbsp; For a given code rate&nbsp; $R = k/n$&nbsp; both&nbsp; $k → ∞$&nbsp; and&nbsp; $n → ∞$ thus apply.
*The statement&nbsp; "The bit error probability is zero"&nbsp; is not the same as&nbsp; "No bit errors occur": &nbsp; Even with a finite number of bit errors and&nbsp; $k → ∞$&nbsp; &rArr;  &nbsp; $p_{\rm B} = 0$.


With the code rate&nbsp; $R = 1  > C$&nbsp; (uncoded transmission) one obtains:
 
:$$p_{\rm B} \ge H_{\rm bin}^{-1} \cdot \left ( 1 - \frac{1/3}{1}\right ) 
= H_{\rm bin}^{-1}(2/3) \approx 0.174 
> 0\hspace{0.05cm}.$$

With the code rate&nbsp; $R = 1/2 > C$&nbsp;, the bit error probability is smaller&nbsp; but also different from zero:
 
:$$p_{\rm B} \ge H_{\rm bin}^{-1} \cdot \left ( 1 - \frac{1/3}{1/2}\right ) 
= H_{\rm bin}^{-1}(1/3) \approx 0.062 
> 0\hspace{0.05cm}.$$}}	 

	 
==Exercises for the chapter==
<br>
[[Aufgaben:Exercise_3.10:_Mutual_Information_at_the_BSC|Exercise 3.10: Mutual Information at the BSC]]

[[Aufgaben:Exercise_3.10Z:_BSC_Channel_Capacity|Exercise 3.10Z: BSC Channel Capacity]]

[[Aufgaben:Exercise_3.11:_Erasure_Channel|Exercise 3.11: Erasure Channel]]

[[Aufgaben:Exercise_3.11Z:_Extremely_Asymmetrical_Channel|Exercise 3.11Z: Extremely Asymmetrical Channel]]

[[Aufgaben:Exercise_3.12:_Strictly_Symmetrical_Channels|Exercise 3.12: Strictly Symmetrical Channels]]

[[Aufgaben:Exercise_3.13:_Code_Rate_and_Reliability|Exercise 3.13: Code Rate and Reliability]]

[[Aufgaben:Exercise_3.14:_Channel_Coding_Theorem|Exercise 3.14: Channel Coding Theorem]]

[[Aufgaben:Exercise_3.15:_Data_Processing_Theorem|Exercise 3.15: Data Processing Theorem]]


	 
==References==
<references/>
{{Display}}