Contents
- 1 Information-theoretical model of digital signal transmission
- 2 Directional diagram for digital signal transmission
- 3 Calculation of the mutual information for the binary channel
- 4 Definition and meaning of channel capacity
- 5 Channel capacity of a binary channel
- 6 Properties of symmetrical channels
- 7 Einige Grundlagen der Kanalcodierung
- 8 Zusammenhang zwischen Blockfehlern und Bitfehlern
- 9 Rate, Kanalkapazität und Bitfehlerwahrscheinlichkeit
- 10 Aufgaben zum Kapitel
- 11 Quellenverzeichnis
Information-theoretical model of digital signal transmission
The entropies defined so far in general terms are now applied to digital signal transmission, whereby we assume a discrete memoryless channel (DMC) according to the graphic:
- The set of possible source symbols is characterised by the discrete random variable $X$ , where $|X|$ indicates the source symbol range:
- $$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, $Y$ characterises the set of sink symbols with the symbol range $|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 $|Y| = |X|$is valid. Also possible is $|Y| > |X|$, for example with the Binary Erasure Channel (BEC) with $X = \{0,\ 1\}$, $Y = \{0,\ 1,\ \ \text{E}\}$ ⇒ $|X| = 2$, $|Y| = 3$.
- The sink symbol $\rm E$ indicates an erasure. The event $Y=\text{E}$ indicates that a decision for $0$ or for $1$ would be too uncertain.
- The symbol probabilities of the source and sink are accounted for in the graph by the probability functions $P_X(X)$ and $P_Y(Y)$ , where:
- $$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: $P_X(X)$ and $P_Y(Y)$ contain no zeros ⇒ $\text{supp}(P_X) = P_X$ and $\text{supp}(P_Y) = P_Y$.
This precondition facilitates the model description without loss of generality. - All transition probabilities of the discrete memoryless channel $\rm (DMC)$ are captured by the conditional probability function $P_{Y|X}(Y|X)$ .
Mit $x_μ ∈ X$ and $y_κ ∈ Y$ , 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 $P_{Y|X}(⋅)$ with $|X|$ inputs and $|Y|$ outputs. Blue connections mark transition probabilities $\text{Pr}(y_i | x_μ)$ starting from $x_μ$ with $1 ≤ i ≤ |Y|$, while all red connections end at $y_κ$: $\text{Pr}(y_κ | x_i)$ with $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.
$\text{Example 1}$: In the book „Channel Coding” we also deal with the Binary Erasure Channel $\rm (BEC)$, which is sketched in a somewhat modified form on the right. The following prerequisites apply:
- Let the input alphabet be binary ⇒ $X = \{0,\ 1 \}$ ⇒ $\vert X\vert = 2$while three values are possible at the output ⇒ $Y = \{0,\ 1,\ \text{E} \}$ ⇒ $\vert Y\vert = 3$.
- The symbol $\text{E}$ indicates the case that the receiver cannot decide for one of the binary symbols $0$ or $1$ due to too much channel interference. „E” stands for erasure.
- With the $\rm BEC$ according to the above sketch, both a transmitted $0$ and a $1$ are erased with probability $λ$ while the probability of a correct transmission is $1 – λ$ in each case.
- In contrast, transmission errors are excluded by the BEC model
⇒ the conditional probabilities $\text{Pr}(Y = 1 \vert X = 0)$ and $\text{Pr}(Y = 0 \vert X = 1)$ are both zero.
At the transmitter, the zeros and ones would not necessarily be equally probable. Rather, we use the probability 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 $P_X(X)$ and $P_Y(Y)$ 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 $\text{Pr}(y_κ\vert x_μ)$ 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)$ and $P_Y(Y)$ are not vectors in the true sense and $P_{Y \vert X}(Y\vert X)$ is not a matrix either.
Directional diagram for digital signal transmission
All entropies defined in the last chapter also apply to digital signal transmission. 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 $X$ to sink $Y$ is recognisable.
Let us now interpret the right graph starting from the general DMC channel model :
- The source entropy $H(X)$ denotes the average information content of the source symbol sequence. With the symbol range $|X|$ 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 equivocation $H(X|Y)$ indicates the average information content that an observer who knows exactly about sink $Y$ gains by observing source $X$ :
- $$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 $H(X)$ that is lost due to channel interference (for digital channel: transmission errors) . The mutual information $I(X; Y)$ 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 irrelevance $H(Y|X)$ indicates the average information content that an observer who knows exactly about the source $X$ gains by observing the sink $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 sink entropy $H(Y)$, the mean information content of the sink, is the sum of the useful mutual information $I(X; Y)$ and the irrelevance $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
These definitions will now be illustrated by an example. We deliberately avoid simplifying the calculations by exploiting symmetries.
$\text{Example 2}$: We consider the general binary channel without memory according to the sketch. 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 binary entropy function $H_{\rm bin}(p)$ , we thus obtain for the source entropy:
- $$H(X) = H_{\rm bin} (0.1) = 0.4690 \,{\rm bit} \hspace{0.05cm}.$$
For the probability 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.2cm} H(Y) = H_{\rm bin} (0.279) = 0.8541 \,{\rm bit} \hspace{0.05cm}. $$
The joint probabilities $p_{\mu \kappa} = \text{Pr}\big[(X = μ) ∩ (Y = κ)\big]$ 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 joint entropy:
- $$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 mutual information:
- $$I(X;Y) = H(X) + H(Y) - H(XY) = 0.4690 + 0.8541 - 1.1268 = 0.1963\,{\rm bit} \hspace{0.05cm},$$
- the equivocation:
- $$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\,{\rm bit} \hspace{0.05cm},$$
- the irrelevance:
- $$H(Y \vert X) = H(Y) - I(X;Y) $$
- $$\Rightarrow \hspace{0.3cm} H(Y \vert X) = 0.8541 - 0.1963 = 0.6578\,{\rm bit} \hspace{0.05cm}.$$
The results are summarised 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
We further consider a discrete memoryless channel (DMC) with a finite number of source symbols ⇒ $|X|$ and also only finitely many sink symbols ⇒ $|Y|$, , as shown in the first section of this chapter.
- If one calculates the mutual information $I(X, Y)$ as last explained in $\text{example 2}$ ausgeführt, it also depends on the source statistic ⇒ $P_X(X)$ .
- Ergo: The mutual information $I(X, Y)$ is not a pure channel characteristic.
$\text{Definition:}$ The channel capacity introduced by Claude E. Shannon according to his standard work [Sha48][1] reads:
- $$C = \max_{P_X(X)} \hspace{0.15cm} I(X;Y) \hspace{0.05cm}.$$
Since according to this definition the best possible source statistics are always the basis, $C$ depends only on the channel properties ⇒ $P_{Y \vert X}(Y \vert X)$ ab, , but not on the source statistics ⇒ $P_X(X)$. Often the additional unit „bit/channel use” .
Shannon needed the channel description quantity $C$ to formulate the channel coding theorem – one of the highlights of the information theory he founded.
$\text{Shannon's channel coding theorem: }$
- For every transmission channel with channel capacity $C > 0$ , there exists (at least) one $(k, n)$–block code, whose (block) error probability approaches zero as long as the code rate $R = k/n$ is less than or equal to the channel capacity:
- $$R ≤ C.$$
- The prerequisite for this, however, is that the following applies to the block length of this code:
- $$n → ∞.$$
The proof of this theorem, which is beyond the scope of our learning tutorial, can be found for example in [CT06][2], [Kra13][3] und [Meck09][4].
As will be shown in task 3.13 , the reverse also is true. This proof can also be found in the literature references just mentioned.
$\text{Reverse of Shannon's channel coding theorem: }$
If the rate $R$ of the $(n$, $k)$–block code used is greater than the channel capacity $C$, then an arbitrarily small block error probability is not achievable.
In the chapter AWGN model for discrete-time band-limited signals it is explained in connection with the continuous-value AWGN channel model what phenomenally great significance Shannon's information-theoretical theorem has for the entire field of information technology, not only for those interested exclusively in theory, but also for practitioners.
Channel capacity of a binary channel
The mutual information of the general (asymmetrical) binary channel according to this sketch was calculated in $\text{example 2}$ . In this model, the input symbols $0$ and $1$ 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 function $P_X(X) = (p_0,\ p_1)$ 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*}$$
„asymmetrical binary channel”
$\text{Example 3}$: In the following we set $ε_0 = 0.01$ and $ε_1 = 0.2$.
Column 4 of the adjacent table shows (highlighted in green) the transinformation $I(X; Y)$ of this asymmetrical binary channel depending on the source symbol probability $p_0 = {\rm Pr}(X = 0)$ . One can see:
- The mutual information depends on the symbol probabilities $p_0$ und $p_1 = 1 - p_0$ ab.
- The maximum value of $I(X; Y)$ here results in $p_0 ≈ 0.55$ ⇒ $p_1 ≈ 0.45$.
- The result $p_0 > p_1$ follows from the relation $ε_0 < ε_1$ (the zero is less distorted).
- The capacity of this channel is $C = 0.5779 \ \rm bit/use$.
In the above equation, the Binary Symmetric Channel $\rm (BSC)$ with parameters $ε = ε_0 = ε_1$ is also included as a special case. Hints:
- In task 3.10 the mutual information of the BSC channel is calculated for the system parameters $ε = 0.1$ and $p_0 = 0.2$ .
- In task 3.10Z its channel capacity is given as follows:
- $$C_{\rm BSC} = 1 - H_{\rm bin} (\varepsilon) \hspace{0.05cm}.$$
Properties of symmetrical channels
The capacity calculation of the (general) discrete memoryless channel is often complex. It simplifies decisively if symmetries of the channel are exploited.
The diagram shows two examples:
- In the case of the uniformly dispersive channel all source symbols $x ∈ X$ result in exactly the same set of transition probabilities ⇒ $\{P_{Y\hspace{0.03cm}|\hspace{0.01cm}X}(y_κ\hspace{0.05cm}|\hspace{0.05cm}x)\}$ with $1 ≤ κ ≤ |Y|$. For the values $q$, $r$, $s$ , $q + r + s = 1$ must always apply here (left graph).
- In the case of the uniformly focusing channel , the same set of transition probabilities ⇒ $\{P_{Y\hspace{0.03cm}|\hspace{0.01cm}X}(y\hspace{0.05cm}|\hspace{0.05cm}x_μ)\}$ with $1 ≤ μ ≤ |X|$ results for all sink symbols $y ∈ Y$ . Here, $t + u + v = 1$ neednot necessarily hold (right graph).
$\text{Definition:}$ Ist ein diskreter gedächtnisloser Kanal sowohl gleichmäßig dispersiv als auch gleichmäßig fokussierend, so liegt ein streng symmetrischer Kanal (englisch: Strongly Symmetric Channel ) vor. Bei gleichverteiltem Quellenalphabet besitzt dieser die Kapazität
- $$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}.$$
Für diese Gleichung kann jedes beliebige $x ∈ X$ herangezogen werden.
Diese Definition soll nun durch ein Beispiel verdeutlicht werden.
$\text{Beispiel 4}$: Beim betrachteten Kanal gibt es Verbindungen zwischen allen $ \vert X \vert = 3$ Eingängen und allen $ \vert Y \vert = 3$ Ausgängen:
- Eine rote Verbindung steht für $P_{Y \hspace{0.03cm}\vert\hspace{0.01cm} X}(y_κ \hspace{0.05cm} \vert \hspace{0.05cm} x_μ) = 0.7$.
- Eine blaue Verbindung steht für $P_{Y \hspace{0.03cm}\vert\hspace{0.01cm} X}(y_κ \hspace{0.05cm}\vert \hspace{0.05cm} x_μ) = 0.2$.
- Eine grüne Verbindung steht für $P_{Y \hspace{0.03cm}\vert\hspace{0.01cm} X}(y_κ \hspace{0.05cm}\vert\hspace{0.05cm} x_μ) = 0.1$.
Nach obiger Gleichung gilt dann für die Kanalkapazität:
- $$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}.$$
Hinweise:
- Der Zusatz „die gleiche Menge an Übergangswahrscheinlichkeiten” bedeutet nicht, dass $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)$ gelten muss.
- Vielmehr geht hier von jedem Eingang ein roter, ein blauer und ein grüner Pfeil ab und an jedem Ausgang kommt ein roter, ein blauer und ein grüner Pfeil an.
- Die jeweiligen Reihenfolgen permutieren: R – G – B, B – R – G, G – B – R.
Ein Beispiel für einen streng symmetrischen Kanal ist der Binary Symmetric Channel $\rm (BSC)$. Dagegen ist der Binary Erasure Channel $\rm (BEC)$ nicht streng symmetrisch,
- da er zwar gleichmäßig dispersiv ist,
- aber nicht gleichmäßig fokussierend.
Die nachfolgende Definition ist weniger restriktiv als die vorherige des streng symmetrischen Kanals.
$\text{Definition:}$ Ein symmetrischer Kanal (englisch: Symmetric Channel ) liegt vor,
- wenn er in mehrere $($allgemein $L)$ streng symmetrische Teilkanäle aufgeteilt werden kann,
- indem das Ausgangsalphabet $Y$ in $L$ Teilmengen $Y_1$, ... , $Y_L$ aufgespalten wird.
Ein solcher symmetrischer Kanal besitzt die folgende Kapazität:
- $$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}.$$
Hierbei sind folgende Bezeichnungen verwendet:
- $p_{\hspace{0.03cm}l}$ gibt die Wahrscheinlichkeit an, dass der $l$–te Teilkanal ausgewählt wird,
- $C_{\hspace{0.03cm}l}$ ist die Kanalkapazität dieses $l$–ten Teilkanals.
streng symmetrischen Teilkanälen $\rm A$ und $\rm B$
Die Grafik verdeutlicht diese Definition für $L = 2$, wobei die Teilkanäle mit $\rm A$ und $\rm B$ bezeichnet sind.
- An den unterschiedlich gezeichneten Übergängen (gestrichelt oder gepunktet) erkennt man, dass die zwei Teilkanäle verschieden sein können, so dass allgemein $C_{\rm A} ≠ C_{\rm B}$ gelten wird.
- Für die Kapazität des Gesamtkanals erhält man somit allgemein:
- $$C = p_{\rm A} \cdot C_{\rm A} + p_{\rm B} \cdot C_{\rm B} \hspace{0.05cm}.$$
- Über die Struktur der beiden Teilkanäle wird hier keine Aussage gemacht.
Im folgenden Beispiel wird sich zeigen, dass auch der Binary Erasure Channel $\rm (BEC)$ durch diese Grafik grundsätzlich beschreibbar ist. Allerdings müssen dann die zwei Ausgangssysmbole $y_3$ und $y_4$ zu einem einzigen Symbol zusammengefasst werden.
$\text{Beispiel 5}$: Die linke Grafik zeigt die übliche Darstellung des Binary Erasure Channels $\rm (BEC)$ mit Eingang $X = \{0,\ 1\}$ und Ausgang $Y = \{0,\ 1,\ \text{E} \}$.
Teilt man diesen entsprechend der rechten Grafik auf in
- einen idealen Kanal $(y = x)$ für
- $$y ∈ Y_{\rm A} = \{0, 1\} \ \ ⇒ \ \ C_{\rm A} = 1 \ \rm bit/use,$$
- einen Auslöschungskanal für
- $$y ∈ Y_{\rm B} = \{\rm E \} \ \ ⇒ \ \ C_{\rm B} = 0,$$
so ergibt sich mit den Teilkanalgewichtungen $p_{\rm A} = 1 – λ$ und $p_{\rm B} = λ$ für die Kanalkapazität:
- $$C_{\rm BEC} = p_{\rm A} \cdot C_{\rm A} = 1 - \lambda \hspace{0.05cm}.$$
Beide Kanäle sind streng symmetrisch. Für den (idealen) Kanal $\rm A$ gilt gleichermaßen
- für $X = 0$ und $X = 1$: $\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 - λ$ ⇒ gleichmäßig dispersiv,
- für $Y = 0$ und $Y = 1$: $\text{Pr}(Y \hspace{0.05cm} \vert \hspace{0.05cm} X= 0) = Pr(Y \hspace{0.05cm}\vert\hspace{0.05cm} X = 1) = 1 - λ$ ⇒ gleichmäßig fokussierend.
Entsprechendes gilt für den Auslöschungskanal $\rm B$.
In der Aufgabe 3.12 wird sich zeigen, dass die Kapazität des Kanalmodells Binary Symmetric Error & Erasure Channel $\rm (BSEC)$ in gleicher Weise berechnet werden kann. Man erhält:
- $$C_{\rm BSEC} = (1- \lambda) \cdot \left [ 1 - H_{\rm bin}(\frac{\varepsilon}{1- \lambda}) \right ]$$
- mit der Verfälschungswahrscheinlichkeit $ε$
- und der Auslöschungswahrscheinlichkeit $λ$.
Einige Grundlagen der Kanalcodierung
Um das Kanalcodierungstheorem richtig interpretieren zu können, sind einige Grundlagen der Kanalcodierung (englisch: Channel Coding) erforderlich. Dieses äußerst wichtige Gebiet der Nachrichtentechnik wird in unserem Lerntutorial $\rm LNTwww$ in einem eigenen Buch namens Channel Coding behandelt.
Die folgende Beschreibung bezieht sich auf das stark vereinfachte Modell für binäre Blockcodes:
- Die unendlich lange Quellensymbolfolge $\underline{u}$ (hier nicht dargestellt) wird in Blöcke zu jeweils $k$ Bit unterteilt. Wir bezeichnen den Informationsblock mit der laufenden Nummerierung $j$ mit $\underline{u}_j^{(k)}$.
- Jeder Informationsblock $\underline{u}_j^{(k)}$ wird durch den gelb hinterlegten Kanalcoder in ein Codewort $\underline{x}_j^{(n)}$ umgesetzt, wobei $n > k$ gelten soll. Das Verhältnis $R = k/n$ bezeichnet man als die Coderate.
- Der Discrete Memoryless Channel $\rm (DMC)$ wird durch Übergangswahrscheinlichkeiten $P_{Y\hspace{0.03cm}|\hspace{0.03cm}X}(⋅)$ berücksichtigt. Dieser grün hinterlegte Block bewirkt Fehler auf Bitebene. Es kann also gelten: $y_{j, \hspace{0.03cm}i} ≠ x_{j,\hspace{0.03cm} i}$.
- Damit können sich auch die aus $n$ Bit bestehenden Empfangsblöcke $\underline{y}_j^{(n)}$ von den Codeworten $\underline{x}_j^{(n)}$ unterscheiden . Ebenso gilt im allgemeinen für die Blöcke nach dem Deoder: $\underline{v}_j^{(k)} ≠ \underline{u}_j^{(k)}$.
$\text{Beispiel 6}$: Die Grafik soll die hier verwendete Nomenklatur am Beispiel $k = 3$ und $n = 4$ verdeutlichen. Dargestellt sind die jeweils ersten acht Blöcke der Informationssequenz $\underline{u}$ und der Codesequenz $\underline{x}$.
Man erkennt folgende Zuordnung zwischen der geblockten und der ungeblockten Beschreibung:
- Bit 3 des 1. Info–Blocks ⇒ $u_{1,\hspace{0.08cm} 3}$ entspricht dem Symbol $u_3$ in ungeblockter Darstellung.
- Bit 1 des 2. Info–Blocks ⇒ $u_{2, \hspace{0.08cm}1}$ entspricht dem Symbol $u_4$ in ungeblockter Darstellung.
- Bit 2 des 6. Info–Blocks ⇒ $u_{6, \hspace{0.08cm}2}$ entspricht dem Symbol $u_{17}$ in ungeblockter Darstellung.
- Bit 4 des 1. Codewortes ⇒ $x_{1, \hspace{0.08cm}4}$ entspricht dem Symbol $x_4$ in ungeblockter Darstellung.
- Bit 1 des 2. Codewortes ⇒ $x_{2, \hspace{0.08cm}1}$ entspricht dem Symbol $x_5$ in ungeblockter Darstellung.
- Bit 2 des 6. Codewortes ⇒ $x_{6, \hspace{0.08cm}2}$ entspricht dem Symbol $x_{22}$ in ungeblockter Darstellung.
Zusammenhang zwischen Blockfehlern und Bitfehlern
Zur Interpretation des Kanalcodierungstheorems benötigen wir noch verschiedene Definitionen für „Fehlerwahrscheinlichkeiten”. Aus dem obigen Systemmodell lassen sich verschiedene Beschreibungsgrößen ableiten:
$\text{Definitionen:}$
- Die $\rm {Kanalfehlerwahrscheinlichkeit}$ ergibt sich beim vorliegenden Kanalmodell zu
- $${\rm Pr(Kanalfehler)} = {\rm Pr} \left ({y}_{j,\hspace{0.05cm} i} \ne {x}_{j,\hspace{0.05cm} i} \right )\hspace{0.05cm}.$$
- Beispielsweise ist beim BSC–Modell $\text{Pr(Kanalfehler)} = ε$ für alle $j = 1, 2$, ... und $1 ≤ i ≤ n$.
- Die $\rm {Blockfehlerwahrscheinlichkeit}$ bezieht sich auf die zugeordneten Informationsblöcke am Codereingang ⇒ $\underline{u}_j^{(k)}$ und am Decoderausgang ⇒ $\underline{v}_j^{(k)}$,
jeweils in Blöcken zu $k$ Bit:
- $${\rm Pr(Blockfehler)} = {\rm Pr} \left (\underline{\upsilon}_j^{(k)} \ne \underline{u}_j^{(k)} \right )\hspace{0.05cm}.$$
- Die $\rm {Bitfehlerwahrscheinlichkeit}$ bezieht sich ebenfalls auf den Eingang und den Ausgang des betrachteten Codiersystems, allerdings auf Bitebene:
- $${\rm Pr(Bitfehler)} = {\rm Pr} \left ({\upsilon}_{j,\hspace{0.05cm} i} \ne {u}_{j,\hspace{0.05cm} i} \right )\hspace{0.05cm}.$$
- Hierbei ist vereinfachend vorausgesetzt, dass alle $k$ Bit $u_{j,\hspace{0.08cm}i}$ des Informationsblockes $j$ mit gleicher Wahrscheinlichkeit verfälscht werden $(1 ≤ i ≤ k)$. Andernfalls müsste über die $k$ Bit noch gemittelt werden.
Zwischen der Blockfehler– und der Bitfehlerwahrscheinlichkeit besteht allgemein der Zusammenhang:
- $$\frac{1}{k} \cdot {\rm Pr(Blockfehler)} \le {\rm Pr(Bitfehler)} \le {\rm Pr(Blockfehler)} \hspace{0.05cm}.$$
- Die untere Schranke ergibt sich, wenn bei allen fehlerhaften Blöcken alle Bit falsch sind.
- Gibt es in jedem fehlerhaften Block genau nur einen einzigen Bitfehler, dann ist die Bitfehlerwahrscheinlichkeit ⇒ ${\rm Pr(Bitfehler)}$ identisch mit der Blockfehlerwahrscheinlichkeit ⇒ ${\rm Pr(Blockfehler)}$.
$\text{Beispiel 7:}$ Die Grafik zeigt oben die ersten acht Empfangsblöcke $\underline{y}_j^{(n)}$ mit jeweils $n = 4$ Bit. Kanalfehler sind grün schraffiert.
Unten ist die Ausgangsfolge $\underline{v}$ skizziert, unterteilt in Blöcke $\underline{v}_j^{(k)}$ mit jeweils $k = 3$ Bit:
- Bitfehler sind im unteren Diagramm rot schraffiert.
- Blockfehler erkennt man an der blauen Umrahmung.
Hierzu einige (aufgrund der kurzen Folge) nur sehr vage Angaben zu den Fehlerwahrscheinlichkeiten:
- Die Hälfte der Empfangsbits sind grün schraffiert. Daraus folgt:
- $${\rm Pr(Kanalfehler)} = 16/32 = 1/2.$$
- Die Bitfehlerwahrscheinlichkeit lautet mit der beispielhaften Codierung & Decodierung:
- $${\rm Pr(Bitfehler)} = 8/24 = 1/3.$$
- Dagegen würde bei uncodierter Übertragung gelten:
- $${\rm Pr(Bitfehler)} = {\rm Pr(Kanalfehler)} = 1/2.$$
- Die Hälfte der decodierten Blöcke sind blau umrandet. Daraus folgt:
- $${\rm Pr(Blockfehler)} = 4/8 = 1/2.$$
Mit ${\rm Pr(Blockfehler)}= 1/2$ und $k = 3$ liegt die Bitfehlerwahrscheinlichkeit in folgendem Bereich:
- $$1/6 \le {\rm Pr(Bitfehler)} \le 1/2 \hspace{0.05cm}.$$
- Die obere Schranke bezüglich Bitfehler ergibt sich, wenn in jedem der vier verfälschten Blöcke alle Bit falsch sind: ${\rm Pr(Bitfehler)} = 12/24 = 1/2.$
- Die untere Schranke gibt an, dass in jedem der vier verfälschten Blöcke jeweils nur ein Bit falsch ist: ${\rm Pr(Bitfehler)} = 4/24 = 1/6$.
Rate, Kanalkapazität und Bitfehlerwahrscheinlichkeit
Grundsätzlich gilt:
- Durch Kanalcodierung wird die Zuverlässigkeit (englisch: Reliability) der Datenübertragung von der Quelle zur Sinke erhöht.
- Vermindert man die Coderate $R = k/n$ und erhöht so die hinzugefügte Redundanz $(1 - R)$, so wird im allgemeinen die Datensicherheit verbessert und damit die Bitfehlerwahrscheinlichkeit herabgesetzt, die wir im Weiteren kurz mit $p_{\rm B}$ bezeichnen:
- $$p_{\rm B} = {\rm Pr(Bitfehler)} = {\rm Pr} \left ({\upsilon}_{j,\hspace{0.05cm} i} \ne {u}_{j,\hspace{0.05cm} i} \right )\hspace{0.05cm}.$$
Das folgende Theorem basiert auf dem Data Processing Theorem und Fano's Lemma. Die Herleitung kann in den Standardwerken zur Informationstheorie nachgelesen werden, zum Beispiel in [CT06][2]:
$\text{Umkehrung des Shannonschen Kanalcodierungstheorems:}$
Benutzt man zur Datenübertragung mit Rate $R$ einen Kanal mit zu kleiner Kapazität $C < R$, so kann die Bitfehlerwahrscheinlichkeit $p_{\rm B}$ auch bei bestmöglicher Kanalcodierung eine untere Schranke nicht unterschreiten:
- $$p_{\rm B} \ge H_{\rm bin}^{-1} \cdot \left ( 1 - {C}/{R}\right ) > 0\hspace{0.05cm}.$$
Hierbei bezeichnet $H_{\rm bin}(⋅)$ die binäre Entropiefunktion.
Da die Wahrscheinlichkeit der Blockfehler nie kleiner sein kann als die der Bitfehler, ist für $R > C$ auch die Blockfehlerwahrscheinlichkeit „Null” nicht möglich.
Aus den angegebenen Schranken für die Bitfehler,
- $$\frac {1}{k} \cdot {\rm Pr}({\rm Blockfehler}) \le {\rm Pr}({\rm Bitfehler}) \le {\rm Pr}({\rm Blockfehler})\hspace{0.05cm},$$
lässt sich auch ein Bereich für die Blockfehlerwahrscheinlichkeit angeben:
- $$ {\rm Pr}({\rm Bitfehler}) \le {\rm Pr}({\rm Blockfehler}) \le k \cdot {\rm Pr}({\rm Bitfehler})\hspace{0.05cm}.$$
$\text{Beispiel 8:}$ Bei einem Kanal mit Kapazität $C = 1/3$ (bit) ist eine fehlerfreie Datenübertragung $(p_{\rm B} = 0)$ mit der Coderate $R < 1/3$ prinzipiell möglich.
- Allerdings ist aus dem Kanalcodierungstheorem der spezielle $(k$, $n)$–Blockcode nicht bekannt, der dieses Wunschergebnis ermöglicht. Auch Shannon macht hierzu keine Aussagen.
- Bekannt ist nur, dass ein solcher bestmöglicher Code mit unendlich langen Blöcken arbeitet. Bei gegebener Coderate $R = k/n$ gilt somit sowohl $k → ∞$ als auch $n → ∞$.
- Deshalb ist die Aussage „Die Bitfehlerwahrscheinlichkeit ist Null” nicht identisch mit „Es treten keine Bitfehler auf”: Auch bei endlich vielen Bitfehlern und $k → ∞$ gilt nämlich $p_{\rm B} = 0$.
Mit der Coderate $R = 1 > C$ (uncodierte Übertragung) erhält man:
- $$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}.$$
Mit der Coderate $R = 1/2 > C$ ist die Bitfehlerwahrscheinlichkeit zwar kleiner, aber ebenfalls von Null verschieden:
- $$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}.$$
Aufgaben zum Kapitel
Aufgabe 3.10: Transinformation beim BSC
Aufgabe 3.10Z: BSC–Kanalkapazität
Aufgabe 3.11: Auslöschungskanal
Aufgabe 3.11Z: Extrem unsymmetrischer Kanal
Aufgabe 3.12: Streng symmetrische Kanäle
Aufgabe 3.13: Coderate und Zuverlässigkeit
Aufgabe 3.14: Kanalcodierungstheorem
Aufgabe 3.15: Data Processing Theorem
Quellenverzeichnis
- ↑ Shannon, C.E.: A Mathematical Theory of Communication. In: Bell Syst. Techn. J. 27 (1948), S. 379-423 und S. 623-656.
- ↑ 2.0 2.1 Cover, T.M.; Thomas, J.A.: Elements of Information Theory. West Sussex: John Wiley & Sons, 2nd Edition, 2006.
- ↑ Kramer, G.: Information Theory. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, Technische Universität München, 2013.
- ↑ Mecking, M.: Information Theory. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, Technische Universität München, 2009.
