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.
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.
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$.
*The branch with the lower value was discarded. One can recognize discarded branches in the graph by dotted lines.
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:
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$.
* die vom Decodierer ausgewählte Codesequenz $\underline{z}$ ⇒ größtmögliche Wahrscheinlichkeit ${\rm Pr}(\underline{z} = \underline{x})$,
* die dazugehörige Informationssequenz $\underline{v}$ mit der größtmöglichen Wahrscheinlichkeit ${\rm Pr}(\underline{v} = \underline{u})$.
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$)$.
Eine Entscheidung zu einem früheren Zeitpunkt, zum Beispiel bei $i = 5$, erfüllt nicht immer das Maximum–Likelihood–Kriterium. Hier gibt es vier überlebende Pfade ${\it \Phi}_5(S_0), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ {\it \Phi}_5(S_3)$, die zur Zeit $i = 5$ in den Zuständen $S_0, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ S_3$ enden.
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:
*Einer dieser vier Pfade ist mit Sicherheit Teil des Maximum–Likelihood–Pfades, der für $i → ∞$ $($bei Terminierung deutlich früher, hier bei $i = 7)$ der bestmögliche Pfad ist.
* the sequence $\underline{z}$ selected by the decoder $($short: "decoder sequence"$)$ ⇒ highest possible probability ${\rm Pr}(\underline{z} = \underline{x})$,
*Soll aber schon zum Zeitpunkt $i = 5$ ein Zwangsentscheid getroffen werden, so entscheidet man sich meist für den Pfad ${\it \Phi}_5(S_{\mu})$ mit der zu diesem Zeitpunkt größten Metrik ${\it \Lambda}_5(S_{\mu})$.
* 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$.
*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})$.
''Hinweise:''
* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Decodierung_von_Faltungscodes| Decodierung von Faltungscodes]].
*Bezug genommen wird insbesondere auf die Seite [[Kanalcodierung/Decodierung_von_Faltungscodes#Auswerten_des_Trellis_im_fehlerfreien_Fall_.E2.80.93_Pfadsuche|Auswerten des Trellis im fehlerfreien Fall –Pfadsuche]].
<u>Hints:</u>
*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_search|"Evaluating the trellis in the error-free case – Path finding"]].
Line 29:
Line 36:
===Fragebogen===
===Questions===
<quiz display=simple>
<quiz display=simple>
{Für welche Codesequenz $\underline{z}$ fällt die Entscheidung zum Zeitpunkt $i = 7$?
{For which estimated sequence $\underline{z}$ $($for the encoded sequence $\underline{z})$ does the decision fall at time $i = 7$?
'''(1)''' Richtig ist der <u>Lösungsvorschlag 2</u>:
'''(1)''' Correct is the <u>proposed solution 2</u>:
*Eindeutig findet man den überlebenden Pfad durch Rückwärtssuche, also vom Knoten ${\it \Lambda}_7(S_0)$ zum Knoten ${\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)$.
*Anhand der an den Übergängen angegebenen Codesequenz $(00, \, 01, \, 10$ oder $11)$ erhält man somit in Vorwärtsrichtung das Ergebnis gemäß dem <u>Lösungsvorschlag 2</u> ⇒ ${\it \Phi}_7(S_0)$ in Grafik:
*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>:
*Aufgrund des Endwertes ${\it \Lambda}_7(S_0) = 8$ bzw. ${\it \Gamma}_7(S_0) = 3$ – siehe [[Aufgaben:3.10_Fehlergr%C3%B6%C3%9Fenberechnung| Aufgabe 3.10]] – kann man aber davon ausgehen, dass eine richtige Entscheidung ⇒ $\underline{z} = \underline{x}$ getroffen wurde.
one detects <u>three bit errors</u> at positions '''2''', '''5''', and '''8'''.
*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.
'''(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.
*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$.
'''(3)''' Richtig ist der <u>Lösungsvorschlag 1</u>:
*Anhand der Farben des überlebenden Pfades – rot steht für $u_i = 0$ und blau für $u_i = 1$ – erkennt man die Richtigkeit von <u>Lösungsvorschlag 1</u>: rot – blau – rot – blau – blau – rot – rot.
*Es ist anzumerken, dass die eigentliche Informationssequenz $\underline{u}$ nur die Länge $L = 5$ aufweist.
*Erst durch die Terminierung kommt man zur Gesamtlänge $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.
'''(4)''' Zur Zeit $i = 6$ gibt es noch zwei überlebende Pfade. Eine Entscheidung könnte man zwangsweise anhand der größeren Metrik treffen. Wegen ${\it \Lambda}_6(S_0) = {\it \Lambda}_6(S_2) = 6$ ist dies aber in unserem Beispiel nicht möglich ⇒ <u>Nein</u>.
*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)''' Die Grafik zeigt, dass <u>alle Lösungsvorschläge</u> richtig sind. Die Pfade sind mit ${\it \Phi}_5(S_0)$, ... , ${\it \Phi}_5(S_3)$ bezeichnet.
'''(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)''' Die Zwangsentscheidung zum Zeitpunkt $i = 5$ würde den Pfad mit der größten Metrik ${\it \Lambda}_5(S_{\mu})$ auswählen, also den Pfad ${\it \Phi}_5(S_2)$ entsprechend <u>Lösungsvorschlag 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)''' Aufgrund unserer Lösung zur Teilaufgabe (1) wäre der Pfad ${\it \Phi}_5(S_3)$ gemäß <u>Lösungsvorschlag 4</u> die bessere Wahl gewesen.
'''(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)$.
*Dieser ist Teil des Pfades ${\it \Phi}_7(S_0)$.
*Zum Zeitpunkt $i = 5$ spricht aber noch nichts für diese Wahl.
*At time $i = 5$, however, there is still nothing in favor of this choice.
*Der (letztlich richtige) Pfad wird erst durch die beiden Terminierungsbit herausgehoben.
*The (ultimately correct) path is only highlighted by the two termination bits.
{{ML-Fuß}}
{{ML-Fuß}}
[[Category:Aufgaben zu Kanalcodierung|^3.4 Decodierung von Faltungscodes^]]
[[Category:Channel Coding: Exercises|^3.4 Decoding of Convolutional Codes^]]
One result of $\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.
The branch with the lower value was discarded. One can recognize discarded branches in the graph by dotted lines.
Otherwise, the same conditions apply as for $\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$.
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})$.
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)$.
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})$.
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 2-bit sequences $(00, \, 01, \, 10$ or $11)$ given at the transitions, we obtain in the forward direction the result according to proposition 2:
one detects three bit errors at positions 2, 5, and 8.
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 $\text{Exercise 3.10}$ – but one can assume that a correct decision ⇒ $\underline{z} = \underline{x}$ has been made.
Viterbi path finding
(3) Correct is the proposed solution 1:
From the colors of the surviving path – red represents $u_i = 0$ and blue represents $u_i = 1$ – one can see the correctness of solution proposal 1: 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$.
(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 ⇒ No.
(5) The graph shows that all proposed solutions 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 proposition 3.
(7) Based on our solution to subtask (1), the path ${\it \Phi}_5(S_3)$ according to proposition 4 would have been the better choice. This is part of the path to ${\it \Phi}_7(S_0)$.
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.
