Aufgaben:Aufgabe 3.09Z: Nochmals Viterbi–Algorithmus: Unterschied zwischen den Versionen
Aus LNTwww
| (3 dazwischenliegende Versionen von 2 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, 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 Trellis des Faltungscodes gemäß [[Aufgaben:Aufgabe_3.6:_Zustandsübergangsdiagramm| Aufgabe 3.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$. |
| Zeile 13: | Zeile 13: | ||
In das Trellis eingezeichnet sind: | In das Trellis eingezeichnet sind: | ||
| − | * Der Initialwert ${\it \Gamma}_0(S_0)$ für den Viterbi–Algorithmus, der stets zu $0$ gewählt wird. | + | * 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 ] $$ | ||
| − | :$$\Rightarrow\hspace{0.3cm} {\it \Gamma}_2(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm min} \ | + | :$$\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 ]$$ | ||
| − | :$$\Rightarrow\hspace{0.3cm} {\it \Gamma}_2(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm min} \ | + | :$$\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 | + | 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. | ||
| − | '' | + | |
| − | * Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Decodierung_von_Faltungscodes| Decodierung von Faltungscodes]]. | + | |
| − | + | ||
| + | |||
| + | ''Hinweis:'' | ||
| + | * Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Decodierung_von_Faltungscodes| Decodierung von Faltungscodes]]. | ||
| + | |||
| Zeile 47: | 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 $i = 3$. |
|type="{}"} | |type="{}"} | ||
${\it \Gamma}_3(S_0) \ = \ ${ 1 } | ${\it \Gamma}_3(S_0) \ = \ ${ 1 } | ||
${\it \Gamma}_3(S_1) \ = \ ${ 1 } | ${\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 $i = 4$. |
|type="{}"} | |type="{}"} | ||
${\it \Gamma}_4(S_0) \ = \ ${ 2 } | ${\it \Gamma}_4(S_0) \ = \ ${ 2 } | ||
${\it \Gamma}_4(S_1) \ = \ ${ 1 } | ${\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 $i = 5$ (Ende). |
|type="{}"} | |type="{}"} | ||
${\it \Gamma}_5(S_0) \ = \ ${ 1 } | ${\it \Gamma}_5(S_0) \ = \ ${ 1 } | ||
| Zeile 65: | 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{ | + | + $\underline{v} = (1, \, 0, \, 0, \, 1, \, 0)$. |
| − | - $\underline{ | + | - $\underline{v} = (1, \, 0, \, 1, \, 0, \, 0)$. |
{Welche Entscheidung wäre ohne Terminierung getroffen worden? | {Welche Entscheidung wäre ohne Terminierung getroffen worden? | ||
| Zeile 76: | Zeile 81: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' [[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)''' [[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)$: |
| − | :$${\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 ] | + | :$${\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}.$$ | |
| − | :$${\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 ] | ||
| − | |||
| − | Eliminiert werden also die beiden Teilpfade, die zum Zeitpunkt $i = 2$ vom Zustand $S_1$ ausgehen ⇒ Punktierung in der Grafik. | + | 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)$: | + | '''(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 ] | + | :$${\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}$$ | |
| − | :$${\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 ] | ||
| − | |||
| − | ⇒ Eliminierung der beiden Teilpfade $S_0 → S_0$ und $S_1 → S_1 | + | ⇒ Eliminierung im vierten Decodierschritt der beiden Teilpfade $S_0 → S_0$ und $S_1 → S_1$. |
| − | + | [[Datei:P_ID2658__KC_Z_3_8d.png|right|frame|Pfadsuche]] | |
| − | :$${\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 ] | + | '''(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$. | 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$ | + | '''(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 Codesequenz $\underline{z} = (11, \, 01, \, 00, \, 11, \, 01)$, | ||
| − | * die wahrscheinlichste Informationssequenz $\underline{ | + | * die wahrscheinlichste Informationssequenz $\underline{v} = (1, \, 0, \, 0, \, 1, \, 0)$. |
| − | Richtig sind also die <u>Lösungsvorschläge 1 und 3</u> | + | 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)''' Ohne Terminierung ⇒ endgültige Entscheidung bei $i = 4$ hätte es zwei durchgehende Pfade gegeben: | '''(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_1 → S_0$ (gelb eingezeichnet), | ||
| − | * von $S_0 → S_1 → S_0 → S_0 → S_1$ (den letztendlich richtigen) | + | * 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{ | + | 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:
- Die Aufgabe gehört zum Kapitel Decodierung von Faltungscodes.
Fragebogen
Musterlösung
(1) 
Ausgehend von ${\it \Gamma}_2(S_0) = 0, \ {\it \Gamma}_2(S_1) = 2$ erhält man mit $\underline{y}_3 = (01)$:
Trellis mit Fehlergrößen
- $${\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.
