Exercise 3.09Z: Viterbi Algorithm again

• Return to book

Trellis für einen Rate–1/2–Code, Gedächtnis  $m = 1$

Die Grafik zeigt das Trellis des Faltungscodes gemäß  Aufgabe 3.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\hspace{0.05cm}' = 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, der stets zu  $0$  gewählt wird.
• 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 ]$$

$$\Rightarrow\hspace{0.3cm} {\it \Gamma}_2(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm min} \big [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+0 \big ] = 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 ]$$

$$\Rightarrow\hspace{0.3cm} {\it \Gamma}_2(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm min} \big [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+2 \big ] = 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{v}$  $($im Idealfall gleich  $\underline{u})$  an den Farben.

Hinweis:

• Die Aufgabe gehört zum Kapitel  Decodierung von Faltungscodes.

Fragebogen

1

Berechnen Sie die minimalen Fehlergrößen für den Zeitpunkt  $i = 3$.

${\it \Gamma}_3(S_0) \ = \ $

${\it \Gamma}_3(S_1) \ = \ $

2

Berechnen Sie die minimalen Fehlergrößen für den Zeitpunkt  $i = 4$.

${\it \Gamma}_4(S_0) \ = \ $

${\it \Gamma}_4(S_1) \ = \ $

3

Berechnen Sie die minimale Fehlergröße für den Zeitpunkt  $i = 5$  (Ende).

${\it \Gamma}_5(S_0) \ = \ $

4

Welche endgültigen Ergebnisse liefert der Viterbi–Algorithmus:

	$\underline{z} = (11, \, 01, \, 00, \, 11, \, 01)$.
	$\underline{z} = (11, \, 01, \, 11, \, 01, \, 00)$.
	$\underline{v} = (1, \, 0, \, 0, \, 1, \, 0)$.
	$\underline{v} = (1, \, 0, \, 1, \, 0, \, 0)$.

5

Welche Entscheidung wäre ohne Terminierung getroffen worden?

	Die gleiche,
	eine andere.

Musterlösung

Solution

(1) 

Trellis mit Fehlergrößen

Ausgehend von ${\it \Gamma}_2(S_0) = 0, \ {\it \Gamma}_2(S_1) = 2$ erhält man mit $\underline{y}_3 = (01)$:

$${\it \Gamma}_3(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm min} \left [0 + d_{\rm H} \big ((00), (01) \big ), \hspace{0.05cm}2 + d_{\rm H} \big ((01), (01) \big ) \right ] = {\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.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [0 + d_{\rm H} \big ((11), (01) \big ), \hspace{0.05cm}2 + d_{\rm H} \big ((10), (01) \big ) \right ] {\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$ (also beim dritten Decodierschritt) 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.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [1 + d_{\rm H} \big ((00), (11) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((01), (11) \big ) \right ] = {\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.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [1 + d_{\rm H} \big ((11), (11) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((10), (11) \big ) \right ] ={\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$ imvierten Decodierschritt.

Pfadsuche

(3)  Für $i = 5$   ⇒   „Terminierung” erhält man mit $\underline{y}_5 = (01)$:

$${\it \Gamma}_5(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [2 + d_{\rm H} \big ((00), (01) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((01), (01) \big ) \right ] {\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{v} = (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 bei der Übertragung das sechste Bit 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 Pfad).

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{v} = (1, \, 0, \, 0, \, 1)$ geführt.

• Im betrachteten Beispiel 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.