Aufgaben:Exercise 3.10Z: Maximum Likelihood Decoding of Convolutional Codes - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:58:35Z

Fix interlanguage link: resolve redirect chain

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

	[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]		[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]
	[[de:Aufgaben:3.~~10Z_ML–Decodierung_von_Faltungscodes~~]]		[[de:Aufgaben:Aufgabe 3.10Z: ML–Decodierung von Faltungscodes]]

Maintenance script: Join 1 split formula blocks

2026-03-16T14:16:22Z

Join 1 split formula blocks

← Older revision		Revision as of 16:16, 16 March 2026
Line 94:		Line 94:
	:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$		:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$
	*But according to the subtask  '''(1)'''  also applies:		*But according to the subtask  '''(1)'''  also applies:
	:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}		:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})/4\hspace{0.2cm}\Rightarrow \hspace{0.2cm} \underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.2cm}\Rightarrow \hspace{0.2cm} \underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}d_{\rm E}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$
	d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})/4
	\hspace{0.2cm}\Rightarrow \hspace{0.2cm} \underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
	d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})
	\hspace{0.2cm}\Rightarrow \hspace{0.2cm} \underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
	d_{\rm E}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})
	\hspace{0.05cm}.$$

	*The factor  $1/4$  does not matter for the minimization.  Since  $d_{\rm E}(\underline{x}, \, \underline{y}) ≥ 0$,  it does not matter whether the minimization is done with respect to   $d_{\rm E}(\underline{x}, \, \underline{y})$   or   $d_{\rm E}^2(\underline{x}, \, \underline{y})$.		*The factor  $1/4$  does not matter for the minimization.  Since  $d_{\rm E}(\underline{x}, \, \underline{y}) ≥ 0$,  it does not matter whether the minimization is done with respect to   $d_{\rm E}(\underline{x}, \, \underline{y})$   or   $d_{\rm E}^2(\underline{x}, \, \underline{y})$.

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

2026-03-16T13:47:59Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:47, 16 March 2026
Line 19:		Line 19:

	In this exercise,  you should determinethe relationship between the  [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding\| $\text{Hamming distance}$]]  $d_{\rm H}(\underline{x}, \, \underline{y})$  and the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_AWGN_channel\|$\text{Euclidean distance}$]]		In this exercise,  you should determinethe relationship between the  [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding\| $\text{Hamming distance}$]]  $d_{\rm H}(\underline{x}, \, \underline{y})$  and the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_AWGN_channel\|$\text{Euclidean distance}$]]
	:$$d_{\rm E}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =		:$$d_{\rm E}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =\sqrt{\sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2}\hspace{0.05cm}.$$
	\sqrt{\sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2}\hspace{0.05cm}.$$

	Then,  the above maximum likelihood criterion is to be formulated with		Then,  the above maximum likelihood criterion is to be formulated with
Line 88:		Line 87:

	*Equal symbols  $(x_i = y_i)$  do not contribute to the Hamming distance and give  $(x_i \, – y_i)^2 = 0$.  According to the  <u>solution 3</u>,  we can therefore write:		*Equal symbols  $(x_i = y_i)$  do not contribute to the Hamming distance and give  $(x_i \, – y_i)^2 = 0$.  According to the  <u>solution 3</u>,  we can therefore write:
	:$$ d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =		:$$ d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =\frac{1}{4} \cdot \sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2= \frac{1}{4} \cdot d_{\rm E}^2(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$
	\frac{1}{4} \cdot \sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2= \frac{1}{4} \cdot d_{\rm E}^2(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$


	'''(2)'''  <u>All proposed solutions</u>  are correct:		'''(2)'''  <u>All proposed solutions</u>  are correct:
	*In the BSC model,  it is common practice to select the code word  $\underline{x}$  with the smallest Hamming distance  $d_{\rm H}(\underline{x}, \, \underline{y})$  for the given received vector  $\underline{y}$:		*In the BSC model,  it is common practice to select the code word  $\underline{x}$  with the smallest Hamming distance  $d_{\rm H}(\underline{x}, \, \underline{y})$  for the given received vector  $\underline{y}$:
	:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}		:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$
	d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$
	*But according to the subtask  '''(1)'''  also applies:		*But according to the subtask  '''(1)'''  also applies:
	:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}		:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
Line 111:		Line 108:
	'''(3)'''  Correct is the  <u>proposed solution 2</u>:		'''(3)'''  Correct is the  <u>proposed solution 2</u>:
	*The square of the Euclidean distance can be expressed as follows:		*The square of the Euclidean distance can be expressed as follows:
	:$$d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =		:$$d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =\sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2 =\hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} x_i^{\hspace{0.15cm}2} \hspace{0.1cm}+ \hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} y_i^{\hspace{0.15cm}2}\hspace{0.1cm}-2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot y_i\hspace{0.05cm}.$$
	\sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2 =
	\hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} x_i^{\hspace{0.15cm}2} \hspace{0.1cm}+ \hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} y_i^{\hspace{0.15cm}2}
	\hspace{0.1cm}-2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot y_i
	\hspace{0.05cm}.$$

	*The first two summands are each equal to  $L$  and need not be considered for minimization.		*The first two summands are each equal to  $L$  and need not be considered for minimization.
Line 129:		Line 122:

	*Based on the equation		*Based on the equation
	:$$d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =		:$$d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =\hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} x_i^{\hspace{0.15cm}2} \hspace{0.1cm}+ \hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} y_i^{\hspace{0.15cm}2}\hspace{0.1cm}-2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot y_i$$
	\hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} x_i^{\hspace{0.15cm}2} \hspace{0.1cm}+ \hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} y_i^{\hspace{0.15cm}2}
	\hspace{0.1cm}-2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot y_i$$

	:the same statements apply for the first and last summands as for the BSC model – see subtask  '''(3)'''.		:the same statements apply for the first and last summands as for the BSC model – see subtask  '''(3)'''.

	*For the middle summand,  $y_i = x_i + n_i$  and  $x_i ∈ \{–1, \, +1\}$  hold:		*For the middle summand,  $y_i = x_i + n_i$  and  $x_i ∈ \{–1, \, +1\}$  hold:
	:$$\sum_{i=1}^{L} \hspace{0.1cm} y_i^{\hspace{0.15cm}2} =		:$$\sum_{i=1}^{L} \hspace{0.1cm} y_i^{\hspace{0.15cm}2} =\hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} x_i^{\hspace{0.15cm}2} \hspace{0.1cm}+ \hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} n_i^{\hspace{0.15cm}2}\hspace{0.1cm}+2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot n_i \hspace{0.05cm}.$$
	\hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} x_i^{\hspace{0.15cm}2} \hspace{0.1cm}+ \hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} n_i^{\hspace{0.15cm}2}
	\hspace{0.1cm}+2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot n_i \hspace{0.05cm}.$$

	*The first summand gives again  $L$,  the second is proportional to the noise power,  and the last term vanishes since  $\underline{x}$  and  $\underline{n}$  are uncorrelated.		*The first summand gives again  $L$,  the second is proportional to the noise power,  and the last term vanishes since  $\underline{x}$  and  $\underline{n}$  are uncorrelated.

Maintenance script: Add German interlanguage link

2026-03-16T12:31:53Z

Add German interlanguage link

← Older revision		Revision as of 14:31, 16 March 2026
Line 148:		Line 148:

	[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]		[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]
			[[de:Aufgaben:3.10Z_ML–Decodierung_von_Faltungscodes]]

Guenter at 14:57, 21 November 2022

2022-11-21T14:57:19Z

← Older revision		Revision as of 16:57, 21 November 2022
Line 1:		Line 1:
	{{quiz-Header\|Buchseite=Channel_Coding/Decoding_of_Convolutional_Codes}}		{{quiz-Header\|Buchseite=Channel_Coding/Decoding_of_Convolutional_Codes}}

	[[File:~~P_ID2678__KC_Z_3_10~~.png\|right\|frame\|Overall system model,  given for this exercise]]		[[File:EN_KC_Z_3_10.png\|right\|frame\|Overall system model,  given for this exercise]]
	The Viterbi algorithm represents the best known realization form for the maximum likelihood decoding of a convolutional code.  We assume here the following model:		The Viterbi algorithm represents the best known realization form for the maximum likelihood decoding of a convolutional code.  We assume here the following model:
	* The information sequence  $\underline{u}$  is converted into the code sequence  $\underline{x}$  by a convolutional code.		* The information sequence  $\underline{u}$  is converted into the code sequence  $\underline{x}$  by a convolutional code.

Guenter at 15:10, 18 November 2022

2022-11-18T15:10:13Z

← Older revision		Revision as of 17:10, 18 November 2022
Line 82:		Line 82:
	===Solution===		===Solution===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  Correct is the <u>proposed solution 3</u>:		'''(1)'''  Correct is the  <u>proposed solution 3</u>:
	*Let the two binary sequences be $\underline{x}$ and $\underline{y}$ with $x_i ∈ \{-1, \, +1\}, \ y_i ∈ \{-1, \, +1\}$. Let the sequence length be $L$ in each case.		*Let the two binary sequences be   $\underline{x}$   and   $\underline{y}$   with   $x_i ∈ \{-1, \, +1\}, \ y_i ∈ \{-1, \, +1\}$.  Let the sequence length be  $L$  in each case.
	*The Hamming distance $d_{\rm H}(\underline{x}, \, \underline{y})$ gives the number of bits in which $\underline{x}$ and $\underline{y}$ differ, for which thus $x_i \, - y_i = ±2$   ⇒   $ (x_i \, - y_i)^2 = 4$ holds.
	*Equal symbols $(x_i = y_i)$ do not contribute to the Hamming~~–~~distance and give $(x_i \, – y_i)^2 = 0$. According to the <u>solution 3</u>, we can therefore write:		*The Hamming distance   $d_{\rm H}(\underline{x}, \, \underline{y})$   gives the number of bits in which  $\underline{x}$  and  $\underline{y}$  differ,  for which thus  $x_i \, - y_i = ±2$   ⇒   $ (x_i \, - y_i)^2 = 4$  holds.

			*Equal symbols  $(x_i = y_i)$  do not contribute to the Hamming distance and give  $(x_i \, – y_i)^2 = 0$.  According to the  <u>solution 3</u>,  we can therefore write:
	:$$ d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =		:$$ d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =
	\frac{1}{4} \cdot \sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2= \frac{1}{4} \cdot d_{\rm E}^2(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$		\frac{1}{4} \cdot \sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2= \frac{1}{4} \cdot d_{\rm E}^2(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$


	'''(2)'''  <u>All proposed solutions</u> are correct:		'''(2)'''  <u>All proposed solutions</u>  are correct:
	*In the BSC model, it is common practice to select the code word $\underline{x}$ with the smallest Hamming distance $d_{\rm H}(\underline{x}, \, \underline{y})$ for the given received vector $\underline{y}$:		*In the BSC model,  it is common practice to select the code word  $\underline{x}$  with the smallest Hamming distance  $d_{\rm H}(\underline{x}, \, \underline{y})$  for the given received vector  $\underline{y}$:
	:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}		:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
	d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$		d_{\rm H}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})\hspace{0.05cm}.$$
	*But according to the subtask '''(1)''' also applies:		*But according to the subtask  '''(1)'''  also applies:
	:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}		:$$\underline{z} = {\rm arg} \min_{\underline{x} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
	d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})/4		d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y})/4
Line 103:		Line 105:
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$

	*The factor $1/4$ does not matter for the minimization. Since $d_{\rm E}(\underline{x}, \, \underline{y}) ≥ 0$, it does not matter whether the minimization is done with respect to $d_{\rm E}(\underline{x}, \, \underline{y})$ or $d_{\rm E}^2(\underline{x}, \, \underline{y})$.		*The factor  $1/4$  does not matter for the minimization.  Since  $d_{\rm E}(\underline{x}, \, \underline{y}) ≥ 0$,  it does not matter whether the minimization is done with respect to   $d_{\rm E}(\underline{x}, \, \underline{y})$   or   $d_{\rm E}^2(\underline{x}, \, \underline{y})$.



	'''(3)'''  Correct is the <u>proposed solution 2</u>:		'''(3)'''  Correct is the  <u>proposed solution 2</u>:
	*The square of the Euclidean distance can be expressed as follows:		*The square of the Euclidean distance can be expressed as follows:
	:$$d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =		:$$d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =
Line 115:		Line 117:
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$

	*The first two summands are each equal to $L$ and need not be considered for minimization.		*The first two summands are each equal to  $L$  and need not be considered for minimization.
	*For the last expression in this equation, $–2 \cdot 〈 \underline{x}, \, \underline{y} 〉$ can be written.
	*Due to the negative sign, minimization becomes maximization   ⇒   <u>answer 2</u>.		*For the last expression in this equation,  $–2 \cdot 〈 \underline{x}, \, \underline{y} 〉$  can be written.

			*Due to the negative sign,  minimization becomes maximization   ⇒   <u>answer 2</u>.



	'''(4)'''  Correct are <u>proposed solutions 2 and 3</u>:		'''(4)'''  Correct are the  <u>proposed solutions 2 and 3</u>:
	*For the AWGN channel, unlike the BSC, no Hamming distance can be specified.		*For the AWGN channel,  unlike the BSC,  no Hamming distance can be specified.

	*Based on the equation		*Based on the equation
	:$$d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =		:$$d_{\rm E}^{\hspace{0.15cm}2}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =
Line 128:		Line 133:
	\hspace{0.1cm}-2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot y_i$$		\hspace{0.1cm}-2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot y_i$$

	:the same statements apply for the first and last summands as for the BSC model – see subtask (3).		:the same statements apply for the first and last summands as for the BSC model – see subtask  '''(3)'''.
	*For the middle summand, $y_i = x_i + n_i$ and $x_i ∈ \{–1, \, +1\}$ hold:
			*For the middle summand,  $y_i = x_i + n_i$  and  $x_i ∈ \{–1, \, +1\}$  hold:
	:$$\sum_{i=1}^{L} \hspace{0.1cm} y_i^{\hspace{0.15cm}2} =		:$$\sum_{i=1}^{L} \hspace{0.1cm} y_i^{\hspace{0.15cm}2} =
	\hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} x_i^{\hspace{0.15cm}2} \hspace{0.1cm}+ \hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} n_i^{\hspace{0.15cm}2}		\hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} x_i^{\hspace{0.15cm}2} \hspace{0.1cm}+ \hspace{0.1cm}\sum_{i=1}^{L} \hspace{0.1cm} n_i^{\hspace{0.15cm}2}
	\hspace{0.1cm}+2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot n_i \hspace{0.05cm}.$$		\hspace{0.1cm}+2 \cdot \sum_{i=1}^{L} \hspace{0.1cm} x_i \cdot n_i \hspace{0.05cm}.$$

	*The first summand again ~~gives~~ $L$, the second is proportional to the noise power, and the last term vanishes since $\underline{x}$ and $\underline{n}$ are uncorrelated.		*The first summand gives again  $L$,  the second is proportional to the noise power,  and the last term vanishes since  $\underline{x}$  and  $\underline{n}$  are uncorrelated.
	*So for minimizing $d_{\rm E}(\underline{x}, \, \underline{y})$, the sum over $y_i^2$ need not be considered since there is no relation to the code sequences $\underline{x}$.
			*So for minimizing  $d_{\rm E}(\underline{x}, \, \underline{y})$,  the sum over  $y_i^2$  need not be considered since there is no relation to the code sequences  $\underline{x}$.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 14:58, 18 November 2022

2022-11-18T14:58:42Z

← Older revision		Revision as of 16:58, 18 November 2022
Line 44:		Line 44:

	* For more information on this topic,  see the following sections in this book:		* For more information on this topic,  see the following sections in this book:
	** [[Channel_Coding/Channel_Models_and_Decision_Structures#Criteria_.C2.BBMaximum-a-posteriori.C2.AB_and_.C2.BBMaximum-Likelihood.C2.AB\| "MAP and ML criterion"]],		:* [[Channel_Coding/Channel_Models_and_Decision_Structures#Criteria_.C2.BBMaximum-a-posteriori.C2.AB_and_.C2.BBMaximum-Likelihood.C2.AB\| "MAP and ML criterion"]],

	** [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_BSC_channel\| "ML decision at the BSC channel"]],		:* [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_BSC_channel\| "ML decision at the BSC channel"]],

	** [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_AWGN_channel\| "ML decision at the AWGN channel"]],		:* [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_AWGN_channel\| "ML decision at the AWGN channel"]],

	** [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements\| "Decoding linear block codes"]].		:* [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements\| "Decoding linear block codes"]].


Line 58:		Line 58:
	{How are   $d_{\rm H}(\underline{x}, \, \underline{y})$   and   $d_{\rm E}(\underline{x}, \, \underline{y})$   related in the BSC model?		{How are   $d_{\rm H}(\underline{x}, \, \underline{y})$   and   $d_{\rm E}(\underline{x}, \, \underline{y})$   related in the BSC model?
	\|type="()"}		\|type="()"}
	-   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}(\underline{x}, \, \underline{y})$ is valid.		-   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}(\underline{x}, \, \underline{y})$  is valid.
	-   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}^2(\underline{x}, \, \underline{y})$ is valid.		-   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}^2(\underline{x}, \, \underline{y})$  is valid.
	+   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}^2(\underline{x}, \, \underline{y})/4$ is valid.		+   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}^2(\underline{x}, \, \underline{y})/4$  is valid.

	{Which of the equations describe the maximum likelihood decoding in the BSC model?  The minimization/maximization refers alwaysto all  $\underline{x} ∈\mathcal{ C}$.		{Which of the equations describe the maximum likelihood decoding in the BSC model?  The minimization/maximization refers alwaysto all  $\underline{x} ∈\mathcal{ C}$.

Guenter at 14:52, 18 November 2022

2022-11-18T14:52:54Z

← Older revision		Revision as of 16:52, 18 November 2022
Line 7:		Line 7:
	*It is valid  $u_i ∈ \{0, \, 1\}$.  In contrast,  the code symbols are represented bipolar   ⇒   $x_i ∈ \{–1, \, +1\}$.		*It is valid  $u_i ∈ \{0, \, 1\}$.  In contrast,  the code symbols are represented bipolar   ⇒   $x_i ∈ \{–1, \, +1\}$.

	* Let the channel be given by the models  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC\|$\text{BSC}$]]    ⇒   received values  $y_i ∈ \{–1, \, +1\}$  or  [[Channel_Coding/Channel_Models_and_Decision_Structures#~~AWGN_channel_at_Binary_Input~~\| $\text{AWGN}$]]   ⇒ $y_i$  real-valued.		* Let the channel be given by the models  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC\|$\text{BSC}$]]    ⇒   received values  $y_i ∈ \{–1, \, +1\}$  or  [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_binary_input\| $\text{AWGN}$]]   ⇒ $y_i$  real-valued.

	* Given a received sequence  $\underline{y}$  the Viterbi algorithm decides for the sequence  $\underline{z}$  according to		* Given a received sequence  $\underline{y}$  the Viterbi algorithm decides for the sequence  $\underline{z}$  according to

Guenter at 14:52, 18 November 2022

2022-11-18T14:52:05Z

← Older revision		Revision as of 16:52, 18 November 2022
Line 7:		Line 7:
	*It is valid  $u_i ∈ \{0, \, 1\}$.  In contrast,  the code symbols are represented bipolar   ⇒   $x_i ∈ \{–1, \, +1\}$.		*It is valid  $u_i ∈ \{0, \, 1\}$.  In contrast,  the code symbols are represented bipolar   ⇒   $x_i ∈ \{–1, \, +1\}$.

	* Let the channel be given by the models  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80. 93_BSC\|$\text{BSC}$]]    ⇒   received values  $y_i ∈ \{–1, \, +1\}$  or  [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input\| $\text{AWGN}$]]   ⇒ $y_i$  real-valued.		* Let the channel be given by the models  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC\|$\text{BSC}$]]    ⇒   received values  $y_i ∈ \{–1, \, +1\}$  or  [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input\| $\text{AWGN}$]]   ⇒ $y_i$  real-valued.

	* Given a received sequence  $\underline{y}$  the Viterbi algorithm decides for the sequence  $\underline{z}$  according to		* Given a received sequence  $\underline{y}$  the Viterbi algorithm decides for the sequence  $\underline{z}$  according to

Guenter at 14:50, 18 November 2022

2022-11-18T14:50:52Z

← Older revision		Revision as of 16:50, 18 November 2022
Line 1:		Line 1:
	{{quiz-Header\|Buchseite=Channel_Coding/Decoding_of_Convolutional_Codes}}		{{quiz-Header\|Buchseite=Channel_Coding/Decoding_of_Convolutional_Codes}}

	[[File:P_ID2678__KC_Z_3_10.png\|right\|frame\|Overall system model ~~<br>enoder~~ &~~ndash~~; ~~channel – Viterbi~~]]		[[File:P_ID2678__KC_Z_3_10.png\|right\|frame\|Overall system model,  given for this exercise]]
	The Viterbi algorithm represents the best known realization form for the maximum likelihood decoding of a convolutional code. We assume the following model ~~here~~:		The Viterbi algorithm represents the best known realization form for the maximum likelihood decoding of a convolutional code.  We assume here the following model:
	* The information sequence  $\underline{u}$  is converted into the code sequence  $\underline{x}$  by a convolutional code. It is valid  $u_i ∈ \{0, \, 1\}$. In contrast, the code symbols are represented bipolar   ⇒   $x_i ∈ \{–1, \, +1\}$.		* The information sequence  $\underline{u}$  is converted into the code sequence  $\underline{x}$  by a convolutional code.
	* Let the channel be given by the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80. 93_BSC\|"BSC~~–Model"~~]]  ~~given~~   ⇒   $y_i ∈ \{–1, \, +1\}$  or ~~the~~  [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input\| "AWGN~~–channel"~~]]~~  provided~~   ⇒   real-valued ~~received values  $y_i$~~.
	* Given a ~~receive~~ sequence  $\underline{y}$  the Viterbi algorithm decides on the ~~code~~ sequence  $\underline{z}$  according to		*It is valid  $u_i ∈ \{0, \, 1\}$.  In contrast,  the code symbols are represented bipolar   ⇒   $x_i ∈ \{–1, \, +1\}$.

			* Let the channel be given by the models  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80. 93_BSC\|$\text{BSC}$]]    ⇒   received values  $y_i ∈ \{–1, \, +1\}$  or  [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input\| $\text{AWGN}$]]   ⇒ $y_i$  real-valued.

			* Given a received sequence  $\underline{y}$  the Viterbi algorithm decides for the sequence  $\underline{z}$  according to
	:$$\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.03cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \|\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.$$		:$$\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.03cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \|\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.$$

	*This corresponds to the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Criteria_.C2.BBMaximum-a-posteriori.C2.AB_and_.C2.BBMaximum-Likelihood.C2.AB\| "Maximum a posteriori"]]  (MAP) criterion. If all information sequences  $\underline{u}$  are equally likely, this transitions to the somewhat simpler  [[Channel_Coding/Channel_Models_and_Decision_Structures#Criteria_.C2.BBMaximum-a-posteriori.C2.AB_and_.C2.BBMaximum-Likelihood.C2.AB\| "Maximum likelihood criterion"]] :		*This corresponds to the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Criteria_.C2.BBMaximum-a-posteriori.C2.AB_and_.C2.BBMaximum-Likelihood.C2.AB\| "Maximum a posteriori"]]  $\rm (MAP)$  criterion.  If all information sequences  $\underline{u}$  are equally likely,  this transitions to the somewhat simpler  [[Channel_Coding/Channel_Models_and_Decision_Structures#Criteria_.C2.BBMaximum-a-posteriori.C2.AB_and_.C2.BBMaximum-Likelihood.C2.AB\| "Maximum likelihood criterion"]]  $\rm (ML)$:
	:$$\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{y} \hspace{0.05cm}\|\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} ) \hspace{0.05cm}.$$		:$$\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{y} \hspace{0.05cm}\|\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} ) \hspace{0.05cm}.$$

	*As a further result, the Viterbi~~–~~algorithm additionally outputs the sequence  $\underline{v}$  as an estimate for the information sequence  $\underline{u}$~~ ~~.		*As a further result,  the Viterbi algorithm additionally outputs the sequence  $\underline{v}$  as an estimate for the information sequence  $\underline{u}$.


	In this exercise, ~~the~~ relationship between the  [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding\| "Hamming~~–Distance"~~]]  $d_{\rm H}(\underline{x}, \, \underline{y})$  and the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_AWGN_channel\| "Euclidean distance"]]		In this exercise,  you should determinethe relationship between the  [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding\| $\text{Hamming distance}$]]  $d_{\rm H}(\underline{x}, \, \underline{y})$  and the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_AWGN_channel\|$\text{Euclidean distance}$]]
	:$$d_{\rm E}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =		:$$d_{\rm E}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) =
	\sqrt{\sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2}\hspace{0.05cm}$$		\sqrt{\sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2}\hspace{0.05cm}.$$

	~~are determined.~~ Then, the above ML criterion is to be formulated with		Then,  the above maximum likelihood criterion is to be formulated with
	* the Hamming distance  $d_{\rm H}(\underline{x}, \, \underline{y})$,		* the Hamming distance  $d_{\rm H}(\underline{x}, \, \underline{y})$,
	* the Euclidean distance  $d_{\rm E}(\underline{x}, \, \underline{y})$, and
	* the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Relationship_between_Hamming_distance_and_correlation\| "correlation value"]]  $〈 x \cdot y 〉$.		* the Euclidean distance  $d_{\rm E}(\underline{x}, \, \underline{y})$,  and

			* the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Relationship_between_Hamming_distance_and_correlation\|$\text{correlation value}$]]  $〈 x \cdot y 〉$.



Line 29:		Line 36:


			<u>Hints:</u>
			* This exercise refers to the chapter  [[Channel_Coding/Decoding_of_Convolutional_Codes\| "Decoding of Convolutional Codes"]].

			* Reference is made in particular to the section  [[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_algorithm_based_on_correlation_and_metrics\|"Viterbi algorithm – based on correlation and metrics"]].

	~~Hints:~~		* For simplicity,  "tilde"  and  "apostrophe"  are omitted.
	* ~~This exercise refers to the chapter~~  ~~[[Channel_Coding/Decoding_of_Convolutional_Codes\|~~ "~~Decoding of Convolutional Codes~~"~~]].~~
	* Reference is made in particular to the page  ~~[[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_algorithm_based_on_correlation_and_metrics\|"Viterbi algorithm~~ &~~ndash~~; ~~based on correlation and metrics"]].~~		* For more information on this topic,  see the following sections in this book:
	* For simplicity, "tilde" and "apostrophe" are omitted.
	* For more information on this topic, see the following ~~pages~~ in this book:
	** [[Channel_Coding/Channel_Models_and_Decision_Structures#Criteria_.C2.BBMaximum-a-posteriori.C2.AB_and_.C2.BBMaximum-Likelihood.C2.AB\| "MAP and ML criterion"]],		** [[Channel_Coding/Channel_Models_and_Decision_Structures#Criteria_.C2.BBMaximum-a-posteriori.C2.AB_and_.C2.BBMaximum-Likelihood.C2.AB\| "MAP and ML criterion"]],

	** [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_BSC_channel\| "ML decision at the BSC channel"]],		** [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_BSC_channel\| "ML decision at the BSC channel"]],

	** [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_AWGN_channel\| "ML decision at the AWGN channel"]],		** [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum-likelihood_decision_at_the_AWGN_channel\| "ML decision at the AWGN channel"]],

	** [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements\| "Decoding linear block codes"]].		** [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements\| "Decoding linear block codes"]].

Line 44:		Line 56:
	===Questions===		===Questions===
	<quiz display=simple>		<quiz display=simple>
	{How are  $d_{\rm H}(\underline{x}, \, \underline{y})$  and  $d_{\rm E}(\underline{x}, \, \underline{y})$  related in the BSC~~–~~model?		{How are   $d_{\rm H}(\underline{x}, \, \underline{y})$   and   $d_{\rm E}(\underline{x}, \, \underline{y})$   related in the BSC model?
	\|type="()"}		\|type="()"}
	-   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}(\underline{x}, \, \underline{y})$ is valid.		-   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}(\underline{x}, \, \underline{y})$ is valid.
Line 50:		Line 62:
	+   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}^2(\underline{x}, \, \underline{y})/4$ is valid.		+   $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}^2(\underline{x}, \, \underline{y})/4$ is valid.

	{Which of the equations describe the ML decoding in the BSC model? The minimization/maximization refers to all  $\underline{x} ∈\mathcal{ C}$~~, respectively~~.		{Which of the equations describe the maximum likelihood decoding in the BSC model?  The minimization/maximization refers alwaysto all  $\underline{x} ∈\mathcal{ C}$.
	\|type="[]"}		\|type="[]"}
	+ $\underline{z} = \arg \min {d_{\rm H}(\underline{x}, \, \underline{y})}$,		+ $\underline{z} = \arg \min {d_{\rm H}(\underline{x}, \, \underline{y})}$,
Line 56:		Line 68:
	+ $\underline{z} = \arg \min {d_{\rm E}^2(\underline{x}, \, \underline{y})}$,		+ $\underline{z} = \arg \min {d_{\rm E}^2(\underline{x}, \, \underline{y})}$,

	{Which equation describes the ML decision in the BSC model?		{Which equation describes the maximum likelihood decision in the BSC model?
	\|type="()"}		\|type="()"}
	- $\underline{z} = \arg \min 〈 \underline{x} \cdot \underline{y} 〉$,		- $\underline{z} = \arg \min 〈 \underline{x} \cdot \underline{y} 〉$,
	+ $\underline{z} = \arg \max 〈 \underline{x} \cdot \underline{y} 〉$.		+ $\underline{z} = \arg \max 〈 \underline{x} \cdot \underline{y} 〉$.

	{What equations apply to the ML decision in the AWGN model?		{What equations apply to the maximum likelihood decision in the AWGN model?
	\|type="[]"}		\|type="[]"}
	- $\underline{z} = \arg \min {d_{\rm H}(\underline{x}, \, \underline{y})}$,		- $\underline{z} = \arg \min {d_{\rm H}(\underline{x}, \, \underline{y})}$,