Aufgaben:Exercise 3.09Z: Viterbi Algorithm again - Revision history

Guenter at 13:06, 18 November 2022

2022-11-18T13:06:24Z

Guenter at 12:43, 18 November 2022

2022-11-18T12:43:08Z

Guenter at 10:57, 18 November 2022

2022-11-18T10:57:34Z

Noah at 19:08, 18 October 2022

2022-10-18T19:08:36Z

Noah at 19:04, 18 October 2022

2022-10-18T19:04:18Z

Show changes

Guenter at 12:15, 10 October 2022

2022-10-10T12:15:12Z

Guenter: Guenter moved page Aufgaben:Aufgabe 3.09Z: Nochmals Viterbi–Algorithmus to Aufgaben:Exercise 3.09Z: Viterbi Algorithm again

2022-10-10T12:07:20Z

Guenter moved page Aufgabe 3.09Z: Nochmals Viterbi–Algorithmus to Exercise 3.09Z: Viterbi Algorithm again

Javier: Text replacement - "„" to """

2021-05-28T14:31:49Z

Text replacement - "„" to """

Javier: Text replacement - "”" to """

2021-05-28T14:24:18Z

Text replacement - "”" to """

Javier: Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

2021-03-23T12:48:33Z

Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

@@ Line 37: / Line 37: @@
-&rArr; &nbsp; Then the continuous path from&nbsp; ${\it \Gamma}_0(S_0)$&nbsp; to&nbsp; ${\it \Gamma}_5(S_0)$&nbsp; is to be found,&nbsp; where the backward direction is recommended.&nbsp; If one follows the found path in forward direction,&nbsp; one recognizes:
+&rArr; &nbsp; Then the continuous path from&nbsp; ${\it \Gamma}_0(S_0)$&nbsp; to&nbsp; ${\it \Gamma}_5(S_0)$&nbsp; is to be found,&nbsp; where the backward direction is recommended.&nbsp;
 * the most likely decoded sequence&nbsp; $\underline{z}$&nbsp; $($ideally equal&nbsp; $\underline{x})$&nbsp; by the labels,
@@ Line 84: / Line 86: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; [[File:P_ID2657__KC_Z_3_8a_v1.png|right|frame|Trellis with branch metrics]] Starting from&nbsp; ${\it \Gamma}_2(S_0) = 0, \ {\it \Gamma}_2(S_1) = 2$ we get $\underline{y}_3 = (01)$:
+[[File:P_ID2657__KC_Z_3_8a_v1.png|right|frame|Trellis with branch metrics]]
 :$${\it \Gamma}_3(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm min} \left [0 + d_{\rm H} \big ((00), (01) \big ), \hspace{0.05cm}2 + d_{\rm H} \big ((01), (01) \big ) \right ] = {\rm min} \left [ 0+1\hspace{0.05cm},\hspace{0.05cm} 2+0 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm},$$
 :$${\it \Gamma}_3(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [0 + d_{\rm H} \big ((11), (01) \big ), \hspace{0.05cm}2 + d_{\rm H} \big ((10), (01) \big ) \right ] {\rm min} \left [ 0+1\hspace{0.05cm},\hspace{0.05cm} 2+2 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}.$$
-Thus, eliminated are the two subpaths that start from state $S_1$ at time $i = 2$ (i.e., at the third decoding step) &nbsp; &#8658; &nbsp; Dotted in the graph.
+&#8658; &nbsp; Eliminated are the two (dotted)&nbsp;  subpaths that start from state&nbsp; $S_1$&nbsp; at time&nbsp; $i = 2$&nbsp; $($i.e.,&nbsp; at the third decoding step$)$.
-'''(2)'''&nbsp; Analogous to subtask (1), we obtain with&nbsp; $y_4 = (11)$:
+'''(2)'''&nbsp; Analogous to subtask&nbsp; '''(1)''',&nbsp; we obtain with&nbsp; $y_4 = (11)$:
 :$${\it \Gamma}_4(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [1 + d_{\rm H} \big ((00), (11) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((01), (11) \big ) \right ] = {\rm min} \left [ 1+2\hspace{0.05cm},\hspace{0.05cm} 1+1 \right ] \hspace{0.15cm}\underline{= 2}\hspace{0.05cm},$$
 :$${\it \Gamma}_4(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [1 + d_{\rm H} \big ((11), (11) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((10), (11) \big ) \right ] ={\rm min} \left [ 1+0\hspace{0.05cm},\hspace{0.05cm} 1+1 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}$$
-&#8658; &nbsp; Elimination in the fourth decoding step of the two subpaths $S_0 &#8594; S_0$ and $S_1 &#8594; S_1$.
+&#8658; &nbsp; Elimination in the fourth decoding step of the two subpaths&nbsp; "$S_0 &#8594; S_0$"&nbsp; and&nbsp; "$S_1 &#8594; S_1$".
-[[File:P_ID2658__KC_Z_3_8d.png|right|frame|Path finding]]
+'''(3)'''&nbsp; For&nbsp;  $i = 5$ &nbsp; &#8658; &nbsp; the&nbsp; "termination"&nbsp; is obtained with&nbsp; $\underline{y}_5 = (01)$:
 :$${\it \Gamma}_5(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [2 + d_{\rm H} \big ((00), (01) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((01), (01) \big ) \right ]  {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 1+0 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}.$$
-To be eliminated here is the subpath $S_0 &#8594; S_0$.
+&#8658; &nbsp; To be eliminated is the subpath&nbsp;  "$S_0 &#8594; S_0$".
-'''(4)'''&nbsp; The backward search of the continuous path from ${\it \Gamma}_5(S_0)$ to ${\it \Gamma}_0(S_0)$ yields
+'''(4)'''&nbsp; The backward search of the continuous path&nbsp;  from ${\it \Gamma}_5(S_0)$&nbsp;  to&nbsp;  ${\it \Gamma}_0(S_0)$&nbsp;  yields
 :$$S_0 &#8592; S_1 &#8592; S_0 &#8592; S_0 &#8592; S_1 &#8592; S_0.$$
-In the forward direction, this yields the path $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; S_1 &#8594; S_0$ and thus the
+In the forward direction,&nbsp;  this yields the path&nbsp;  "$S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; S_1 &#8594; S_0$" and thus the
-* the most likely code sequence $\underline{z} = (11, \, 01, \, 00, \, 11, \, 01)$,
+* the most likely code sequence&nbsp;  $\underline{z} = (11, \, 01, \, 00, \, 11, \, 01)$,
 * the most likely information sequence $\underline{v} = (1, \, 0, \, 0, \, 1, \, 0)$.
-'''(5)'''&nbsp; Without termination &#8658; final decision at $i = 4$, there would have been two continuous paths:
+* from&nbsp; "$S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; S_1$"&nbsp; $($the ultimately correct path$)$.
-The constraint decision at time $i = 4$ would have led here to the second path and thus to the result $\underline{v} = (1, \, 0, \, 0, \, 1)$ because of ${\it \Gamma}_4(S_1) < {\it \Gamma}_4(S_0)$.
+The constraint decision at time&nbsp; $i = 4$&nbsp; would have led here to the second path and thus to the result&nbsp; $\underline{v} = (1, \, 0, \, 0, \, 1)$&nbsp; because of&nbsp; ${\it \Gamma}_4(S_1) < {\it \Gamma}_4(S_0)$.
 *In the considered example, therefore, to the <u>same decision</u> as in subtask (4) with termination bit.
-*However, there are many constellations where only the termination bit enables the correct and safe decision.
+*In the considered example,&nbsp; therefore,&nbsp; to the&nbsp; <u>same decision</u>&nbsp; as in subtask&nbsp; '''(4)'''&nbsp; with termination bit.
 {{ML-Fuß}}

@@ Line 55: / Line 55: @@
 ===Questions===
 <quiz display=simple>
-{Calculate the minimum branch metrics for time&nbsp; $i = 3$.
+{Calculate the minimum error values for time&nbsp; $i = 3$.
 |type="{}"}
 ${\it \Gamma}_3(S_0) \ = \ ${ 1 }
 ${\it \Gamma}_3(S_1) \ = \ ${ 1 }
-{Calculate the minimum branch metrics for time&nbsp; $i = 4$.
+{Calculate the minimum error values for time&nbsp; $i = 4$.
 |type="{}"}
 ${\it \Gamma}_4(S_0) \ = \ ${ 2 }
 ${\it \Gamma}_4(S_1) \ = \ ${ 1 }
-{Calculate the minimum branch metrics for time&nbsp; $i = 5$ (end).
+{Calculate the final error value for time&nbsp; $i = 5$.
 |type="{}"}
 ${\it \Gamma}_5(S_0) \ = \ ${ 1 }

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Decoding_of_Convolutional_Codes}}
-[[File:P_ID2656__KC_Z_3_8_neu.png|right|frame|Trellis for a rate 1/2 code, memory&nbsp; $m = 1$]]
+[[File:P_ID2656__KC_Z_3_8_neu.png|right|frame|Trellis for a rate-1/2 code and memory&nbsp; $m = 1$]]
-The diagram shows the trellis of the convolutional code according to&nbsp; [[Aufgaben:Exercise_3.6:_State_Transition_Diagram| "Exercise 3.6"]], characterized by the following quantities:
+The diagram shows the trellis of the convolutional code according to&nbsp; [[Aufgaben:Exercise_3.6:_State_Transition_Diagram|$\text{Exercise 3.6}$]],&nbsp; characterized by the following quantities:
 * Rate 1/2&nbsp; &#8658; &nbsp; $k = 1, \ n = 2$,
 * memory&nbsp; $m = 1$,
 * transfer function matrix&nbsp; $\mathbf{G}(D) = (1, \ 1 + D)$,
 * length of information sequence:&nbsp; $L = 4$,
 * sequence length including termination:&nbsp; $L\hspace{0.05cm}' = L + m = 5$.
-On the basis of this representation, the Viterbi decoding is to be understood step by step, starting from the following reception sequence: &nbsp; $\underline{y} = (11, \, 01, \, 01, \, 11, \, 01)$.
+On the basis of this representation,&nbsp; the Viterbi decoding is to be understood step-by-step,&nbsp; starting from the following received sequence: &nbsp;
-Drawn into the trellis are:
+Into the trellis are drawn:
-* The initial value&nbsp; ${\it \Gamma}_0(S_0)$&nbsp; for the Viterbi&ndash;algorithm, which is always chosen to&nbsp; $0$&nbsp;.
+* The initial value&nbsp; ${\it \Gamma}_0(S_0)$&nbsp; for the Viterbi algorithm,&nbsp; which is always chosen to&nbsp; $0$.
-* The two branch metrics for the first decoding step&nbsp; $(i = 1)$&nbsp; are obtained with&nbsp; $\underline{y}_1 = (11)$&nbsp; as follows:
 :$${\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}.$$
-* The branch metrics to step&nbsp; $i = 2$ &nbsp; &#8658; &nbsp; $\underline{y}_2 = (01)$&nbsp; are obtained by the following comparisons:
+* The error values for step&nbsp; $i = 2$ &nbsp; &#8658; &nbsp; $\underline{y}_2 = (01)$&nbsp; are obtained by the following comparisons:
 :$${\it \Gamma}_2(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{1}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{1}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] $$
 :$$\Rightarrow\hspace{0.3cm} {\it \Gamma}_2(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm min} \big [ 2+1\hspace{0.05cm},\hspace{0.05cm} 0+0 \big ] = 0\hspace{0.05cm},$$
@@ Line 25: / Line 31: @@
-In the same way you are to
+In the same way you are
-* compute the branch metrics at time points&nbsp; $i = 3, \ i = 4$&nbsp; and&nbsp; $i = 5$&nbsp; (termination), and
+* to compute the error values at time points&nbsp; $i = 3, \ i = 4$&nbsp; and&nbsp; $i = 5$&nbsp; $($termination$)$,&nbsp; and
-* eliminate the less favorable paths to a node&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; in each case. In the graph this is indicated by dotted lines for&nbsp; $i = 2$&nbsp;.
-Then the continuous path from&nbsp; ${\it \Gamma}_0(S_0)$&nbsp; to&nbsp; ${\it \Gamma}_5(S_0)$&nbsp; is to be found, where the backward direction is recommended.
+&rArr; &nbsp; Then the continuous path from&nbsp; ${\it \Gamma}_0(S_0)$&nbsp; to&nbsp; ${\it \Gamma}_5(S_0)$&nbsp; is to be found,&nbsp; where the backward direction is recommended.&nbsp; If one follows the found path in forward direction,&nbsp; one recognizes:
 * the most probable information sequence&nbsp; $\underline{v}$&nbsp; $($ideally equal&nbsp; $\underline{u})$&nbsp; at the colors.
@@ Line 41: / Line 47: @@
+<u>Hints:</u>&nbsp; This exercise belongs to the chapter&nbsp; [[Channel_Coding/Decoding_of_Convolutional_Codes|"Decoding of Convolutional Codes"]].

@@ Line 95: / Line 95: @@
-[[File:P_ID2658__KC_Z_3_8d.png|right|frame|Path search]]
+[[File:P_ID2658__KC_Z_3_8d.png|right|frame|Path finding]]
 '''(3)'''&nbsp; Für $i = 5$ &nbsp; &#8658; &nbsp; "Termination" is obtained with&nbsp; $\underline{y}_5 = (01)$:
 :$${\it \Gamma}_5(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [2 + d_{\rm H} \big ((00), (01) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((01), (01) \big ) \right ]  {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 1+0 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}.$$

← Older revision		Revision as of 12:15, 10 October 2022
Line 126:		Line 126:


−	[[Category:Channel Coding: Exercises\|^3.4 ~~Decodierung von Faltungscodes~~^]]	+	[[Category:Channel Coding: Exercises\|^3.4 Decoding of Convolutional Codes^]]

← Older revision	Revision as of 12:07, 10 October 2022
(No difference)

@@ Line 96: / Line 96: @@
 [[File:P_ID2658__KC_Z_3_8d.png|right|frame|Pfadsuche]]
-'''(3)'''&nbsp; Für $i = 5$ &nbsp; &#8658; &nbsp; &bdquo;Terminierung" erhält man mit&nbsp; $\underline{y}_5 = (01)$:
+'''(3)'''&nbsp; Für $i = 5$ &nbsp; &#8658; &nbsp; "Terminierung" erhält man mit&nbsp; $\underline{y}_5 = (01)$:
 :$${\it \Gamma}_5(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [2 + d_{\rm H} \big ((00), (01) \big ), \hspace{0.05cm}1 + d_{\rm H} \big ((01), (01) \big ) \right ]  {\rm min} \left [ 2+1\hspace{0.05cm},\hspace{0.05cm} 1+0 \right ] \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}.$$

← Older revision		Revision as of 12:48, 23 March 2021
Line 126:		Line 126:


−	[[Category:~~Aufgaben zu Kanalcodierung~~\|^3.4 Decodierung von Faltungscodes^]]	+	[[Category:Channel Coding: Exercises\|^3.4 Decodierung von Faltungscodes^]]