Kanalcodierung/Decodierung von Faltungscodes: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(12 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 8: Zeile 8:
 
== Blockschaltbild und Voraussetzungen ==
 
== Blockschaltbild und Voraussetzungen ==
 
<br>
 
<br>
Ein wesentlicher Vorteil der Faltungscodierung ist, dass es hierfür mit dem Viterbi&ndash;Algorithmus ein sehr effizientes Decodierverfahren gibt. Dieser von [https://de.wikipedia.org/wiki/Andrew_J._Viterbi Andrew James Viterbi] entwickelte Algorithmus wurde bereits im Kapitel [[Digitalsignalübertragung/Viterbi–Empfänger| Viterbi–Empfänger]] des Buches &bdquo;Digitalsignalübertragung&rdquo; im Hinblick auf seinen Einsatz zur Entzerrung beschrieben.  
+
Ein wesentlicher Vorteil der Faltungscodierung ist, dass es hierfür mit dem Viterbi&ndash;Algorithmus ein sehr effizientes Decodierverfahren gibt. Dieser von&nbsp; [https://de.wikipedia.org/wiki/Andrew_J._Viterbi Andrew James Viterbi]&nbsp; entwickelte Algorithmus wurde bereits im Kapitel&nbsp; [[Digitalsignalübertragung/Viterbi–Empfänger| Viterbi–Empfänger]]&nbsp; des Buches &bdquo;Digitalsignalübertragung&rdquo; im Hinblick auf seinen Einsatz zur Entzerrung beschrieben.  
  
 
[[Datei:P ID2651 KC T 3 4 S1 v1.png|center|frame|Systemmodell zur Beschreibung der Decodierung von Faltungscodes|class=fit]]
 
[[Datei:P ID2651 KC T 3 4 S1 v1.png|center|frame|Systemmodell zur Beschreibung der Decodierung von Faltungscodes|class=fit]]
  
 
Für seinen Einsatz als Faltungsdecodierer gehen wir von obigem Blockschaltbild und den folgenden Voraussetzungen aus:<br>
 
Für seinen Einsatz als Faltungsdecodierer gehen wir von obigem Blockschaltbild und den folgenden Voraussetzungen aus:<br>
*Die Informationssequenz $\underline{u} = (u_1, \ u_2, \ \text{...} \ )$ ist hier im Gegensatz zur Beschreibung der linearen Blockcodes &nbsp; &#8658; &nbsp; [[Kanalcodierung/Decodierung_linearer_Blockcodes#Blockschaltbild_und_Voraussetzungen| Hauptkapitel 1]] oder von Reed&ndash;Solomon&ndash;Codes &nbsp; &#8658; &nbsp;  [[Kanalcodierung/Reed%E2%80%93Solomon%E2%80%93Decodierung_beim_Ausl%C3%B6schungskanal#Blockschaltbild_und_Voraussetzungen| Hauptkapitel 2]] im allgemeinen unendlich lang (<i>&bdquo;semi&ndash;infinite&rdquo;</i>&nbsp;). Für die Informationssymbole gilt stets $u_i &#8712; \{0, 1\}$.<br>
+
*Die Informationssequenz&nbsp; $\underline{u} = (u_1, \ u_2, \ \text{...} \ )$&nbsp; ist hier im Gegensatz zur Beschreibung der linearen Blockcodes &nbsp; &#8658; &nbsp; [[Kanalcodierung/Decodierung_linearer_Blockcodes#Blockschaltbild_und_Voraussetzungen| Erstes Hauptkapitel]]&nbsp; oder von Reed&ndash;Solomon&ndash;Codes &nbsp; &#8658; &nbsp;  [[Kanalcodierung/Reed%E2%80%93Solomon%E2%80%93Decodierung_beim_Ausl%C3%B6schungskanal#Blockschaltbild_und_Voraussetzungen| Zweites Hauptkapitel]]&nbsp; im allgemeinen unendlich lang&nbsp; (<i>&bdquo;semi&ndash;infinite&rdquo;</i>&nbsp;). Für die Informationssymbole gilt stets&nbsp; $u_i &#8712; \{0, 1\}$.<br>
  
*Die Codesequenz $\underline{x} = (x_1, \ x_2, \ \text{...})$ mit $x_i &#8712; \{0, 1\}$ hängt außer von $\underline{u}$ auch  von der Coderate $R = 1/n$, dem Gedächtnis $m$ und der Übertragungsfunktionsmatrix $\mathbf{G}(D)$ ab. Bei endlicher Anzahl $L$ an Informationsbits sollte der Faltungscode durch Anfügen von $m$ Nullen terminiert werden:
+
*Die Codesequenz&nbsp; $\underline{x} = (x_1, \ x_2, \ \text{...})$&nbsp; mit&nbsp; $x_i &#8712; \{0, 1\}$&nbsp; hängt außer von&nbsp; $\underline{u}$&nbsp; auch  von der Coderate&nbsp; $R = 1/n$, dem Gedächtnis&nbsp; $m$&nbsp; und der Übertragungsfunktionsmatrix&nbsp; $\mathbf{G}(D)$&nbsp; ab. Bei endlicher Anzahl&nbsp; $L$&nbsp; an Informationsbits sollte der Faltungscode durch Anfügen von&nbsp; $m$&nbsp; Nullen terminiert werden:
  
 
::<math>\underline{u}= (u_1,\hspace{0.05cm} u_2,\hspace{0.05cm} \text{...} \hspace{0.1cm}, u_L, \hspace{0.05cm} 0 \hspace{0.05cm},\hspace{0.05cm} \text{...}  \hspace{0.1cm}, 0 ) \hspace{0.3cm}\Rightarrow \hspace{0.3cm}
 
::<math>\underline{u}= (u_1,\hspace{0.05cm} u_2,\hspace{0.05cm} \text{...} \hspace{0.1cm}, u_L, \hspace{0.05cm} 0 \hspace{0.05cm},\hspace{0.05cm} \text{...}  \hspace{0.1cm}, 0 ) \hspace{0.3cm}\Rightarrow \hspace{0.3cm}
 
\underline{x}= (x_1,\hspace{0.05cm} x_2,\hspace{0.05cm} \text{...}  \hspace{0.1cm}, x_{2L}, \hspace{0.05cm} x_{2L+1} ,\hspace{0.05cm} \text{...}  \hspace{0.1cm}, \hspace{0.05cm} x_{2L+2m} ) \hspace{0.05cm}.</math>
 
\underline{x}= (x_1,\hspace{0.05cm} x_2,\hspace{0.05cm} \text{...}  \hspace{0.1cm}, x_{2L}, \hspace{0.05cm} x_{2L+1} ,\hspace{0.05cm} \text{...}  \hspace{0.1cm}, \hspace{0.05cm} x_{2L+2m} ) \hspace{0.05cm}.</math>
  
*Die Empfangssequenz $\underline{y} = (y_1, \ y_2, \ \text{...} )$ ergibt sich entsprechend dem angenommenen Kanalmodell. Bei einem digitalen Modell wie dem [[Kanalcodierung/Klassifizierung_von_Signalen#Binary_Symmetric_Channel_.E2.80.93_BSC| Binary Symmetric Channel]] (BSC) gilt $y_i &#8712; \{0, 1\}$, so dass die Verfälschung von $\underline{x}$ auf $\underline{y}$ mit der [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung| Hamming&ndash;Distanz]] $d_{\rm H}(\underline{x}, \underline{y})$ quantifiziert werden kann. Die erforderlichen Modifikationen für den [[Kanalcodierung/Klassifizierung_von_Signalen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| AWGN&ndash;Kanal]] folgen im Abschnitt [[Kanalcodierung/Decodierung_von_Faltungscodes#Viterbi.E2.80.93Algorithmus.2C_basierend_auf_Korrelation_und_Metriken| Viterbi&ndash;Algorithmus, basierend auf Korrelation und Metriken]].
+
*Die Empfangssequenz&nbsp; $\underline{y} = (y_1, \ y_2, \ \text{...} )$&nbsp; ergibt sich entsprechend dem angenommenen Kanalmodell. Bei einem digitalen Modell wie dem&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC| Binary Symmetric Channel]]&nbsp; (BSC) gilt&nbsp; $y_i &#8712; \{0, 1\}$, so dass die Verfälschung von&nbsp; $\underline{x}$&nbsp; auf&nbsp; $\underline{y}$&nbsp; mit der&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung| Hamming&ndash;Distanz]]&nbsp; $d_{\rm H}(\underline{x}, \underline{y})$&nbsp; quantifiziert werden kann. Die erforderlichen Modifikationen für den&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| AWGN&ndash;Kanal]]&nbsp; folgen im Abschnitt&nbsp; [[Kanalcodierung/Decodierung_von_Faltungscodes#Viterbi.E2.80.93Algorithmus.2C_basierend_auf_Korrelation_und_Metriken| Viterbi&ndash;Algorithmus, basierend auf Korrelation und Metriken]].
  
*Der Viterbi&ndash;Algorithmus liefert eine Schätzung $\underline{z}$ für die Codesequenz $\underline{x}$ und eine weitere Schätzung $\underline{\upsilon}$ für die Informationssequenz $\underline{u}$. Dabei gilt:
+
*Der Viterbi&ndash;Algorithmus liefert eine Schätzung&nbsp; $\underline{z}$&nbsp; für die Codesequenz&nbsp; $\underline{x}$&nbsp; und eine weitere Schätzung&nbsp; $\underline{v}$&nbsp; für die Informationssequenz&nbsp; $\underline{u}$. Dabei gilt:
  
 
::<math>{\rm Pr}(\underline{z} \ne \underline{x})\stackrel{!}{=}{\rm Minimum}
 
::<math>{\rm Pr}(\underline{z} \ne \underline{x})\stackrel{!}{=}{\rm Minimum}
Zeile 30: Zeile 30:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Fazit:}$&nbsp;  Bei einem digitalen Kanalmodell (zum Beispiel BSC) sucht der Viterbi&ndash;Algorithmus von allen möglichen Codesequenzen $\underline{x}\hspace{0.05cm}'$ diejenige Sequenz $\underline{z}$ mit der minimalen Hamming&ndash;Distanz $d_{\rm H}(\underline{x}\hspace{0.05cm}', \underline{y})$ zur Empfangssequenz $\underline{y}$:
+
$\text{Fazit:}$&nbsp;  Bei einem digitalen Kanalmodell (zum Beispiel dem BSC&ndash;Modell) sucht der Viterbi&ndash;Algorithmus von allen möglichen Codesequenzen&nbsp; $\underline{x}\hspace{0.05cm}'$&nbsp; diejenige Sequenz&nbsp; $\underline{z}$&nbsp; mit der minimalen Hamming&ndash;Distanz&nbsp; $d_{\rm H}(\underline{x}\hspace{0.05cm}', \underline{y})$&nbsp; zur Empfangssequenz&nbsp; $\underline{y}$:
  
 
:<math>\underline{z} = {\rm arg} \min_{\underline{x}\hspace{0.05cm}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm} d_{\rm H}( \underline{x}\hspace{0.05cm}'\hspace{0.02cm},\hspace{0.02cm} \underline{y}  )  
 
:<math>\underline{z} = {\rm arg} \min_{\underline{x}\hspace{0.05cm}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm} d_{\rm H}( \underline{x}\hspace{0.05cm}'\hspace{0.02cm},\hspace{0.02cm} \underline{y}  )  
 
= {\rm arg} \max_{\underline{x}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm} {\rm Pr}( \underline{y}  \hspace{0.05cm} \vert \hspace{0.05cm} \underline{x}')\hspace{0.05cm}.</math>
 
= {\rm arg} \max_{\underline{x}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm} {\rm Pr}( \underline{y}  \hspace{0.05cm} \vert \hspace{0.05cm} \underline{x}')\hspace{0.05cm}.</math>
  
Das bedeutet auch: &nbsp; Der Viterbi&ndash;Algorithmus erfüllt das [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Maximum-a-posteriori.E2.80.93_und_Maximum-Likelihood.E2.80.93Kriterium| Maximum&ndash;Likelihood&ndash;Kriterium]].}}<br>
+
Das bedeutet auch: &nbsp; Der Viterbi&ndash;Algorithmus erfüllt das&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Maximum-a-posteriori.E2.80.93_und_Maximum-Likelihood.E2.80.93Kriterium| Maximum&ndash;Likelihood&ndash;Kriterium]].}}<br>
  
 
== Vorbemerkungen zu den nachfolgenden Decodierbeispielen ==
 
== Vorbemerkungen zu den nachfolgenden Decodierbeispielen ==
 
<br>
 
<br>
Für die Beispiele in diesem Kapitels gelten stets folgende '''Voraussetzungen''':
+
[[Datei:P ID2652 KC T 3 4 S2 v1.png|right|frame|Trellis zur Decodierung der Empfangssequenz&nbsp;  $\underline{y}$|class=fit]]
 +
Für alle Beispiele in diesem Kapitels gelten folgende&nbsp; '''Voraussetzungen''':
  
[[Datei:P ID2652 KC T 3 4 S2 v1.png|right|frame|Trellis zur Decodierung der Empfangssequenz  $\underline{y}$|class=fit]]
+
*Standard&ndash;Faltungscodierer: &nbsp; Rate $R = 1/2$,&nbsp; Gedächtnis&nbsp; $m = 2$;  
*Standard&ndash;Faltungscodierer: &nbsp; Rate $R = 1/2$,&nbsp; Gedächtnis $m = 2$;  
 
 
*Übertragungsfunktionsmatrix: &nbsp; $\mathbf{G}(D) = (1 + D + D^2, 1 + D^2)$;
 
*Übertragungsfunktionsmatrix: &nbsp; $\mathbf{G}(D) = (1 + D + D^2, 1 + D^2)$;
 
*Länge der Informationssequenz: &nbsp; $L = 5$;
 
*Länge der Informationssequenz: &nbsp; $L = 5$;
 
*Berücksichtigung der Terminierung: &nbsp; $L\hspace{0.05cm}' = 7$;  
 
*Berücksichtigung der Terminierung: &nbsp; $L\hspace{0.05cm}' = 7$;  
*Länge der Sequenzen $\underline{x}$ und $\underline{y}$: &nbsp; jeweils  $14$ Bit;
+
*Länge der Sequenzen&nbsp; $\underline{x}$&nbsp; und&nbsp; $\underline{y}$&nbsp;: &nbsp; jeweils  $14$ Bit;
*Aufteilung gemäß $\underline{y} = (\underline{y}_1, \ \underline{y}_2, \ \text{...} \ , \ \underline{y}_7)$ <br>&rArr; &nbsp; Bitpaare $\underline{y}_i &#8712; \{00, 01, 10, 11\}$;
+
*Aufteilung gemäß&nbsp; $\underline{y} = (\underline{y}_1, \ \underline{y}_2, \ \text{...} \ , \ \underline{y}_7)$ <br>&rArr; &nbsp; Bitpaare&nbsp; $\underline{y}_i &#8712; \{00, 01, 10, 11\}$;
 
*Viterbi&ndash;Decodierung mittels Trellisdiagramms:  
 
*Viterbi&ndash;Decodierung mittels Trellisdiagramms:  
::roter Pfeil &nbsp; &rArr; &nbsp; Hypothese $u_i = 0$,  
+
::roter Pfeil &nbsp; &rArr; &nbsp; Hypothese&nbsp; $u_i = 0$,  
::blauer Pfeil &nbsp; &rArr; &nbsp; Hypothese $u_i = 1$;
+
::blauer Pfeil &nbsp; &rArr; &nbsp; Hypothese&nbsp; $u_i = 1$;
*hypothetische Codesequenz $\underline{x}_i\hspace{0.01cm}' &#8712; \{00, 01, 10, 11\}$;
+
*hypothetische Codesequenz&nbsp; $\underline{x}_i\hspace{0.01cm}' &#8712; \{00, 01, 10, 11\}$;
 
*alle hypothetischen Größen mit Apostroph.
 
*alle hypothetischen Größen mit Apostroph.
 
<br clear=all>
 
<br clear=all>
Wir gehen stets davon aus, dass die Viterbi&ndash;Decodierung auf der [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung| Hamming&ndash;Distanz]] $d_{\rm H}(\underline{x}_i\hspace{0.01cm}', \ \underline{y}_i)$ zwischen dem Empfangswort $\underline{y}_i$ und den vier möglichen Codeworten $x_i\hspace{0.01cm}' &#8712; \{00, 01, 10, 11\}$ basiert. Dann gehen wir wie folgt vor:
+
Wir gehen stets davon aus, dass die Viterbi&ndash;Decodierung auf der&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung| Hamming&ndash;Distanz]]&nbsp; $d_{\rm H}(\underline{x}_i\hspace{0.01cm}', \ \underline{y}_i)$&nbsp; zwischen dem Empfangswort&nbsp; $\underline{y}_i$&nbsp; und den vier möglichen Codeworten&nbsp; $x_i\hspace{0.01cm}' &#8712; \{00, 01, 10, 11\}$&nbsp; basiert. Dann gehen wir wie folgt vor:
  
*In den noch leeren Kreisen werden die Fehlergrößen ${\it \Gamma}_i(S_{\mu})$ der Zustände $S_{\mu} (0 &#8804; \mu &#8804; 3)$ zu den Zeitpunkten $i$ eingetragen. Der Startwert ist stets ${\it \Gamma}_0(S_0) = 0$.
+
*In die noch leeren Kreise werden die Fehlergrößen&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; der Zustände&nbsp; $S_{\mu} (0 &#8804; \mu &#8804; 3)$&nbsp; zu den Zeitpunkten&nbsp; $i$&nbsp; eingetragen. Der Startwert ist stets&nbsp; ${\it \Gamma}_0(S_0) = 0$.
  
*Die Fehlergrößen für $i = 1$ und $i = 2$ ergeben sich zu
+
*Die Fehlergrößen für&nbsp; $i = 1$&nbsp; und&nbsp; $i = 2$&nbsp; ergeben sich zu
  
 
::<math>{\it \Gamma}_1(S_0) =d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_1 \big )  \hspace{0.05cm}, \hspace{2.38cm}{\it \Gamma}_1(S_1) = d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_1 \big )  \hspace{0.05cm},</math>
 
::<math>{\it \Gamma}_1(S_0) =d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_1 \big )  \hspace{0.05cm}, \hspace{2.38cm}{\it \Gamma}_1(S_1) = d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_1 \big )  \hspace{0.05cm},</math>
 
::<math>{\it \Gamma}_2(S_0) ={\it \Gamma}_1(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )\hspace{0.05cm}, \hspace{0.6cm}{\it \Gamma}_2(S_1) = {\it \Gamma}_1(S_0)+ d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )  \hspace{0.05cm},\hspace{0.6cm}{\it \Gamma}_2(S_2) ={\it \Gamma}_1(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )\hspace{0.05cm}, \hspace{0.6cm}{\it \Gamma}_2(S_3) = {\it \Gamma}_1(S_1)+ d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )  \hspace{0.05cm}.</math>
 
::<math>{\it \Gamma}_2(S_0) ={\it \Gamma}_1(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )\hspace{0.05cm}, \hspace{0.6cm}{\it \Gamma}_2(S_1) = {\it \Gamma}_1(S_0)+ d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )  \hspace{0.05cm},\hspace{0.6cm}{\it \Gamma}_2(S_2) ={\it \Gamma}_1(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )\hspace{0.05cm}, \hspace{0.6cm}{\it \Gamma}_2(S_3) = {\it \Gamma}_1(S_1)+ d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )  \hspace{0.05cm}.</math>
  
*Ab $i = 3$ hat das Trellis seine Grundform erreicht, und zur Berechnung aller ${\it \Gamma}_i(S_{\mu})$ muss jeweils das Minimum zwischen zwei Summen ermittelt werden:
+
*Ab&nbsp; $i = 3$&nbsp; hat das Trellis seine Grundform erreicht, und zur Berechnung aller&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; muss jeweils das Minimum zwischen zwei Summen ermittelt werden:
  
 
::<math>{\it \Gamma}_i(S_0) ={\rm Min} \left [{\it \Gamma}_{i-1}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm},</math>
 
::<math>{\it \Gamma}_i(S_0) ={\rm Min} \left [{\it \Gamma}_{i-1}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm},</math>
Zeile 70: Zeile 70:
 
::<math>{\it \Gamma}_i(S_3) ={\rm Min} \left [{\it \Gamma}_{i-1}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm}.</math>
 
::<math>{\it \Gamma}_i(S_3) ={\rm Min} \left [{\it \Gamma}_{i-1}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm}.</math>
  
*Von den zwei an einem Knoten ${\it \Gamma}_i(S_{\mu})$ ankommenden Zweigen wird der schlechtere (der zu einem größeren ${\it \Gamma}_i(S_{\mu})$ geführt hätte) eliminiert. Zu jedem Knoten führt dann nur noch ein einziger Zweig.<br>
+
*Von den zwei an einem Knoten&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; ankommenden Zweigen wird der schlechtere (der zu einem größeren&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; geführt hätte) eliminiert. Zu jedem Knoten führt dann nur noch ein einziger Zweig.<br>
  
*Sind alle Fehlergrößen bis einschließlich $i = 7$ ermittelt, so kann der Viterbi&ndash;Algotithmus mit der Suche das zusammenhängenden Pfades vom Ende des Trellis &nbsp; &#8658; &nbsp; ${\it \Gamma}_7(S_0)$ bis zum Anfang &nbsp; &#8658; &nbsp; ${\it \Gamma}_0(S_0)$ abgeschlossen werden.<br>
+
*Sind alle Fehlergrößen bis einschließlich&nbsp; $i = 7$&nbsp; ermittelt, so kann der Viterbi&ndash;Algotithmus mit der Suche des zusammenhängenden Pfades vom Ende des Trellis &nbsp; &#8658; &nbsp; ${\it \Gamma}_7(S_0)$&nbsp; bis zum Anfang &nbsp; &#8658; &nbsp; ${\it \Gamma}_0(S_0)$&nbsp; abgeschlossen werden.<br>
  
*Durch diesen Pfad liegen dann die  am wahrscheinlichsten erscheinende Codesequenz $\underline{z}$ und die wahrscheinlichste Informationssequenz $\underline{v}$ fest.  
+
*Durch diesen Pfad liegen dann die  am wahrscheinlichsten erscheinende Codesequenz&nbsp; $\underline{z}$&nbsp; und die wahrscheinlichste Informationssequenz&nbsp; $\underline{v}$&nbsp; fest.  
*Nicht für alle Empfangssequenzen $\underline{y}$ gilt aber $\underline{z} = \underline{x}$ und $\underline{v} = \underline{u}$. Das heißt: &nbsp; '''Bei zu vielen Übertragungsfehlern versagt auch der Viterbi&ndash;Algorithmus'''.<br>
+
*Nicht für alle Empfangssequenzen&nbsp; $\underline{y}$&nbsp; gilt aber&nbsp; $\underline{z} = \underline{x}$&nbsp; und&nbsp; $\underline{v} = \underline{u}$. Das heißt: &nbsp; '''Bei zu vielen Übertragungsfehlern versagt auch der Viterbi&ndash;Algorithmus'''.<br>
  
 
== Erstellen des Trellis im fehlerfreien Fall &nbsp;&ndash;&nbsp; Fehlergrößenberechnung==
 
== Erstellen des Trellis im fehlerfreien Fall &nbsp;&ndash;&nbsp; Fehlergrößenberechnung==
 
<br>
 
<br>
Zunächst gehen wir von der Empfangssequenz $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$ aus, die hier &ndash; wegen der Codewortlänge $n = 2$ &ndash; bereits in Bitpaare $\underline{y}_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ \underline{y}_7$ unterteilt ist. Die in das Trellis eingetragenen Zahlenwerte und die verschiedenen Stricharten werden im folgenden Text erklärt.<br>
+
Zunächst gehen wir von der Empfangssequenz&nbsp; $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$&nbsp; aus, die hier &ndash; wegen der Codewortlänge&nbsp; $n = 2$&nbsp; &ndash; bereits in Bitpaare&nbsp; $\underline{y}_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ \underline{y}_7$&nbsp; unterteilt ist. Die in das Trellis eingetragenen Zahlenwerte und die verschiedenen Stricharten werden im folgenden Text erklärt.<br>
  
[[Datei:P ID2653 KC T 3 4 S2 v95.png|right|frame|Viterbi–Schema für den Empfangsvektor $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$|class=fit]]
+
[[Datei:KC_T_3_4_S3a_neu.png|right|frame|Viterbi–Schema für den Empfangsvektor&nbsp; $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$|class=fit]]
  
*Ausgehend vom Initialwert ${\it \Gamma}_0(S_0) = 0$ kommt man mit $\underline{y}_1 = (11)$ durch Addition der Hamming-Distanzen
+
*Ausgehend vom Initialwert&nbsp; ${\it \Gamma}_0(S_0) = 0$&nbsp; kommt man mit&nbsp; $\underline{y}_1 = (11)$&nbsp; durch Addition der Hamming-Distanzen
 
:$$d_{\rm H}((00), \ \underline{y}_1) = 2\text{    bzw.    }d_{\rm H}((11), \ \underline{y}_1) = 0$$
 
:$$d_{\rm H}((00), \ \underline{y}_1) = 2\text{    bzw.    }d_{\rm H}((11), \ \underline{y}_1) = 0$$
  
:zu den Fehlergrößen ${\it \Gamma}_1(S_0) = 2, \ {\it \Gamma}_1(S_1) = 0$.<br>
+
:zu den Fehlergrößen&nbsp; ${\it \Gamma}_1(S_0) = 2, \ {\it \Gamma}_1(S_1) = 0$.<br>
  
*Im zweiten Decodierschritt gibt es Fehlergrößen für alle vier Zustände: Mit $\underline{y}_2 = (01)$ erhält man:
+
*Im zweiten Decodierschritt gibt es Fehlergrößen für alle vier Zustände: &nbsp; Mit&nbsp; $\underline{y}_2 = (01)$&nbsp; erhält man:
  
 
::<math>{\it \Gamma}_2(S_0) = {\it \Gamma}_1(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )  = 2+1 = 3 \hspace{0.05cm},</math>
 
::<math>{\it \Gamma}_2(S_0) = {\it \Gamma}_1(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )  = 2+1 = 3 \hspace{0.05cm},</math>
Zeile 95: Zeile 95:
 
::<math>{\it \Gamma}_2(S_3) = {\it \Gamma}_1(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big )  = 0+0=0 \hspace{0.05cm}.</math>
 
::<math>{\it \Gamma}_2(S_3) = {\it \Gamma}_1(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big )  = 0+0=0 \hspace{0.05cm}.</math>
  
*In allen weiteren Decodierschritten müssen jeweils zwei Werte verglichen werden, wobei dem Knoten ${\it \Gamma}_i(S_{\mu})$ stets der kleinere Wert zugewiesen wird. Beispielsweise gilt für $i = 3$ mit $\underline{y}_3 = (01)$:
+
*In allen weiteren Decodierschritten müssen jeweils zwei Werte verglichen werden, wobei dem Knoten&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; stets der kleinere Wert zugewiesen wird. Beispielsweise gilt für&nbsp; $i = 3$&nbsp; mit&nbsp; $\underline{y}_3 = (01)$:
  
::<math>{\it \Gamma}_3(S_0) ={\rm min} \left [{\it \Gamma}_{2}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{2}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \right ] = 3\hspace{0.05cm},</math>
+
::<math>{\it \Gamma}_3(S_0) ={\rm min} \left [{\it \Gamma}_{2}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{2}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \big [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \big ] = 3\hspace{0.05cm},</math>
::<math>{\it \Gamma}_3(S_3) ={\rm min} \left [{\it \Gamma}_{2}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{2}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+0\hspace{0.05cm},\hspace{0.05cm} 0+2 \right ] = 2\hspace{0.05cm}.</math>
+
::<math>{\it \Gamma}_3(S_3) ={\rm min} \left [{\it \Gamma}_{2}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{2}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \big [ 3+0\hspace{0.05cm},\hspace{0.05cm} 0+2 \big ] = 2\hspace{0.05cm}.</math>
  
*Ab $i = 6$ wird im betrachteten Beispiel die Terminierung des Faltungscodes wirksam. Hier sind nur noch zwei Vergleiche zur Bestimmung von ${\it \Gamma}_6(S_0)$ und ${\it \Gamma}_6(S_2)$ anzustellen, und für $i = 7$ nur noch ein Vergleich mit dem Endergebnis ${\it \Gamma}_7(S_0)$.<br>
+
*Ab&nbsp; $i = 6$&nbsp; wird im betrachteten Beispiel die Terminierung des Faltungscodes wirksam. Hier sind nur noch zwei Vergleiche zur Bestimmung von&nbsp; ${\it \Gamma}_6(S_0) = 3$&nbsp; und&nbsp; ${\it \Gamma}_6(S_2)= 0$&nbsp; anzustellen, und für&nbsp; $i = 7$&nbsp; nur noch ein einziger ein Vergleich mit dem Endergebnis&nbsp; ${\it \Gamma}_7(S_0) = 0$.<br>
  
  
Zeile 107: Zeile 107:
 
== Auswerten des Trellis im fehlerfreien Fall &nbsp;&ndash;&nbsp; Pfadsuche==
 
== Auswerten des Trellis im fehlerfreien Fall &nbsp;&ndash;&nbsp; Pfadsuche==
 
<br>
 
<br>
Nachdem alle Fehlergrößen ${\it \Gamma}_i(S_{\mu})$ &nbsp;&ndash;&nbsp; im vorliegenden Beispiel für $1 &#8804; i &#8804; 7$ und $0 &#8804; \mu &#8804; 3$ &nbsp;&ndash;&nbsp; ermittelt wurden, kann der Viterbi&ndash;Decoder mit der Pfadsuche beginnen:<br>
+
Nachdem alle Fehlergrößen&nbsp; ${\it \Gamma}_i(S_{\mu})$ &nbsp;&ndash;&nbsp; im vorliegenden Beispiel für&nbsp; $1 &#8804; i &#8804; 7$&nbsp; und&nbsp; $0 &#8804; \mu &#8804; 3$ &nbsp;&ndash;&nbsp; ermittelt wurden, kann der Viterbi&ndash;Decoder mit der Pfadsuche beginnen:<br>
  
[[Datei:P ID2654 KC T 3 4 S3b v1.png|right|frame|Viterbi–Pfadsuche für für den Empfangsvektor $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$|class=fit]]
+
[[Datei:P ID2654 KC T 3 4 S3b v1.png|right|frame|Viterbi–Pfadsuche für für den Empfangsvektor&nbsp; $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$|class=fit]]
*Die Grafik zeigt das Trellis nach der Fehlergrößenberechnung.  
+
*Die Grafik zeigt das Trellis nach der Fehlergrößenberechnung. Alle Kreise sind mit Zahlenwerten belegt.  
*Alle Kreise sind mit Zahlenwerten belegt.  
 
 
*Allerding ist der in der Grafik bereits eingezeichnete wahrscheinlichste Pfad noch nicht bekannt.
 
*Allerding ist der in der Grafik bereits eingezeichnete wahrscheinlichste Pfad noch nicht bekannt.
 
+
*Von den jeweils zwei an einem Knoten ankommenden Zweigen wird stets nur derjenige bei der abschließenden Pfadsuche herangezogen, der zur minimalen Fehlergröße&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; geführt hat.  
 
+
*Die &bdquo;schlechten&rdquo; Zweige werden verworfen. Sie sind in obiger Grafik jeweils punktiert dargestellt.
*Von den jeweils zwei an einem Knoten ankommenden Zweigen wird stets nur derjenige bei der abschließenden Pfadsuche herangezogen, der zur minimalen Fehlergröße ${\it \Gamma}_i(S_{\mu})$ geführt hat.  
 
*Die &bdquo;schlechten&rdquo; Zweige werden verworfen.  
 
*Sie sind in obiger Grafik jeweils punktiert dargestellt.<br><br>
 
 
<br clear=all>
 
<br clear=all>
 
Die Pfadsuche läuft wie folgt ab:
 
Die Pfadsuche läuft wie folgt ab:
*Ausgehend vom Endwert ${\it \Gamma}_7(S_0)$ wird in Rückwärtsrichtung ein zusammenhängender Pfad bis zum Startwert ${\it \Gamma}_0(S_0)$ gesucht. Erlaubt sind nur die durchgezogenen Zweige. Punktierte Linien können nicht Teil des ausgewählten Pfades sein.<br>
+
*Ausgehend vom Endwert&nbsp; ${\it \Gamma}_7(S_0)$&nbsp; wird in Rückwärtsrichtung ein zusammenhängender Pfad bis zum Startwert&nbsp; ${\it \Gamma}_0(S_0)$&nbsp; gesucht. Erlaubt sind nur die durchgezogenen Zweige. Punktierte Linien können nicht Teil des ausgewählten Pfades sein.<br>
 +
 
 +
*Der ausgewählte Pfad durchläuft von rechts nach links die Zustände&nbsp; $S_0 &#8592; S_2 &#8592; S_1 &#8592; S_0 &#8592; S_2 &#8592; S_3 &#8592; S_1 &#8592; S_0$&nbsp; und ist in der Grafik grau hinterlegt. Es gibt keinen zweiten durchgehenden Pfad von&nbsp; ${\it \Gamma}_7(S_0)$ zu ${\it \Gamma}_0(S_0)$. Das bedeutet: &nbsp; Das Decodierergebnis ist eindeutig.<br>
  
*Der ausgewählte Pfad durchläuft von rechts nach links die Zustände $S_0 &#8592; S_2 &#8592; S_1 &#8592; S_0 &#8592; S_2 &#8592; S_3 &#8592; S_1 &#8592; S_0$ und ist in der Grafik grau hervorgehoben. Es gibt keinen zweiten durchgehenden Pfad von ${\it \Gamma}_7(S_0)$ zu ${\it \Gamma}_0(S_0)$. Das bedeutet: &nbsp; Das Decodierergebnis ist eindeutig.<br>
+
*Das Ergebnis&nbsp; $\underline{v} = (1, 1, 0, 0, 1, 0, 0)$&nbsp; des Viterbi&ndash;Decoders hinsichtlich der Informationssequenz erhält man, wenn man für den durchgehenden Pfad &nbsp;&ndash;&nbsp; nun aber in Vorwärtsrichtung von links nach rechts &nbsp;&ndash;&nbsp; die Farben der einzelnen Zweige auswertet $($rot entspricht einer&nbsp; $0$&nbsp;und blau einer&nbsp; $1)$.<br><br>
  
*Das Ergebnis $\underline{v} = (1, 1, 0, 0, 1, 0, 0)$ des Viterbi&ndash;Decoders hinsichtlich der Informationssequenz erhält man, wenn man für den durchgehenden Pfad &nbsp;&ndash;&nbsp; nun aber in Vorwärtsrichtung von links nach rechts &nbsp;&ndash;&nbsp; die Farben der einzelnen Zweige auswertet (rot entspricht einer $0$, blau einer $1$).<br><br>
+
Aus dem Endwert&nbsp; ${\it \Gamma}_7(S_0) = 0$&nbsp; erkennt man, dass  in diesem ersten Beispiel keine Übertragungsfehler vorlagen:
 +
*Das Decodierergebnis&nbsp; $\underline{z}$&nbsp; stimmt also mit dem Empfangsvektor &nbsp;$\underline{y} = (11, 01, 01, 11, 11, 10, 11)$&nbsp; und der tatsächlichen Codesequenz&nbsp; $\underline{x}$&nbsp; überein.
 +
*Bei fehlerfreier Übertragung  ist &nbsp;$\underline{v}$&nbsp; nicht nur die nach dem ML&ndash;Kriterium wahrscheinlichste Informationssequenz&nbsp; $\underline{u}$, sondern beide sind sogar identisch: &nbsp; $\underline{v} \equiv \underline{u}$.<br>
  
Aus dem Endwert ${\it \Gamma}_7(S_0) = 0$ erkennt man, dass  in diesem ersten Beispiel keine Übertragungsfehler vorlagen:
 
*Das Decodierergebnis $\underline{z}$ stimmt also mit dem Empfangsvektor &nbsp;$\underline{y} = (11, 01, 01, 11, 11, 10, 11)$&nbsp; und der tatsächlichen Codesequenz $\underline{x}$ überein.
 
*Bei fehlerfreier Übertragung  ist &nbsp;$\underline{v}$&nbsp; nicht nur die nach dem ML&ndash;Kriterium wahrscheinlichste Informationssequenz $\underline{u}$, sondern beide sind sogar identisch: &nbsp; $\underline{v} \equiv \underline{u}$.<br>
 
  
 +
<i>Anmerkung:</i> &nbsp; Bei der beschriebenen Decodierung wurde natürlich von der bereits in der Überschrift enthaltenen Information &bdquo;Fehlerfreier Fall&rdquo; kein Gebrauch gemacht.
  
<i>Anmerkung:</i> &nbsp; Bei der beschriebenen Decodierung wurde von der bereits in der Überschrift enthaltenen Information &bdquo;Fehlerfreier Fall&rdquo; natürlich kein Gebrauch gemacht. Nun folgen zwei Beispiele zur Viterbi&ndash;Decodierung  für den fehlerbehafteten Fall. <br>
+
Nun folgen drei Beispiele zur Viterbi&ndash;Decodierung  für den fehlerbehafteten Fall. <br>
  
 
== Decodierbeispiele für den fehlerbehafteten Fall  ==
 
== Decodierbeispiele für den fehlerbehafteten Fall  ==
 
<br>
 
<br>
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 1:}$&nbsp;  Wir gehen hier vom Empfangsvektor &nbsp;$\underline{y} = \big (11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) $&nbsp; aus, der keine gültige Codesequenz $\underline{x}$ darstellt. Die Berechnung der Fehlergrößen ${\it \Gamma}_i(S_{\mu})$ und die Pfadsuche geschieht wie auf der Seite[[Kanalcodierung/Decodierung_von_Faltungscodes#Vorbemerkungen_zu_den_nachfolgenden_Decodierbeispielen| Vorbemerkungen]] beschrieben und auf den beiden  letzten Seite für den fehlerfreien Fall demonstriert.<br>
+
$\text{Beispiel 1:}$&nbsp;  Wir gehen hier vom Empfangsvektor &nbsp;$\underline{y} = \big (11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) $&nbsp; aus, der keine gültige Codesequenz&nbsp;  $\underline{x}$&nbsp; darstellt. Die Berechnung der Fehlergrößen&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; und die Pfadsuche geschieht wie auf der Seite&nbsp; [[Kanalcodierung/Decodierung_von_Faltungscodes#Vorbemerkungen_zu_den_nachfolgenden_Decodierbeispielen| Vorbemerkungen]]&nbsp; beschrieben und auf den beiden  letzten Seite für den fehlerfreien Fall demonstriert.<br>
  
 
[[Datei:P ID2655 KC T 3 4 S4a v1.png|center|frame|Decodierbeispiel mit zwei Bitfehlern|class=fit]]
 
[[Datei:P ID2655 KC T 3 4 S4a v1.png|center|frame|Decodierbeispiel mit zwei Bitfehlern|class=fit]]
  
Als Resümee dieses ersten Beispiels mit obigem Trellis ist festzuhalten:
+
Als&nbsp; '''Resümee'''&nbsp; dieses ersten Beispiels ist festzuhalten:
*Auch hier lässt sich ein eindeutiger Pfad (mit dunkelgrauer Hinterlegung) zurückverfolgen, der zu den folgenden Ergebnissen führt (erkennbar an den Beschriftungen bzw. den Farben dieses Pfades):
+
*Auch beim obigen Trellis  lässt sich ein eindeutiger Pfad (mit dunkelgrauer Hinterlegung) zurückverfolgen, der zu den folgenden Ergebnissen führt <br>(erkennbar an den Beschriftungen bzw. den Farben dieses Pfades):
  
 
::<math>\underline{z} = \big (00\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11 \hspace{0.05cm} \big ) \hspace{0.05cm},</math>
 
::<math>\underline{z} = \big (00\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11 \hspace{0.05cm} \big ) \hspace{0.05cm},</math>
Zeile 152: Zeile 150:
 
*Das Beispiel zeigt, dass eine zu frühe Entscheidung oft nicht zielführend ist. Man erkennt auch die Zweckmäßigkeit der Terminierung: &nbsp; Bei endgültiger Entscheidung bei $i = 5$ (Ende der Informationssequenz) wären die Sequenzen &nbsp;$(0, 1, 0, 1, 1)$&nbsp; und &nbsp;$(1, 1, 1, 1, 0)$&nbsp; noch als gleichwahrscheinlich angesehen worden.<br><br>
 
*Das Beispiel zeigt, dass eine zu frühe Entscheidung oft nicht zielführend ist. Man erkennt auch die Zweckmäßigkeit der Terminierung: &nbsp; Bei endgültiger Entscheidung bei $i = 5$ (Ende der Informationssequenz) wären die Sequenzen &nbsp;$(0, 1, 0, 1, 1)$&nbsp; und &nbsp;$(1, 1, 1, 1, 0)$&nbsp; noch als gleichwahrscheinlich angesehen worden.<br><br>
  
<i>Anmerkungen:</i> &nbsp; Bei der Berechnung von ${\it \Gamma}_5(S_0) = 3$ und ${\it \Gamma}_5(S_1) = 3$ führen hier jeweils die beiden Vergleichszweige zur exakt gleichen minimalen Fehlergröße. In der Grafik sind diese beiden Sonderfälle durch Strichpunktierung markiert.<br>
+
<i>Anmerkungen:</i> &nbsp; Bei der Berechnung von&nbsp; ${\it \Gamma}_5(S_0) = 3$&nbsp; und&nbsp; ${\it \Gamma}_5(S_1) = 3$&nbsp; führen hier jeweils die beiden Vergleichszweige zur exakt gleichen minimalen Fehlergröße. In der Grafik sind diese beiden Sonderfälle durch Strichpunktierung markiert.<br>
  
 
*In diesem Beispiel hat dieser Sonderfall keine Auswirkung auf die Pfadsuche.  
 
*In diesem Beispiel hat dieser Sonderfall keine Auswirkung auf die Pfadsuche.  
Zeile 168: Zeile 166:
  
 
Aus der Grafik erkennt man, dass sich hier der Decoder trotz dreier Bitfehler für den richtigen Pfad (dunkle Hinterlegung) entscheidet.  
 
Aus der Grafik erkennt man, dass sich hier der Decoder trotz dreier Bitfehler für den richtigen Pfad (dunkle Hinterlegung) entscheidet.  
*Es gibt also nicht immer eine Fehlentscheidung, wenn mehr als $d_{\rm F}/2$ Bitfehler aufgetreten sind.  
+
*Es gibt also nicht immer eine Fehlentscheidung, wenn mehr als&nbsp; $d_{\rm F}/2$&nbsp; Bitfehler aufgetreten sind.  
 
*Aber bei statistischer Verteilung der drei Übertragungsfehler würde häufiger falsch entschieden als richtig.}}<br>
 
*Aber bei statistischer Verteilung der drei Übertragungsfehler würde häufiger falsch entschieden als richtig.}}<br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 3:}$&nbsp;  Auch hier gelte <math>\underline{u} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0  \big )\hspace{0.3cm}\Rightarrow \hspace{0.3cm}
+
$\text{Beispiel 3:}$&nbsp;  Auch hier gelte&nbsp; <math>\underline{u} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0  \big )\hspace{0.3cm}\Rightarrow \hspace{0.3cm}
\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) \hspace{0.05cm}.</math> Im Unterschied zum $\text{Beispiel 2}$ ist aber noch ein vierter Bitfehler in Form von $\underline{y}_7 = (01)$ hinzugefügt.
+
\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) \hspace{0.05cm}.</math> Im Unterschied zum&nbsp; $\text{Beispiel 2}$&nbsp; ist aber noch ein vierter Bitfehler in Form von&nbsp; $\underline{y}_7 = (01)$ hinzugefügt.
  
 
[[Datei:P ID2704 KC T 3 4 S4c v1.png|center|frame|Decodierbeispiel mit vier Bitfehlern|class=fit]]
 
[[Datei:P ID2704 KC T 3 4 S4c v1.png|center|frame|Decodierbeispiel mit vier Bitfehlern|class=fit]]
  
*Nun führen beide Zweige im Schritt $i = 7$ zur minimalen Fehlergröße ${\it \Gamma}_7(S_0) = 4$, erkennbar an den strichpunktierten Übergängen. Entscheidet man sich im dann erforderlichen Losverfahren für den dunkel hinterlegten Pfad, so wird auch bei vier Bitfehlern  noch die richtige Entscheidung getroffen:  &nbsp; $\underline{v} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0  \big )$. <br>
+
*Nun führen beide Zweige im Schritt&nbsp; $i = 7$&nbsp; zur minimalen Fehlergröße&nbsp; ${\it \Gamma}_7(S_0) = 4$, erkennbar an den strichpunktierten Übergängen. Entscheidet man sich im dann erforderlichen Losverfahren für den dunkel hinterlegten Pfad, so wird auch bei vier Bitfehlern  noch die richtige Entscheidung getroffen:  &nbsp; $\underline{v} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0  \big )$. <br>
  
*Andernfalls kommt es zu einer Fehlentscheidung. Je nachdem, wie das Auswürfeln im Schritt $i =6$ zwischen den beiden strichpunktierten Konkurrenten ausgeht, entscheidet man sich entweder für den violetten oder den hellgrauen Pfad.  Mit dem richtigen Pfad haben beide wenig gemein.}}
+
*Andernfalls kommt es zu einer Fehlentscheidung. Je nachdem, wie das Auswürfeln im Schritt&nbsp; $i =6$&nbsp; zwischen den beiden strichpunktierten Konkurrenten ausgeht, entscheidet man sich entweder für den violetten oder den hellgrauen Pfad.  Mit dem richtigen Pfad haben beide wenig gemein.}}
  
  
Zeile 185: Zeile 183:
 
== Zusammenhang zwischen Hamming–Distanz und Korrelation ==
 
== Zusammenhang zwischen Hamming–Distanz und Korrelation ==
 
<br>
 
<br>
Insbesondere beim [[Kanalcodierung/Klassifizierung_von_Signalen#Binary_Symmetric_Channel_.E2.80.93_BSC| BSC&ndash;Modell]] &ndash; aber auch bei jedem anderen Binärkanal &nbsp; &#8658; &nbsp; Eingang $x_i &#8712; \{0,1\}$, Ausgang $y_i &#8712; \{0,1\}$ wie zum Beispiel dem [[Digitalsignalübertragung/Bündelfehlerkanäle#Kanalmodell_nach_Gilbert.E2.80.93Elliott| Gilbert&ndash;Elliott&ndash;Modell]] &ndash; liefert die Hamming&ndash;Distanz $d_{\rm H}(\underline{x}, \ \underline{y})$ genau die gleiche Information über die Ähnlichkeit der Eingangsfolge $\underline{x}$ und der Ausgangsfolge $\underline{y}$ wie das [[Digitalsignalübertragung/Signale,_Basisfunktionen_und_Vektorräume#Zur_Nomenklatur_im_vierten_Kapitel| innere Produkt]]. Nimmt man an, dass die beiden Folgen in bipolarer Darstellung vorliegen (gekennzeichnet durch Tilden) und dass die Folgenlänge jeweils $L$ ist, so gilt für das innere Produkt:
+
Insbesondere beim&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC| BSC&ndash;Modell]]&nbsp; &ndash; aber auch bei jedem anderen Binärkanal &nbsp; &#8658; &nbsp; Eingang&nbsp; $x_i &#8712; \{0,1\}$,&nbsp; Ausgang $y_i &#8712; \{0,1\}$&nbsp; wie zum Beispiel dem&nbsp; [[Digitalsignalübertragung/Bündelfehlerkanäle#Kanalmodell_nach_Gilbert.E2.80.93Elliott| Gilbert&ndash;Elliott&ndash;Modell]]&nbsp; &ndash; liefert die Hamming&ndash;Distanz&nbsp; $d_{\rm H}(\underline{x}, \ \underline{y})$&nbsp; genau die gleiche Information über die Ähnlichkeit der Eingangsfolge&nbsp; $\underline{x}$&nbsp; und der Ausgangsfolge&nbsp; $\underline{y}$&nbsp; wie das&nbsp; [[Digitalsignalübertragung/Signale,_Basisfunktionen_und_Vektorräume#Zur_Nomenklatur_im_vierten_Kapitel| innere Produkt]]. Nimmt man an, dass die beiden Folgen in bipolarer Darstellung vorliegen (gekennzeichnet durch Tilden) und dass die Folgenlänge jeweils&nbsp; $L$&nbsp; ist, so gilt für das innere Produkt:
  
 
::<math><\hspace{-0.1cm}\underline{\tilde{x}}, \hspace{0.05cm}\underline{\tilde{y}} \hspace{-0.1cm}> \hspace{0.15cm}
 
::<math><\hspace{-0.1cm}\underline{\tilde{x}}, \hspace{0.05cm}\underline{\tilde{y}} \hspace{-0.1cm}> \hspace{0.15cm}
 
= \sum_{i = 1}^{L} \tilde{x}_i \cdot \tilde{y}_i \hspace{0.3cm}{\rm mit } \hspace{0.2cm} \tilde{x}_i = 1 - 2 \cdot x_i  \hspace{0.05cm},\hspace{0.2cm} \tilde{y}_i = 1 - 2 \cdot y_i \hspace{0.05cm},\hspace{0.2cm} \tilde{x}_i, \hspace{0.05cm}\tilde{y}_i \in \hspace{0.1cm}\{ -1, +1\} \hspace{0.05cm}.</math>
 
= \sum_{i = 1}^{L} \tilde{x}_i \cdot \tilde{y}_i \hspace{0.3cm}{\rm mit } \hspace{0.2cm} \tilde{x}_i = 1 - 2 \cdot x_i  \hspace{0.05cm},\hspace{0.2cm} \tilde{y}_i = 1 - 2 \cdot y_i \hspace{0.05cm},\hspace{0.2cm} \tilde{x}_i, \hspace{0.05cm}\tilde{y}_i \in \hspace{0.1cm}\{ -1, +1\} \hspace{0.05cm}.</math>
  
Wir bezeichnen dieses innere Produkt manchmal auch als &bdquo;Korrelationswert&rdquo;. Die Anführungszeichen sollen darauf hinweisen, dass der Wertebereich eines [[Stochastische_Signaltheorie/Zweidimensionale_Zufallsgr%C3%B6%C3%9Fen#Korrelationskoeffizient| Korrelationskoeffizienten]] eigentlich $&plusmn;1$ ist.<br>
+
Wir bezeichnen dieses innere Produkt manchmal auch als den&nbsp; "'''Korrelationswert'''".&nbsp; Im Unterschied zum&nbsp; [[Stochastische_Signaltheorie/Zweidimensionale_Zufallsgr%C3%B6%C3%9Fen#Korrelationskoeffizient| Korrelationskoeffizienten]]&nbsp; kann der Korrelationswert den Wertebereich&nbsp;  $&plusmn;1$&nbsp; durchaus überschreiten.<br>
  
 +
[[Datei:KC_T_3_4_S5_neu.png|right|frame|Zusammenhang zwischen Haming–Distanz und Korrelationswert |class=fit]]
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 4:}$&nbsp;  Wir betrachten hier zwei Binärfolgen der Länge $L = 10$.<br>
+
$\text{Beispiel 4:}$&nbsp;  Wir betrachten hier zwei Binärfolgen der Länge&nbsp; $L = 10$.<br>
*Links dargestellt sind die unipolaren Folgen $\underline{x}$ und $\underline{y}$ sowie das Produkt $\underline{x} \cdot \underline{y}$. Man erkennt die Hamming&ndash;Distanz $d_{\rm H}(\underline{x}, \ \underline{y}) = 6$ &nbsp;&#8658;&nbsp; sechs Bitfehler an den Pfeilpositionen. Das innere Produkt $&#9001;\underline{x} \cdot \underline{y}&#9002; = 0$ hat hier keine Aussagekraft. Zum Beispiel ist $&#9001;\underline{0} \cdot \underline{y}&#9002;$ unabhängig von $\underline{y}$ stets Null.
+
*Links dargestellt sind die unipolaren Folgen&nbsp; $\underline{x}$&nbsp; und&nbsp; $\underline{y}$&nbsp; sowie das Produkt&nbsp; $\underline{x} \cdot \underline{y}$.  
 +
*Man erkennt die Hamming&ndash;Distanz&nbsp; $d_{\rm H}(\underline{x}, \ \underline{y}) = 6$ &nbsp; &#8658; &nbsp; sechs Bitfehler an den Pfeilpositionen.  
 +
*Das innere Produkt&nbsp; $ < \underline{x} \cdot \underline{y} > \hspace{0.15cm} = \hspace{0.15cm}0$&nbsp; hat hier keine Aussagekraft. Zum Beispiel ist&nbsp; $< \underline{0} \cdot \underline{y} >&nbsp;$ unabhängig von&nbsp; $\underline{y}$&nbsp; stets Null.
 +
 
  
*Die Hamming&ndash;Distanz $d_{\rm H} = 6$ erkennt man auch aus der bipolaren (antipodalen) Darstellung der rechten Grafik. Die &bdquo;Korrelationswert&rdquo; hat nun den richtigen Wert $4 \cdot (+1) + 6 \cdot (&ndash;1) = \, &ndash;2$. Es gilt der deterministische Zusammenhang zwischen den beiden Größen mit der Folgenlänge $L$:
+
Die Hamming&ndash;Distanz&nbsp; $d_{\rm H} = 6$&nbsp; erkennt man auch aus der bipolaren (antipodalen) Darstellung der rechten Grafik.  
 +
*Die &bdquo;Korrelationswert&rdquo; hat nun den richtigen Wert:
 +
:$$4 \cdot (+1) + 6 \cdot (-1) = \, -2.$$
 +
*Es gilt der deterministische Zusammenhang zwischen den beiden Größen mit der Folgenlänge&nbsp; $L$:
  
[[Datei:KC_T_3_4_S5_version2.png|right|frame|Zusammenhang zwischen Haming–Distanz und „Korrelation” |class=fit]]
+
:$$ < \underline{ \tilde{x} } \cdot \underline{\tilde{y} } > \hspace{0.15cm} = \hspace{0.15cm} L - 2 \cdot d_{\rm H} (\underline{\tilde{x} }, \hspace{0.05cm}\underline{\tilde{y} })\hspace{0.05cm}. $$}}
::<math><\hspace{-0.1cm}\underline{\tilde{x} }, \hspace{0.05cm}\underline{\tilde{y} } \hspace{-0.1cm}> \hspace{0.15cm}
 
= L - 2 \cdot d_{\rm H} (\underline{\tilde{x} }, \hspace{0.05cm}\underline{\tilde{y} })\hspace{0.05cm}.</math>
 
 
<br clear=all>
 
<br clear=all>
 
 
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Fazit:}$&nbsp;  Interpretieren wir nun diese Gleichung für einige Sonderfälle:
 
$\text{Fazit:}$&nbsp;  Interpretieren wir nun diese Gleichung für einige Sonderfälle:
*Identische Folgen: Die Hamming&ndash;Distanz ist gleich $0$ und der &bdquo;Korrelationswert&rdquo; gleich $L$.<br>
+
*Identische Folgen: &nbsp; Die Hamming&ndash;Distanz ist gleich&nbsp; $0$&nbsp; und der &bdquo;Korrelationswert&rdquo; gleich&nbsp; $L$.<br>
  
*Invertierte: Folgen: Die Hamming&ndash;Distanz ist gleich $L$ und der &bdquo;Korrelationswert&rdquo; gleich $-L$.<br>
+
*Invertierte: Folgen: &nbsp; Die Hamming&ndash;Distanz ist gleich&nbsp; $L$&nbsp; und der &bdquo;Korrelationswert&rdquo; gleich&nbsp; $-L$.<br>
  
*Unkorrelierte Folgen: Die Hamming&ndash;Distanz ist gleich $L/2$, der &bdquo;Korrelationswert&rdquo; gleich $0$.}}
+
*Unkorrelierte Folgen: &nbsp; Die Hamming&ndash;Distanz ist gleich&nbsp; $L/2$, der &bdquo;Korrelationswert&rdquo; gleich&nbsp; $0$.}}
  
 
== Viterbi–Algorithmus, basierend auf Korrelation und Metriken ==
 
== Viterbi–Algorithmus, basierend auf Korrelation und Metriken ==
Zeile 219: Zeile 220:
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Alternative Beschreibung:}$&nbsp;   
 
$\text{Alternative Beschreibung:}$&nbsp;   
Der Viterbi&ndash;Algorithmus sucht von allen möglichen Codesequenzen $\underline{x}' &#8712; \mathcal{C}$ die Sequenz $\underline{z}$ mit dem maximalen &bdquo; Korrelationswert&rdquo; zur Empfangssequenz $\underline{y}$:
+
Der Viterbi&ndash;Algorithmus sucht von allen möglichen Codesequenzen&nbsp; $\underline{x}' &#8712; \mathcal{C}$&nbsp; die Sequenz&nbsp; $\underline{z}$&nbsp; mit dem maximalen &bdquo; Korrelationswert&rdquo; zur Empfangssequenz&nbsp; $\underline{y}$:
  
 
::<math>\underline{z} = {\rm arg} \max_{\underline{x}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm} \left\langle \tilde{\underline{x} }'\hspace{0.05cm} ,\hspace{0.05cm}  \tilde{\underline{y} } \right\rangle
 
::<math>\underline{z} = {\rm arg} \max_{\underline{x}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm} \left\langle \tilde{\underline{x} }'\hspace{0.05cm} ,\hspace{0.05cm}  \tilde{\underline{y} } \right\rangle
  \hspace{0.4cm}{\rm mit }\hspace{0.4cm}\tilde{\underline{x} }'= 1 - 2 \cdot \underline{x}'\hspace{0.05cm}, \hspace{0.2cm}
+
  \hspace{0.4cm}{\rm mit }\hspace{0.4cm}\tilde{\underline{x} }\hspace{0.05cm}'= 1 - 2 \cdot \underline{x}'\hspace{0.05cm}, \hspace{0.2cm}
 
  \tilde{\underline{y} }= 1 - 2 \cdot \underline{y}
 
  \tilde{\underline{y} }= 1 - 2 \cdot \underline{y}
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
$&#9001;\ \text{ ...} \  &#9002;$ bezeichnet einen &bdquo;Korrelationswert&rdquo; entsprechend den Aussagen auf der letzten Seite. Die Tilden weisen wieder auf die bipolare (antipodale) Darstellung hin.}}<br>
+
$&#9001;\ \text{ ...} \  &#9002;$&nbsp; bezeichnet einen &bdquo;Korrelationswert&rdquo; entsprechend den Aussagen auf der letzten Seite. Die Tilden weisen wieder auf die bipolare (antipodale) Darstellung hin.}}<br>
 +
 
 +
Die Grafik zeigt die diesbezügliche Trellisauswertung. Zugrunde liegt wie für die&nbsp; [[Kanalcodierung/Decodierung_von_Faltungscodes#Decodierbeispiele_f.C3.BCr_den_fehlerbehafteten_Fall| Trellisauswertung gemäß Beispiel 1]]&nbsp; &ndash; basierend auf der minimalen Hamming&ndash;Distanz und den Fehlergrößen ${\it \Gamma}_i(S_{\mu})$ &ndash; wieder die Eingangsfolge&nbsp;
 +
$\underline{u} = \big (0\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0 \hspace{0.05cm} \big )$ &nbsp; &rArr; &nbsp; Codefolge
 +
$\underline{x} = \big (00, 11, 10, 00, 01, 01, 11 \big ) \hspace{0.05cm}.$
  
Die Grafik zeigt die diesbezügliche Trellisauswertung. Zugrunde liegt wie für die [[Kanalcodierung/Decodierung_von_Faltungscodes#Decodierbeispiele_f.C3.BCr_den_fehlerbehafteten_Fall| Trellisauswertung gemäß Beispiel 1]] &ndash; basierend auf der minimalen Hamming&ndash;Distanz und den Fehlergrößen ${\it \Gamma}_i(S_{\mu})$ &ndash; wieder
 
 
[[Datei:P ID2663 KC T 3 4 S6 v1.png|right|frame|Viterbi–Decodierung, basierend auf Korrelation und Metrik|class=fit]]
 
[[Datei:P ID2663 KC T 3 4 S6 v1.png|right|frame|Viterbi–Decodierung, basierend auf Korrelation und Metrik|class=fit]]
*der Standard&ndash;Faltungscodierer:<br> Rate $R = 1/2$,Gedächtnis $m = 2$;  
+
Weiter werden vorausgesetzt:
*die Übertragungsfunktionsmatrix:<br> $\mathbf{G}(D) = (1 + D + D^2, 1 + D^2)$;
+
*der Standard&ndash;Faltungscodierer: &nbsp; Rate&nbsp; $R = 1/2$,&nbsp; Gedächtnis&nbsp; $m = 2$;  
*Länge der Informationssequenz: $L = 5$;
+
*die Übertragungsfunktionsmatrix: &nbsp; $\mathbf{G}(D) = (1 + D + D^2, 1 + D^2)$;
*Berücksichtigung der Terminierung: $L' = 7$;  
+
*Länge der Informationssequenz: &nbsp; $L = 5$;
*der Empfangsvektor $\underline{y} = (11, 11, 10, 00, 01, 01, 11)$
+
*Berücksichtigung der Terminierung: &nbsp;$L' = 7$;  
 +
*der Empfangsvektor &nbsp; $\underline{y} = (11, 11, 10, 00, 01, 01, 11)$ <br>&rArr; &nbsp; zwei Bitfehler zu Beginn;
 
*Viterbi&ndash;Decodierung mittels Trellisdiagramms:  
 
*Viterbi&ndash;Decodierung mittels Trellisdiagramms:  
::roter Pfeil &rArr; &nbsp; Hypothese $u_i = 0$,  
+
**roter Pfeil &rArr; &nbsp; Hypothese $u_i = 0$,  
::blauer Pfeil &rArr; &nbsp; Hypothese $u_i = 1$.
+
**blauer Pfeil &rArr; &nbsp; Hypothese $u_i = 1$.
 +
 
  
Beide Darstellungen ähneln sich sehr.<br clear=all>
+
Nebenstehendes Trellis und die&nbsp;  [[Kanalcodierung/Decodierung_von_Faltungscodes#Decodierbeispiele_f.C3.BCr_den_fehlerbehafteten_Fall| Trellisauswertung gemäß Beispiel 1]]&nbsp; ähneln sich sehr. Ebenso wie die Suche nach der Sequenz mit der minimalen Hamming&ndash;Distanz geschieht auch die&nbsp; <i>Suche nach dem maximalen Korrelationswert</i>&nbsp; schrittweise:  
Ebenso wie die Suche nach der Sequenz mit der minimalen Hamming&ndash;Distanz geschieht auch die <i>Suche nach dem maximalen Korrelationswert</i> schrittweise:  
+
*Die Knoten bezeichnet man hier als die Metriken&nbsp; ${\it \Lambda}_i(S_{\mu})$.  
*Die Knoten bezeichnet man hier als die Metriken ${\it \Lambda}_i(S_{\mu})$. Die englische Bezeichnung hierfür ist <i>Cumulative Metric</i>, während  <i>Branch Metric</i> den Metrikzuwachs angibt.<br>
+
*Die englische Bezeichnung hierfür ist&nbsp; <i>Cumulative Metric</i>, während&nbsp; <i>Branch Metric</i>&nbsp; den Metrikzuwachs angibt.<br>
  
*Der Endwert ${\it \Lambda}_7(S_0) = 10$ gibt den &bdquo;Korrelationswert&rdquo; zwischen der ausgewählten Folge $\underline{z}$ und dem Empfangsvektor $\underline{y}$ an. Im fehlerfreien Fall ergäbe sich ${\it \Lambda}_7(S_0) = 14$.<br><br>
+
*Der Endwert&nbsp; ${\it \Lambda}_7(S_0) = 10$&nbsp; gibt den &bdquo;Korrelationswert&rdquo; zwischen der ausgewählten Folge&nbsp; $\underline{z}$&nbsp; und dem Empfangsvektor&nbsp; $\underline{y}$&nbsp; an.  
 +
*Im fehlerfreien Fall ergäbe sich&nbsp; ${\it \Lambda}_7(S_0) = 14$.<br><br>
  
Die folgende Detailbeschreibung der Trellisauswertung beziehen sich auf das obige Trellisdiagramm:
+
{{GraueBox|TEXT= 
 +
$\text{Beispiel 5:}$&nbsp;  Die folgende Detailbeschreibung der Trellisauswertung beziehen sich auf das obige Trellis:
  
*Die Metriken zum Zeitpunkt $i = 1$ ergeben sich mit $\underline{y}_1 = (11)$ zu
+
*Die Metriken zum Zeitpunkt&nbsp; $i = 1$&nbsp; ergeben sich mit&nbsp; $\underline{y}_1 = (11)$&nbsp; zu
  
 
::<math>{\it \Lambda}_1(S_0) \hspace{0.15cm}  =  \hspace{0.15cm} <\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm}
 
::<math>{\it \Lambda}_1(S_0) \hspace{0.15cm}  =  \hspace{0.15cm} <\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm}
Zeile 256: Zeile 264:
 
= \hspace{0.1cm} +2  \hspace{0.05cm}.</math>
 
= \hspace{0.1cm} +2  \hspace{0.05cm}.</math>
  
*Entsprechend gilt zum Zeitpunkt $i = 2$ mit $\underline{y}_2 = (11)$:
+
*Entsprechend gilt zum Zeitpunkt&nbsp; $i = 2$&nbsp; mit&nbsp; $\underline{y}_2 = (11)$:
  
 
::<math>{\it \Lambda}_2(S_0) =  {\it \Lambda}_1(S_0) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm}
 
::<math>{\it \Lambda}_2(S_0) =  {\it \Lambda}_1(S_0) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm}
Zeile 267: Zeile 275:
 
= \hspace{0.1cm} +2+0 = +2  \hspace{0.05cm}.</math>
 
= \hspace{0.1cm} +2+0 = +2  \hspace{0.05cm}.</math>
  
*Ab dem Zeitpunkt $i =3$ muss eine Entscheidung zwischen zwei Metriken getroffen werden. Beispielsweise erhält man mit $\underline{y}_3 = (10)$ für die oberste und die unterste Metrik im Trellis:
+
*Ab dem Zeitpunkt&nbsp; $i =3$&nbsp; muss eine Entscheidung zwischen zwei Metriken getroffen werden. Beispielsweise erhält man mit&nbsp; $\underline{y}_3 = (10)$&nbsp; für die oberste und die unterste Metrik im Trellis:
  
 
::<math>{\it \Lambda}_3(S_0)={\rm max} \left [{\it \Lambda}_{2}(S_0) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm} \hspace{0.05cm}, \hspace{0.2cm}{\it \Lambda}_{2}(S_1) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}> \right ] = {\rm max} \left [ -4+0\hspace{0.05cm},\hspace{0.05cm} +2+0 \right ] = +2\hspace{0.05cm},</math>
 
::<math>{\it \Lambda}_3(S_0)={\rm max} \left [{\it \Lambda}_{2}(S_0) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm} \hspace{0.05cm}, \hspace{0.2cm}{\it \Lambda}_{2}(S_1) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}> \right ] = {\rm max} \left [ -4+0\hspace{0.05cm},\hspace{0.05cm} +2+0 \right ] = +2\hspace{0.05cm},</math>
 
::<math>{\it \Lambda}_3(S_3) ={\rm max} \left [{\it \Lambda}_{2}(S_1) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(01)\hspace{0.05cm}, \hspace{0.05cm}(10) \hspace{-0.05cm}>\hspace{0.2cm} \hspace{0.05cm}, \hspace{0.2cm}{\it \Lambda}_{2}(S_3) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(10)\hspace{0.05cm}, \hspace{0.05cm}(10) \hspace{-0.05cm}> \right ] = {\rm max} \left [ 0+0\hspace{0.05cm},\hspace{0.05cm} +2+2 \right ] = +4\hspace{0.05cm}.</math>
 
::<math>{\it \Lambda}_3(S_3) ={\rm max} \left [{\it \Lambda}_{2}(S_1) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(01)\hspace{0.05cm}, \hspace{0.05cm}(10) \hspace{-0.05cm}>\hspace{0.2cm} \hspace{0.05cm}, \hspace{0.2cm}{\it \Lambda}_{2}(S_3) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(10)\hspace{0.05cm}, \hspace{0.05cm}(10) \hspace{-0.05cm}> \right ] = {\rm max} \left [ 0+0\hspace{0.05cm},\hspace{0.05cm} +2+2 \right ] = +4\hspace{0.05cm}.</math>
  
Vergleicht man die zu zu maximierenden Metriken ${\it \Lambda}_i(S_{\mu})$ mit den zu minimierenden Fehlergrößen ${\it \Gamma}_i(S_{\mu})$ gemäß [[Kanalcodierung/Decodierung_von_Faltungscodes#Decodierbeispiele_f.C3.BCr_den_fehlerbehafteten_Fall| Beispiel 1]], so erkennt man den folgenden deterministischen Zusammenhang:
+
Vergleicht man die zu zu maximierenden Metriken&nbsp; ${\it \Lambda}_i(S_{\mu})$&nbsp; mit den zu minimierenden Fehlergrößen&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; gemäß dem&nbsp;[[Kanalcodierung/Decodierung_von_Faltungscodes#Decodierbeispiele_f.C3.BCr_den_fehlerbehafteten_Fall| $\text{Beispiel 1}$]], so erkennt man den folgenden deterministischen Zusammenhang:
  
 
::<math>{\it \Lambda}_i(S_{\mu}) = 2 \cdot  \big [ i -  {\it \Gamma}_i(S_{\mu}) \big ] \hspace{0.05cm}.</math>
 
::<math>{\it \Lambda}_i(S_{\mu}) = 2 \cdot  \big [ i -  {\it \Gamma}_i(S_{\mu}) \big ] \hspace{0.05cm}.</math>
  
Die Auswahl der zu den einzelnen Decodierschritten überlebenden Zweige ist bei beiden Verfahren identisch, und auch die Pfadsuche liefert das gleiche Ergebnis.<br>
+
Die Auswahl der zu den einzelnen Decodierschritten überlebenden Zweige ist bei beiden Verfahren identisch, und auch die Pfadsuche liefert das gleiche Ergebnis.<br>}}
  
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Fazit:}$&nbsp;   
 
$\text{Fazit:}$&nbsp;   
*Beim Binärkanal &ndash; zum Beispiel dem BSC&ndash;Modell &ndash; führen die beiden beschriebenen Viterbi&ndash;Varianten <i>Fehlergrößenminimierung</i> und <i>Metrikmaximierung</i> zum gleichen Ergebnis.<br>
+
*Beim Binärkanal &ndash; zum Beispiel nach dem BSC&ndash;Modell &ndash; führen die beiden beschriebenen Viterbi&ndash;Varianten &bdquo;Fehlergrößenminimierung&rdquo; und &bdquo;Metrikmaximierung&rdquo; zum gleichen Ergebnis.<br>
  
*Beim AWGN&ndash;Kanal ist die Fehlergrößenminimierung nicht anwendbar, da keine Hamming&ndash;Distanz zwischen dem binären Eingang $\underline{x}$ und dem analogen Ausgang $\underline{y}$ angegeben werden kann.<br>
+
*Beim AWGN&ndash;Kanal ist dagegen die Fehlergrößenminimierung nicht anwendbar, da keine Hamming&ndash;Distanz zwischen dem binären Eingang&nbsp; $\underline{x}$&nbsp; und dem analogen Ausgang&nbsp; $\underline{y}$&nbsp; angegeben werden kann.<br>
  
*Die Metrikmaximierung ist beim AWGN&ndash;Kanal vielmehr identisch mit der Minimierung der [[Kanalcodierung/Klassifizierung_von_Signalen#ML.E2.80.93Entscheidung_beim_AWGN.E2.80.93Kanal| Euklidischen Distanz]] &ndash; siehe [[Aufgabe 3.10Z]].<br>
+
*Die Metrikmaximierung ist beim AWGN&ndash;Kanal vielmehr identisch mit der Minimierung der&nbsp; [[Kanalcodierung/Klassifizierung_von_Signalen#ML.E2.80.93Entscheidung_beim_AWGN.E2.80.93Kanal| Euklidischen Distanz]]&nbsp; &ndash; siehe&nbsp; [[Aufgaben:Aufgabe_3.10Z:_ML–Decodierung_von_Faltungscodes|Aufgabe 3.10Z]].<br>
  
*Ein weiterer Vorteil der Metrikmaximierung ist, dass eine Zuverlässigkeitsinformation über die Empfangswerte $\underline{y}$ in einfacher Weise berücksichtigt werden kann.}}<br>
+
*Ein weiterer Vorteil der Metrikmaximierung ist, dass eine Zuverlässigkeitsinformation über die Empfangswerte&nbsp; $\underline{y}$&nbsp; in einfacher Weise berücksichtigt werden kann.}}<br>
  
 
== Viterbi–Entscheidung bei nicht–terminierten Faltungscodes==
 
== Viterbi–Entscheidung bei nicht–terminierten Faltungscodes==
 
<br>
 
<br>
Bisher wurde stets ein terminierter Faltungscode der Länge $L' = L + m$ betrachtet, und das Ergebnis des Viterbi&ndash;Decoders war der durchgehende Trellispfad vom Startzeitpunkt $(i = 0)$ bis zum Ende $(i = L')$.<br>
+
Bisher wurde stets ein terminierter Faltungscode der Länge&nbsp; $L\hspace{0.05cm}' = L + m$&nbsp; betrachtet, und das Ergebnis des Viterbi&ndash;Decoders war der durchgehende Trellispfad vom Startzeitpunkt&nbsp; $(i = 0)$&nbsp; bis zum Ende&nbsp; $(i = L\hspace{0.05cm}')$.<br>
*Bei nicht&ndash;terminierten Faltungscodes $(L' &#8594; &#8734;)$ ist diese Entscheidungsstrategie nicht anwendbar.  
+
*Bei nicht&ndash;terminierten Faltungscodes&nbsp; $(L\hspace{0.05cm}' &#8594; &#8734;)$&nbsp; ist diese Entscheidungsstrategie nicht anwendbar.  
 
*Hier muss der Algorithmus abgewandelt werden, um in endlicher Zeit eine bestmögliche Schätzung (gemäß Maximum&ndash;Likelihood) der einlaufenden Bits der Codesequenz liefern zu können.<br>
 
*Hier muss der Algorithmus abgewandelt werden, um in endlicher Zeit eine bestmögliche Schätzung (gemäß Maximum&ndash;Likelihood) der einlaufenden Bits der Codesequenz liefern zu können.<br>
  
Der Grafik zeigt im oberen Teil ein beispielhaftes Trellis für
+
 
 +
Die Grafik zeigt im oberen Teil ein beispielhaftes Trellis für
 
*&bdquo;unseren&rdquo; Standard&ndash;Codierer &nbsp; &#8658; &nbsp; $R = 1/2, \ m = 2, \ {\rm G}(D) = (1 + D + D^2, \ 1 + D^2)$,<br>
 
*&bdquo;unseren&rdquo; Standard&ndash;Codierer &nbsp; &#8658; &nbsp; $R = 1/2, \ m = 2, \ {\rm G}(D) = (1 + D + D^2, \ 1 + D^2)$,<br>
  
 
*die Nullfolge &nbsp; &#8658; &nbsp; $\underline{u} = \underline{0} = (0, 0, 0, \ \text{...})$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $\underline{x} = \underline{0} = (00, 00, 00, \ \text{...})$,<br>
 
*die Nullfolge &nbsp; &#8658; &nbsp; $\underline{u} = \underline{0} = (0, 0, 0, \ \text{...})$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $\underline{x} = \underline{0} = (00, 00, 00, \ \text{...})$,<br>
  
*jeweils einen Übertragungsfehler bei $i = 4$ und $i = 5$.<br><br>
+
*jeweils einen Übertragungsfehler bei&nbsp; $i = 4$&nbsp; und&nbsp; $i = 5$.<br><br>
  
 
Anhand der Stricharten erkennt man erlaubte (durchgezogene) und verbotene (punktierte) Pfeile in rot $(u_i = 0)$ und blau $(u_i = 1)$. Punktierte Linien haben einen Vergleich gegen einen Konkurrenten verloren und können nicht Teil des ausgewählten Pfades sein.<br>
 
Anhand der Stricharten erkennt man erlaubte (durchgezogene) und verbotene (punktierte) Pfeile in rot $(u_i = 0)$ und blau $(u_i = 1)$. Punktierte Linien haben einen Vergleich gegen einen Konkurrenten verloren und können nicht Teil des ausgewählten Pfades sein.<br>
Zeile 306: Zeile 315:
 
[[Datei:P ID2676 KC T 3 4 S7 v1.png|center|frame|Beispielhaftes Trellis und überlebende Pfade|class=fit]]
 
[[Datei:P ID2676 KC T 3 4 S7 v1.png|center|frame|Beispielhaftes Trellis und überlebende Pfade|class=fit]]
  
Der untere Teil der Grafik zeigt die $2^m$ überlebenden Pfade ${\it \Phi}_9(S_{\mu})$ zum Zeitpunkt $i = 9$.  
+
Der untere Teil der Grafik zeigt die&nbsp; $2^m = 4$&nbsp; überlebenden Pfade&nbsp; ${\it \Phi}_9(S_{\mu})$&nbsp; zum Zeitpunkt&nbsp; $i = 9$.  
*Man findet diese Pfade am einfachsten von rechts nach links.  
+
*Man findet diese Pfade am einfachsten von rechts nach links (Rückwärtsrichtung).  
*Die folgende Angabe zeigt die durchlaufenen Zustände $S_{\mu}$ allerdings in Vorwärtsrichtung:<br>
+
*Die folgende Angabe zeigt die durchlaufenen Zustände&nbsp; $S_{\mu}$&nbsp; allerdings in Vorwärtsrichtung:<br>
 
:$${\it \Phi}_9(S_0) \text{:} \hspace{0.4cm} S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0,$$
 
:$${\it \Phi}_9(S_0) \text{:} \hspace{0.4cm} S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0,$$
 
:$${\it \Phi}_9(S_1) \text{:} \hspace{0.4cm}  S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_1 &#8594; S_2 &#8594; S_1 &#8594; S_3 &#8594; S_2 &#8594; S_1,$$
 
:$${\it \Phi}_9(S_1) \text{:} \hspace{0.4cm}  S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_1 &#8594; S_2 &#8594; S_1 &#8594; S_3 &#8594; S_2 &#8594; S_1,$$
Zeile 314: Zeile 323:
 
:$${\it \Phi}_9(S_3) \text{:} \hspace{0.4cm}  S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_1 &#8594; S_2 &#8594; S_1 &#8594; S_2 &#8594; S_1 &#8594; S_3.$$
 
:$${\it \Phi}_9(S_3) \text{:} \hspace{0.4cm}  S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; S_1 &#8594; S_2 &#8594; S_1 &#8594; S_2 &#8594; S_1 &#8594; S_3.$$
  
Zu früheren Zeitpunkten $i$ würden sich andere überlebende Pfade ${\it \Phi}_i(S_{\mu})$ ergeben. Deshalb definieren wir:
+
Zu früheren Zeitpunkten&nbsp; $(i<9)$&nbsp; würden sich andere überlebende Pfade&nbsp; ${\it \Phi}_i(S_{\mu})$&nbsp; ergeben. Deshalb definieren wir:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp;  Der <b>überlebende Pfad</b> (englisch: <i>Survivor</i>) ${\it \Phi}_i(S_{\mu})$ ist der durchgehende Pfad vom Start $S_0$ (bei $i = 0$) zum Knoten $S_{\mu}$ zum Zeitpunkt $i$. Empfehlenswert ist die Pfadsuche in Rückwärtsrichtung.}}<br>
+
$\text{Definition:}$&nbsp;  Der&nbsp; <b>überlebende Pfad</b>&nbsp; (englisch: &nbsp;<i>Survivor</i>)&nbsp; ${\it \Phi}_i(S_{\mu})$&nbsp; ist der durchgehende Pfad vom Start&nbsp; $S_0$&nbsp; $($bei&nbsp; $i = 0)$&nbsp; zum Knoten&nbsp; $S_{\mu}$ zum Zeitpunkt&nbsp; $i$. Empfehlenswert ist die Pfadsuche in Rückwärtsrichtung.}}<br>
  
Die folgende Grafik zeigt die überlebenden Pfade für die Zeitpunkte $i = 6$ bis $i = 9$. Zusätzlich sind die jeweiligen Metriken ${\it \Lambda}_i(S_{\mu})$ für alle vier Zustände angegeben.  
+
Die folgende Grafik zeigt die überlebenden Pfade für die Zeitpunkte&nbsp; $i = 6$&nbsp; bis&nbsp; $i = 9$. Zusätzlich sind die jeweiligen Metriken&nbsp; ${\it \Lambda}_i(S_{\mu})$&nbsp; für alle vier Zustände angegeben.  
  
[[Datei:P ID2677 KC T 3 4 S7b v1.png|center|frame|Die überlebenden Pfade ${\it \Phi}_6, \ \text{...} \ , \ {\it \Phi}_9$|class=fit]]
+
[[Datei:P ID2677 KC T 3 4 S7b v1.png|center|frame|Die überlebenden Pfade&nbsp; ${\it \Phi}_6, \ \text{...} \ , \ {\it \Phi}_9$|class=fit]]
  
 
Diese Grafik ist wie folgt zu interpretieren:
 
Diese Grafik ist wie folgt zu interpretieren:
*Zum Zeitpunkt $i = 9$ kann noch keine endgültige ML&ndash;Entscheidung über die ersten neun Bit der Informationssequenz getroffen werden. Allerdings ist bereits sicher, dass die wahrscheinlichste Bitfolge durch einen der Pfade ${\it \Phi}_9(S_0), \ \text{...0} \ , \ {\it \Phi}_9(S_3)$ richtig wiedergegeben wird.<br>
+
*Zum Zeitpunkt&nbsp; $i = 9$&nbsp; kann noch keine endgültige ML&ndash;Entscheidung über die ersten neun Bit der Informationssequenz getroffen werden. Allerdings ist bereits sicher, dass die wahrscheinlichste Bitfolge durch einen der Pfade&nbsp; ${\it \Phi}_9(S_0), \ \text{...} \ , \ {\it \Phi}_9(S_3)$&nbsp; richtig wiedergegeben wird.<br>
  
*Da alle vier Pfade bei $i = 3$ zusammenlaufen, ist die Entscheidung &bdquo;$v_1 = 0, v_2 = 0, \ v_3 = 0$&rdquo; die bestmögliche (hellgraue Hinterlegung). Auch zu einem späteren Zeitpunkt würde keine andere Entscheidung getroffen werden. Hinsichtlich der Bits $v_4, \ v_5, \ \text{...}$ sollte man sich zu diesem frühen Zeitpunkt noch nicht festlegen.<br>
+
*Da alle vier Pfade bis&nbsp; $i = 3$&nbsp; identisch sind, ist die Entscheidung &bdquo;$v_1 = 0, v_2 = 0, \ v_3 = 0$&rdquo; die bestmögliche (hellgraue Hinterlegung). Auch zu einem späteren Zeitpunkt würde keine andere Entscheidung getroffen werden. Hinsichtlich der Bits&nbsp; $v_4, \ v_5, \ \text{...}$&nbsp; sollte man sich zu diesem frühen Zeitpunkt noch nicht festlegen.<br>
  
*Müsste man zum Zeitpunkt $i = 9$ eine Zwangsentscheidung treffen, so würde man sich für ${\it \Phi}_9(S_0)$ &nbsp; &#8658; &nbsp; $\underline{v} = (0, 0, \ \text{...} \ , 0)$ entscheiden, da die Metrik ${\it \Lambda}_9(S_0) = 14$ größer ist als die Vergleichsmetriken.<br>
+
*Müsste man zum Zeitpunkt&nbsp; $i = 9$&nbsp; eine Zwangsentscheidung treffen, so würde man sich für&nbsp; ${\it \Phi}_9(S_0)$ &nbsp; &#8658; &nbsp; $\underline{v} = (0, 0, \ \text{...} \ , 0)$ entscheiden, da die Metrik&nbsp; ${\it \Lambda}_9(S_0) = 14$&nbsp; größer ist als die Vergleichsmetriken.<br>
  
*Die Zwangsentscheidung zum Zeitpunkt $i = 9$ führt in diesem Beispiel zum richtigen Ergebnis. Zum Zeitpunkt $i = 6$ wäre ein solcher Zwangsentscheid  falsch gewesen &nbsp; &#8658; &nbsp;  $\underline{v} = (0, 0, 0, 1, 0, 1)$, und zu den Zeitpunten $i = 7$ bzw. $i = 8$ nicht eindeutig.<br>
+
*Die Zwangsentscheidung zum Zeitpunkt&nbsp; $i = 9$&nbsp; führt in diesem Beispiel zum richtigen Ergebnis. Zum Zeitpunkt&nbsp; $i = 6$&nbsp; wäre ein solcher Zwangsentscheid  falsch gewesen &nbsp; &#8658; &nbsp;  $\underline{v} = (0, 0, 0, 1, 0, 1)$, und zu den Zeitpunten&nbsp; $i = 7$&nbsp; bzw.&nbsp; $i = 8$&nbsp; nicht eindeutig.<br>
  
  
Zeile 336: Zeile 345:
 
== Weitere Decodierverfahren für Faltungscodes ==
 
== Weitere Decodierverfahren für Faltungscodes ==
 
<br>
 
<br>
Wir haben uns bisher nur mit dem Viterbi&ndash;Algorithmus in der Form beschäftigt, der 1967 von Andrew J. Viterbi in [Vit67]<ref name'Vit67'>Viterbi, A.J.: ''Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm''. In: IEEE Transactions on Information Theory, vol. IT-13, pp. 260-269, April 1967.</ref> veröffentlicht wurde. Erst 1974 hat [https://de.wikipedia.org/wiki/David_Forney George David Forney] nachgewiesen, dass dieser Algorithmus eine Maximum&ndash;Likelihood&ndash;Decodierung von Faltungscodes durchführt.<br>
+
Wir haben uns bisher nur mit dem Viterbi&ndash;Algorithmus in der Form beschäftigt, der 1967 von Andrew J. Viterbi in&nbsp; [Vit67]<ref name'Vit67'>Viterbi, A.J.: ''Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm''. In: IEEE Transactions on Information Theory, vol. IT-13, pp. 260-269, April 1967.</ref> veröffentlicht wurde. Erst 1974 hat&nbsp; [https://de.wikipedia.org/wiki/David_Forney George David Forney]&nbsp; nachgewiesen, dass dieser Algorithmus eine Maximum&ndash;Likelihood&ndash;Decodierung von Faltungscodes durchführt.<br>
  
Aber schon in den Jahren zuvor waren viele Wissenschaftler sehr bemüht, effiziente Decodierverfahren für die 1955 erstmals von [https://de.wikipedia.org/wiki/Peter_Elias Peter Elias] beschriebenen Faltungscodes bereitzustellen. Zu nennen sind hier unter Anderem &ndash; genauere Beschreibungen findet man beispielsweise in [Bos98]<ref name='Bos98'>Bossert, M.: ''Kanalcodierung.'' Stuttgart: B. G. Teubner, 1998.</ref> oder der englischsprachigen Ausgabe [Bos99]<ref name='Bos99'>Bossert, M.: ''Channel Coding for Telecommunications.'' Wiley & Sons, 1999.</ref>.  
+
Aber schon in den Jahren zuvor waren viele Wissenschaftler sehr bemüht, effiziente Decodierverfahren für die 1955 erstmals von&nbsp; [https://de.wikipedia.org/wiki/Peter_Elias Peter Elias]&nbsp; beschriebenen Faltungscodes bereitzustellen. Zu nennen sind hier unter Anderem &ndash; genauere Beschreibungen findet man beispielsweise in&nbsp; [Bos98]<ref name='Bos98'>Bossert, M.: ''Kanalcodierung.'' Stuttgart: B. G. Teubner, 1998.</ref> oder der englischen Ausgabe&nbsp; [Bos99]<ref name='Bos99'>Bossert, M.: ''Channel Coding for Telecommunications.'' Wiley & Sons, 1999.</ref>.  
*[http://ieeexplore.ieee.org/document/1057663/ <i>Sequential Decoding</i>] von J. M. Wozencraft und B. Reiffen aus dem Jahre 1961,<br>
+
*[http://ieeexplore.ieee.org/document/1057663/ <i>Sequential Decoding</i>&nbsp;]&nbsp; von J. M. Wozencraft und B. Reiffen aus dem Jahre 1961,<br>
  
*der Vorschlag von [https://en.wikipedia.org/wiki/Robert_Fano Robert Mario Fano] (1963), der als <i>Fano&ndash;Algorithmus</i> bekannt wurde,<br>
+
*der Vorschlag von&nbsp; [https://en.wikipedia.org/wiki/Robert_Fano Robert Mario Fano]&nbsp; (1963), der als <i>Fano&ndash;Algorithmus</i>&nbsp; bekannt wurde,<br>
  
*die Arbeiten von Kamil Zigangirov (1966) und Frederick Jelinek (1969), deren Decodierverfahren als <i>Stack&ndash;Algorithmus</i> bezeichnet wird.<br><br>
+
*die Arbeiten von Kamil Zigangirov (1966) und&nbsp; [https://en.wikipedia.org/wiki/Frederick_Jelinek Frederick Jelinek]&nbsp; (1969), deren Decodierverfahren auch als <i>Stack&ndash;Algorithmus</i>&nbsp; bezeichnet wird.<br><br>
  
 
Alle diese Decodierverfahren und auch der Viterbi&ndash;Algorithmus in seiner bisher beschriebenen Form liefern &bdquo;hart&rdquo; entschiedene Ausgangswerte &nbsp; &#8658; &nbsp;  $v_i &#8712; \{0, 1\}$. Oftmals wären jedoch Informationen über die Zuverlässigkeit der getroffenen Entscheidungen wünschenswert, insbesondere dann, wenn ein verkettetes Codierschema mit einem äußeren und einem inneren Code vorliegt.<br>
 
Alle diese Decodierverfahren und auch der Viterbi&ndash;Algorithmus in seiner bisher beschriebenen Form liefern &bdquo;hart&rdquo; entschiedene Ausgangswerte &nbsp; &#8658; &nbsp;  $v_i &#8712; \{0, 1\}$. Oftmals wären jedoch Informationen über die Zuverlässigkeit der getroffenen Entscheidungen wünschenswert, insbesondere dann, wenn ein verkettetes Codierschema mit einem äußeren und einem inneren Code vorliegt.<br>
  
Kennt man die Zuverlässigkeit der vom inneren Decoder entschiedenen Bits zumindest grob, so kann durch diese Information die Bitfehlerwahrscheinlichkeit des äußeren Decoders (signifikant) herabgesetzt werden. Der von J. Hagenauer in [Hag90]<ref name='Hag90'>Hagenauer, J.: ''Soft Output Viterbi Decoder.'' In: Technischer Report, Deutsche Forschungsanstalt für Luft- und Raumfahrt (DLR), 1990.</ref> vorgeschlagene <i>Soft&ndash;Output&ndash;Viterbi&ndash;Algorithmus</i> (SOVA) erlaubt es, zusätzlich zu den entschiedenen Symbolen auch jeweils ein Zuverlässigkeitsmaß anzugeben.<br>
+
Kennt man die Zuverlässigkeit der vom inneren Decoder entschiedenen Bits zumindest grob, so kann durch diese Information die Bitfehlerwahrscheinlichkeit des äußeren Decoders (signifikant) herabgesetzt werden. Der von&nbsp; [[Biografien_und_Bibliografien/Lehrstuhlinhaber_des_LNT#Prof._Dr.-Ing._Dr.-Ing._E.h._Joachim_Hagenauer_.281993-2006.29|Joachim Hagenauer]]&nbsp; in&nbsp; [Hag90]<ref name='Hag90'>Hagenauer, J.: ''Soft Output Viterbi Decoder.'' In: Technischer Report, Deutsche Forschungsanstalt für Luft- und Raumfahrt (DLR), 1990.</ref> vorgeschlagene&nbsp; <i>Soft&ndash;Output&ndash;Viterbi&ndash;Algorithmus</i>&nbsp; (SOVA) erlaubt es, zusätzlich zu den entschiedenen Symbolen auch jeweils ein Zuverlässigkeitsmaß anzugeben.<br>
 +
 
 +
Abschließend gehen wir noch etwas genauer auf den&nbsp; <i>BCJR&ndash;Algorithmus</i>&nbsp; ein, benannt nach dessen Erfindern L. R. Bahl, J. Cocke, F. Jelinek  und J. Raviv&nbsp; [BCJR74]<ref name='BCJR74'>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.: ''Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.'' In: IEEE Transactions on Information Theory, Vol. IT-20, S. 284-287, 1974.</ref>.
 +
*Während der Viterbi&ndash;Algorithmus nur eine Schätzung der Gesamtsequenz vornimmt &nbsp; &#8658; &nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Definitionen_der_verschiedenen_Optimalempf.C3.A4nger|''block&ndash;wise ML'']], schätzt der BCJR&ndash;Algorithmus ein einzelnes Symbol (Bit) unter Berücksichtigung der gesamten empfangenen Codesequenz.
 +
* Es handelt sich hierbei also um eine&nbsp; <i>symbolweise Maximum&ndash;Aposteriori&ndash;Decodierung</i> &nbsp; &#8658; &nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Definitionen_der_verschiedenen_Optimalempf.C3.A4nger|''bit&ndash;wise MAP'']].<br>
  
Abschließend gehen wir noch etwas genauer auf den <i>BCJR&ndash;Algorithmus</i> ein, benannt nach dessen Erfindern L. R. Bahl, J. Cocke, F. Jelinek  und J. Raviv [BCJR74]<ref name='BCJR74'>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.: ''Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.'' In: IEEE Transactions on Information Theory, Vol. IT-20, S. 284-287, 1974.</ref>. Während der Viterbi&ndash;Algorithmus nur eine Schätzung der Gesamtsequenz vornimmt &nbsp; &#8658; &nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Definitionen_der_verschiedenen_Optimalempf.C3.A4nger|block&ndash;wise ML]], schätzt der BCJR&ndash;Algorithmus ein einzelnes Symbol (Bit) unter Berücksichtigung der gesamten empfangenen Codesequenz. Es handelt sich hierbei also um eine <i>symbolweise Maximum&ndash;Aposteriori&ndash;Decodierung</i> &nbsp; &#8658; &nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Definitionen_der_verschiedenen_Optimalempf.C3.A4nger|bit&ndash;wise MAP]].<br>
 
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Fazit:}$&nbsp; Der Unterschied zwischen Viterbi&ndash;Algorithmus und BCJR&ndash;Algorithmus soll &ndash; stark vereinfacht &ndash; am Beispiel eines terminierten Faltungscodes dargestellt werden:
 
$\text{Fazit:}$&nbsp; Der Unterschied zwischen Viterbi&ndash;Algorithmus und BCJR&ndash;Algorithmus soll &ndash; stark vereinfacht &ndash; am Beispiel eines terminierten Faltungscodes dargestellt werden:
*Der <b>Viterbi&ndash;Algorithmus</b> arbeitet das Trellis nur in einer Richtung &ndash; der  <i>Vorwärtsrichtung</i> &ndash; ab und berechnet für jeden Knoten die Metriken ${\it \Lambda}_i(S_{\mu})$. Nach Erreichen des Endknotens wird der  überlebende Pfad gesucht, der die wahrscheinlichste Codesequenz kennzeichnet.<br>
+
*Der&nbsp; <b>Viterbi&ndash;Algorithmus</b>&nbsp; arbeitet das Trellis nur in einer Richtung &ndash; der  <i>Vorwärtsrichtung</i>&nbsp; &ndash; ab und berechnet für jeden Knoten die Metriken&nbsp; ${\it \Lambda}_i(S_{\mu})$. Nach Erreichen des Endknotens wird der  überlebende Pfad gesucht, der die wahrscheinlichste Codesequenz kennzeichnet.<br>
  
*Beim <b>BCJR&ndash;Algorithmus</b> wird das Trellis zweimal abgearbeitet, einmal in Vorwärtsrichtung und anschließend in <i>Rückwärtsrichtung</i>. Für jeden Knoten sind dann zwei Metriken angebbar,  aus denen für jedes Bit die Aposterori&ndash;Wahrscheinlichkeit bestimmt werden kann.}}<br><br>
+
*Beim&nbsp; <b>BCJR&ndash;Algorithmus</b>&nbsp; wird das Trellis zweimal abgearbeitet, einmal in Vorwärtsrichtung und anschließend in <i>Rückwärtsrichtung</i>. Für jeden Knoten sind dann zwei Metriken angebbar,  aus denen für jedes Bit die Aposterori&ndash;Wahrscheinlichkeit bestimmt werden kann.}}<br>
  
<i>Hinweis:</i> Diese Kurzzusammenfassung basiert auf dem Lehrbüchern  [Bos98]<ref name='Bos98'>Bossert, M.: ''Kanalcodierung.'' Stuttgart: B. G. Teubner, 1998.</ref> bzw. [Bos99]<ref name='Bos99'>Bossert, M.: ''Channel Coding for Telecommunications.'' Wiley & Sons, 1999.</ref>. Eine etwas ausführlichere Beschreibung des BCJR&ndash;Algorithmus' folgt auf der Seite [[Kanalcodierung/Soft–in_Soft–out_Decoder#Hard_Decision_vs._Soft_Decision| Hard Decision vs. Soft Decision]] im vierten Hauptkapitel.<br>
+
<i>Hinweise:</i>  
 +
*Diese Kurzzusammenfassung basiert auf dem Lehrbüchern&nbsp; [Bos98]<ref name='Bos98'>Bossert, M.: ''Kanalcodierung.'' Stuttgart: B. G. Teubner, 1998.</ref>&nbsp; bzw.&nbsp; [Bos99]<ref name='Bos99'>Bossert, M.: ''Channel Coding for Telecommunications.'' Wiley & Sons, 1999.</ref>.  
 +
*Eine etwas ausführlichere Beschreibung des BCJR&ndash;Algorithmus' folgt auf der Seite&nbsp; [[Kanalcodierung/Soft–in_Soft–out_Decoder#Hard_Decision_vs._Soft_Decision| Hard Decision vs. Soft Decision]]&nbsp; [https://www.lntwww.de/Kanalcodierung im vierten Hauptkapitel]&nbsp; &bdquo;Iterative Decodierverfahren&rdquo;.<br>
  
  

Aktuelle Version vom 17. November 2022, 19:50 Uhr

Blockschaltbild und Voraussetzungen


Ein wesentlicher Vorteil der Faltungscodierung ist, dass es hierfür mit dem Viterbi–Algorithmus ein sehr effizientes Decodierverfahren gibt. Dieser von  Andrew James Viterbi  entwickelte Algorithmus wurde bereits im Kapitel  Viterbi–Empfänger  des Buches „Digitalsignalübertragung” im Hinblick auf seinen Einsatz zur Entzerrung beschrieben.

Systemmodell zur Beschreibung der Decodierung von Faltungscodes

Für seinen Einsatz als Faltungsdecodierer gehen wir von obigem Blockschaltbild und den folgenden Voraussetzungen aus:

  • Die Informationssequenz  $\underline{u} = (u_1, \ u_2, \ \text{...} \ )$  ist hier im Gegensatz zur Beschreibung der linearen Blockcodes   ⇒   Erstes Hauptkapitel  oder von Reed–Solomon–Codes   ⇒   Zweites Hauptkapitel  im allgemeinen unendlich lang  („semi–infinite” ). Für die Informationssymbole gilt stets  $u_i ∈ \{0, 1\}$.
  • Die Codesequenz  $\underline{x} = (x_1, \ x_2, \ \text{...})$  mit  $x_i ∈ \{0, 1\}$  hängt außer von  $\underline{u}$  auch von der Coderate  $R = 1/n$, dem Gedächtnis  $m$  und der Übertragungsfunktionsmatrix  $\mathbf{G}(D)$  ab. Bei endlicher Anzahl  $L$  an Informationsbits sollte der Faltungscode durch Anfügen von  $m$  Nullen terminiert werden:
\[\underline{u}= (u_1,\hspace{0.05cm} u_2,\hspace{0.05cm} \text{...} \hspace{0.1cm}, u_L, \hspace{0.05cm} 0 \hspace{0.05cm},\hspace{0.05cm} \text{...} \hspace{0.1cm}, 0 ) \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline{x}= (x_1,\hspace{0.05cm} x_2,\hspace{0.05cm} \text{...} \hspace{0.1cm}, x_{2L}, \hspace{0.05cm} x_{2L+1} ,\hspace{0.05cm} \text{...} \hspace{0.1cm}, \hspace{0.05cm} x_{2L+2m} ) \hspace{0.05cm}.\]
  • Der Viterbi–Algorithmus liefert eine Schätzung  $\underline{z}$  für die Codesequenz  $\underline{x}$  und eine weitere Schätzung  $\underline{v}$  für die Informationssequenz  $\underline{u}$. Dabei gilt:
\[{\rm Pr}(\underline{z} \ne \underline{x})\stackrel{!}{=}{\rm Minimum} \hspace{0.25cm}\Rightarrow \hspace{0.25cm} {\rm Pr}(\underline{\upsilon} \ne \underline{u})\stackrel{!}{=}{\rm Minimum} \hspace{0.05cm}.\]

$\text{Fazit:}$  Bei einem digitalen Kanalmodell (zum Beispiel dem BSC–Modell) sucht der Viterbi–Algorithmus von allen möglichen Codesequenzen  $\underline{x}\hspace{0.05cm}'$  diejenige Sequenz  $\underline{z}$  mit der minimalen Hamming–Distanz  $d_{\rm H}(\underline{x}\hspace{0.05cm}', \underline{y})$  zur Empfangssequenz  $\underline{y}$:

\[\underline{z} = {\rm arg} \min_{\underline{x}\hspace{0.05cm}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm} d_{\rm H}( \underline{x}\hspace{0.05cm}'\hspace{0.02cm},\hspace{0.02cm} \underline{y} ) = {\rm arg} \max_{\underline{x}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm} {\rm Pr}( \underline{y} \hspace{0.05cm} \vert \hspace{0.05cm} \underline{x}')\hspace{0.05cm}.\]

Das bedeutet auch:   Der Viterbi–Algorithmus erfüllt das  Maximum–Likelihood–Kriterium.


Vorbemerkungen zu den nachfolgenden Decodierbeispielen


Trellis zur Decodierung der Empfangssequenz  $\underline{y}$

Für alle Beispiele in diesem Kapitels gelten folgende  Voraussetzungen:

  • Standard–Faltungscodierer:   Rate $R = 1/2$,  Gedächtnis  $m = 2$;
  • Übertragungsfunktionsmatrix:   $\mathbf{G}(D) = (1 + D + D^2, 1 + D^2)$;
  • Länge der Informationssequenz:   $L = 5$;
  • Berücksichtigung der Terminierung:   $L\hspace{0.05cm}' = 7$;
  • Länge der Sequenzen  $\underline{x}$  und  $\underline{y}$ :   jeweils $14$ Bit;
  • Aufteilung gemäß  $\underline{y} = (\underline{y}_1, \ \underline{y}_2, \ \text{...} \ , \ \underline{y}_7)$
    ⇒   Bitpaare  $\underline{y}_i ∈ \{00, 01, 10, 11\}$;
  • Viterbi–Decodierung mittels Trellisdiagramms:
roter Pfeil   ⇒   Hypothese  $u_i = 0$,
blauer Pfeil   ⇒   Hypothese  $u_i = 1$;
  • hypothetische Codesequenz  $\underline{x}_i\hspace{0.01cm}' ∈ \{00, 01, 10, 11\}$;
  • alle hypothetischen Größen mit Apostroph.


Wir gehen stets davon aus, dass die Viterbi–Decodierung auf der  Hamming–Distanz  $d_{\rm H}(\underline{x}_i\hspace{0.01cm}', \ \underline{y}_i)$  zwischen dem Empfangswort  $\underline{y}_i$  und den vier möglichen Codeworten  $x_i\hspace{0.01cm}' ∈ \{00, 01, 10, 11\}$  basiert. Dann gehen wir wie folgt vor:

  • In die noch leeren Kreise werden die Fehlergrößen  ${\it \Gamma}_i(S_{\mu})$  der Zustände  $S_{\mu} (0 ≤ \mu ≤ 3)$  zu den Zeitpunkten  $i$  eingetragen. Der Startwert ist stets  ${\it \Gamma}_0(S_0) = 0$.
  • Die Fehlergrößen für  $i = 1$  und  $i = 2$  ergeben sich zu
\[{\it \Gamma}_1(S_0) =d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_1 \big ) \hspace{0.05cm}, \hspace{2.38cm}{\it \Gamma}_1(S_1) = d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_1 \big ) \hspace{0.05cm},\]
\[{\it \Gamma}_2(S_0) ={\it \Gamma}_1(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )\hspace{0.05cm}, \hspace{0.6cm}{\it \Gamma}_2(S_1) = {\it \Gamma}_1(S_0)+ d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big ) \hspace{0.05cm},\hspace{0.6cm}{\it \Gamma}_2(S_2) ={\it \Gamma}_1(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )\hspace{0.05cm}, \hspace{0.6cm}{\it \Gamma}_2(S_3) = {\it \Gamma}_1(S_1)+ d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big ) \hspace{0.05cm}.\]
  • Ab  $i = 3$  hat das Trellis seine Grundform erreicht, und zur Berechnung aller  ${\it \Gamma}_i(S_{\mu})$  muss jeweils das Minimum zwischen zwei Summen ermittelt werden:
\[{\it \Gamma}_i(S_0) ={\rm Min} \left [{\it \Gamma}_{i-1}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm},\]
\[{\it \Gamma}_i(S_1)={\rm Min} \left [{\it \Gamma}_{i-1}(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_2) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm},\]
\[{\it \Gamma}_i(S_2) ={\rm Min} \left [{\it \Gamma}_{i-1}(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_3) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm},\]
\[{\it \Gamma}_i(S_3) ={\rm Min} \left [{\it \Gamma}_{i-1}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm}.\]
  • Von den zwei an einem Knoten  ${\it \Gamma}_i(S_{\mu})$  ankommenden Zweigen wird der schlechtere (der zu einem größeren  ${\it \Gamma}_i(S_{\mu})$  geführt hätte) eliminiert. Zu jedem Knoten führt dann nur noch ein einziger Zweig.
  • Sind alle Fehlergrößen bis einschließlich  $i = 7$  ermittelt, so kann der Viterbi–Algotithmus mit der Suche des zusammenhängenden Pfades vom Ende des Trellis   ⇒   ${\it \Gamma}_7(S_0)$  bis zum Anfang   ⇒   ${\it \Gamma}_0(S_0)$  abgeschlossen werden.
  • Durch diesen Pfad liegen dann die am wahrscheinlichsten erscheinende Codesequenz  $\underline{z}$  und die wahrscheinlichste Informationssequenz  $\underline{v}$  fest.
  • Nicht für alle Empfangssequenzen  $\underline{y}$  gilt aber  $\underline{z} = \underline{x}$  und  $\underline{v} = \underline{u}$. Das heißt:   Bei zu vielen Übertragungsfehlern versagt auch der Viterbi–Algorithmus.

Erstellen des Trellis im fehlerfreien Fall  –  Fehlergrößenberechnung


Zunächst gehen wir von der Empfangssequenz  $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$  aus, die hier – wegen der Codewortlänge  $n = 2$  – bereits in Bitpaare  $\underline{y}_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ \underline{y}_7$  unterteilt ist. Die in das Trellis eingetragenen Zahlenwerte und die verschiedenen Stricharten werden im folgenden Text erklärt.

Viterbi–Schema für den Empfangsvektor  $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$
  • Ausgehend vom Initialwert  ${\it \Gamma}_0(S_0) = 0$  kommt man mit  $\underline{y}_1 = (11)$  durch Addition der Hamming-Distanzen
$$d_{\rm H}((00), \ \underline{y}_1) = 2\text{ bzw. }d_{\rm H}((11), \ \underline{y}_1) = 0$$
zu den Fehlergrößen  ${\it \Gamma}_1(S_0) = 2, \ {\it \Gamma}_1(S_1) = 0$.
  • Im zweiten Decodierschritt gibt es Fehlergrößen für alle vier Zustände:   Mit  $\underline{y}_2 = (01)$  erhält man:
\[{\it \Gamma}_2(S_0) = {\it \Gamma}_1(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) = 2+1 = 3 \hspace{0.05cm},\]
\[{\it \Gamma}_2(S_1) ={\it \Gamma}_1(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) = 2+1 = 3 \hspace{0.05cm},\]
\[{\it \Gamma}_2(S_2) ={\it \Gamma}_1(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) = 0+2=2 \hspace{0.05cm},\]
\[{\it \Gamma}_2(S_3) = {\it \Gamma}_1(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) = 0+0=0 \hspace{0.05cm}.\]
  • In allen weiteren Decodierschritten müssen jeweils zwei Werte verglichen werden, wobei dem Knoten  ${\it \Gamma}_i(S_{\mu})$  stets der kleinere Wert zugewiesen wird. Beispielsweise gilt für  $i = 3$  mit  $\underline{y}_3 = (01)$:
\[{\it \Gamma}_3(S_0) ={\rm min} \left [{\it \Gamma}_{2}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{2}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \big [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \big ] = 3\hspace{0.05cm},\]
\[{\it \Gamma}_3(S_3) ={\rm min} \left [{\it \Gamma}_{2}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{2}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \big [ 3+0\hspace{0.05cm},\hspace{0.05cm} 0+2 \big ] = 2\hspace{0.05cm}.\]
  • Ab  $i = 6$  wird im betrachteten Beispiel die Terminierung des Faltungscodes wirksam. Hier sind nur noch zwei Vergleiche zur Bestimmung von  ${\it \Gamma}_6(S_0) = 3$  und  ${\it \Gamma}_6(S_2)= 0$  anzustellen, und für  $i = 7$  nur noch ein einziger ein Vergleich mit dem Endergebnis  ${\it \Gamma}_7(S_0) = 0$.


Die Beschreibung des Viterbi–Decodiervorgangs wird auf der nächsten Seite fortgesetzt.

Auswerten des Trellis im fehlerfreien Fall  –  Pfadsuche


Nachdem alle Fehlergrößen  ${\it \Gamma}_i(S_{\mu})$  –  im vorliegenden Beispiel für  $1 ≤ i ≤ 7$  und  $0 ≤ \mu ≤ 3$  –  ermittelt wurden, kann der Viterbi–Decoder mit der Pfadsuche beginnen:

Viterbi–Pfadsuche für für den Empfangsvektor  $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$
  • Die Grafik zeigt das Trellis nach der Fehlergrößenberechnung. Alle Kreise sind mit Zahlenwerten belegt.
  • Allerding ist der in der Grafik bereits eingezeichnete wahrscheinlichste Pfad noch nicht bekannt.
  • Von den jeweils zwei an einem Knoten ankommenden Zweigen wird stets nur derjenige bei der abschließenden Pfadsuche herangezogen, der zur minimalen Fehlergröße  ${\it \Gamma}_i(S_{\mu})$  geführt hat.
  • Die „schlechten” Zweige werden verworfen. Sie sind in obiger Grafik jeweils punktiert dargestellt.


Die Pfadsuche läuft wie folgt ab:

  • Ausgehend vom Endwert  ${\it \Gamma}_7(S_0)$  wird in Rückwärtsrichtung ein zusammenhängender Pfad bis zum Startwert  ${\it \Gamma}_0(S_0)$  gesucht. Erlaubt sind nur die durchgezogenen Zweige. Punktierte Linien können nicht Teil des ausgewählten Pfades sein.
  • Der ausgewählte Pfad durchläuft von rechts nach links die Zustände  $S_0 ← S_2 ← S_1 ← S_0 ← S_2 ← S_3 ← S_1 ← S_0$  und ist in der Grafik grau hinterlegt. Es gibt keinen zweiten durchgehenden Pfad von  ${\it \Gamma}_7(S_0)$ zu ${\it \Gamma}_0(S_0)$. Das bedeutet:   Das Decodierergebnis ist eindeutig.
  • Das Ergebnis  $\underline{v} = (1, 1, 0, 0, 1, 0, 0)$  des Viterbi–Decoders hinsichtlich der Informationssequenz erhält man, wenn man für den durchgehenden Pfad  –  nun aber in Vorwärtsrichtung von links nach rechts  –  die Farben der einzelnen Zweige auswertet $($rot entspricht einer  $0$ und blau einer  $1)$.

Aus dem Endwert  ${\it \Gamma}_7(S_0) = 0$  erkennt man, dass in diesem ersten Beispiel keine Übertragungsfehler vorlagen:

  • Das Decodierergebnis  $\underline{z}$  stimmt also mit dem Empfangsvektor  $\underline{y} = (11, 01, 01, 11, 11, 10, 11)$  und der tatsächlichen Codesequenz  $\underline{x}$  überein.
  • Bei fehlerfreier Übertragung ist  $\underline{v}$  nicht nur die nach dem ML–Kriterium wahrscheinlichste Informationssequenz  $\underline{u}$, sondern beide sind sogar identisch:   $\underline{v} \equiv \underline{u}$.


Anmerkung:   Bei der beschriebenen Decodierung wurde natürlich von der bereits in der Überschrift enthaltenen Information „Fehlerfreier Fall” kein Gebrauch gemacht.

Nun folgen drei Beispiele zur Viterbi–Decodierung für den fehlerbehafteten Fall.

Decodierbeispiele für den fehlerbehafteten Fall


$\text{Beispiel 1:}$  Wir gehen hier vom Empfangsvektor  $\underline{y} = \big (11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) $  aus, der keine gültige Codesequenz  $\underline{x}$  darstellt. Die Berechnung der Fehlergrößen  ${\it \Gamma}_i(S_{\mu})$  und die Pfadsuche geschieht wie auf der Seite  Vorbemerkungen  beschrieben und auf den beiden letzten Seite für den fehlerfreien Fall demonstriert.

Decodierbeispiel mit zwei Bitfehlern

Als  Resümee  dieses ersten Beispiels ist festzuhalten:

  • Auch beim obigen Trellis lässt sich ein eindeutiger Pfad (mit dunkelgrauer Hinterlegung) zurückverfolgen, der zu den folgenden Ergebnissen führt
    (erkennbar an den Beschriftungen bzw. den Farben dieses Pfades):
\[\underline{z} = \big (00\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11 \hspace{0.05cm} \big ) \hspace{0.05cm},\]
\[ \underline{\upsilon} =\big (0\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0 \hspace{0.05cm} \big ) \hspace{0.05cm}.\]
  • Der Vergleich der am wahrscheinlichsten gesendeten Codesequenz  $\underline{z}$  mit dem Empfangsvektor  $\underline{y}$  zeigt, dass hier zwei Bitfehler (gleich am Beginn) vorlagen. Da aber der verwendete Faltungscode die freie Distanz $d_{\rm F} = 5$ aufweist, führen zwei Fehler noch nicht zu einem falschen Decodierergebnis.
  • Es gibt andere Pfade wie zum Beispiel den heller markierten Pfad $(S_0 → S_1 → S_3 → S_3 → S_3 → S_2 → S_0 → S_0)$, die zunächst als vielversprechend erscheinen. Erst im letzten Decodierschritt $(i = 7)$ kann dieser hellgraue Pfad endgültig verworfen werden.
  • Das Beispiel zeigt, dass eine zu frühe Entscheidung oft nicht zielführend ist. Man erkennt auch die Zweckmäßigkeit der Terminierung:   Bei endgültiger Entscheidung bei $i = 5$ (Ende der Informationssequenz) wären die Sequenzen  $(0, 1, 0, 1, 1)$  und  $(1, 1, 1, 1, 0)$  noch als gleichwahrscheinlich angesehen worden.

Anmerkungen:   Bei der Berechnung von  ${\it \Gamma}_5(S_0) = 3$  und  ${\it \Gamma}_5(S_1) = 3$  führen hier jeweils die beiden Vergleichszweige zur exakt gleichen minimalen Fehlergröße. In der Grafik sind diese beiden Sonderfälle durch Strichpunktierung markiert.

  • In diesem Beispiel hat dieser Sonderfall keine Auswirkung auf die Pfadsuche.
  • Der Algorithmus erwartet trotzdem stets eine Entscheidung zwischen zwei konkurrierenden Zweigen.
  • In der Praxis hilft man sich dadurch, dass man bei Gleichheit einen der beiden Pfade zufällig auswählt.


$\text{Beispiel 2:}$  Im diesem Beispiel gehen wir von folgenden Voraussetzungen bezüglich Quelle und Coder aus:

\[\underline{u} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0 \big )\hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) \hspace{0.05cm}.\]
Decodierbeispiel mit drei Bitfehlern

Aus der Grafik erkennt man, dass sich hier der Decoder trotz dreier Bitfehler für den richtigen Pfad (dunkle Hinterlegung) entscheidet.

  • Es gibt also nicht immer eine Fehlentscheidung, wenn mehr als  $d_{\rm F}/2$  Bitfehler aufgetreten sind.
  • Aber bei statistischer Verteilung der drei Übertragungsfehler würde häufiger falsch entschieden als richtig.


$\text{Beispiel 3:}$  Auch hier gelte  \(\underline{u} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0 \big )\hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) \hspace{0.05cm}.\) Im Unterschied zum  $\text{Beispiel 2}$  ist aber noch ein vierter Bitfehler in Form von  $\underline{y}_7 = (01)$ hinzugefügt.

Decodierbeispiel mit vier Bitfehlern
  • Nun führen beide Zweige im Schritt  $i = 7$  zur minimalen Fehlergröße  ${\it \Gamma}_7(S_0) = 4$, erkennbar an den strichpunktierten Übergängen. Entscheidet man sich im dann erforderlichen Losverfahren für den dunkel hinterlegten Pfad, so wird auch bei vier Bitfehlern noch die richtige Entscheidung getroffen:   $\underline{v} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0 \big )$.
  • Andernfalls kommt es zu einer Fehlentscheidung. Je nachdem, wie das Auswürfeln im Schritt  $i =6$  zwischen den beiden strichpunktierten Konkurrenten ausgeht, entscheidet man sich entweder für den violetten oder den hellgrauen Pfad. Mit dem richtigen Pfad haben beide wenig gemein.


Zusammenhang zwischen Hamming–Distanz und Korrelation


Insbesondere beim  BSC–Modell  – aber auch bei jedem anderen Binärkanal   ⇒   Eingang  $x_i ∈ \{0,1\}$,  Ausgang $y_i ∈ \{0,1\}$  wie zum Beispiel dem  Gilbert–Elliott–Modell  – liefert die Hamming–Distanz  $d_{\rm H}(\underline{x}, \ \underline{y})$  genau die gleiche Information über die Ähnlichkeit der Eingangsfolge  $\underline{x}$  und der Ausgangsfolge  $\underline{y}$  wie das  innere Produkt. Nimmt man an, dass die beiden Folgen in bipolarer Darstellung vorliegen (gekennzeichnet durch Tilden) und dass die Folgenlänge jeweils  $L$  ist, so gilt für das innere Produkt:

\[<\hspace{-0.1cm}\underline{\tilde{x}}, \hspace{0.05cm}\underline{\tilde{y}} \hspace{-0.1cm}> \hspace{0.15cm} = \sum_{i = 1}^{L} \tilde{x}_i \cdot \tilde{y}_i \hspace{0.3cm}{\rm mit } \hspace{0.2cm} \tilde{x}_i = 1 - 2 \cdot x_i \hspace{0.05cm},\hspace{0.2cm} \tilde{y}_i = 1 - 2 \cdot y_i \hspace{0.05cm},\hspace{0.2cm} \tilde{x}_i, \hspace{0.05cm}\tilde{y}_i \in \hspace{0.1cm}\{ -1, +1\} \hspace{0.05cm}.\]

Wir bezeichnen dieses innere Produkt manchmal auch als den  "Korrelationswert".  Im Unterschied zum  Korrelationskoeffizienten  kann der Korrelationswert den Wertebereich  $±1$  durchaus überschreiten.

Zusammenhang zwischen Haming–Distanz und Korrelationswert

$\text{Beispiel 4:}$  Wir betrachten hier zwei Binärfolgen der Länge  $L = 10$.

  • Links dargestellt sind die unipolaren Folgen  $\underline{x}$  und  $\underline{y}$  sowie das Produkt  $\underline{x} \cdot \underline{y}$.
  • Man erkennt die Hamming–Distanz  $d_{\rm H}(\underline{x}, \ \underline{y}) = 6$   ⇒   sechs Bitfehler an den Pfeilpositionen.
  • Das innere Produkt  $ < \underline{x} \cdot \underline{y} > \hspace{0.15cm} = \hspace{0.15cm}0$  hat hier keine Aussagekraft. Zum Beispiel ist  $< \underline{0} \cdot \underline{y} > $ unabhängig von  $\underline{y}$  stets Null.


Die Hamming–Distanz  $d_{\rm H} = 6$  erkennt man auch aus der bipolaren (antipodalen) Darstellung der rechten Grafik.

  • Die „Korrelationswert” hat nun den richtigen Wert:
$$4 \cdot (+1) + 6 \cdot (-1) = \, -2.$$
  • Es gilt der deterministische Zusammenhang zwischen den beiden Größen mit der Folgenlänge  $L$:
$$ < \underline{ \tilde{x} } \cdot \underline{\tilde{y} } > \hspace{0.15cm} = \hspace{0.15cm} L - 2 \cdot d_{\rm H} (\underline{\tilde{x} }, \hspace{0.05cm}\underline{\tilde{y} })\hspace{0.05cm}. $$


$\text{Fazit:}$  Interpretieren wir nun diese Gleichung für einige Sonderfälle:

  • Identische Folgen:   Die Hamming–Distanz ist gleich  $0$  und der „Korrelationswert” gleich  $L$.
  • Invertierte: Folgen:   Die Hamming–Distanz ist gleich  $L$  und der „Korrelationswert” gleich  $-L$.
  • Unkorrelierte Folgen:   Die Hamming–Distanz ist gleich  $L/2$, der „Korrelationswert” gleich  $0$.

Viterbi–Algorithmus, basierend auf Korrelation und Metriken


Mit den Erkenntnissen der letzten Seite lässt sich der Viterbi–Algorithmus auch wie folgt charakterisieren.

$\text{Alternative Beschreibung:}$  Der Viterbi–Algorithmus sucht von allen möglichen Codesequenzen  $\underline{x}' ∈ \mathcal{C}$  die Sequenz  $\underline{z}$  mit dem maximalen „ Korrelationswert” zur Empfangssequenz  $\underline{y}$:

\[\underline{z} = {\rm arg} \max_{\underline{x}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm} \left\langle \tilde{\underline{x} }'\hspace{0.05cm} ,\hspace{0.05cm} \tilde{\underline{y} } \right\rangle \hspace{0.4cm}{\rm mit }\hspace{0.4cm}\tilde{\underline{x} }\hspace{0.05cm}'= 1 - 2 \cdot \underline{x}'\hspace{0.05cm}, \hspace{0.2cm} \tilde{\underline{y} }= 1 - 2 \cdot \underline{y} \hspace{0.05cm}.\]

$〈\ \text{ ...} \ 〉$  bezeichnet einen „Korrelationswert” entsprechend den Aussagen auf der letzten Seite. Die Tilden weisen wieder auf die bipolare (antipodale) Darstellung hin.


Die Grafik zeigt die diesbezügliche Trellisauswertung. Zugrunde liegt wie für die  Trellisauswertung gemäß Beispiel 1  – basierend auf der minimalen Hamming–Distanz und den Fehlergrößen ${\it \Gamma}_i(S_{\mu})$ – wieder die Eingangsfolge  $\underline{u} = \big (0\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0 \hspace{0.05cm} \big )$   ⇒   Codefolge $\underline{x} = \big (00, 11, 10, 00, 01, 01, 11 \big ) \hspace{0.05cm}.$

Viterbi–Decodierung, basierend auf Korrelation und Metrik

Weiter werden vorausgesetzt:

  • der Standard–Faltungscodierer:   Rate  $R = 1/2$,  Gedächtnis  $m = 2$;
  • die Übertragungsfunktionsmatrix:   $\mathbf{G}(D) = (1 + D + D^2, 1 + D^2)$;
  • Länge der Informationssequenz:   $L = 5$;
  • Berücksichtigung der Terminierung:  $L' = 7$;
  • der Empfangsvektor   $\underline{y} = (11, 11, 10, 00, 01, 01, 11)$
    ⇒   zwei Bitfehler zu Beginn;
  • Viterbi–Decodierung mittels Trellisdiagramms:
    • roter Pfeil ⇒   Hypothese $u_i = 0$,
    • blauer Pfeil ⇒   Hypothese $u_i = 1$.


Nebenstehendes Trellis und die  Trellisauswertung gemäß Beispiel 1  ähneln sich sehr. Ebenso wie die Suche nach der Sequenz mit der minimalen Hamming–Distanz geschieht auch die  Suche nach dem maximalen Korrelationswert  schrittweise:

  • Die Knoten bezeichnet man hier als die Metriken  ${\it \Lambda}_i(S_{\mu})$.
  • Die englische Bezeichnung hierfür ist  Cumulative Metric, während  Branch Metric  den Metrikzuwachs angibt.
  • Der Endwert  ${\it \Lambda}_7(S_0) = 10$  gibt den „Korrelationswert” zwischen der ausgewählten Folge  $\underline{z}$  und dem Empfangsvektor  $\underline{y}$  an.
  • Im fehlerfreien Fall ergäbe sich  ${\it \Lambda}_7(S_0) = 14$.

$\text{Beispiel 5:}$  Die folgende Detailbeschreibung der Trellisauswertung beziehen sich auf das obige Trellis:

  • Die Metriken zum Zeitpunkt  $i = 1$  ergeben sich mit  $\underline{y}_1 = (11)$  zu
\[{\it \Lambda}_1(S_0) \hspace{0.15cm} = \hspace{0.15cm} <\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm} = \hspace{0.2cm}<(+1,\hspace{0.05cm} +1)\hspace{0.05cm}, \hspace{0.05cm}(-1,\hspace{0.05cm} -1) >\hspace{0.1cm} = \hspace{0.1cm} -2 \hspace{0.05cm},\]
\[{\it \Lambda}_1(S_1) \hspace{0.15cm} = \hspace{0.15cm} <\hspace{-0.05cm}(11)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm} = \hspace{0.2cm}<(-1,\hspace{0.05cm} -1)\hspace{0.05cm}, \hspace{0.05cm}(-1,\hspace{0.05cm} -1) >\hspace{0.1cm} = \hspace{0.1cm} +2 \hspace{0.05cm}.\]
  • Entsprechend gilt zum Zeitpunkt  $i = 2$  mit  $\underline{y}_2 = (11)$:
\[{\it \Lambda}_2(S_0) = {\it \Lambda}_1(S_0) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm} = \hspace{0.1cm} -2-2 = -4 \hspace{0.05cm},\]
\[{\it \Lambda}_2(S_1) = {\it \Lambda}_1(S_0) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(11)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm} = \hspace{0.1cm} -2+2 = 0 \hspace{0.05cm},\]
\[{\it \Lambda}_2(S_2)= {\it \Lambda}_1(S_1) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(10)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm} = \hspace{0.1cm} +2+0 = +2 \hspace{0.05cm},\]
\[{\it \Lambda}_2(S_3)= {\it \Lambda}_1(S_1) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(01)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm} = \hspace{0.1cm} +2+0 = +2 \hspace{0.05cm}.\]
  • Ab dem Zeitpunkt  $i =3$  muss eine Entscheidung zwischen zwei Metriken getroffen werden. Beispielsweise erhält man mit  $\underline{y}_3 = (10)$  für die oberste und die unterste Metrik im Trellis:
\[{\it \Lambda}_3(S_0)={\rm max} \left [{\it \Lambda}_{2}(S_0) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}>\hspace{0.2cm} \hspace{0.05cm}, \hspace{0.2cm}{\it \Lambda}_{2}(S_1) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(00)\hspace{0.05cm}, \hspace{0.05cm}(11) \hspace{-0.05cm}> \right ] = {\rm max} \left [ -4+0\hspace{0.05cm},\hspace{0.05cm} +2+0 \right ] = +2\hspace{0.05cm},\]
\[{\it \Lambda}_3(S_3) ={\rm max} \left [{\it \Lambda}_{2}(S_1) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(01)\hspace{0.05cm}, \hspace{0.05cm}(10) \hspace{-0.05cm}>\hspace{0.2cm} \hspace{0.05cm}, \hspace{0.2cm}{\it \Lambda}_{2}(S_3) \hspace{0.2cm}+ \hspace{0.1cm}<\hspace{-0.05cm}(10)\hspace{0.05cm}, \hspace{0.05cm}(10) \hspace{-0.05cm}> \right ] = {\rm max} \left [ 0+0\hspace{0.05cm},\hspace{0.05cm} +2+2 \right ] = +4\hspace{0.05cm}.\]

Vergleicht man die zu zu maximierenden Metriken  ${\it \Lambda}_i(S_{\mu})$  mit den zu minimierenden Fehlergrößen  ${\it \Gamma}_i(S_{\mu})$  gemäß dem  $\text{Beispiel 1}$, so erkennt man den folgenden deterministischen Zusammenhang:

\[{\it \Lambda}_i(S_{\mu}) = 2 \cdot \big [ i - {\it \Gamma}_i(S_{\mu}) \big ] \hspace{0.05cm}.\]

Die Auswahl der zu den einzelnen Decodierschritten überlebenden Zweige ist bei beiden Verfahren identisch, und auch die Pfadsuche liefert das gleiche Ergebnis.


$\text{Fazit:}$ 

  • Beim Binärkanal – zum Beispiel nach dem BSC–Modell – führen die beiden beschriebenen Viterbi–Varianten „Fehlergrößenminimierung” und „Metrikmaximierung” zum gleichen Ergebnis.
  • Beim AWGN–Kanal ist dagegen die Fehlergrößenminimierung nicht anwendbar, da keine Hamming–Distanz zwischen dem binären Eingang  $\underline{x}$  und dem analogen Ausgang  $\underline{y}$  angegeben werden kann.
  • Ein weiterer Vorteil der Metrikmaximierung ist, dass eine Zuverlässigkeitsinformation über die Empfangswerte  $\underline{y}$  in einfacher Weise berücksichtigt werden kann.


Viterbi–Entscheidung bei nicht–terminierten Faltungscodes


Bisher wurde stets ein terminierter Faltungscode der Länge  $L\hspace{0.05cm}' = L + m$  betrachtet, und das Ergebnis des Viterbi–Decoders war der durchgehende Trellispfad vom Startzeitpunkt  $(i = 0)$  bis zum Ende  $(i = L\hspace{0.05cm}')$.

  • Bei nicht–terminierten Faltungscodes  $(L\hspace{0.05cm}' → ∞)$  ist diese Entscheidungsstrategie nicht anwendbar.
  • Hier muss der Algorithmus abgewandelt werden, um in endlicher Zeit eine bestmögliche Schätzung (gemäß Maximum–Likelihood) der einlaufenden Bits der Codesequenz liefern zu können.


Die Grafik zeigt im oberen Teil ein beispielhaftes Trellis für

  • „unseren” Standard–Codierer   ⇒   $R = 1/2, \ m = 2, \ {\rm G}(D) = (1 + D + D^2, \ 1 + D^2)$,
  • die Nullfolge   ⇒   $\underline{u} = \underline{0} = (0, 0, 0, \ \text{...})$   ⇒   $\underline{x} = \underline{0} = (00, 00, 00, \ \text{...})$,
  • jeweils einen Übertragungsfehler bei  $i = 4$  und  $i = 5$.

Anhand der Stricharten erkennt man erlaubte (durchgezogene) und verbotene (punktierte) Pfeile in rot $(u_i = 0)$ und blau $(u_i = 1)$. Punktierte Linien haben einen Vergleich gegen einen Konkurrenten verloren und können nicht Teil des ausgewählten Pfades sein.

Beispielhaftes Trellis und überlebende Pfade

Der untere Teil der Grafik zeigt die  $2^m = 4$  überlebenden Pfade  ${\it \Phi}_9(S_{\mu})$  zum Zeitpunkt  $i = 9$.

  • Man findet diese Pfade am einfachsten von rechts nach links (Rückwärtsrichtung).
  • Die folgende Angabe zeigt die durchlaufenen Zustände  $S_{\mu}$  allerdings in Vorwärtsrichtung:
$${\it \Phi}_9(S_0) \text{:} \hspace{0.4cm} S_0 → S_0 → S_0 → S_0 → S_0 → S_0 → S_0 → S_0 → S_0 → S_0,$$
$${\it \Phi}_9(S_1) \text{:} \hspace{0.4cm} S_0 → S_0 → S_0 → S_0 → S_1 → S_2 → S_1 → S_3 → S_2 → S_1,$$
$${\it \Phi}_9(S_2) \text{:} \hspace{0.4cm} S_0 → S_0 → S_0 → S_0 → S_1 → S_2 → S_1 → S_2 → S_1 → S_2,$$
$${\it \Phi}_9(S_3) \text{:} \hspace{0.4cm} S_0 → S_0 → S_0 → S_0 → S_1 → S_2 → S_1 → S_2 → S_1 → S_3.$$

Zu früheren Zeitpunkten  $(i<9)$  würden sich andere überlebende Pfade  ${\it \Phi}_i(S_{\mu})$  ergeben. Deshalb definieren wir:

$\text{Definition:}$  Der  überlebende Pfad  (englisch:  Survivor)  ${\it \Phi}_i(S_{\mu})$  ist der durchgehende Pfad vom Start  $S_0$  $($bei  $i = 0)$  zum Knoten  $S_{\mu}$ zum Zeitpunkt  $i$. Empfehlenswert ist die Pfadsuche in Rückwärtsrichtung.


Die folgende Grafik zeigt die überlebenden Pfade für die Zeitpunkte  $i = 6$  bis  $i = 9$. Zusätzlich sind die jeweiligen Metriken  ${\it \Lambda}_i(S_{\mu})$  für alle vier Zustände angegeben.

Die überlebenden Pfade  ${\it \Phi}_6, \ \text{...} \ , \ {\it \Phi}_9$

Diese Grafik ist wie folgt zu interpretieren:

  • Zum Zeitpunkt  $i = 9$  kann noch keine endgültige ML–Entscheidung über die ersten neun Bit der Informationssequenz getroffen werden. Allerdings ist bereits sicher, dass die wahrscheinlichste Bitfolge durch einen der Pfade  ${\it \Phi}_9(S_0), \ \text{...} \ , \ {\it \Phi}_9(S_3)$  richtig wiedergegeben wird.
  • Da alle vier Pfade bis  $i = 3$  identisch sind, ist die Entscheidung „$v_1 = 0, v_2 = 0, \ v_3 = 0$” die bestmögliche (hellgraue Hinterlegung). Auch zu einem späteren Zeitpunkt würde keine andere Entscheidung getroffen werden. Hinsichtlich der Bits  $v_4, \ v_5, \ \text{...}$  sollte man sich zu diesem frühen Zeitpunkt noch nicht festlegen.
  • Müsste man zum Zeitpunkt  $i = 9$  eine Zwangsentscheidung treffen, so würde man sich für  ${\it \Phi}_9(S_0)$   ⇒   $\underline{v} = (0, 0, \ \text{...} \ , 0)$ entscheiden, da die Metrik  ${\it \Lambda}_9(S_0) = 14$  größer ist als die Vergleichsmetriken.
  • Die Zwangsentscheidung zum Zeitpunkt  $i = 9$  führt in diesem Beispiel zum richtigen Ergebnis. Zum Zeitpunkt  $i = 6$  wäre ein solcher Zwangsentscheid falsch gewesen   ⇒   $\underline{v} = (0, 0, 0, 1, 0, 1)$, und zu den Zeitpunten  $i = 7$  bzw.  $i = 8$  nicht eindeutig.


Weitere Decodierverfahren für Faltungscodes


Wir haben uns bisher nur mit dem Viterbi–Algorithmus in der Form beschäftigt, der 1967 von Andrew J. Viterbi in  [Vit67][1] veröffentlicht wurde. Erst 1974 hat  George David Forney  nachgewiesen, dass dieser Algorithmus eine Maximum–Likelihood–Decodierung von Faltungscodes durchführt.

Aber schon in den Jahren zuvor waren viele Wissenschaftler sehr bemüht, effiziente Decodierverfahren für die 1955 erstmals von  Peter Elias  beschriebenen Faltungscodes bereitzustellen. Zu nennen sind hier unter Anderem – genauere Beschreibungen findet man beispielsweise in  [Bos98][2] oder der englischen Ausgabe  [Bos99][3].

  • der Vorschlag von  Robert Mario Fano  (1963), der als Fano–Algorithmus  bekannt wurde,
  • die Arbeiten von Kamil Zigangirov (1966) und  Frederick Jelinek  (1969), deren Decodierverfahren auch als Stack–Algorithmus  bezeichnet wird.

Alle diese Decodierverfahren und auch der Viterbi–Algorithmus in seiner bisher beschriebenen Form liefern „hart” entschiedene Ausgangswerte   ⇒   $v_i ∈ \{0, 1\}$. Oftmals wären jedoch Informationen über die Zuverlässigkeit der getroffenen Entscheidungen wünschenswert, insbesondere dann, wenn ein verkettetes Codierschema mit einem äußeren und einem inneren Code vorliegt.

Kennt man die Zuverlässigkeit der vom inneren Decoder entschiedenen Bits zumindest grob, so kann durch diese Information die Bitfehlerwahrscheinlichkeit des äußeren Decoders (signifikant) herabgesetzt werden. Der von  Joachim Hagenauer  in  [Hag90][4] vorgeschlagene  Soft–Output–Viterbi–Algorithmus  (SOVA) erlaubt es, zusätzlich zu den entschiedenen Symbolen auch jeweils ein Zuverlässigkeitsmaß anzugeben.

Abschließend gehen wir noch etwas genauer auf den  BCJR–Algorithmus  ein, benannt nach dessen Erfindern L. R. Bahl, J. Cocke, F. Jelinek und J. Raviv  [BCJR74][5].

  • Während der Viterbi–Algorithmus nur eine Schätzung der Gesamtsequenz vornimmt   ⇒   block–wise ML, schätzt der BCJR–Algorithmus ein einzelnes Symbol (Bit) unter Berücksichtigung der gesamten empfangenen Codesequenz.
  • Es handelt sich hierbei also um eine  symbolweise Maximum–Aposteriori–Decodierung   ⇒   bit–wise MAP.


$\text{Fazit:}$  Der Unterschied zwischen Viterbi–Algorithmus und BCJR–Algorithmus soll – stark vereinfacht – am Beispiel eines terminierten Faltungscodes dargestellt werden:

  • Der  Viterbi–Algorithmus  arbeitet das Trellis nur in einer Richtung – der Vorwärtsrichtung  – ab und berechnet für jeden Knoten die Metriken  ${\it \Lambda}_i(S_{\mu})$. Nach Erreichen des Endknotens wird der überlebende Pfad gesucht, der die wahrscheinlichste Codesequenz kennzeichnet.
  • Beim  BCJR–Algorithmus  wird das Trellis zweimal abgearbeitet, einmal in Vorwärtsrichtung und anschließend in Rückwärtsrichtung. Für jeden Knoten sind dann zwei Metriken angebbar, aus denen für jedes Bit die Aposterori–Wahrscheinlichkeit bestimmt werden kann.


Hinweise:


Aufgaben zum Kapitel


Aufgabe 3.9: Grundlegendes zum Viterbi–Algorithmus

Aufgabe 3.9Z: Nochmals Viterbi–Algorithmus

Aufgabe 3.10: Fehlergrößenberechnung

Aufgabe 3.10Z: ML–Decodierung von Faltungscodes

Aufgabe 3.11: Viterbi–Pfadsuche

Quellenverzeichnis

  1. Viterbi, A.J.: Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm. In: IEEE Transactions on Information Theory, vol. IT-13, pp. 260-269, April 1967.
  2. 2,0 2,1 Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998.
  3. 3,0 3,1 Bossert, M.: Channel Coding for Telecommunications. Wiley & Sons, 1999.
  4. Hagenauer, J.: Soft Output Viterbi Decoder. In: Technischer Report, Deutsche Forschungsanstalt für Luft- und Raumfahrt (DLR), 1990.
  5. Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.: Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate. In: IEEE Transactions on Information Theory, Vol. IT-20, S. 284-287, 1974.