Aufgaben:Exercise 1.16: Block Error Probability Bounds for AWGN - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:58:39Z

Fix interlanguage link: resolve redirect chain

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

2026-03-16T13:47:22Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:47, 16 March 2026
Line 116:		Line 116:
	'''(2)'''  The distance spectrum of the  $(8, 4, 4)$  code was given as  $W_{0} = 1 , \ W_{4} = 14, \ W_{8} = 1$.		'''(2)'''  The distance spectrum of the  $(8, 4, 4)$  code was given as  $W_{0} = 1 , \ W_{4} = 14, \ W_{8} = 1$.
	*Thus,  one obtains for $\sigma = 1$:		*Thus,  one obtains for $\sigma = 1$:
	:$$p_1 = W_4 \cdot {\rm Q}\left ( 2 \right ) + W_8 \cdot {\rm Q}\left ( 2 \cdot \sqrt{2} \right )		:$$p_1 = W_4 \cdot {\rm Q}\left ( 2 \right ) + W_8 \cdot {\rm Q}\left ( 2 \cdot \sqrt{2} \right )= 14 \cdot 2.28 \cdot 10^{-2}+ 1 \cdot 0.23 \cdot 10^{-2} \hspace{0.15cm}\underline{\approx 32.15\%}\hspace{0.05cm},$$
	= 14 \cdot 2.28 \cdot 10^{-2}+ 1 \cdot 0.23 \cdot 10^{-2} \hspace{0.15cm}\underline{\approx 32.15\%}\hspace{0.05cm},$$

	*For  $\sigma = 0.5$:		*For  $\sigma = 0.5$:
	:$$p_1 = 14 \cdot {\rm Q}\left ( 4 \right ) + {\rm Q}\left ( 4 \cdot \sqrt{2} \right )		:$$p_1 = 14 \cdot {\rm Q}\left ( 4 \right ) + {\rm Q}\left ( 4 \cdot \sqrt{2} \right )= 14 \cdot 3.17 \cdot 10^{-5}+ 1.1 \cdot 10^{-8} \hspace{0.15cm}\underline{\approx 0.0444 \%}\hspace{0.05cm}.$$
	= 14 \cdot 3.17 \cdot 10^{-5}+ 1.1 \cdot 10^{-8} \hspace{0.15cm}\underline{\approx 0.0444 \%}\hspace{0.05cm}.$$


Line 159:		Line 157:
	*The weight function of the  $(8, 4, 4)$  code is:		*The weight function of the  $(8, 4, 4)$  code is:

	:$$W(X) = 1 + W_4 \cdot X^4 + W_8 \cdot X^8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} W(\beta) - 1 = W_4 \cdot \beta^4 + W_8 \cdot \beta^8\hspace{0.3cm}		:$$W(X) = 1 + W_4 \cdot X^4 + W_8 \cdot X^8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} W(\beta) - 1 = W_4 \cdot \beta^4 + W_8 \cdot \beta^8\hspace{0.3cm}\Rightarrow \hspace{0.3cm} p_3 = W(\beta) - 1 \ge p_1\hspace{0.05cm}.$$
	\Rightarrow \hspace{0.3cm} p_3 = W(\beta) - 1 \ge p_1\hspace{0.05cm}.$$

Maintenance script: Add German interlanguage link

2026-03-16T12:30:05Z

Add German interlanguage link

← Older revision		Revision as of 14:30, 16 March 2026
Line 186:		Line 186:

	[[Category:Channel Coding: Exercises\|^1.6 Error Probability Bounds^]]		[[Category:Channel Coding: Exercises\|^1.6 Error Probability Bounds^]]
			[[de:Aufgaben:1.16_Schranken_für_AWGN]]

Guenter at 15:17, 5 August 2022

2022-08-05T15:17:43Z

← Older revision		Revision as of 17:17, 5 August 2022
Line 57:		Line 57:
	* The above cited reference  "[Liv10]"  refers to the lecture manuscript "Liva, G.:  Channel Coding.  Chair of Communications Engineering, TU Munich and DLR Oberpfaffenhofen, 2010."		* The above cited reference  "[Liv10]"  refers to the lecture manuscript "Liva, G.:  Channel Coding.  Chair of Communications Engineering, TU Munich and DLR Oberpfaffenhofen, 2010."

	* Further we refer to the interactive applet  [[Applets:Komplementäre_Gaußsche_Fehlerfunktionen\| "Complementary Gaussian error functions"]].		* Further we refer to the interactive HTML5/JavaScript applet  [[Applets:Komplementäre_Gaußsche_Fehlerfunktionen\| "Complementary Gaussian error functions"]].

Guenter at 15:16, 5 August 2022

2022-08-05T15:16:12Z

← Older revision		Revision as of 17:16, 5 August 2022
Line 53:		Line 53:

	Hints:		Hints:
	* This exercise belongs to the chapter  [[Channel_Coding/Bounds_for_Block_Error_Probability\|"Bounds for ~~Block Error Probability~~"]].		* This exercise belongs to the chapter  [[Channel_Coding/Bounds_for_Block_Error_Probability\|"Bounds for block error probability"]].

	* The above cited reference  "[Liv10]"  refers to the lecture manuscript "Liva, G.:  Channel Coding.  Chair of Communications Engineering, TU Munich and DLR Oberpfaffenhofen, 2010."		* The above cited reference  "[Liv10]"  refers to the lecture manuscript "Liva, G.:  Channel Coding.  Chair of Communications Engineering, TU Munich and DLR Oberpfaffenhofen, 2010."

Guenter at 14:41, 5 August 2022

2022-08-05T14:41:12Z

← Older revision		Revision as of 16:41, 5 August 2022
Line 101:		Line 101:
	===Solution===		===Solution===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  ~~Richtig ist die~~ <u>~~Antwort~~ 2</u>~~. Das Distanzspektrum $\{W_i\}$ ist definiert für $i = 0, \ \text{...} \ , \ n$~~:		'''(1)'''  The correct solution is <u>suggestion 2</u>:

	*$W_{1}$ ~~indicates how often the Hamming weight~~ $~~w_{~~\~~rm H}(~~\~~underline~~{~~x}_{i}) = 1$ occurs~~.		*The distance spectrum  $\{W_i\}$  is defined for  $i = 0, \ \text{...} \ , \ n$:
	*$W_{n}~~$ indicates how often the Hamming weight $w_{~~\~~rm H}(~~\~~underline{x}_{i}) =~~ n$ ~~occurs.~~

			#$W_{1}$  indicates how often the Hamming weight  $w_{\rm H}(\underline{x}_{i}) = 1$  occurs.
			#$W_{n}$  indicates how often the Hamming weight  $w_{\rm H}(\underline{x}_{i}) = n$  occurs.

	With that, the ''Union Bound'' is:
			*With that,  the  "Union Bound"  is:

	:$$p_1 = {\rm Pr(Union \hspace{0.15cm}Bound)}= \sum_{i = 1}^{n}\hspace{0.05cm}W_i \cdot {\rm Q}\left ( \sqrt{i/\sigma^2} \right ) \hspace{0.05cm}.$$		:$$p_1 = {\rm Pr(Union \hspace{0.15cm}Bound)}= \sum_{i = 1}^{n}\hspace{0.05cm}W_i \cdot {\rm Q}\left ( \sqrt{i/\sigma^2} \right ) \hspace{0.05cm}.$$


	'''(2)'''  The distance spectrum of the $(8, 4, 4)$ code was given as $W_{0} = 1 , \ W_{4} = 14, \ W_{8} = 1$. Thus, one obtains for $\sigma = 1$:		'''(2)'''  The distance spectrum of the  $(8, 4, 4)$  code was given as  $W_{0} = 1 , \ W_{4} = 14, \ W_{8} = 1$.
			*Thus,  one obtains for $\sigma = 1$:
	:$$p_1 = W_4 \cdot {\rm Q}\left ( 2 \right ) + W_8 \cdot {\rm Q}\left ( 2 \cdot \sqrt{2} \right )		:$$p_1 = W_4 \cdot {\rm Q}\left ( 2 \right ) + W_8 \cdot {\rm Q}\left ( 2 \cdot \sqrt{2} \right )
	= 14 \cdot 2.28 \cdot 10^{-2}+ 1 \cdot 0.23 \cdot 10^{-2} \hspace{0.15cm}\underline{\approx 32.15\%}\hspace{0.05cm},$$		= 14 \cdot 2.28 \cdot 10^{-2}+ 1 \cdot 0.23 \cdot 10^{-2} \hspace{0.15cm}\underline{\approx 32.15\%}\hspace{0.05cm},$$

	~~or for~~ $\sigma = 0.5$:		*For  $\sigma = 0.5$:
	:$$p_1 = 14 \cdot {\rm Q}\left ( 4 \right ) + {\rm Q}\left ( 4 \cdot \sqrt{2} \right )		:$$p_1 = 14 \cdot {\rm Q}\left ( 4 \right ) + {\rm Q}\left ( 4 \cdot \sqrt{2} \right )
	= 14 \cdot 3.17 \cdot 10^{-5}+ 1.1 \cdot 10^{-8} \hspace{0.15cm}\underline{\approx 0.0444 \%}\hspace{0.05cm}.$$		= 14 \cdot 3.17 \cdot 10^{-5}+ 1.1 \cdot 10^{-8} \hspace{0.15cm}\underline{\approx 0.0444 \%}\hspace{0.05cm}.$$


	'''(3)'''  With the minimum distance $d_{\rm min} = 4$ we get:		'''(3)'''  With the minimum distance  $d_{\rm min} = 4$  we get:

	:$$\sigma = 1.0\text{:} \hspace{0.4cm} p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} W_4 \cdot {\rm Q}\left ( 2 \right ) \hspace{0.15cm}\underline{= 31.92\%}\hspace{0.05cm},$$		:$$\sigma = 1.0\text{:} \hspace{0.4cm} p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} W_4 \cdot {\rm Q}\left ( 2 \right ) \hspace{0.15cm}\underline{= 31.92\%}\hspace{0.05cm},$$
Line 127:		Line 130:


	'''(4)'''  The correct solution is <u>suggestion 1</u>:		'''(4)'''  The correct solution is  <u>suggestion 1</u>:
	*The ''Union Bound'' - denoted here by $p_{1}$ - is an upper bound on the block error probability in all cases.		*The  "Union Bound"  - denoted here by  $p_{1}$ - is an upper bound on the block error probability in all cases.
	*For the bound $p_{2}$ (''Truncated Union Bound'') this is not always true.
	*For example, in the $(7, 4, 3)$ Hamming code   ⇒   $W_{3} = W_{4} = 7, \ W_{7} = 1$ is obtained with standard deviation $\sigma = 1$:		*For the bound  $p_{2}$  ("Truncated Union Bound")  this is not always true.

			*For example,  in the  $(7, 4, 3)$  Hamming code   ⇒   $W_{3} = W_{4} = 7, \ W_{7} = 1$  is obtained with standard deviation  $\sigma = 1$:

	:$$p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 7 \cdot {\rm Q}\left ( \sqrt{3} \right ) = 7 \cdot 4.18 \cdot 10^{-2} \approx 0.293\hspace{0.05cm},$$		:$$p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 7 \cdot {\rm Q}\left ( \sqrt{3} \right ) = 7 \cdot 4.18 \cdot 10^{-2} \approx 0.293\hspace{0.05cm},$$
	:$$p_1 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} p_2 + 7 \cdot {\rm Q}\left ( \sqrt{4} \right )+ 1 \cdot {\rm Q}\left ( \sqrt{7} \right ) \approx 0.455 \hspace{0.05cm}.$$		:$$p_1 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} p_2 + 7 \cdot {\rm Q}\left ( \sqrt{4} \right )+ 1 \cdot {\rm Q}\left ( \sqrt{7} \right ) \approx 0.455 \hspace{0.05cm}.$$

	The actual block error probability is likely to be between $p_{2} = 29.3\%$ and $p_{1} = 45.5\%$ (but has not been verified). <br>That is,   $p_{2}$ is not an upper bound.		*The actual block error probability is likely to be between  $p_{2} = 29.3\%$  and  $p_{1} = 45.5\%$  (but this has not been verified). <br>That is,   $p_{2}$ is not an upper bound.


	'''(5)'''  Correct are <u>suggested solutions 1 and 3</u>, as the following calculation for the $(8, 4, 4)$ code shows:		'''(5)'''  Correct are  <u>suggested solutions 1 and 3</u>,  as the following calculation for the  $(8, 4, 4)$  code shows:

	*It holds ${\rm Q}(x) ≤ {\rm Q_{CR}}(x) = {\rm e}^{-x^2/2}$. Thus, for the Union Bound		*It holds  ${\rm Q}(x) ≤ {\rm Q_{CR}}(x) = {\rm e}^{-x^2/2}$.  Thus,  for the Union Bound

	:$$p_1 = W_4 \cdot {\rm Q}\left ( \sqrt{4/\sigma^2} \right ) +W_8 \cdot {\rm Q}\left ( \sqrt{8/\sigma^2} \right )$$		:$$p_1 = W_4 \cdot {\rm Q}\left ( \sqrt{4/\sigma^2} \right ) +W_8 \cdot {\rm Q}\left ( \sqrt{8/\sigma^2} \right )$$
Line 148:		Line 153:
	:$$p_1 \le W_4 \cdot {\rm e}^{ - {4}/(2 \sigma^2) } +W_8 \cdot {\rm e}^{ - {8}/(2 \sigma^2) } \hspace{0.05cm}.$$		:$$p_1 \le W_4 \cdot {\rm e}^{ - {4}/(2 \sigma^2) } +W_8 \cdot {\rm e}^{ - {8}/(2 \sigma^2) } \hspace{0.05cm}.$$

	*With $\beta = {\rm e}^{-1/(2\sigma^2)}$ can be written for this also (so the given $\beta = 1/\sigma$ is wrong):		*With  $\beta = {\rm e}^{-1/(2\sigma^2)}$  can be written for this also  (so the given  $\beta = 1/\sigma$  is wrong):

	:$$p_1 \le W_4 \cdot \beta^4 + W_8 \cdot \beta^8 \hspace{0.05cm}.$$		:$$p_1 \le W_4 \cdot \beta^4 + W_8 \cdot \beta^8 \hspace{0.05cm}.$$

	*The weight function of the $(8, 4, 4)$ code is:		*The weight function of the  $(8, 4, 4)$  code is:

	:$$W(X) = 1 + W_4 \cdot X^4 + W_8 \cdot X^8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} W(\beta) - 1 = W_4 \cdot \beta^4 + W_8 \cdot \beta^8\hspace{0.3cm}		:$$W(X) = 1 + W_4 \cdot X^4 + W_8 \cdot X^8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} W(\beta) - 1 = W_4 \cdot \beta^4 + W_8 \cdot \beta^8\hspace{0.3cm}
Line 158:		Line 163:


	'''(6)'''  With $\sigma = 1$, the Bhattacharyya parameter is $\beta = {\rm e}^{-0.5} = 0.6065$, and thus one obtains for the Bhattacharyya ~~bound~~:		'''(6)'''  With  $\sigma = 1$,  the Bhattacharyya parameter is  $\beta = {\rm e}^{-0.5} = 0.6065$,  and thus one obtains for the Bhattacharyya Bound:

	:$$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 0.135 + 0.018= 1.913 \hspace{0.15cm}\underline{= 191.3%}\hspace{0.05cm}.$$		:$$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 0.135 + 0.018= 1.913 \hspace{0.15cm}\underline{= 191.3%}\hspace{0.05cm}.$$

	*Considering that $p_{3}$ is a bound for a probability, $p_{3} = 1.913$ is only a trivial bound.		*Considering that  $p_{3}$  is a bound for a probability,  $p_{3} = 1.913$  is only a trivial bound.
	*For $\sigma = 0.5$, on the other hand, $\beta = {\rm e}^{-2} \approx 0.135.$ Then holds:
			*For  $\sigma = 0.5$,  on the other hand,  $\beta = {\rm e}^{-2} \approx 0.135.$  Then holds:

	:$$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 3.35 \cdot 10^{-4} + 1.1 \cdot 10^{-7} \hspace{0.15cm}\underline{= 0.47 \%}\hspace{0.05cm}.$$		:$$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 3.35 \cdot 10^{-4} + 1.1 \cdot 10^{-7} \hspace{0.15cm}\underline{= 0.47 \%}\hspace{0.05cm}.$$

	A comparison with subtask (2) shows that in the present example the Bhattacharyya ~~bound~~ $p_{3}$ is above the ~~''union bound''~~ $p_{1}$ by a factor $(0.47 - 10^{-2})/(0.044 - 10^{-2}) > 10$.		A comparison with subtask  '''(2)'''  shows that in the present example the Bhattacharyya Bound  $p_{3}$  is above the  "Union Bound"  $p_{1}$  by a factor
	*The reason for this large deviation is the Chernoff-Rubin bound, which is well above the ${\rm Q}$ function.		:$$(0.47 - 10^{-2})/(0.044 - 10^{-2}) > 10.$$
	*In [[Aufgaben:Exercise_1.16Z:_Bounds_for_the_Gaussian_Error_Function\|"Exercise 1.16Z"]], the deviation between ${\rm Q}_{\rm CR}$ and ${\rm Q}(x)$ is also calculated quantitatively:
			*The reason for this large deviation is the Chernoff-Rubin bound,  which is well above the  ${\rm Q}$ function.

			*In  [[Aufgaben:Exercise_1.16Z:_Bounds_for_the_Gaussian_Error_Function\|"Exercise 1.16Z"]],  the deviation between  ${\rm Q}_{\rm CR}$  and  ${\rm Q}(x)$  is also calculated quantitatively:

	:$${{\rm Q_{CR}}( x )}/{{\rm Q}( x )} \approx 2.5 \cdot x \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {{\rm Q_{CR}}( x = 4 )}/{{\rm Q}( x = 4)} \approx 10 \hspace{0.05cm}.$$		:$${{\rm Q_{CR}}( x )}/{{\rm Q}( x )} \approx 2.5 \cdot x \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {{\rm Q_{CR}}( x = 4 )}/{{\rm Q}( x = 4)} \approx 10 \hspace{0.05cm}.$$

Guenter at 13:40, 5 August 2022

2022-08-05T13:40:42Z

← Older revision		Revision as of 15:40, 5 August 2022
Line 53:		Line 53:

	Hints:		Hints:
	* This exercise belongs to the chapter  [[Channel_Coding/~~Schranken_für_die_Blockfehlerwahrscheinlichkeit~~\|"Block ~~error probability bounds~~"]].		* This exercise belongs to the chapter  [[Channel_Coding/Bounds_for_Block_Error_Probability\|"Bounds for Block Error Probability"]].

	* The above cited reference  "[Liv10]"  refers to the lecture manuscript "Liva, G.:  Channel Coding.  Chair of Communications Engineering, TU Munich and DLR Oberpfaffenhofen, 2010."		* The above cited reference  "[Liv10]"  refers to the lecture manuscript "Liva, G.:  Channel Coding.  Chair of Communications Engineering, TU Munich and DLR Oberpfaffenhofen, 2010."

Guenter at 13:37, 5 August 2022

2022-08-05T13:37:35Z

Show changes

Noah at 17:33, 30 July 2022

2022-07-30T17:33:15Z

Show changes

Noah at 16:54, 30 July 2022

2022-07-30T16:54:32Z

← Older revision		Revision as of 18:54, 30 July 2022
Line 1:		Line 1:
	{{quiz-Header\|Buchseite=Channel_Coding/Limits_for_Block_Error_Probability}}		{{quiz-Header\|Buchseite=Channel_Coding/Limits_for_Block_Error_Probability}}

	[[File:P_ID2414__KC_A_1_15.png\|right\|frame\|~~Fehlerfunktion~~  ${\rm Q}(x)$  ~~und Näherungen~~ ]]		[[File:P_ID2414__KC_A_1_15.png\|right\|frame\|Error function  ${\rm Q}(x)$  and approximations ]]

	~~Wir gehen von der folgenden Konstellation aus~~:		We assume the following constellation:
	*~~ein linearer Blockcode mit Coderate~~  $R = k/n$  ~~und Distanzspektrum~~  $\{W_i\}, \ i = 1, \ \text{...} \ , n$,		*a linear block code with code rate  $R = k/n$  and distance spectrum  $\{W_i\}, \ i = 1, \ \text{...} \ , n$,
	*~~ein AWGN–Kanal, gekennzeichnet durch~~  $E_{\rm B}/N_{0}$   ⇒   ~~umrechenbar in die Rauschleistung~~  $\sigma^2$,		*an AWGN channel characterized by  $E_{\rm B}/N_{0}$   ⇒   convertible to noise power  $\sigma^2$,
	*~~ein Empfänger, basierend auf~~ ''~~Soft Decision~~'' ~~sowie dem~~ ''~~Maximum–Likelihood–Kriterium~~''.		*a receiver based on ''soft decision'' as well as the ''maximum likelihood criterion''.


	~~Unter der für die gesamte Aufgabe gültigen Annahme, dass stets das Nullwort~~  $\underline{x}_{1} = (0, 0, \text{...} \ , 0)$  ~~gesendet wird~~, ~~gilt für die~~  [[Channel_Coding/~~Schranken_für_die_Blockfehlerwahrscheinlichkeit~~#~~Union_Bound_der_Blockfehlerwahrscheinlichkeit~~\|~~„paarweise Fehlerwahrscheinlichkeit”~~]] ~~mit einem anderen Codewort~~  $\underline{x}_{l} (l = 2,\ \text{...} \ , 2^k)$:		Under the assumption valid for the entire exercise that always the null word  $\underline{x}_{1} = (0, 0, \text{... } \ , 0)$  is sent, the  [[Channel_Coding/Limits_for_Block_Error_Probability#Union_Bound_of_the_block_error_probability\|"pairwise error probability"]] with a different codeword  $\underline{x}_{l} (l = 2,\ \text{...} \ , 2^k)$:

	:$$ {\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = {\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm}.$$		:$$ {\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = {\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm}.$$

	~~Die Herleitung dieser Beziehung finden Sie~~ in [Liv10]. ~~In dieser Gleichung werden verwendet~~:		The derivation of this relation can be found in [Liv10]. Used in this equation are:
	*~~die~~  [[Theory_of_Stochastic_Signals/~~Gaußverteilte_Zufallsgrößen~~#~~.C3.9Cberschreitungswahrscheinlichkeit~~\|~~komplementäre Gaußsche Fehlerfunktion~~]]  ${\rm Q}(x)$,		*the  [[Theory_of_Stochastic_Signals/Gaussian_Distributed_Random_Variables#Exceedance_probability\|complementary Gaussian error function]]  ${\rm Q}(x)$,
	*~~das~~  [[Channel_Coding/~~Zielsetzung_der_Kanalcodierung~~#~~Einige_wichtige_Definitionen_zur_Blockcodierung~~\|~~Hamming–Gewicht~~]]  $w_{\rm H}(\underline{x}_{l})$  ~~des Codewortes~~  $\underline{x}_{l}$,		*the  [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding\|Hamming weight]]  $w_{\rm H}(\underline{x}_{l})$  of the codeword  $\underline{x}_{l}$,
	*~~die~~  [[Digital_Signal_Transmission/~~Optimierung_der_Basisbandübertragungssysteme~~#~~Systemoptimierung_bei_Leistungsbegrenzung~~\|~~AWGN–Rauschleistung~~]]  $\sigma^2 = (2 · R · E_{\rm B}/N_{0})^{–1}.$		*the  [[Digital_Signal_Transmission/Optimization_of_Baseband_Transmission_Systems#System_optimization_with_power_limitation\|AWGN noise power]]  $\sigma^2 = (2 - R - E_{\rm B}/N_{0})^{-1}.$


	Damit lassen sich verschiedene Schranken für die Blockfehlerwahrscheinlichkeit angeben:		Damit lassen sich verschiedene Schranken für die Blockfehlerwahrscheinlichkeit angeben:

	*~~die~~ so ~~genannte~~  [[Channel_Coding/~~Schranken_für_die_Blockfehlerwahrscheinlichkeit~~#~~Union_Bound_der_Blockfehlerwahrscheinlichkeit~~\|Union Bound]]  (UB):		*the so called  [[Channel_Coding/Limits_for_Block_Error_Probability#Union_Bound_of_the_block_error_probability\|Union Bound]]  (UB):

	:$$p_1 = \sum_{l = 2}^{2^k}\hspace{0.05cm}{\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = \sum_{l \hspace{0.05cm}= \hspace{0.05cm}2}^{2^k}\hspace{0.05cm}{\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm},$$		:$$p_1 = \sum_{l = 2}^{2^k}\hspace{0.05cm}{\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = \sum_{l \hspace{0.05cm}= \hspace{0.05cm}2}^{2^k}\hspace{0.05cm}{\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm},$$

	*~~die~~ so ~~genannte~~  [[Channel_Coding/~~Schranken_für_die_Blockfehlerwahrscheinlichkeit~~#~~Schranken_f.C3.BCr_den_~~.287.2C_4.2C_3.~~29.E2.80.93Hamming.E2.80.93Code_beim_AWGN.E2.80.93Kanal~~\|Truncated Union Bound]]  (TUB):		*the so called  [[Channel_Coding/Limits_for_Block_Error_Probability#Bounds_for_the_.287.2C_4.2C_3.29_Hamming_code_at_the_AWGN_channel\|Truncated Union Bound]]  (TUB):

	:$$p_2 = W_{d_{\rm min}} \cdot {\rm Q}\left ( \sqrt{d_{\rm min}/\sigma^2} \right ) \hspace{0.05cm},$$		:$$p_2 = W_{d_{\rm min}} \cdot {\rm Q}\left ( \sqrt{d_{\rm min}/\sigma^2} \right ) \hspace{0.05cm},$$

	*~~die~~  [[Channel_Coding/~~Schranken_für_die_Blockfehlerwahrscheinlichkeit~~#~~Die_obere_Schranke_nach_Bhattacharyya~~\|~~Bhattacharyya–Schranke~~]]:		*the  [[Channel_Coding/Limits_for_Block_Error_Probability#The_upper_bound_according_to_Bhattacharyya\|Bhattacharyya bound]]:

	:$$p_3 = W(\beta) - 1\hspace{0.05cm},\hspace{0.2cm} {\rm mit}\hspace{0.15cm} \beta = {\rm e}^{ - 1/(2\sigma^2) } \hspace{0.05cm}.$$		:$$p_3 = W(\beta) - 1\hspace{0.05cm},\hspace{0.2cm} {\rm mit}\hspace{0.15cm} \beta = {\rm e}^{ - 1/(2\sigma^2) } \hspace{0.05cm}.$$

	:In ~~diesem Fall ist das Distanzspektrum~~  $\{W_i\}$  ~~durch die Gewichtsfunktion zu ersetzen~~:		:In this case, replace the distance spectrum  $\{W_i\}$  with the weight enumerator function:

	:$$\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.$$		:$$\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.$$

	~~Beim Übergang von der~~ ''Union Bound''  $p_{1}$  ~~zur ungenaueren Schranke~~  $p_{3}$  ~~wird unter Anderem die Funktion~~  ${\rm Q}(x)$  ~~durch die~~  [https://de.wikipedia.org/wiki/Chernoff-~~Ungleichung Chernoff–Rubin–Schranke~~]  ${\rm Q}_{\rm CR}(x)$  ~~ersetzt~~. ~~Beide Funktionen sind~~ in ~~obigerer Grafik dargestellt~~ (~~rote bzw. grüne Kurve~~).		In the transition from the ''Union Bound''  $p_{1}$  to the more imprecise bound  $p_{3}$  among others the function  ${\rm Q}(x)$  is replaced by the  [https://en.wikipedia.org/wiki/Chernoff_bound Chernoff-Rubin bound]  ${\rm Q}_{\rm CR}(x)$ . Both functions are shown in the above graph (red and green curve, respectively).

	In ~~der~~  [[Aufgaben:~~Aufgabe_1~~.16Z:~~_Schranken_für_die_Gaußsche_Fehlerfunktion~~\|~~Aufgabe~~ 1.16Z]]  ~~wird der Zusammenhang zwischen diesen Funktionen numerisch ausgewertet und zu den Schranken~~  ${\rm Q}_{o}(x)$ ~~und~~ ${\rm Q}_{u}(x)$  ~~Bezug genommen, die~~ in ~~obiger Grafik ebenfalls eingezeichnet sind~~.		In the  [[Aufgaben:Exercise_1.16Z:_Bounds_for_the_Gaussian_Error_Function\|Exercise 1.16Z]]  the relationship between these functions is evaluated numerically and referenced to the bounds  ${\rm Q}_{o}(x)$ and ${\rm Q}_{u}(x)$  which are also drawn in the above graph.




	~~''Hinweise~~:''		Hints:
	* ~~Die Aufgabe gehört zum Kapitel~~  [[Channel_Coding/Schranken_für_die_Blockfehlerwahrscheinlichkeit\|Schranken für die Blockfehlerwahrscheinlichkeit]].		* This exercise belongs to the chapter  [[Channel_Coding/Schranken_für_die_Blockfehlerwahrscheinlichkeit\|Schranken für die Blockfehlerwahrscheinlichkeit]].
	* Die oben zitierte Literaturstelle [Liv10] verweist auf das Vorlesungsmanuskript "Liva, G.: ''Channel Coding''. Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010."		* Die oben zitierte Literaturstelle [Liv10] verweist auf das Vorlesungsmanuskript "Liva, G.: ''Channel Coding''. Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010."
	* Weiter verweisen wir auf das interaktive Applet  [[Applets:Komplementäre_Gaußsche_Fehlerfunktionen\| Komplementäre Gaußsche Fehlerfunktionen]].		* Weiter verweisen wir auf das interaktive Applet  [[Applets:Komplementäre_Gaußsche_Fehlerfunktionen\| Komplementäre Gaußsche Fehlerfunktionen]].

← Older revision		Revision as of 17:58, 16 March 2026
Line 11:		Line 11:


	Under the assumption valid for the entire exercise that always the zero-word  $\underline{x}_{1} = (0, 0, \text{... } \ , 0)$  is sent, the  [[Channel_Coding/~~Limits_for_Block_Error_Probability~~#Union_Bound_of_the_block_error_probability\|"pairwise error probability"]]  with a different code word  $\underline{x}_{l} (l = 2,\ \text{...} \ , 2^k)$:		Under the assumption valid for the entire exercise that always the zero-word  $\underline{x}_{1} = (0, 0, \text{... } \ , 0)$  is sent, the  [[Channel_Coding/Bounds_for_Block_Error_Probability#Union_Bound_of_the_block_error_probability\|"pairwise error probability"]]  with a different code word  $\underline{x}_{l} (l = 2,\ \text{...} \ , 2^k)$:

	:$$ {\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = {\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm}.$$		:$$ {\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = {\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm}.$$
Line 25:		Line 25:
	This allows various bounds to be specified for the block error probability:		This allows various bounds to be specified for the block error probability:

	*the so called  [[Channel_Coding/~~Limits_for_Block_Error_Probability~~#Union_Bound_of_the_block_error_probability\|"Union Bound"]]  $\rm (UB)$:		*the so called  [[Channel_Coding/Bounds_for_Block_Error_Probability#Union_Bound_of_the_block_error_probability\|"Union Bound"]]  $\rm (UB)$:

	:$$p_1 = \sum_{l = 2}^{2^k}\hspace{0.05cm}{\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = \sum_{l \hspace{0.05cm}= \hspace{0.05cm}2}^{2^k}\hspace{0.05cm}{\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm},$$		:$$p_1 = \sum_{l = 2}^{2^k}\hspace{0.05cm}{\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = \sum_{l \hspace{0.05cm}= \hspace{0.05cm}2}^{2^k}\hspace{0.05cm}{\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm},$$

	*the so called  [[Channel_Coding/~~Limits_for_Block_Error_Probability~~#Bounds_for_the_~~.287.2C_4.2C_3.29_Hamming_code_at_the_AWGN_channel~~\|"Truncated Union Bound"]]  $\rm (TUB)$:		*the so called  [[Channel_Coding/Bounds_for_Block_Error_Probability#Bounds_for_the_(7,_4,_3)_Hamming_code_at_the_AWGN_channel\|"Truncated Union Bound"]]  $\rm (TUB)$:

	:$$p_2 = W_{d_{\rm min}} \cdot {\rm Q}\left ( \sqrt{d_{\rm min}/\sigma^2} \right ) \hspace{0.05cm},$$		:$$p_2 = W_{d_{\rm min}} \cdot {\rm Q}\left ( \sqrt{d_{\rm min}/\sigma^2} \right ) \hspace{0.05cm},$$

	*the  [[Channel_Coding/~~Limits_for_Block_Error_Probability~~#The_upper_bound_according_to_Bhattacharyya\|"Bhattacharyya Bound"]]:		*the  [[Channel_Coding/Bounds_for_Block_Error_Probability#The_upper_bound_according_to_Bhattacharyya\|"Bhattacharyya Bound"]]:

	:$$p_3 = W(\beta) - 1\hspace{0.05cm},\hspace{0.2cm} {\rm with}\hspace{0.15cm} \beta = {\rm e}^{ - 1/(2\sigma^2) } \hspace{0.05cm}.$$		:$$p_3 = W(\beta) - 1\hspace{0.05cm},\hspace{0.2cm} {\rm with}\hspace{0.15cm} \beta = {\rm e}^{ - 1/(2\sigma^2) } \hspace{0.05cm}.$$
Line 183:		Line 183:

	[[Category:Channel Coding: Exercises\|^1.6 Error Probability Bounds^]]		[[Category:Channel Coding: Exercises\|^1.6 Error Probability Bounds^]]
	[[de:Aufgaben:1.~~16_Schranken_für_AWGN~~]]		[[de:Aufgaben:Aufgabe 1.16: Fehlerwahrscheinlichkeitsschranken für AWGN]]