Aufgaben:Exercise 3.15: Data Processing Theorem - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:57:09Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:57, 16 March 2026
Line 111:		Line 111:

	[[Category:Information Theory: Exercises\|^3.3 Application to Digital Signal Transmission^]]		[[Category:Information Theory: Exercises\|^3.3 Application to Digital Signal Transmission^]]
	[[de:Aufgaben:3.~~14_Data_Processing_Theorem~~]]		[[de:Aufgaben:Aufgabe 3.15: Data Processing Theorem]]

Maintenance script: Join split $$ formula lines for correct rendering

2026-03-16T13:30:46Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:30, 16 March 2026
Line 71:		Line 71:
	*Here it does not matter at all whether one starts from  $X = 0$  or from  $X = 1$ .		*Here it does not matter at all whether one starts from  $X = 0$  or from  $X = 1$ .
	*For  $X = 0$  one obtains with  $P_{Y\hspace{0.03cm}\|\hspace{0.03cm}X}(Y = 1\hspace{0.03cm}\|\hspace{0.03cm}X = 0) = p$  and  $P_{Y\hspace{0.03cm}\|\hspace{0.03cm}X}(Y = 0\hspace{0.03cm}\|\hspace{0.03cm}X = 0) = 1 – p\hspace{0.05cm}$:		*For  $X = 0$  one obtains with  $P_{Y\hspace{0.03cm}\|\hspace{0.03cm}X}(Y = 1\hspace{0.03cm}\|\hspace{0.03cm}X = 0) = p$  and  $P_{Y\hspace{0.03cm}\|\hspace{0.03cm}X}(Y = 0\hspace{0.03cm}\|\hspace{0.03cm}X = 0) = 1 – p\hspace{0.05cm}$:
	:$$ I(X;Y) = 1 + p \cdot {\rm log}_2 \hspace{0.1cm} (p) + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} (1-p) = 1 - H_{\rm bin}(p)\hspace{0.05cm},		:$$ I(X;Y) = 1 + p \cdot {\rm log}_2 \hspace{0.1cm} (p) + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} (1-p) = 1 - H_{\rm bin}(p)\hspace{0.05cm},\hspace{1.0cm}H_{\rm bin}(p)= p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p}+ (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}\hspace{0.05cm}.$$
	\hspace{1.0cm}H_{\rm bin}(p)= p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p}+ (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}\hspace{0.05cm}.$$
	*However, the result holds only for  $P_X(X) = (0.5, \ 0.5)$   ⇒   maximum mutual information   ⇒   channel capacity.		*However, the result holds only for  $P_X(X) = (0.5, \ 0.5)$   ⇒   maximum mutual information   ⇒   channel capacity.
	*Otherwise,  $I(X; Y)$  is smaller.     For example, for $P_X(X) = (1, \ 0)$:   $H(X) = 0$   ⇒   $I(X; Y) = 0.$		*Otherwise,  $I(X; Y)$  is smaller.     For example, for $P_X(X) = (1, \ 0)$:   $H(X) = 0$   ⇒   $I(X; Y) = 0.$
Line 106:		Line 105:
	*Also for  $p < 0.5$  and  $q > 0.5$  the Data Processing Theorem is not violated, which will be shown here only by an example:		*Also for  $p < 0.5$  and  $q > 0.5$  the Data Processing Theorem is not violated, which will be shown here only by an example:
	::With  $p = 0.1$  and  $q = 0.8$ , the same result is obtained as in subtask  '''(4)''':		::With  $p = 0.1$  and  $q = 0.8$ , the same result is obtained as in subtask  '''(4)''':
	::$$\varepsilon = 0.1 + 0.8 - 2\cdot 0.1 \cdot 0.8 = 0.74 \hspace{0.3cm}		::$$\varepsilon = 0.1 + 0.8 - 2\cdot 0.1 \cdot 0.8 = 0.74 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} I(X;Z) = 1 - H_{\rm bin}(0.74) = 1 - H_{\rm bin}(0.26) =0.173 \,{\rm (bit)} \hspace{0.05cm}.$$
	\Rightarrow \hspace{0.3cm} I(X;Z) = 1 - H_{\rm bin}(0.74) = 1 - H_{\rm bin}(0.26) =0.173 \,{\rm (bit)} \hspace{0.05cm}.$$
	{{ML-Fuß}}		{{ML-Fuß}}

Maintenance script: Add German interlanguage link

2026-03-16T12:32:04Z

Add German interlanguage link

← Older revision		Revision as of 14:32, 16 March 2026
Line 113:		Line 113:

	[[Category:Information Theory: Exercises\|^3.3 Application to Digital Signal Transmission^]]		[[Category:Information Theory: Exercises\|^3.3 Application to Digital Signal Transmission^]]
			[[de:Aufgaben:3.14_Data_Processing_Theorem]]

Guenter at 12:22, 24 September 2021

2021-09-24T12:22:45Z

Guenter at 12:09, 24 September 2021

2021-09-24T12:09:09Z

← Older revision		Revision as of 14:09, 24 September 2021
Line 30:		Line 30:
	Hints:		Hints:
	*The task belongs to the chapter  [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung\| Application to Digital Signal Transmission]].		*The task belongs to the chapter  [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung\| Application to Digital Signal Transmission]].
	*Reference is also made to the page  [[Information_Theory/Different_Entropy_Measures_of_Two-Dimensional_Random_Variables#Chain_rule_of_the_mutual_information\|Chain rule of ~~the_mutual_information~~]]nbsp; in the previous chapter]].		*Reference is also made to the page  [[Information_Theory/Different_Entropy_Measures_of_Two-Dimensional_Random_Variables#Chain_rule_of_the_mutual_information\|Chain rule of the mutual information]]  in the previous chapter]].

Guenter at 12:08, 24 September 2021

2021-09-24T12:08:38Z

← Older revision		Revision as of 14:08, 24 September 2021
Line 30:		Line 30:
	Hints:		Hints:
	*The task belongs to the chapter  [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung\| Application to Digital Signal Transmission]].		*The task belongs to the chapter  [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung\| Application to Digital Signal Transmission]].
	*Reference is also made to the page  [[Information_Theory/~~Verschiedene_Entropien_zweidimensionaler_Zufallsgrößen~~#Chain_rule_of_the_mutual_information\|Chain ~~Rule~~ of ~~Transinformation~~ in the previous chapter]].		*Reference is also made to the page  [[Information_Theory/Different_Entropy_Measures_of_Two-Dimensional_Random_Variables#Chain_rule_of_the_mutual_information\|Chain rule of the_mutual_information]]nbsp; in the previous chapter]].

Guenter at 12:05, 24 September 2021

2021-09-24T12:05:06Z

Guenter at 11:58, 24 September 2021

2021-09-24T11:58:24Z

← Older revision		Revision as of 13:58, 24 September 2021
Line 112:		Line 112:


	[[Category:Information Theory: Exercises\|^3.3 ~~Anwendung auf DSÜ-Kanäle~~^]]		[[Category:Information Theory: Exercises\|^3.3 Application to Digital Signal Transmission^]]

Noah at 09:12, 24 September 2021

2021-09-24T09:12:03Z

← Older revision		Revision as of 11:12, 24 September 2021
Line 1:		Line 1:

	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Anwendung auf die Digitalsignalübertragung~~		{{quiz-Header\|Buchseite=Information_Theory/Application_to_Digital_Signal_Transmission
	}}		}}

Noah at 12:41, 23 September 2021

2021-09-23T12:41:39Z

Show changes

← Older revision		Revision as of 14:22, 24 September 2021
Line 73:		Line 73:
	:$$ I(X;Y) = 1 + p \cdot {\rm log}_2 \hspace{0.1cm} (p) + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} (1-p) = 1 - H_{\rm bin}(p)\hspace{0.05cm},		:$$ I(X;Y) = 1 + p \cdot {\rm log}_2 \hspace{0.1cm} (p) + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} (1-p) = 1 - H_{\rm bin}(p)\hspace{0.05cm},
	\hspace{1.0cm}H_{\rm bin}(p)= p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p}+ (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}\hspace{0.05cm}.$$		\hspace{1.0cm}H_{\rm bin}(p)= p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p}+ (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}\hspace{0.05cm}.$$
	*However, the result holds only for  $P_X(X) = (0.5, \ 0.5)$   ⇒   ~~maximale~~ mutual information   ⇒   channel capacity.		*However, the result holds only for  $P_X(X) = (0.5, \ 0.5)$   ⇒   maximum mutual information   ⇒   channel capacity.
	*Otherwise,  $I(X; Y)$  is smaller.     For example, for $P_X(X) = (1, \ 0)$:   $H(X) = 0$   ⇒   $I(X; Y) = 0.$		*Otherwise,  $I(X; Y)$  is smaller.     For example, for $P_X(X) = (1, \ 0)$:   $H(X) = 0$   ⇒   $I(X; Y) = 0.$
	*The binary entropy function is concave, but this property was not used in the derivation   ⇒   ~~Antwort~~ 2 is incorrect.		*The binary entropy function is concave, but this property was not used in the derivation   ⇒   answer 2 is incorrect.


Line 94:		Line 94:


	'''(5)'''  The answer is  <u>YES</u>, ~~of course~~  ''Data Processing Theorem'' assumes exactly the conditions given here.		'''(5)'''  The answer is  <u>YES</u>,  because the  "Data Processing Theorem" assumes exactly the conditions given here.

	However, we want to evaluate some additional numerical results:		However, we want to evaluate some additional numerical results:
	* If  $0 ≤ p < 0.5$  and  $0 ≤ q < 0.5$, hold, we obtain:		* If  $0 ≤ p < 0.5$  and  $0 ≤ q < 0.5$  hold, we obtain:
	:$$\varepsilon = p + q \cdot (1-2p) > p \hspace{0.3cm}\Rightarrow \hspace{0.3cm} I(X;Z) < I(X;Y) \hspace{0.05cm},$$		:$$\varepsilon = p + q \cdot (1-2p) > p \hspace{0.3cm}\Rightarrow \hspace{0.3cm} I(X;Z) < I(X;Y) \hspace{0.05cm},$$
	:$$\varepsilon = q + p \cdot (1-2q) > q \hspace{0.3cm}\Rightarrow \hspace{0.3cm} I(X;Z) < I(Y;Z) \hspace{0.05cm}.$$		:$$\varepsilon = q + p \cdot (1-2q) > q \hspace{0.3cm}\Rightarrow \hspace{0.3cm} I(X;Z) < I(Y;Z) \hspace{0.05cm}.$$
	*For  $p = 0.5$  holds independently of  $q$, since  $I(X; Z)$  cannot be greater than  $I(X; Y)$:		*For  $p = 0.5$  holds independently of  $q$,  since  $I(X; Z)$  cannot be greater than  $I(X; Y)$:
	:$$\varepsilon = 0.5 + q \cdot (1-1) = 0.5 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} I(X;Y) = 0 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} I(X;Z) = 0 \hspace{0.05cm}.$$		:$$\varepsilon = 0.5 + q \cdot (1-1) = 0.5 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} I(X;Y) = 0 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} I(X;Z) = 0 \hspace{0.05cm}.$$
	*Similarly, with  $q = 0.5$  independent of  $p$, we obtain:		*Similarly, with  $q = 0.5$  independent of  $p$, we obtain:

← Older revision		Revision as of 14:05, 24 September 2021
Line 5:		Line 5:
	[[File:P_ID2818__Inf_A_3_14.png\|right\|frame\|"Data Processing Theorem"]]		[[File:P_ID2818__Inf_A_3_14.png\|right\|frame\|"Data Processing Theorem"]]
	We consider the following data processing chain:		We consider the following data processing chain:
	* Binary input data  $X$  is processed by processor  $1$  (top half in the graph) which is describable by conditional probabilities   ⇒   $P_{Y\hspace{0.03cm}\|\hspace{0.03cm}X}(\cdot)$ .  Its output variable is  $Y$.		* Binary input data  $X$  is processed by processor   $1$  (top half in the graph)  which is describable by conditional probabilities   ⇒   $P_{Y\hspace{0.03cm}\|\hspace{0.03cm}X}(\cdot)$ .  Its output variable is  $Y$.
	* A second processor with random variable  $Y$  at input and random variable  $Z$  at output is given by  $P_{Z\hspace{0.03cm}\|\hspace{0.03cm}Y}(\cdot)$  ~~gegeben ~~ (lower half in the graph).  $Z$  depends on  $Y$  alone  (deterministic or stochastic)  and is independent of  $X$:		* A second processor with random variable  $Y$  at input and random variable  $Z$  at output is given by  $P_{Z\hspace{0.03cm}\|\hspace{0.03cm}Y}(\cdot)$  (lower half in the graph).  $Z$  depends on  $Y$  alone  (deterministic or stochastic)  and is independent of  $X$:
	:$$P_{Z\hspace{0.05cm}\|\hspace{0.03cm} XY\hspace{-0.03cm}}(z\hspace{0.03cm}\|\hspace{0.03cm} x, y) =P_{Z\hspace{0.05cm}\|\hspace{0.03cm} Y\hspace{-0.03cm}}(z\hspace{0.03cm}\|\hspace{0.03cm} y) \hspace{0.05cm}.$$		:$$P_{Z\hspace{0.05cm}\|\hspace{0.03cm} XY\hspace{-0.03cm}}(z\hspace{0.03cm}\|\hspace{0.03cm} x, y) =P_{Z\hspace{0.05cm}\|\hspace{0.03cm} Y\hspace{-0.03cm}}(z\hspace{0.03cm}\|\hspace{0.03cm} y) \hspace{0.05cm}.$$
	The following nomenclature was used for this description:		The following nomenclature was used for this description:
Line 14:		Line 14:
	This also means:		This also means:

	$X → Y → Z$  form a  [[Theory_of_Stochastic_Signals/Markovketten\|Markov chain]].  For such a one, the  ''Data Processing Theorem''  holds with the following consequence:		$X → Y → Z$  form a  [[Theory_of_Stochastic_Signals/Markovketten\|Markov chain]].  For such a one, the  "Data Processing Theorem"  holds with the following consequence:
	:$$I(X;Z) \le I(X;Y ) \hspace{0.05cm}, $$		:$$I(X;Z) \le I(X;Y ) \hspace{0.05cm}, $$
	:$$I(X;Z) \le I(Y;Z ) \hspace{0.05cm}.$$		:$$I(X;Z) \le I(Y;Z ) \hspace{0.05cm}.$$
	The theorem thus states:		The theorem thus states:
	:* One cannot gain additional information about input  $X$  by manipulating   (''processing'')  data  $Y$ .		:* One cannot gain additional information about input  $X$  by manipulating   ("processing")  data  $Y$ .
	:* Data processing  (by processor   $1$)  serves only the purpose of making the information contained in  $X$  more visible.		:* Data processing  (by processor   $1$)  serves only the purpose of making the information contained in  $X$  more visible.

Line 42:		Line 42:
	+ The derivation is based on the properties of a strictly symmetric channel.		+ The derivation is based on the properties of a strictly symmetric channel.
	- It is exploited that  $H_{\rm bin}(p)$  is a concave function.		- It is exploited that  $H_{\rm bin}(p)$  is a concave function.
	- The result is valid for any probability function  $P_X(X)$.		- The result is valid for any probability mass function  $P_X(X)$.