Aufgaben:Aufgabe 3.09Z: Nochmals Viterbi–Algorithmus: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(9 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung von Faltungscodes}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung von Faltungscodes}}
  
[[Datei:P_ID2656__KC_Z_3_8_neu.png|right|frame|Trellis für einen Rate–1/2–Code mit Gedächtnis $m = 1$]]
+
[[Datei:P_ID2656__KC_Z_3_8_neu.png|right|frame|Trellis für einen Rate–1/2–Code, Gedächtnis  $m = 1$]]
Die Grafik zeigt das Trellisdiagramm das Faltungscodes entsprechend [[Aufgaben:3.6_Zustands%C3%BCbergangsdiagramm| Aufgabe A3.6]], gekennzeichnet durch folgende Größen:
+
Die Grafik zeigt das Trellis des Faltungscodes gemäß  [[Aufgaben:Aufgabe_3.6:_Zustandsübergangsdiagramm| Aufgabe 3.6]], gekennzeichnet durch folgende Größen:
* Rate 1/2  ⇒  $k = 1, \ n = 2$,
+
* Rate 1/2   ⇒   $k = 1, \ n = 2$,
* Gedächtnis $m = 1$,
+
* Gedächtnis  $m = 1$,
* Übertragungsfunktionsmatrix $\mathbf{G}(D) = (1, \ 1 + D)$,
+
* Übertragungsfunktionsmatrix  $\mathbf{G}(D) = (1, \ 1 + D)$,
* Länge der Informationssequenz: $L = 4$,
+
* Länge der Informationssequenz:  $L = 4$,
* Sequenzlänge inklusive Terminierung: $L' = L + m = 5$.
+
* 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)$.
+
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:
 
In das Trellis eingezeichnet sind:
* Der Initialwert ${\it \Gamma}_0(S_0)$ für den Viterbi–Algorithmus wird stets zu $0$ gewählt.
+
* 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:
+
* 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_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}.$$
 
:$${\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:
+
* 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 ] =$$
+
:$${\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},$$
+
:$$\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 ] =$$
+
:$${\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{1.35cm} = \ \hspace{-0.15cm} {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+2 \right ] = 2\hspace{0.05cm}.$$
+
:$$\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  
 
In gleicher Weise sollen Sie  
* die Fehlergrößen zu den Zeitpunkten $i = 3, \ i = 4$ und $i = 5$ (Terminierung) berechnen, und  
+
* 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.
+
* 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
+
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.  
* 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.  
 
  
 +
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.
  
''Hinweise:''
+
 
* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Decodierung_von_Faltungscodes| Kapitel 3.4]].
+
 
* Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
+
 
 +
 
 +
 
 +
 
 +
 
 +
''Hinweis:''  
 +
* Die Aufgabe gehört zum Kapitel  [[Kanalcodierung/Decodierung_von_Faltungscodes| Decodierung von Faltungscodes]].
 +
  
  
Zeile 44: Zeile 52:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Berechnen Sie die minimalen Fehlergrößen für den Zeitpunkt $i = 3$.
+
{Berechnen Sie die minimalen Fehlergrößen für den Zeitpunkt&nbsp; $i = 3$.
 
|type="{}"}
 
|type="{}"}
${\it \Gamma}_3(S_0) \ = \ ${ 1 3% }
+
${\it \Gamma}_3(S_0) \ = \ ${ 1 }
${\it \Gamma}_3(S_1) \ = \ ${ 1 3% }
+
${\it \Gamma}_3(S_1) \ = \ ${ 1 }
  
{Berechnen Sie die minimalen Fehlergrößen für den Zeitpunkt $i = 4$.
+
{Berechnen Sie die minimalen Fehlergrößen für den Zeitpunkt&nbsp; $i = 4$.
 
|type="{}"}
 
|type="{}"}
${\it \Gamma}_4(S_0) \ = \ ${ 2 3% }
+
${\it \Gamma}_4(S_0) \ = \ ${ 2 }
${\it \Gamma}_4(S_1) \ = \ ${ 1 3% }
+
${\it \Gamma}_4(S_1) \ = \ ${ 1 }
  
{Berechnen Sie die minimale Fehlergröße für den Zeitpunkt $i = 5$ (Ende).
+
{Berechnen Sie die minimale Fehlergröße für den Zeitpunkt&nbsp; $i = 5$&nbsp; (Ende).
 
|type="{}"}
 
|type="{}"}
${\it \Gamma}_5(S_0) \ = \ ${ 1 3% }  
+
${\it \Gamma}_5(S_0) \ = \ ${ 1 }  
  
 
{Welche endgültigen Ergebnisse liefert der Viterbi&ndash;Algorithmus:
 
{Welche endgültigen Ergebnisse liefert der Viterbi&ndash;Algorithmus:
Zeile 62: Zeile 70:
 
+ $\underline{z} = (11, \, 01, \, 00, \, 11, \, 01)$.
 
+ $\underline{z} = (11, \, 01, \, 00, \, 11, \, 01)$.
 
- $\underline{z} = (11, \, 01, \, 11, \, 01, \, 00)$.
 
- $\underline{z} = (11, \, 01, \, 11, \, 01, \, 00)$.
+ $\underline{\upsilon} = (1, \, 0, \, 0, \, 1, \, 0)$.
+
+ $\underline{v} = (1, \, 0, \, 0, \, 1, \, 0)$.
- $\underline{\upsilon} = (1, \, 0, \, 1, \, 0, \, 0)$.
+
- $\underline{v} = (1, \, 0, \, 1, \, 0, \, 0)$.
  
 
{Welche Entscheidung wäre ohne Terminierung getroffen worden?
 
{Welche Entscheidung wäre ohne Terminierung getroffen worden?
Zeile 73: Zeile 81:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; [[Datei:P_ID2657__KC_Z_3_8a_v1.png|right|frame|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)$:
+
'''(1)'''&nbsp; [[Datei:P_ID2657__KC_Z_3_8a_v1.png|right|frame|Trellis mit Fehlergrößen]] Ausgehend von&nbsp; ${\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.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 ] $$
+
:$${\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},$$
:$$\hspace{1.35cm} = \ \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.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}.$$
:$${\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{1.35cm} = \ \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 &nbsp;&#8658;&nbsp; Punktierung in der Grafik.
+
Eliminiert werden also die beiden Teilpfade, die zum Zeitpunkt $i = 2$ (also beim dritten Decodierschritt) vom Zustand $S_1$ ausgehen &nbsp; &#8658; &nbsp; Punktierung in der Grafik.
  
  
'''(2)'''&nbsp; Analog zur Teilaufgabe (1) erhält man mit $y_4 = (11)$:
+
'''(2)'''&nbsp; Analog zur Teilaufgabe (1) erhält man mit&nbsp; $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 ] $$
+
:$${\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},$$
:$$\hspace{1.35cm} = \ \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.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}$$
:$${\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{1.35cm} = \ \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}$$
 
  
&#8658;&nbsp; Eliminierung der beiden Teilpfade $S_0 &#8594; S_0$ und $S_1 &#8594; S_1$ im Decodierschritt $i = 4$.
+
&#8658; &nbsp; Eliminierung im vierten Decodierschritt der beiden Teilpfade $S_0 &#8594; S_0$ und $S_1 &#8594; S_1$.
  
  
'''(3)'''&nbsp; [[Datei:P_ID2658__KC_Z_3_8d.png|right|frame|Pfadsuche]] Für $i = 5$ &nbsp;&#8658;&nbsp; Terminierung erhält man mit $\underline{y}_5 = (01)$:
+
[[Datei:P_ID2658__KC_Z_3_8d.png|right|frame|Pfadsuche]]  
:$${\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 ] $$
+
'''(3)'''&nbsp; Für $i = 5$ &nbsp; &#8658; &nbsp; &bdquo;Terminierung&rdquo; erhält man mit&nbsp; $\underline{y}_5 = (01)$:
:$$\hspace{1.35cm} = \ \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}.$$
+
:$${\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 &#8594; S_0$.
 
Zu eliminieren ist hier der Teilpfad $S_0 &#8594; S_0$.
  
  
'''(4)'''&nbsp; Die Rückwärtssuche des durchgehenden Pfades von ${\it \Gamma}_5(S_0)$ nach ${\it \Gamma}_0(S_0)$ liefert $S_0 &#8592; S_1 &#8592; S_0 &#8592; S_0 &#8592; S_1 &#8592; S_0$. In Vorwärtsrichtung ergibt dies den Pfad $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; S_1 &#8594; S_0$ und die damit die  
+
'''(4)'''&nbsp; Die Rückwärtssuche des durchgehenden Pfades von ${\it \Gamma}_5(S_0)$ nach ${\it \Gamma}_0(S_0)$ liefert  
 +
:$$S_0 &#8592; S_1 &#8592; S_0 &#8592; S_0 &#8592; S_1 &#8592; S_0.$$  
 +
 
 +
In Vorwärtsrichtung ergibt dies den Pfad $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; S_1 &#8594; S_0$ und die damit die  
 
* die wahrscheinlichste Codesequenz $\underline{z} = (11, \, 01, \, 00, \, 11, \, 01)$,
 
* die wahrscheinlichste Codesequenz $\underline{z} = (11, \, 01, \, 00, \, 11, \, 01)$,
* die wahrscheinlichste Informationssequenz $\underline{\upsilon} = (1, \, 0, \, 0, \, 1, \, 0)$.
+
* die wahrscheinlichste Informationssequenz $\underline{v} = (1, \, 0, \, 0, \, 1, \, 0)$.
  
  
Richtig sind also die <u>Lösungsvorschläge 1 und 3</u>. Ein Vergleich mit dem vorgegebenen Empfangsvektor $\underline{y} = (11, \, 01, \, 01, \, 11, \, 01)$ zeigt, dass das sechste Bit bei der Übertragung verfälscht wurde.
+
Richtig sind also die <u>Lösungsvorschläge 1 und 3</u>:
 +
*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)'''&nbsp; Ohne Terminierung &#8658; endgültige Entscheidung bei $i = 4$ hätte es zwei durchgehende Pfade gegeben:
 
'''(5)'''&nbsp; Ohne Terminierung &#8658; endgültige Entscheidung bei $i = 4$ hätte es zwei durchgehende Pfade gegeben:
 
* von $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_1 &#8594; S_0$ (gelb eingezeichnet),
 
* von $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_1 &#8594; S_0$ (gelb eingezeichnet),
* von $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; S_1$ (den letztendlich richtigen),
+
* von $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; 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{\upsilon} = (1, \, 0, \, 0, \, 1)$ geführt. Also zur <u>gleichen Entscheidung</u> wie in der Teilaufgabe (4) mit Terminierungsbit. Es gibt aber viele Konstellationen, bei denen erst das Terminierungsbit die richtige und sichere Entscheidung ermöglicht.
+
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 <u>gleichen Entscheidung</u> wie in der Teilaufgabe (4) mit Terminierungsbit.  
 +
*Es gibt aber viele Konstellationen, bei denen erst das Terminierungsbit die richtige und sichere Entscheidung ermöglicht.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 26. Juni 2019, 07:45 Uhr

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:



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

(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 im vierten Decodierschritt der beiden Teilpfade $S_0 → S_0$ und $S_1 → S_1$.


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.