Difference between revisions of "Aufgaben:Exercise 3.12: Strictly Symmetrical Channels"
(3 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Information_Theory/Application_to_Digital_Signal_Transmission |
}} | }} | ||
Line 87: | Line 87: | ||
===Solution=== | ===Solution=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' Subchannel $\rm A$ is a ( | + | '''(1)''' Subchannel $\rm A$ is a ("Binary Symmetric Channel") with crossover probability $q$ ⇒ <u>Proposed solution 1</u>. |
− | + | '''(2)''' Subchannel $\rm B$ is an "erasure channel". Both the sink entropy and irrelevance of this subchannel are zero ⇒ <u>Proposed solution 3</u>. | |
− | '''(2)''' Subchannel $\rm B$ is an | ||
− | |||
Line 99: | Line 97: | ||
:$$ C = p_{\rm A} \cdot C_{\rm A} + p_{\rm B} \cdot C_{\rm B} = p_{\rm A} \cdot \big[1 - H_{\rm bin}(q)\big]\hspace{0.05cm}.$$ | :$$ C = p_{\rm A} \cdot C_{\rm A} + p_{\rm B} \cdot C_{\rm B} = p_{\rm A} \cdot \big[1 - H_{\rm bin}(q)\big]\hspace{0.05cm}.$$ | ||
Thus, the <u>proposed solution 2</u> is correct here. | Thus, the <u>proposed solution 2</u> is correct here. | ||
− | |||
Line 109: | Line 106: | ||
− | '''(5)''' In the BSEC ( | + | '''(5)''' In the BSEC ("Binary Symmetric Error & Erasure Channel") model, for example: |
:$$ {\rm Pr}(Y \hspace{-0.05cm} = 1\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 0) =\varepsilon \hspace{0.05cm}.$$ | :$$ {\rm Pr}(Y \hspace{-0.05cm} = 1\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 0) =\varepsilon \hspace{0.05cm}.$$ | ||
*In contrast, for our auxiliary model according to the graph below, the result is: | *In contrast, for our auxiliary model according to the graph below, the result is: | ||
:$${\rm Pr}(Y \hspace{-0.05cm} = 1\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 0) =(1- \lambda) \cdot q \hspace{0.05cm}.$$ | :$${\rm Pr}(Y \hspace{-0.05cm} = 1\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 0) =(1- \lambda) \cdot q \hspace{0.05cm}.$$ | ||
*This gives $q = ε/(1 – λ)$ ⇒ <u>Proposed solution 4</u>. | *This gives $q = ε/(1 – λ)$ ⇒ <u>Proposed solution 4</u>. | ||
− | *The graph uses colours and line type (solid/dotted) to illustrate the relationship between the models. | + | *The graph uses colours and line type (solid/dotted) to illustrate the relationship between the models. |
− | |||
− | '''(6)''' Using the results of subtasks '''(3)''', '''(4)''' and '''(5)''' we obtain in general for the | + | '''(6)''' Using the results of subtasks '''(3)''', '''(4)''' and '''(5)''' we obtain in general for the "Binary Symmetric Error & Erasure Channel": |
:$$C_{\rm BSEC} = (1- \lambda) \cdot \left [ 1 - H_{\rm bin}(\frac{\varepsilon}{1- \lambda}) \right ]\hspace{0.05cm},$$ | :$$C_{\rm BSEC} = (1- \lambda) \cdot \left [ 1 - H_{\rm bin}(\frac{\varepsilon}{1- \lambda}) \right ]\hspace{0.05cm},$$ | ||
:or the numerical values for $ε = 0.08$ and $λ = 0.2$: | :or the numerical values for $ε = 0.08$ and $λ = 0.2$: | ||
:$$C_{\rm BSEC} = 0.8 \cdot \big [ 1 - H_{\rm bin}(0.1) \big ] = 0.8 \cdot \left [ 1 - 0.469 \right ] \hspace{0.15cm} \underline {=0.425\,{\rm bit}}\hspace{0.05cm}.$$ | :$$C_{\rm BSEC} = 0.8 \cdot \big [ 1 - H_{\rm bin}(0.1) \big ] = 0.8 \cdot \left [ 1 - 0.469 \right ] \hspace{0.15cm} \underline {=0.425\,{\rm bit}}\hspace{0.05cm}.$$ | ||
− | + | '''(7)''' The "Binary Symmetric Channel" (BSC) is a special case of the BSEC with $λ = 0$: | |
− | |||
− | '''(7)''' The | ||
:$$ C_{\rm BSC} = 1 - H_{\rm bin}(\varepsilon) = 1 - H_{\rm bin}(0.08) = 1 - 0.402 \hspace{0.15cm} \underline {=0.598\,{\rm bit}}\hspace{0.05cm}.$$ | :$$ C_{\rm BSC} = 1 - H_{\rm bin}(\varepsilon) = 1 - H_{\rm bin}(0.08) = 1 - 0.402 \hspace{0.15cm} \underline {=0.598\,{\rm bit}}\hspace{0.05cm}.$$ | ||
− | + | '''(8)''' The "Binary Erasure Channel" (BEC) is a special case of the BSEC with $ε = 0$: | |
− | |||
− | '''(8)''' The | ||
:$$C_{\rm BEC} = (1- \lambda) \cdot \big [ 1 - H_{\rm bin}(0) \big ] = 1- \lambda\hspace{0.05cm}.$$ | :$$C_{\rm BEC} = (1- \lambda) \cdot \big [ 1 - H_{\rm bin}(0) \big ] = 1- \lambda\hspace{0.05cm}.$$ | ||
− | *With $λ = 0.2$ , this results in $C_{\rm BEC} = 0.8 \ \rm bit.$ | + | *With $λ = 0.2$ , this results in $C_{\rm BEC}\hspace{0.15cm} \underline { = 0.8 \ \rm bit}.$ |
{{ML-Fuß}} | {{ML-Fuß}} | ||
Line 138: | Line 130: | ||
− | [[Category:Information Theory: Exercises|^3.3 | + | [[Category:Information Theory: Exercises|^3.3 Application to Digital Signal Transmission^]] |
Latest revision as of 12:57, 24 September 2021
The upper diagram shows two strictly symmetric subchannels $\rm A$ and $\rm B$.
- A strongly symmetric channel is one that is "uniformly dispersive" ⇒ each input symbol $u$ has the same set of transition probabilities:
- $$\left \{ P_{\hspace{0.05cm}Y\hspace{-0.01cm}|\hspace{0.02cm}U}(y\hspace{0.03cm} |\hspace{0.03cm} u) \hspace{-0.05cm}: \hspace{0.25cm}u \in U \right \} \hspace{0.05cm},$$
- moreover, uniformly focusing ⇒ each output symbol $y$ has the same set of transition probabilities:
- $$ \left \{ P_{\hspace{0.05cm}Y\hspace{-0.01cm}|\hspace{0.02cm}U}(y\hspace{0.03cm} |\hspace{0.03cm} u) \hspace{-0.05cm}: \hspace{0.25cm}y \in Y \right \} \hspace{0.05cm}.$$
The random quantity $U = \{0,\ 1\}$ occurs directly at the inputs of the sub-channels $\rm A$ and $\rm B$.
The channel capacity of a strictly symmetrical channel can be calculated much more easily than in the asymmetrical case. However, this will not be discussed in detail in this exercise.
For the capacity of the total channel applies:
- $$ C = p_{\rm A} \cdot C_{\rm A} + p_{\rm B} \cdot C_{\rm B}\hspace{0.05cm}$$
Here $p_{\rm A}$ denotes the probability that the sub-channel $\rm A$ is selected and $C_{\rm A}$ indicates its capacity. The same applies to sub-channel $\rm B$.
Subsequently, the channel capacity of the Binary Symmetric Error & Erasure Channel $\rm (BSEC)$ is also to be determined according to the sketch below (grey background) by deriving the relationship between
- the parameters $p_{\rm A}$, $p_{\rm B}$ and the crossover probability $q$ of the sub-channel model shown above, and
- the parameters $λ$ and $\varepsilon$ of the BSEC model.
Hints:
- The exercise belongs to the chapter Application to Digital Signal Transmission.
- Reference is made in particular to the page Properties of symmetrical channels.
- According to Exercise 3.10Z , the following applies to the channel capacity of the BSC model with the crossover probability $\varepsilon$:
- $$ C_{\rm BSC} = 1 - H_{\rm bin}(\varepsilon)\hspace{0.05cm}.$$
Questions
Solution
(2) Subchannel $\rm B$ is an "erasure channel". Both the sink entropy and irrelevance of this subchannel are zero ⇒ Proposed solution 3.
(3) The capacity $C$ of the total channel can be calculated using the given equation:
- $$ C = p_{\rm A} \cdot C_{\rm A} + p_{\rm B} \cdot C_{\rm B} = p_{\rm A} \cdot \big[1 - H_{\rm bin}(q)\big]\hspace{0.05cm}.$$
Thus, the proposed solution 2 is correct here.
(4) In the model considered so far, the transition probabilities are as follows:
- $${\rm Pr}(Y \hspace{-0.05cm} = {\rm E}\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 0) ={\rm Pr}(Y \hspace{-0.05cm} = {\rm E}\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 1) = p_{\rm B} \hspace{0.05cm}.$$
- In the BSEC model, the corresponding conditional probabilities are equal to $λ$
⇒ see graph on the information page. - Therefore, the correct solution proposal is 2:
- $$p_{\rm B} = \lambda = 1 - p_{\rm A} \hspace{0.3cm}\Rightarrow \hspace{0.3cm} p_{\rm A} = 1- \lambda\hspace{0.05cm}.$$
(5) In the BSEC ("Binary Symmetric Error & Erasure Channel") model, for example:
- $$ {\rm Pr}(Y \hspace{-0.05cm} = 1\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 0) =\varepsilon \hspace{0.05cm}.$$
- In contrast, for our auxiliary model according to the graph below, the result is:
- $${\rm Pr}(Y \hspace{-0.05cm} = 1\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 0) =(1- \lambda) \cdot q \hspace{0.05cm}.$$
- This gives $q = ε/(1 – λ)$ ⇒ Proposed solution 4.
- The graph uses colours and line type (solid/dotted) to illustrate the relationship between the models.
(6) Using the results of subtasks (3), (4) and (5) we obtain in general for the "Binary Symmetric Error & Erasure Channel":
- $$C_{\rm BSEC} = (1- \lambda) \cdot \left [ 1 - H_{\rm bin}(\frac{\varepsilon}{1- \lambda}) \right ]\hspace{0.05cm},$$
- or the numerical values for $ε = 0.08$ and $λ = 0.2$:
- $$C_{\rm BSEC} = 0.8 \cdot \big [ 1 - H_{\rm bin}(0.1) \big ] = 0.8 \cdot \left [ 1 - 0.469 \right ] \hspace{0.15cm} \underline {=0.425\,{\rm bit}}\hspace{0.05cm}.$$
(7) The "Binary Symmetric Channel" (BSC) is a special case of the BSEC with $λ = 0$:
- $$ C_{\rm BSC} = 1 - H_{\rm bin}(\varepsilon) = 1 - H_{\rm bin}(0.08) = 1 - 0.402 \hspace{0.15cm} \underline {=0.598\,{\rm bit}}\hspace{0.05cm}.$$
(8) The "Binary Erasure Channel" (BEC) is a special case of the BSEC with $ε = 0$:
- $$C_{\rm BEC} = (1- \lambda) \cdot \big [ 1 - H_{\rm bin}(0) \big ] = 1- \lambda\hspace{0.05cm}.$$
- With $λ = 0.2$ , this results in $C_{\rm BEC}\hspace{0.15cm} \underline { = 0.8 \ \rm bit}.$