Aufgaben:Exercise 3.09: Basics of the Viterbi Algorithm - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:54:52Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:54, 16 March 2026
Line 113:		Line 113:

	[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]		[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]
	[[de:Aufgaben:3.~~09_Viterbi–Algorithmus~~:~~_Grundlegendes~~]]		[[de:Aufgaben:Aufgabe 3.09: Grundlegendes zum Viterbi–Algorithmus]]

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

2026-03-16T13:47:58Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:47, 16 March 2026
Line 85:		Line 85:
	:expressed with the sequence of states:   $S_0 → S_0 → S_0 → S_0 → \ \text{...} \ $		:expressed with the sequence of states:   $S_0 → S_0 → S_0 → S_0 → \ \text{...} \ $
	*One of the sequences  $\underline{x} ≠ \underline{0}$,  which differs from   $\underline{0}$   only in the minimum number of code bits,  follows the path  $S_0 → S_1 → S_0 → S_0 → \text{...} \ $:		*One of the sequences  $\underline{x} ≠ \underline{0}$,  which differs from   $\underline{0}$   only in the minimum number of code bits,  follows the path  $S_0 → S_1 → S_0 → S_0 → \text{...} \ $:
	:$$\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, ... \hspace{0.1cm} \big )		:$$\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, ... \hspace{0.1cm} \big )\hspace{0.3cm}\Rightarrow \hspace{0.3cm} d_{\rm F}\hspace{0.1cm}\underline{ = 3}\hspace{0.05cm}.$$
	\hspace{0.3cm}\Rightarrow \hspace{0.3cm} d_{\rm F}\hspace{0.1cm}\underline{ = 3}
	\hspace{0.05cm}.$$

Maintenance script: Add German interlanguage link

2026-03-16T12:31:52Z

Add German interlanguage link

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

	[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]		[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]
			[[de:Aufgaben:3.09_Viterbi–Algorithmus:_Grundlegendes]]

Guenter at 13:08, 18 November 2022

2022-11-18T13:08:41Z

← Older revision		Revision as of 15:08, 18 November 2022
Line 2:		Line 2:

	[[File:P_ID2659__KC_A_3_8.png\|right\|frame\|Trellis to be analyzed]]		[[File:P_ID2659__KC_A_3_8.png\|right\|frame\|Trellis to be analyzed]]
	The graph shows a trellis diagram and simultaneously defines the ~~accumulated~~ error values  $($"metrics"$)$   ${\it \Gamma}_i(S_0)$  and  ${\it \Gamma}_i(S_1)$  at times  $i = 0$  to  $i = 5$.		The graph shows a trellis diagram and simultaneously defines the cumulative error values  $($"metrics"$)$   ${\it \Gamma}_i(S_0)$  and  ${\it \Gamma}_i(S_1)$  at times  $i = 0$  to  $i = 5$.

	From this trellis can be read,  for example:		From this trellis can be read,  for example:

Guenter at 10:41, 18 November 2022

2022-11-18T10:41:09Z

← Older revision		Revision as of 12:41, 18 November 2022
Line 108:		Line 108:


	'''(5)''' <u> None of the proposed solutions</u> is correct, as can be seen from the ~~examples below~~.		'''(5)''' <u> None of the proposed solutions</u> is correct, as can be seen from the second graphic.

	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 10:40, 18 November 2022

2022-11-18T10:40:02Z

← Older revision		Revision as of 12:40, 18 November 2022
Line 68:		Line 68:
	===Solution===		===Solution===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  Correct are the <u>solutions 1 and 3</u>:		'''(1)'''  Correct are the  <u>solutions 1 and 3</u>:
	*There are $2^{k \cdot m} = 2$ states here. It follows that $k = 1$ and $m = 1$.		*There are   $2^{k \cdot m} = 2$   states here.  It follows that  $k = 1$  and  $m = 1$.
	*Per coding step, $n = 2$ code bits are output   ⇒   $R = 1/2$.
	*The information sequence length is $L = 4$.		*Per coding step,  $n = 2$  code bits are output   ⇒   $R = 1/2$.
	*Only by one (since $m = 1$) additional termination bit one arrives at the total length $L' = 5$.
			*The information sequence length is  $L = 4$.

			*Only by one  $($since  $m = 1)$  additional termination bit one arrives at the total length  $L' = 5$.



	'''(2)'''  The free distance $d_{\rm F}$ is defined as the number of ~~codebits~~ in which two sequences $\underline{x}$ and $\underline{x'}$ differ. We choose the zero sequence as the reference sequence:		'''(2)'''  The free distance  $d_{\rm F}$  is defined as the number of code bits in which two sequences  $\underline{x}$  and  $\underline{x'}$  differ.
			*We choose the zero sequence as the reference sequence:
	:$$\underline{x}\hspace{0.03cm}' = \underline{0} = \big (00\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, ... \hspace{0.1cm} \big ) \hspace{0.05cm},$$		:$$\underline{x}\hspace{0.03cm}' = \underline{0} = \big (00\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, ... \hspace{0.1cm} \big ) \hspace{0.05cm},$$

	expressed with the sequence of states:   $S_0 → S_0 → S_0 → S_0 → \ \text{...} \ $		:expressed with the sequence of states:   $S_0 → S_0 → S_0 → S_0 → \ \text{...} \ $
	*One of the sequences $\underline{x} ≠ \underline{0}$, which differs from $\underline{0}$ only in the minimum number of ~~codebits~~, follows the path $S_0 → S_1 → S_0 → S_0 → \text{...} \ $:		*One of the sequences  $\underline{x} ≠ \underline{0}$,  which differs from   $\underline{0}$   only in the minimum number of code bits,  follows the path  $S_0 → S_1 → S_0 → S_0 → \text{...} \ $:
	:$$\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, ... \hspace{0.1cm} \big )		:$$\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, ... \hspace{0.1cm} \big )
	\hspace{0.3cm}\Rightarrow \hspace{0.3cm} d_{\rm F}\hspace{0.1cm}\underline{ = 3}		\hspace{0.3cm}\Rightarrow \hspace{0.3cm} d_{\rm F}\hspace{0.1cm}\underline{ = 3}
Line 86:		Line 90:


			[[File:P_ID2660__KC_A_3_9c.png\|right\|frame\|Trellis without error  (above)  and with three transmission errors  (below)]]
			[[File:P_ID2661__KC_A_3_9e.png\|right\|frame\|Trellis with two transmission errors]]

	'''(3)'''  Only <u>proposition 3</u> is correct here, because the event "No transmission error" is much more likely than three errors at exactly specified positions. Consider the ~~following graphic~~:		'''(3)'''  Only  <u>proposition 3</u>  is correct here,  because the event  "No transmission error"  is much more likely than three errors at exactly specified positions.  Consider the graph:
			*If the zero sequence is sent and this is also received,  the Viterbi decoding can be illustrated by the upper trellis.

			*The final value of the metric is  ${\it \Gamma}_5(S_0) = 0$,  and the Viterbi decoder decides correctly with certainty:   $\underline{z} = \underline{x}  ⇒  \underline{v} = \underline{u}$.

	~~[[File:P_ID2660__KC_A_3_9c~~.~~png\|center\|frame\|Trellis without error/with three transmission errors]]~~		*For the lower trellis,  we also assume  $\underline{u} = (0, \, 0, \, 0, \, 0 \, 0)   ⇒   \underline{x} = (00, \, 00, \, 00, \, 00, \, 00)$.

	*~~If the zero sequence is sent and this is also received, the Viterbi decoding can be illustrated by the upper trellis.~~		*However,  $\underline{y} = (00, \, 00, \, 00, \, 11, \, 01)$  is received now.
	*The final value of the branch metric is ${\it \Gamma}_5(S_0) = 0$, and the Viterbi decoder decides correctly with certainty: $\underline{z} = \underline{x}  ⇒  \underline{v} = \underline{u}$.
	*For the lower trellis, we also assume $\underline{u} = (0, \, 0, \, 0, \, 0 \, 0)   ~~⇒   \underline{x} = (00, \, 00, \, 00, \, 00, \, 00)$. However,~~ $\underline{y} = (00, \, 00, \, 00, \, 11, \, 01)$ is now ~~received. Nevertheless, ${\it \Gamma}_5(S_0) = 0$ holds. The example proves that the first two statements are false~~.

			*Nevertheless,  ${\it \Gamma}_5(S_0) = 0$  holds.  The example proves that the first two statements are false.

	~~'''(4)'''  Correct are <u>all answers</u>:~~
	*If it is known for sure that only one transmission error occurred, for a convolutional code with free distance $d_{\rm F} = 3$ the Viterbi algorithm works perfectly, no matter at which position the error occurred.

			'''(4)'''  Correct are <u>all answers</u>:  If it is known for sure that only one transmission error occurred,  for a convolutional code with free distance  $d_{\rm F} = 3$  the Viterbi algorithm works perfectly,  no matter at which position the error occurred.


	'''(5)''' <u> None of the proposed solutions</u> is correct, as can be seen from the examples below.		'''(5)''' <u> None of the proposed solutions</u> is correct, as can be seen from the examples below.

	~~[[File:P_ID2661__KC_A_3_9e.png\|center\|frame\|Trellis with two transmission errors]]~~
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 10:06, 18 November 2022

2022-11-18T10:06:41Z

← Older revision		Revision as of 12:06, 18 November 2022
Line 2:		Line 2:

	[[File:P_ID2659__KC_A_3_8.png\|right\|frame\|Trellis to be analyzed]]		[[File:P_ID2659__KC_A_3_8.png\|right\|frame\|Trellis to be analyzed]]
	The graph shows a trellis diagram and simultaneously defines the ~~branch~~ metrics  ${\it \Gamma}_i(S_0)$  and  ${\it \Gamma}_i(S_1)$  at times  $i = 0$  to  $i = 5$.		The graph shows a trellis diagram and simultaneously defines the accumulated error values  $($"metrics"$)$   ${\it \Gamma}_i(S_0)$  and  ${\it \Gamma}_i(S_1)$  at times  $i = 0$  to  $i = 5$.

	From this trellis can be read, for example:		From this trellis can be read,  for example:
	* the code rate  $R$,		* the code rate  $R$,

	* the memory  $m$,		* the memory  $m$,

	* the free distance  $d_{\rm F}$,		* the free distance  $d_{\rm F}$,

	* the information sequence length  $L$,		* the information sequence length  $L$,

	* the sequence length  $L\hspace{0.05cm}'$  including the termination.		* the sequence length  $L\hspace{0.05cm}'$  including the termination.


	In the exercise it is further necessary to clarify:		In the exercise it is further necessary to clarify:
	* the meaning of the final value  ${\it \Gamma}_5(S_0)$,		* the meaning of the final error value  ${\it \Gamma}_5(S_0)$,
	* effects of one and two transmission errors, respectively.



			* effects of one and two transmission errors,  respectively.


Line 23:		Line 25:


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


Line 37:		Line 38:
	{Which of the following statements are confirmed by the trellis?		{Which of the following statements are confirmed by the trellis?
	\|type="[]"}		\|type="[]"}
	+ It is a rate 1/2 convolutional code.		+ It is a rate-1/2 convolutional code.
	- The memory of the code is  $m = 2$.		- The memory of the code is  $m = 2$.
	+ The convolutional code is terminated.		+ The convolutional code is terminated.
Line 46:		Line 47:
	$d_{\rm F} \ = \ ${ 3 3% }		$d_{\rm F} \ = \ ${ 3 3% }

	{What statements does the final value  ${\it \Gamma}_5(S_0) = 0$  of the ~~branch~~ metric allow?		{What statements does the final value  ${\it \Gamma}_5(S_0) = 0$  of the metric allow?
	\|type="[]"}		\|type="[]"}
	- No transmission error has occurred.		- No transmission error has occurred.
	- The decoding result  $\underline{v}$  is certainly correct $($equal  $\underline{u})$.		- The decoding result   $\underline{v}$   is certainly correct  $($equal  $\underline{u})$.
	+ The decoding result minimizes the probability  ${\rm Pr}(\underline{v} ≠ \underline{u})$.		+ The decoding result minimizes the probability   ${\rm Pr}(\underline{v} ≠ \underline{u})$.

	{Which statements are true <u>in the case of a single</u> transmission error?		{Which statements are true  <u>in the case of a single</u>  transmission error?
	\|type="[]"}		\|type="[]"}
	+ The final ~~branch~~ metric is  ${\it \Gamma}_5(S_0) = 1$.		+ The final metric is  ${\it \Gamma}_5(S_0) = 1$.
	+ The decoding result  $\underline{v}$  is certainly correct  $($equal  $\underline{u})$.		+ The decoding result  $\underline{v}$  is certainly correct  $($equal  $\underline{u})$.
	+ The decoding result minimizes the probability  ${\rm Pr}(\underline{v} ≠ \underline{u})$.		+ The decoding result minimizes the probability   ${\rm Pr}(\underline{v} ≠ \underline{u})$.

	{Which statements are true <u>in the case of two</u> transmission errors?		{Which statements are true  <u>in the case of two</u>  transmission errors?
	\|type="[]"}		\|type="[]"}
	- The final ~~branch~~ metric is  ${\it \Gamma}_5(S_0) = 2$.		- The final metric is  ${\it \Gamma}_5(S_0) = 2$.
	- The decoding result  $\underline{v}$  is certainly correct  $($equal  $\underline{u})$.		- The decoding result  $\underline{v}$  is certainly correct  $($equal  $\underline{u})$.
	- The decoding result  $\underline{v}$  is certainly false  $($unequal  $\underline{u})$.		- The decoding result  $\underline{v}$  is certainly false  $($unequal  $\underline{u})$.

Noah at 20:47, 17 October 2022

2022-10-17T20:47:15Z

Show changes

Guenter at 12:14, 10 October 2022

2022-10-10T12:14:16Z

← Older revision		Revision as of 14:14, 10 October 2022
Line 108:		Line 108:


	[[Category:Channel Coding: Exercises\|^3.4 ~~Decodierung von Faltungscodes~~^]]		[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]

Guenter: Guenter moved page Aufgaben:Aufgabe 3.09: Grundlegendes zum Viterbi–Algorithmus to Aufgaben:Exercise 3.09: Basics of the Viterbi Algorithm

2022-10-10T12:04:51Z

Guenter moved page Aufgaben:Aufgabe 3.09: Grundlegendes zum Viterbi–Algorithmus to Aufgaben:Exercise 3.09: Basics of the Viterbi Algorithm

← Older revision	Revision as of 14:04, 10 October 2022
(No difference)