Difference between revisions of "Aufgaben:Exercise 3.09Z: Viterbi Algorithm again"

Revision as of 22:37, 3 December 2017

Trellis für einen Rate–1/2–Code mit Gedächtnis

$m = 1$

Die Grafik zeigt das Trellisdiagramm das Faltungscodes entsprechend Aufgabe A3.6, gekennzeichnet durch folgende Größen:

Rate 1/2 ⇒ $k = 1, \ n = 2$ ,
Gedächtnis $m = 1$ ,
Übertragungsfunktionsmatrix $\mathbf{G}(D) = (1, \ 1 + D)$ ,
Länge der Informationssequenz: $L = 4$ ,
Sequenzlänge inclusive Terminierung: $L' = L + m = 5$ .

Anhand dieser Darstellung soll die Viterbi–Decodierung schrittweise nachvollzogen werde, wobei von der folgenden Empfangssequenz auszugehen ist: $\underline{y} = (11, \, 01, \, 01, \, 11, \, 01)$ .

In das Trellis eingezeichnet sind:

Der Initialwert ${\it \Gamma}_0(S_0)$ für den Viterbi–Algorithmus wird stets zu $0$ gewählt.
Die beiden Fehlergrößen für den ersten Decodierschritt $(i = 1)$ erhält man mit $\underline{y}_1 = (11)$ wie folgt:

${\it \Gamma}_1(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\it \Gamma}_0(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (11) \big ) = 2 \hspace{0.05cm},$

${\it \Gamma}_1(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\it \Gamma}_0(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (11) \big ) = 0 \hspace{0.05cm}.$

Die Fehlergrößen zum Schritt $i = 2$ ⇒ $\underline{y}_2 = (01)$ egeben sich durch folgende Vergleiche:

${\it \Gamma}_2(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{1}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{1}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] =$

$\ = \ \hspace{-0.15cm} {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+0 \right ] = 0\hspace{0.05cm},$

${\it \Gamma}_2(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{1}(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{1}(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] =$

$\ = \ \hspace{-0.15cm} {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+2 \right ] = 2\hspace{0.05cm}.$

Fragebogen

Musterlösung

Solution

(1) (2) (3) (4) (5)

@@ Line 1: / Line 1: @@
-{{quiz-Header|Buchseite=Kanalcodierung/Decodierung von Faltungscodes
+{{quiz-Header|Buchseite=Kanalcodierung/Decodierung von Faltungscodes}}
+[[File:P_ID2656__KC_Z_3_8_neu.png|right|frame|Trellis für einen Rate–1/2–Code mit Gedächtnis  $m = 1$ ]]
+Die Grafik zeigt das Trellisdiagramm das Faltungscodes entsprechend [[Aufgaben:3.6_Zustands%C3%BCbergangsdiagramm| Aufgabe A3.6]], gekennzeichnet durch folgende Größen:
+* Rate 1/2 &nbsp;&#8658;&nbsp;  $k = 1, \ n = 2$ ,
+* Gedächtnis  $m = 1$ ,
+* Übertragungsfunktionsmatrix  $\mathbf{G}(D) = (1, \ 1 + D)$ ,
+* Länge der Informationssequenz:  $L = 4$ ,
+* Sequenzlänge inclusive Terminierung:  $L' = L + m = 5$ .
+Anhand dieser Darstellung soll die Viterbi&ndash;Decodierung schrittweise nachvollzogen werde, wobei von der folgenden Empfangssequenz auszugehen ist:  $\underline{y} = (11, \, 01, \, 01, \, 11, \, 01)$ .
+In das Trellis eingezeichnet sind:
+* Der Initialwert  ${\it \Gamma}_0(S_0)$  für den Viterbi&ndash;Algorithmus wird stets zu  $0$  gewählt.
+* Die beiden Fehlergrößen für den ersten Decodierschritt  $(i = 1)$  erhält man mit  $\underline{y}_1 = (11)$  wie folgt:
+: ${\it \Gamma}_1(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\it \Gamma}_0(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (11) \big )  = 2  \hspace{0.05cm},$
+: ${\it \Gamma}_1(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\it \Gamma}_0(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (11) \big )  = 0  \hspace{0.05cm}.$
+* Die Fehlergrößen zum Schritt  $i = 2$  &nbsp;&#8658;&nbsp;  $\underline{y}_2 = (01)$  egeben sich durch folgende Vergleiche:
+: ${\it \Gamma}_2(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{1}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{1}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] =$
+: $\ = \ \hspace{-0.15cm} {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+0 \right ] = 0\hspace{0.05cm},$
+: ${\it \Gamma}_2(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{1}(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{1}(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] =$
+: $\ = \ \hspace{-0.15cm} {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+2 \right ] = 2\hspace{0.05cm}.$
-}}
-[[File:|right|]]
 ===Fragebogen===
 <quiz display=simple>
-{Multiple-Choice Frage
+{Multiple-Choice
 |type="[]"}
-- Falsch
++ correct
-+ Richtig
+- false
 {Input-Box Frage
 |type="{}"}
-$\alpha$ = { 0.3 }
+$xyz \ = \ ${ 5.4 3% }  $ab$
 </quiz>
 ===Musterlösung===
 {{ML-Kopf}}
-'''1.'''
+'''(1)'''&nbsp;
-'''2.'''
+'''(2)'''&nbsp;
-'''3.'''
+'''(3)'''&nbsp;
-'''4.'''
+'''(4)'''&nbsp;
-'''5.'''
+'''(5)'''&nbsp;
-'''6.'''
-'''7.'''
 {{ML-Fuß}}
-[[Category:Aufgaben zu  Kanalcodierung|^3.4 Decodierung von Faltungscodes
+[[Category:Aufgaben zu  Kanalcodierung|^3.4 Decodierung von Faltungscodes^]]
-^]]