Aufgaben:Exercise 3.11: Viterbi Path Finding - Revision history

Guenter at 15:06, 19 November 2022

2022-11-19T15:06:13Z

Guenter at 14:40, 19 November 2022

2022-11-19T14:40:01Z

Guenter at 14:38, 19 November 2022

2022-11-19T14:38:42Z

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

Guenter at 12:17, 10 October 2022

2022-10-10T12:17:02Z

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 Aufgabe 3.11: Viterbi–Pfadsuche to Exercise 3.11: Viterbi Path Finding

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

2021-05-28T14:30:02Z

Text replacement - "”" to """

Javier: Text replacement - "„" to """

2021-05-28T14:28:15Z

Text replacement - "„" to """

Javier: Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

2021-03-23T12:49:26Z

Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

@@ Line 83: / Line 83: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Correct is the <u>proposed solution 2</u>:
+'''(1)'''&nbsp; Correct is the&nbsp; <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,&nbsp; i.e.,&nbsp; from node&nbsp; ${\it \Lambda}_7(S_0)$&nbsp; to node&nbsp; ${\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> &nbsp; &#8658; &nbsp; ${\it \Phi}_7(S_0)$:
 :$$\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&nbsp; ${\it \Lambda}_7(S_0)$&nbsp; along other paths.
-'''(2)'''&nbsp; By comparing the code sequence $\underline{z}$ selected in subtask (1) with the received sequence
+'''(2)'''&nbsp; By comparing the decoder sequence&nbsp; $\underline{z}$&nbsp; selected in subtask&nbsp; '''(1)'''&nbsp; 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&nbsp; <u>three bit errors</u>&nbsp; at positions&nbsp; '''2''',&nbsp; '''5''',&nbsp; and&nbsp; '''8'''.
-*If a code sequence $\underline{x} &ne; \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$ &ndash; see [[Aufgaben:Exercise_3.10:_Metric_Calculation| "Exercise 3.10"]] &ndash; but one can assume that a correct decision &nbsp; &#8658; &nbsp; $\underline{z} = \underline{x}$ has been made.
+*If a encoded sequence&nbsp; $\underline{x} &ne; \underline{z}$&nbsp; was sent,&nbsp; there can of course be more.
 [[File:P_ID2697__KC_A_3_11_ML_neu.png|right|frame|Viterbi path finding]]
-'''(3)'''&nbsp; Correct is <u>proposed solution 1</u>:
+'''(3)'''&nbsp; Correct is the&nbsp; <u>proposed solution 1</u>:
-*From the colors of the surviving path &ndash; red represents $u_i = 0$ and blue represents $u_i = 1$ &ndash; one can see the correctness of <u>solution proposal 1</u>: red &ndash; blue &ndash; red &ndash; blue &ndash; blue &ndash; red &ndash; red.
+*From the colors of the surviving path&nbsp; &ndash; red represents&nbsp; $u_i = 0$&nbsp; and blue represents&nbsp; $u_i = 1$&nbsp; &ndash;&nbsp; one can see the correctness of&nbsp; <u>solution proposal 1</u>:&nbsp; red &ndash; blue &ndash; red &ndash; blue &ndash; blue &ndash; red &ndash; 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&nbsp; $\underline{u}$&nbsp; is only of length&nbsp; $L = 5$.&nbsp; Only by termination one arrives at the total length&nbsp; $L' = L + m = 7$.
-'''(4)'''&nbsp; 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 &nbsp;&#8658;&nbsp; <u>No</u>.
+'''(4)'''&nbsp; At time&nbsp; $i = 6$&nbsp; there are still two surviving paths.&nbsp;
 '''(7)'''&nbsp; 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)'''&nbsp; Based on our solution to subtask&nbsp; '''(1)''',&nbsp; the path&nbsp; ${\it \Phi}_5(S_3)$&nbsp; according to&nbsp; <u>proposition 4</u>&nbsp; would have been the better choice.&nbsp; This is part of the path to&nbsp; ${\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&nbsp; $i = 5$,&nbsp; however,&nbsp; there is still nothing in favor of this choice.
 {{ML-Fuß}}

← Older revision		Revision as of 14: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"]].

@@ Line 2: / Line 2: @@
 [[File:P_ID2694__KC_A_3_11.png|right|frame|Evaluated trellis diagram]]
-One result of&nbsp; [[Aufgaben:Exercise_3.10:_Metric_Calculation| "Exercise 3.10"]]&nbsp; was adjacent trellis evaluation in terms of metrics&nbsp; ${\it \Lambda}_i(S_{\mu})$. At all decoding steps&nbsp; $i$&nbsp; the (in general)&nbsp; $2^m = 4$&nbsp; 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&nbsp; [[Aufgaben:Exercise_3.10:_Metric_Calculation| $\text{Exercise 3.10}$]]&nbsp; was adjacent trellis evaluation in terms of metrics&nbsp; ${\it \Lambda}_i(S_{\mu})$.&nbsp;
-Otherwise, the same conditions apply as for&nbsp; [[Aufgaben:Exercise_3.10:_Metric_Calculation| "Exercise 3.10"]]. For example, also in the adjacent graph, a red arrow indicates the information bit&nbsp; $u_i = 0$&nbsp; and a blue arrow stands for&nbsp; $u_i = 1$.
+*The branch with the lower value was discarded. One can recognize discarded branches in the graph by dotted lines.
-At the end time (in the example&nbsp; $i = 7$)&nbsp; there is only one surviving path&nbsp; ${\it \Phi}_7(S_0)$ due to termination. From this it is possible to extract:
+Otherwise,&nbsp; the same conditions apply as for&nbsp; [[Aufgaben:Exercise_3.10:_Metric_Calculation| $\text{Exercise 3.10}$]].&nbsp; For example,&nbsp; also in the adjacent graph,&nbsp; a red arrow indicates the information bit&nbsp; $u_i = 0$&nbsp; and a blue arrow stands for&nbsp; $u_i = 1$.
-* the code sequence selected by the decoder&nbsp; $\underline{z}$ &nbsp; &#8658; &nbsp; highest possible probability&nbsp; ${\rm Pr}(\underline{z} = \underline{x})$,
 * the associated information sequence&nbsp; $\underline{v}$&nbsp; with the greatest possible probability&nbsp; ${\rm Pr}(\underline{v} = \underline{u})$.
-A decision at an earlier time, for example at&nbsp; $i = 5$, does not always satisfy the maximum likelihood criterion. Here there are four surviving paths&nbsp; ${\it \Phi}_5(S_0), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ {\it \Phi}_5(S_3)$, which at time&nbsp; $i = 5$ are in states&nbsp; $S_0, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ S_3$&nbsp; end.
+A decision at an earlier time,&nbsp; for example at&nbsp; $i = 5$,&nbsp; does not always satisfy the maximum likelihood criterion.&nbsp; Here there are four surviving paths&nbsp; ${\it \Phi}_5(S_0), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ {\it \Phi}_5(S_3)$, which at time&nbsp; $i = 5$&nbsp; are in states&nbsp; $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&nbsp; $i &#8594; &#8734;$&nbsp; $($at termination significantly earlier, here at&nbsp; $i = 7)$&nbsp; .
+*One of these four paths is certainly part of the maximum likelihood path,&nbsp; which is the best possible path for&nbsp; $i &#8594; &#8734;$&nbsp; $($at termination significantly earlier,&nbsp; here at&nbsp; $i = 7)$.
 Hints:
 *This exercise belongs to the chapter&nbsp; [[Channel_Coding/Decoding_of_Convolutional_Codes| "Decoding of Convolutional Codes"]].
-*Reference is made in particular to the page&nbsp; [[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 &ndash;Path finding"]].
@@ Line 31: / Line 38: @@
 ===Questions===
 <quiz display=simple>
-{For which code sequence&nbsp; $\underline{z}$&nbsp; does the decision fall at time&nbsp; $i = 7$?
+{For which estimated sequence&nbsp; $\underline{z}$&nbsp; $($for the encoded sequence&nbsp; $\underline{z})$&nbsp; does the decision fall at time&nbsp; $i = 7$?
 |type="()"}
 - $\underline{z} = (11, \, 10, \, 00, \, 01, \, 01, \, 11, \, 00)$,
@@ Line 37: / Line 44: @@
 - $\underline{z} = (00, \, 11, \, 01, \, 01, \, 00, \, 10, \, 11)$.
-{How many transmission errors (at least) have occurred?
+{How many transmission errors have occurred&nbsp;  $($at least$)$?
 |type="{}"}
-$N_{\rm Bit\:error} \ = \ ${ 3 3% }
+$N_{\rm bit\:error} \ = \ ${ 3 3% }
 {Which information sequence&nbsp; $\underline{v}$&nbsp; does the Viterbi decoder choose?
@@ Line 47: / Line 54: @@
 - $\underline{v} = (0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0)$.
-{Would a final (and correct) decision have been possible already at&nbsp; $i = 6$&nbsp;?
+{Would a final&nbsp; $($and correct$)$&nbsp; decision have been possible already at&nbsp; $i = 6$?
 |type="()"}
 - Yes.
@@ Line 59: / Line 66: @@
 + $S_0 &#8594; S_0 &#8594; S_1 &#8594; S_2 &#8594; S_1 &#8594; S_3$.
-{Which path would you choose at time&nbsp; $i = 5$&nbsp;?
+{Which path would you choose at time&nbsp; $i = 5$?
 |type="()"}
 - $S_0 &#8594; S_0 &#8594; S_1 &#8594; S_3 &#8594; S_2 &#8594; S_0$,

@@ 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&nbsp; [[Aufgaben:3.10_Fehlergr%C3%B6%C3%9Fenberechnung| Aufgabe 3.10]]&nbsp; war nebenstehende Trellis&ndash;Auswertung hinsichtlich der Metriken&nbsp; ${\it \Lambda}_i(S_{\mu})$. Zu allen Decodierschritten&nbsp; $i$&nbsp; wurden die (im Allgemeinen)&nbsp; $2^m = 4$&nbsp; 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.

← Older revision		Revision as of 12: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^]]

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

@@ Line 6: / Line 6: @@
 Ansonsten gelten die gleichen Voraussetzungen wie für die&nbsp; [[Aufgaben:3.10_Fehlergr%C3%B6%C3%9Fenberechnung| Aufgabe 3.10]]. Zum Beispiel kennzeichnet auch in nebenstehender Grafik ein roter Pfeil das Informationsbit&nbsp; $u_i = 0$&nbsp; und ein blauer Pfeil steht für&nbsp; $u_i = 1$.
-In der vorliegenden Aufgabe betrachten wir den zweiten und wichtigen Teil des Viterbi&ndash;Algorithmuses, nämlich die Suche nach den "überlebenden&rdquo; Pfaden&nbsp; ${\it \Phi}_i(S_{\mu})$. Diese befinden sich zum Zeitpunkt&nbsp; $i$&nbsp; im Zustand&nbsp; $S_{\mu}$&nbsp; mit&nbsp;$\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&ndash;Algorithmuses, nämlich die Suche nach den "überlebenden" Pfaden&nbsp; ${\it \Phi}_i(S_{\mu})$. Diese befinden sich zum Zeitpunkt&nbsp; $i$&nbsp; im Zustand&nbsp; $S_{\mu}$&nbsp; mit&nbsp;$\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&nbsp; $i = 7$)&nbsp; gibt es aufgrund der Terminierung nur einen überlebenden Pfad&nbsp; ${\it \Phi}_7(S_0)$. Aus diesem lässt sich extrahieren:

← Older revision		Revision as of 12:49, 23 March 2021
Line 117:		Line 117:


−	[[Category:~~Aufgaben zu Kanalcodierung~~\|^3.4 Decodierung von Faltungscodes^]]	+	[[Category:Channel Coding: Exercises\|^3.4 Decodierung von Faltungscodes^]]