Exercise 3.11: Viterbi Path Finding
Ein Ergebnis von Aufgabe A3.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 diese Zweige an punktierten Linien.
Ansonsten gelten die gleichen Voraussetzungen wie für die Aufgabe A3.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}(S_{\mu})$. Diese befinden sich zum Zeitpunkt $i$ und Zustand $S_{\mu}$. 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:
- die vom Decodierer ausgewählte Codesequenz $\underline{z}$ ⇒ größtmögliche Wahrscheinlichkeit ${\rm Pr}(\underline{z} = \underline{x})$,
- die dazugehörige Informationssequenz $\upsilon$ mit der größtmöglichen Wahrscheinlichkeit ${\rm Pr}(\underline{\upsilon} = \underline{u})$.
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), \ ... \ , \ {\it \Phi}_5(S_3)$, die zur Zeit $i = 5$ in den Zuständen $S_0, \ ... \ , \ S_3$ enden. 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. 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 größten Metrik ${\it \Lambda}_5(S_{\mu})$.
Hinweis:
- Die Aufgabe gehört zum Kapitel Decodierung von Faltungscodes.
Fragebogen
Musterlösung
