Aufgaben:Exercise 3.11: Viterbi Path Finding - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:57:41Z

Fix interlanguage link: resolve redirect chain

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

	[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]		[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]
	[[de:Aufgaben:3.~~11_Viterbi–Pfadsuche~~]]		[[de:Aufgaben:Aufgabe 3.11: Viterbi–Pfadsuche]]

Maintenance script: Add German interlanguage link

2026-03-16T12:31:59Z

Add German interlanguage link

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

	[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]		[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]
			[[de:Aufgaben:3.11_Viterbi–Pfadsuche]]

Guenter at 15:06, 19 November 2022

2022-11-19T15:06:13Z

← Older revision		Revision as of 17:06, 19 November 2022
Line 83:		Line 83:
	===Solution===		===Solution===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  Correct is the <u>proposed solution 2</u>:		'''(1)'''  Correct is the  <u>proposed solution 2</u>:
	*Unambiguously find the surviving path by searching backwards, i.e., from node ${\it \Lambda}_7(S_0)$ to node ${\it \Lambda}_0(S_0)$.		*Unambiguously find the surviving path by searching backwards,  i.e.,  from node  ${\it \Lambda}_7(S_0)$  to node  ${\it \Lambda}_0(S_0)$.
	*Using the ~~code~~ sequences $(00, \, 01, \, 10$ or $11)$ given at the transitions, we obtain in the forward direction the result according to <u>~~Proposition~~ 2</u> ~~  ⇒   ${\it \Phi}_7(S_0)$~~:
			*Using the 2-bit sequences  $(00, \, 01, \, 10$ or $11)$  given at the transitions,  we obtain in the forward direction the result according to  <u>proposition 2</u>:
	:$$\underline{z} = \big (00\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.03cm} \big ) \hspace{0.05cm}.$$		:$$\underline{z} = \big (00\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.03cm} \big ) \hspace{0.05cm}.$$

	*Do not reach the final node ${\it \Lambda}_7(S_0)$ along ~~the~~ other paths.		*One not reach the final node  ${\it \Lambda}_7(S_0)$  along other paths.



	'''(2)'''  By comparing the ~~code~~ sequence $\underline{z}$ selected in subtask (1) with the received sequence		'''(2)'''  By comparing the decoder sequence  $\underline{z}$  selected in subtask  '''(1)'''  with the received sequence
	:$$\underline{y} = \big (01\hspace{0.05cm}, 11\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.03cm} \big )$$		:$$\underline{y} = \big (01\hspace{0.05cm}, 11\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.03cm} \big ),$$

	one detects <u>three bit errors</u> at positions 2, 5, and 8.		one detects  <u>three bit errors</u>  at positions  '''2''',  '''5''',  and  '''8'''.
	*If a ~~code~~ sequence $\underline{x} ≠ \underline{z}$ was sent, there can of course be more.
	*Because of the final value ${\it \Lambda}_7(S_0) = 8$ or ${\it \Gamma}_7(S_0) = 3$ – see [[Aufgaben:Exercise_3.10:_Metric_Calculation\| "Exercise 3.10"]] – but one can assume that a correct decision   ⇒   $\underline{z} = \underline{x}$ has been made.		*If a encoded sequence  $\underline{x} ≠ \underline{z}$  was sent,  there can of course be more.

			*Because of the final value  ${\it \Lambda}_7(S_0) = 8$  or  ${\it \Gamma}_7(S_0) = 3$  – see [[Aufgaben:Exercise_3.10:_Metric_Calculation\|$\text{Exercise 3.10}$]]  – but one can assume that a correct decision   ⇒   $\underline{z} = \underline{x}$  has been made.


	[[File:P_ID2697__KC_A_3_11_ML_neu.png\|right\|frame\|Viterbi path finding]]		[[File:P_ID2697__KC_A_3_11_ML_neu.png\|right\|frame\|Viterbi path finding]]
	'''(3)'''  Correct is <u>proposed solution 1</u>:		'''(3)'''  Correct is the  <u>proposed solution 1</u>:
	*From the colors of the surviving path – red represents $u_i = 0$ and blue represents $u_i = 1$ – one can see the correctness of <u>solution proposal 1</u>: red – blue – red – blue – blue – red – red.		*From the colors of the surviving path  – red represents  $u_i = 0$  and blue represents  $u_i = 1$  –  one can see the correctness of  <u>solution proposal 1</u>:  red – blue – red – blue – blue – red – red.
	*It should be noted that the actual information sequence $\underline{u}$ is only of length $L = 5$.
	*Only by termination one arrives at the total length $L' = L + m = 7$.		*It should be noted that the actual information sequence  $\underline{u}$  is only of length  $L = 5$.  Only by termination one arrives at the total length  $L' = L + m = 7$.


	'''(4)'''  At time $i = 6$ there are still two surviving paths. A decision could be forcibly made based on the larger metric. ~~However, because of ${\it \Lambda}_6(S_0) = {\it \Lambda}_6(S_2) = 6$ this is not possible in our example  ⇒~~  ~~<u>No</u>.~~		'''(4)'''  At time  $i = 6$  there are still two surviving paths.
			*A decision could be forcibly made based on the larger metric.

			*However,  because of  ${\it \Lambda}_6(S_0) = {\it \Lambda}_6(S_2) = 6$  this is not possible in our example  ⇒  <u>No</u>.

	~~'''(5)'''  The graph shows that <u>all proposed solutions</u> are correct. The paths are labeled ${\it \Phi}_5(S_0)$, ... , ${\it \Phi}_5(S_3)$.~~

			'''(5)'''  The graph shows that  <u>all proposed solutions</u>  are correct.  The paths are labeled  ${\it \Phi}_5(S_0)$, ... , ${\it \Phi}_5(S_3)$.

	'''(6)'''  The constraint decision at time $i = 5$ would select the path with the largest metric ${\it \Lambda}_5(S_{\mu})$, i.e., the path ${\it \Phi}_5(S_2)$ corresponding to <u>proposition 3</u>.

			'''(6)'''  The constraint decision at  time $i = 5$  would select the path with the largest metric  ${\it \Lambda}_5(S_{\mu})$, <br>i.e.,  the path  ${\it \Phi}_5(S_2)$  corresponding to  <u>proposition 3</u>.

	'''(7)'''  Based on our solution to subtask (1), the path ${\it \Phi}_5(S_3)$ according to <u>proposition 4</u> would have been the better choice.
	*This is part of the path ${\it \Phi}_7(S_0)$.		'''(7)'''  Based on our solution to subtask  '''(1)''',  the path  ${\it \Phi}_5(S_3)$  according to  <u>proposition 4</u>  would have been the better choice.  This is part of the path to  ${\it \Phi}_7(S_0)$.
	*At ~~the~~ time $i = 5$, however, there is still nothing in favor of this choice.
	*The (ultimately correct) path is only highlighted by the two termination bits.		*At time  $i = 5$,  however,  there is still nothing in favor of this choice.

			*The  (ultimately correct)  path is only highlighted by the two termination bits.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 14:40, 19 November 2022

2022-11-19T14:40:01Z

← Older revision		Revision as of 16:40, 19 November 2022
Line 30:		Line 30:
	*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"]].

	*Reference is made in particular to the section  [[Channel_Coding/Decoding_of_Convolutional_Codes#Evaluating_the_trellis_in_the_error-free_case_.E2.80.~~93_Path_finding~~\|"Evaluating the trellis in the error-free case – Path finding"]].		*Reference is made in particular to the section  [[Channel_Coding/Decoding_of_Convolutional_Codes#Evaluating_the_trellis_in_the_error-free_case_.E2.80.93_Path_search\|"Evaluating the trellis in the error-free case – Path finding"]].

Guenter at 14:38, 19 November 2022

2022-11-19T14:38:42Z

← Older revision		Revision as of 16:38, 19 November 2022
Line 2:		Line 2:

	[[File:P_ID2694__KC_A_3_11.png\|right\|frame\|Evaluated trellis diagram]]		[[File:P_ID2694__KC_A_3_11.png\|right\|frame\|Evaluated trellis diagram]]
	One result of  [[Aufgaben:Exercise_3.10:_Metric_Calculation\| "Exercise 3.10"]]  was adjacent trellis evaluation in terms of metrics  ${\it \Lambda}_i(S_{\mu})$. At all decoding steps  $i$  the (in general)  $2^m = 4$  metrics were determined, selecting for each node the larger of two comparison values. ~~The branch with the lower value was discarded. One can recognize discarded branches in the graph by dotted lines.~~		One result of  [[Aufgaben:Exercise_3.10:_Metric_Calculation\| $\text{Exercise 3.10}$]]  was adjacent trellis evaluation in terms of metrics  ${\it \Lambda}_i(S_{\mu})$.
			*At all decoding steps  $i$  the  $($in general$)$  $2^m = 4$  metrics were determined,  selecting for each node the larger of two comparison values.

	~~Otherwise,~~ the ~~same conditions apply as for  [[Aufgaben:Exercise_3~~.~~10:_Metric_Calculation\| "Exercise 3.10"]]. For example, also~~ in the ~~adjacent~~ graph~~, a red arrow indicates the information bit  $u_i = 0$  and a blue arrow stands for  $u_i = 1$~~.		*The branch with the lower value was discarded. One can recognize discarded branches in the graph by dotted lines.

	In the present exercise we consider the second and important part of the Viterbi–algorithm, namely the search for the "surviving" paths  ${\it \Phi}_i(S_{\mu})$. These are at time  $i$  in state  $S_{\mu}$  with $\mu \in 1, 2, 3, 4$. The search is best organized in the backward direction (i.e., from bottom to top in the graph).

	At the end time (in the example  $i = 7$)  there is only one surviving path  ${\it \Phi}_7(S_0)$ due to termination. From this it is possible to extract:		Otherwise,  the same conditions apply as for  [[Aufgaben:Exercise_3.10:_Metric_Calculation\| $\text{Exercise 3.10}$]].  For example,  also in the adjacent graph,  a red arrow indicates the information bit  $u_i = 0$  and a blue arrow stands for  $u_i = 1$.
	* the ~~code~~ sequence ~~selected by the decoder~~  $\underline{z}$   ⇒   highest possible probability  ${\rm Pr}(\underline{z} = \underline{x})$,
			In the present exercise we consider the second and important part of the Viterbi algorithm,  namely the search for the  "surviving paths"  ${\it \Phi}_i(S_{\mu})$.  These are at time  $i$  in state  $S_{\mu}$  with $\mu \in \{1,\ 2,\ 3,\ 4 \}$.  The search is best organized in the backward direction  $($i.e.,  from bottom to top in the graph$)$.

			At the end time  $($in the example  $i = 7)$  there is only one surviving path  ${\it \Phi}_7(S_0)$ due to termination.  From this it is possible to extract:
			* the sequence  $\underline{z}$   selected by the decoder  $($short:  "decoder sequence"$)$  ⇒   highest possible probability  ${\rm Pr}(\underline{z} = \underline{x})$,

	* the associated information sequence  $\underline{v}$  with the greatest possible probability  ${\rm Pr}(\underline{v} = \underline{u})$.		* the associated information sequence  $\underline{v}$  with the greatest possible probability  ${\rm Pr}(\underline{v} = \underline{u})$.


	A decision at an earlier time, for example at  $i = 5$, does not always satisfy the maximum likelihood criterion. Here there are four surviving paths  ${\it \Phi}_5(S_0), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ {\it \Phi}_5(S_3)$, which at time  $i = 5$ are in states  $S_0, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ S_3$~~  end~~.		A decision at an earlier time,  for example at  $i = 5$,  does not always satisfy the maximum likelihood criterion.  Here there are four surviving paths  ${\it \Phi}_5(S_0), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ {\it \Phi}_5(S_3)$, which at time  $i = 5$  are in states  $S_0, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ S_3$.
	*One of these four paths is certainly part of the maximum likelihood path, which is the best possible path for  $i → ∞$  $($at termination significantly earlier, ~~here at~~  ~~$i = 7)$  .~~		*One of these four paths is certainly part of the maximum likelihood path,  which is the best possible path for  $i → ∞$  $($at termination significantly earlier,  here at  $i = 7)$.
	*But if a constraint decision is to be made already at ~~time~~  $i = ~~5$  one usually chooses the path  ${\it \Phi}_5(S_{\mu})$  with the largest metric at that time  ${\it \Lambda}_5(S_{\mu}~~)$.

			*But if a constraint decision is to be made already at time  $i = 5$,  one usually chooses the path  ${\it \Phi}_5(S_{\mu})$  with the largest metric at that time  ${\it \Lambda}_5(S_{\mu})$.




	Hints:
			<u>Hints:</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"]].
	*Reference is made in particular to the ~~page~~  [[Channel_Coding/Decoding_of_Convolutional_Codes#Evaluating_the_trellis_in_the_error-free_case_.E2.80.93_Path_finding\|"Evaluating the trellis in the error-free case –Path finding"]].
			*Reference is made in particular to the section  [[Channel_Coding/Decoding_of_Convolutional_Codes#Evaluating_the_trellis_in_the_error-free_case_.E2.80.93_Path_finding\|"Evaluating the trellis in the error-free case – Path finding"]].


Line 31:		Line 38:
	===Questions===		===Questions===
	<quiz display=simple>		<quiz display=simple>
	{For which ~~code~~ sequence  $\underline{z}$  does the decision fall at time  $i = 7$?		{For which estimated sequence  $\underline{z}$  $($for the encoded sequence  $\underline{z})$  does the decision fall at time  $i = 7$?
	\|type="()"}		\|type="()"}
	- $\underline{z} = (11, \, 10, \, 00, \, 01, \, 01, \, 11, \, 00)$,		- $\underline{z} = (11, \, 10, \, 00, \, 01, \, 01, \, 11, \, 00)$,
Line 37:		Line 44:
	- $\underline{z} = (00, \, 11, \, 01, \, 01, \, 00, \, 10, \, 11)$.		- $\underline{z} = (00, \, 11, \, 01, \, 01, \, 00, \, 10, \, 11)$.

	{How many transmission errors (at least) ~~have occurred~~?		{How many transmission errors have occurred  $($at least$)$?
	\|type="{}"}		\|type="{}"}
	$N_{\rm ~~Bit~~\:error} \ = \ ${ 3 3% }		$N_{\rm bit\:error} \ = \ ${ 3 3% }

	{Which information sequence  $\underline{v}$  does the Viterbi decoder choose?		{Which information sequence  $\underline{v}$  does the Viterbi decoder choose?
Line 47:		Line 54:
	- $\underline{v} = (0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0)$.		- $\underline{v} = (0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0)$.

	{Would a final (and correct) decision have been possible already at  $i = 6$~~ ~~?		{Would a final  $($and correct$)$  decision have been possible already at  $i = 6$?
	\|type="()"}		\|type="()"}
	- Yes.		- Yes.
Line 59:		Line 66:
	+ $S_0 → S_0 → S_1 → S_2 → S_1 → S_3$.		+ $S_0 → S_0 → S_1 → S_2 → S_1 → S_3$.

	{Which path would you choose at time  $i = 5$~~ ~~?		{Which path would you choose at time  $i = 5$?
	\|type="()"}		\|type="()"}
	- $S_0 → S_0 → S_1 → S_3 → S_2 → S_0$,		- $S_0 → S_0 → S_1 → S_3 → S_2 → S_0$,

Noah at 20:41, 18 October 2022

2022-10-18T20:41:18Z

Show changes

Noah at 19:54, 18 October 2022

2022-10-18T19:54:57Z

← Older revision		Revision as of 21:54, 18 October 2022
Line 1:		Line 1:
	{{quiz-Header\|Buchseite=~~Kanalcodierung~~/~~Decodierung von Faltungscodes~~}}		{{quiz-Header\|Buchseite=Channel_Coding/Decoding_of_Convolutional_Codes}}

	[[File:P_ID2694__KC_A_3_11.png\|right\|frame\|~~Ausgewertetes Trellisdiagramm~~]]		[[File:P_ID2694__KC_A_3_11.png\|right\|frame\|Evaluated trellis diagram]]
	Ein Ergebnis von  [[Aufgaben:3.10_Fehlergr%C3%B6%C3%9Fenberechnung\| Aufgabe 3.10]]  war nebenstehende Trellis–Auswertung hinsichtlich der Metriken  ${\it \Lambda}_i(S_{\mu})$. Zu allen Decodierschritten  $i$  wurden die (im Allgemeinen)  $2^m = 4$  Metriken bestimmt, wobei für jeden Knoten der größere von zwei Vergleichswerten ausgewählt wurde. Der Zweig mit dem niedrigeren Wert wurde verworfen. Man erkennt verworfene Zweige in der Grafik an punktierten Linien.		Ein Ergebnis von  [[Aufgaben:3.10_Fehlergr%C3%B6%C3%9Fenberechnung\| Aufgabe 3.10]]  war nebenstehende Trellis–Auswertung hinsichtlich der Metriken  ${\it \Lambda}_i(S_{\mu})$. Zu allen Decodierschritten  $i$  wurden die (im Allgemeinen)  $2^m = 4$  Metriken bestimmt, wobei für jeden Knoten der größere von zwei Vergleichswerten ausgewählt wurde. Der Zweig mit dem niedrigeren Wert wurde verworfen. Man erkennt verworfene Zweige in der Grafik an punktierten Linien.

Guenter at 12:17, 10 October 2022

2022-10-10T12:17:02Z

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


	[[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.11: Viterbi–Pfadsuche to Aufgaben:Exercise 3.11: Viterbi Path Finding

2022-10-10T12:12:59Z

Guenter moved page Aufgaben:Aufgabe 3.11: Viterbi–Pfadsuche to Aufgaben:Exercise 3.11: Viterbi Path Finding

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

Javier: Text replacement - "”" to """

2021-05-28T14:30:02Z

Text replacement - "”" to """

← Older revision		Revision as of 16:30, 28 May 2021
Line 6:		Line 6:
	Ansonsten gelten die gleichen Voraussetzungen wie für die  [[Aufgaben:3.10_Fehlergr%C3%B6%C3%9Fenberechnung\| Aufgabe 3.10]]. Zum Beispiel kennzeichnet auch in nebenstehender Grafik ein roter Pfeil das Informationsbit  $u_i = 0$  und ein blauer Pfeil steht für  $u_i = 1$.		Ansonsten gelten die gleichen Voraussetzungen wie für die  [[Aufgaben:3.10_Fehlergr%C3%B6%C3%9Fenberechnung\| Aufgabe 3.10]]. Zum Beispiel kennzeichnet auch in nebenstehender Grafik ein roter Pfeil das Informationsbit  $u_i = 0$  und ein blauer Pfeil steht für  $u_i = 1$.

	In der vorliegenden Aufgabe betrachten wir den zweiten und wichtigen Teil des Viterbi–Algorithmuses, nämlich die Suche nach den "überlebenden~~”~~ Pfaden  ${\it \Phi}_i(S_{\mu})$. Diese befinden sich zum Zeitpunkt  $i$  im Zustand  $S_{\mu}$  mit $\mu \in 1, 2, 3, 4$. Die Suche organisiert man am besten in Rückwärtsrichtung (also in der Grafik von unten nach oben).		In der vorliegenden Aufgabe betrachten wir den zweiten und wichtigen Teil des Viterbi–Algorithmuses, nämlich die Suche nach den "überlebenden" Pfaden  ${\it \Phi}_i(S_{\mu})$. Diese befinden sich zum Zeitpunkt  $i$  im Zustand  $S_{\mu}$  mit $\mu \in 1, 2, 3, 4$. Die Suche organisiert man am besten in Rückwärtsrichtung (also in der Grafik von unten nach oben).

	Zum Endzeitpunkt (im Beispiel  $i = 7$)  gibt es aufgrund der Terminierung nur einen überlebenden Pfad  ${\it \Phi}_7(S_0)$. Aus diesem lässt sich extrahieren:		Zum Endzeitpunkt (im Beispiel  $i = 7$)  gibt es aufgrund der Terminierung nur einen überlebenden Pfad  ${\it \Phi}_7(S_0)$. Aus diesem lässt sich extrahieren:

← Older revision		Revision as of 21:54, 18 October 2022
Line 1:		Line 1:
	{{quiz-Header\|Buchseite=~~Kanalcodierung~~/~~Decodierung von Faltungscodes~~}}		{{quiz-Header\|Buchseite=Channel_Coding/Decoding_of_Convolutional_Codes}}

	[[File:P_ID2694__KC_A_3_11.png\|right\|frame\|~~Ausgewertetes Trellisdiagramm~~]]		[[File:P_ID2694__KC_A_3_11.png\|right\|frame\|Evaluated trellis diagram]]
	Ein Ergebnis von  [[Aufgaben:3.10_Fehlergr%C3%B6%C3%9Fenberechnung\| Aufgabe 3.10]]  war nebenstehende Trellis–Auswertung hinsichtlich der Metriken  ${\it \Lambda}_i(S_{\mu})$. Zu allen Decodierschritten  $i$  wurden die (im Allgemeinen)  $2^m = 4$  Metriken bestimmt, wobei für jeden Knoten der größere von zwei Vergleichswerten ausgewählt wurde. Der Zweig mit dem niedrigeren Wert wurde verworfen. Man erkennt verworfene Zweige in der Grafik an punktierten Linien.		Ein Ergebnis von  [[Aufgaben:3.10_Fehlergr%C3%B6%C3%9Fenberechnung\| Aufgabe 3.10]]  war nebenstehende Trellis–Auswertung hinsichtlich der Metriken  ${\it \Lambda}_i(S_{\mu})$. Zu allen Decodierschritten  $i$  wurden die (im Allgemeinen)  $2^m = 4$  Metriken bestimmt, wobei für jeden Knoten der größere von zwei Vergleichswerten ausgewählt wurde. Der Zweig mit dem niedrigeren Wert wurde verworfen. Man erkennt verworfene Zweige in der Grafik an punktierten Linien.