+ The metrics ${\it \Lambda}_i(S_{\mu})$ provide the same information as ${\it \Gamma}_i(S_{\mu})$.
+ Für alle Knoten gilt ${\it \Lambda}_i(S_{\mu}) = 2 \cdot \big [i \, –{\it \Gamma}_i(S_{\mu})\big ]$.
+ For all nodes, ${\it \Lambda}_i(S_{\mu}) = 2 \cdot \big [i \, –{\it \Gamma}_i(S_{\mu})\big ]$.
- Für die Metrikzuwächse gilt $〈 \underline{x}_i', \, \underline{y}_i 〉 ∈ \{0, \, 1, \, 2\}$.
- For the metric increments, $〈 \underline{x}_i', \, \underline{y}_i 〉 ∈ \{0, \, 1, \, 2\}$.
</quiz>
</quiz>
===Musterlösung===
===Solution===
{{ML-Kopf}}
{{ML-Kopf}}
'''(1)''' Bei allen Knoten $S_{\mu}$ muss eine Entscheidung zwischen den beiden ankommenden Zweigen getroffen werden. Ausgewählt wird dann jeweils der Zweig, der zur (minimalen) Fehlergröße ${\it \Gamma}_5(S_{\mu})$ geführt hat. Mit $\underline{y}_5 = (01)$ erhält man:
'''(1)''' At all nodes $S_{\mu}$ a decision must be made between the two incoming branches. The branch that led to the (minimum) error metric ${\it \Gamma}_5(S_{\mu})$ is then selected in each case. With $\underline{y}_5 = (01)$ one obtains:
'''(2)''' Zum Zeitpunk $i = 6$ ist bereits die Terminierung wirksam und es gibt nur noch zwei Fehlergrößen. Für diese erhält man mit $\underline{y}_6 = (01)$:
'''(2)''' At time $i = 6$ the termination is already effective and there are only two branch metrics left. For these one obtains with $\underline{y}_6 = (01)$:
Beim BSC–Modell kann man aus ${\it \Gamma}_7(S_{\mu}) = 3$ darauf schließen, dass drei Übertragungsfehler aufgetreten sind ⇒ <u>Lösungsvorschläge 1 und 3</u>.
In the BSC model, one can infer from ${\it \Gamma}_7(S_{\mu}) = 3$ that three transmission errors occurred ⇒ <u>solutions 1 and 3</u>.
'''(4)''' Richtig sind die <u>Aussagen 1 und 2</u>:
'''(4)''' Correct are <u>statements 1 and 2</u>:
*Die Maximierung der Metriken ${\it \Lambda}_i(S_{\mu})$ entsprechend der rechten Skizze in obiger Grafik liefert das gleiche Ergebnis wie die links dargestellte Minimierung der Fehlergrößen ${\it \Gamma}_i(S_{\mu})$. Auch die überlebenden und gestrichenen Zweige sind in beiden Grafiken identisch.
*Maximizing the branch metrics ${\it \Lambda}_i(S_{\mu})$ according to the right sketch in the above graph gives the same result as minimizing the branch metrics ${\it \Gamma}_i(S_{\mu})$ shown on the left. Also, the surviving and deleted branches are identical in both graphs.
*Die angegebene Gleichung ist ebenfalls richtig, was hier nur am Beispiel $i = 7$ gezeigt wird:
*The given equation is also correct, which is shown here only on the example $i = 7$:
*Die letzte Aussage ist falsch. Vielmehr gilt $〈x_i', \, y_i〉 ∈ \{–2, \, 0, \, +2\}$.
*The last statement is false. Rather applies $〈x_i', \, y_i〉 ∈ \{–2, \, 0, \, +2\}$.
''Hinweis:'' In der [[Aufgaben:Aufgabe_3.11:_Viterbi–Pfadsuche| Aufgabe 3.11]] wird für das gleiche Beispiel die Pfadsuche demonstiert, wobei von den ${\it \Lambda}_i(S_{\mu})$–Metriken gemäß der rechten Grafik ausgegangen wird.
Hints: In [[Aufgaben:Exercise_3.11:_Viterbi_Path_Finding| "Exercise 3.11"]], path finding is demonstrable for the same example, assuming ${\it \Lambda}_i(S_{\mu})$–metrics as shown in the right graph.
In the "theory section" of this chapter, the calculation of the branch metrics ${\it \Gamma}_i(S_{\mu})$ has been discussed in detail, based on the Hamming distance $d_{\rm H}(\underline{x}\hspace{0.05cm}', \ \underline{y}_i)$ between the possible codewords $\underline{x}\hspace{0.05cm}' ∈ \{00, \, 01, \, 10, \, 11\}$ and the 2–bit–words $\underline{y}_i$ received at time $i$ is based.
The exercise deals exactly with this topic. In the adjacent graph
the considered trellis is shown– valid for the code with rate $R = 1/2$, memory $m = 2$ and $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$,
are the received words $\underline{y}_1 = (01), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \underline{y}_7 = (11)$ indicated in the rectangles,
are all branch metrics ${\it \Gamma}_0(S_{\mu}), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ {\it \Gamma}_4(S_{\mu})$ already entered.
For example, the branch metric ${\it \Gamma}_4(S_0)$ with $\underline{y}_4 = (01)$ as the minimum of the two comparison values
The surviving branch – here from ${\it \Gamma}_3(S_2)$ to ${\it \Gamma}_4(S_0)$ – is drawn solid, the eliminated branch from ${\it \Gamma}_3(S_0)$ to ${\it \Gamma}_4(S_0)$ dotted. Red arrows represent the information bit $u_i = 0$, blue arrows $u_i = 1$.
In the subtask (4) the relationship between
the ${\it \Gamma}_i(S_{\mu})$ minimization and
the ${\it \Lambda}_i(S_{\mu})$ maximization.
shall be worked out. Here, we refer to the nodes ${\it \Lambda}_i(S_{\mu})$ as metrics, where the metric increment over the predecessor nodes results from the correlation value $〈\underline{x}_i\hspace{0.05cm}', \, \underline{y}_i 〉$ . For more details on this topic, see the following theory pages:
(1) At all nodes $S_{\mu}$ a decision must be made between the two incoming branches. The branch that led to the (minimum) error metric ${\it \Gamma}_5(S_{\mu})$ is then selected in each case. With $\underline{y}_5 = (01)$ one obtains:
The left graph shows the final evaluated ${\it \Gamma}_i(S_{\mu})$ trellis.
Evaluated trellis diagrams
(2) At time $i = 6$ the termination is already effective and there are only two branch metrics left. For these one obtains with $\underline{y}_6 = (01)$:
In the BSC model, one can infer from ${\it \Gamma}_7(S_{\mu}) = 3$ that three transmission errors occurred ⇒ solutions 1 and 3.
(4) Correct are statements 1 and 2:
Maximizing the branch metrics ${\it \Lambda}_i(S_{\mu})$ according to the right sketch in the above graph gives the same result as minimizing the branch metrics ${\it \Gamma}_i(S_{\mu})$ shown on the left. Also, the surviving and deleted branches are identical in both graphs.
The given equation is also correct, which is shown here only on the example $i = 7$:
