Exercise 3.09Z: Viterbi Algorithm again
Die Grafik zeigt das Trellisdiagramm das Faltungscodes entsprechend Aufgabe A3.6, gekennzeichnet durch folgende Größen:
- Rate 1/2 ⇒ $k = 1, \ n = 2$,
- Gedächtnis $m = 1$,
- Übertragungsfunktionsmatrix $\mathbf{G}(D) = (1, \ 1 + D)$,
- Länge der Informationssequenz: $L = 4$,
- Sequenzlänge inklusive Terminierung: $L' = L + m = 5$.
Anhand dieser Darstellung soll die Viterbi–Decodierung schrittweise nachvollzogen werde, wobei von der folgenden Empfangssequenz auszugehen ist: $\underline{y} = (11, \, 01, \, 01, \, 11, \, 01)$.
In das Trellis eingezeichnet sind:
- Der Initialwert ${\it \Gamma}_0(S_0)$ für den Viterbi–Algorithmus wird stets zu $0$ gewählt.
- Die beiden Fehlergrößen für den ersten Decodierschritt $(i = 1)$ erhält man mit $\underline{y}_1 = (11)$ wie folgt:
- $${\it \Gamma}_1(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\it \Gamma}_0(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (11) \big ) = 2 \hspace{0.05cm},$$
- $${\it \Gamma}_1(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\it \Gamma}_0(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (11) \big ) = 0 \hspace{0.05cm}.$$
- Die Fehlergrößen zum Schritt $i = 2$ ⇒ $\underline{y}_2 = (01)$ ergeben sich durch folgende Vergleiche:
- $${\it \Gamma}_2(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{1}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{1}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] =$$
- $$\hspace{1.35cm} = \ \hspace{-0.15cm} {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+0 \right ] = 0\hspace{0.05cm},$$
- $${\it \Gamma}_2(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{1}(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{1}(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] =$$
- $$\ = \ \hspace{-0.15cm} {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+2 \right ] = 2\hspace{0.05cm}.$$
In gleicher Weise sollen Sie
- die Fehlergrößen zu den Zeitpunkten $i = 3, \ i = 4$ und $i = 5$ (Terminierung) berechnen, und
- die jeweils ungünstigeren Wege zu einem Knoten ${\it \Gamma}_i(S_{\mu})$ eliminieren. In der Grafik ist dies für $i = 2$ durch punktierte Linien angedeutet.
Anschließend ist der durchgehende Pfad von ${\it \Gamma}_0(S_0)$ bis ${\it \Gamma}_5(S_0)$ zu finden, wobei die Rückwärtsrichtung zu empfehlen ist. Verfolgt man den gefundenen Pfad in Vorwärtsrichtung, so erkennt man
- die wahrscheinlichste Codesequenz $\underline{z}$ (im Idealfall gleich $\underline{x}$) an den Beschriftungen,
- die wahscheinlichste Informationssequenz $\underline{\upsilon}$ (im Idealfall gleich $\underline{u}$) an den Farben.
Hinweise:
- Die Aufgabe gehört zum Kapitel Kapitel 3.4.
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Fragebogen
Musterlösung
- $${\it \Gamma}_3(S_0) \hspace{-0.25cm} \ = \ \hspace{-0.25cm}{\rm min} \left [0 + d_{\rm H} \big ((00), (01) \big ), \hspace{0.05cm}2 + d_{\rm H} \big ((01), (01) \big ) \right ] $$
- $$\ = \ \hspace{-0.25cm} {\rm min} \left [ 0+1\hspace{0.05cm},\hspace{0.05cm} 2+0 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm},$$
- $${\it \Gamma}_3(S_1) \hspace{-0.25cm} \ = \ \hspace{-0.25cm}{\rm min} \left [0 + d_{\rm H} \big ((11), (01) \big ), \hspace{0.05cm}2 + d_{\rm H} \big ((10), (01) \big ) \right ] $$
- $$\ = \ \hspace{-0.25cm} {\rm min} \left [ 0+1\hspace{0.05cm},\hspace{0.05cm} 2+2 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}.$$
Eliminiert werden also die beiden Teilpfade, die zum Zeitpunkt $i = 2$ vom Zustand $S_1$ ausgehen ⇒ Punktierung in der Grafik.
(2) Analog zur Teilaufgabe (1) erhält man mit $y_4 = (11)$:
- $${\it \Gamma}_4(S_0) \hspace{-0.25cm} \ = \ \hspace{-0.25cm}{\rm min} \left [1 + d_{\rm H} \big ((00), (11) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((01), (11) \big ) \right ] $$
- $$\ = \ \hspace{-0.25cm} {\rm min} \left [ 1+2\hspace{0.05cm},\hspace{0.05cm} 1+1 \right ] \hspace{0.15cm}\underline{= 2}\hspace{0.05cm},$$
- $${\it \Gamma}_4(S_1) \hspace{-0.25cm} \ = \ \hspace{-0.25cm}{\rm min} \left [1 + d_{\rm H} \big ((11), (11) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((10), (11) \big ) \right ] $$
- $$\ = \ \hspace{-0.25cm} {\rm min} \left [ 1+0\hspace{0.05cm},\hspace{0.05cm} 1+1 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}$$
⇒ Eliminierung der beiden Teilpfade $S_0 → S_0$ und $S_1 → S_1$ im Decodierschritt $i = 4$.
- $${\it \Gamma}_5(S_0) \hspace{-0.25cm} \ = \ \hspace{-0.25cm}{\rm min} \left [2 + d_{\rm H} \big ((00), (01) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((01), (01) \big ) \right ] $$
- $$\ = \ \hspace{-0.25cm} {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 1+0 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}.$$
Zu eliminieren ist hier der Teilpfad $S_0 → S_0$.
(4) Die Rückwärtssuche des durchgehenden Pfades von ${\it \Gamma}_5(S_0)$ nach ${\it \Gamma}_0(S_0)$ liefert $S_0 ← S_1 ← S_0 ← S_0 ← S_1 ← S_0$. In Vorwärtsrichtung ergibt dies den Pfad $S_0 → S_1 → S_0 → S_0 → S_1 → S_0$ und die damit die
- die wahrscheinlichste Codesequenz $\underline{z} = (11, \, 01, \, 00, \, 11, \, 01)$,
- die wahrscheinlichste Informationssequenz $\underline{\upsilon} = (1, \, 0, \, 0, \, 1, \, 0)$.
Richtig sind also die Lösungsvorschläge 1 und 3. Ein Vergleich mit dem vorgegebenen Empfangsvektor $\underline{y} = (11, \, 01, \, 01, \, 11, \, 01)$ zeigt, dass das sechste Bit bei der Übertragung verfälscht wurde.
(5) Ohne Terminierung ⇒ endgültige Entscheidung bei $i = 4$ hätte es zwei durchgehende Pfade gegeben:
- von $S_0 → S_1 → S_0 → S_1 → S_0$ (gelb eingezeichnet),
- von $S_0 → S_1 → S_0 → S_0 → S_1$ (den letztendlich richtigen),
Die Zwangsentscheidung zum Zeitpunkt $i = 4$ hätte hier wegen ${\it \Gamma}_4(S_1) < {\it \Gamma}_4(S_0)$ zum zweiten Pfad und damit zum Ergebnis $\underline{\upsilon} = (1, \, 0, \, 0, \, 1)$ geführt. Also zur gleichen Entscheidung wie in der Teilaufgabe (4) mit Terminierungsbit. Es gibt aber viele Konstellationen, bei denen erst das Terminierungsbit die richtige und sichere Entscheidung ermöglicht.
