Aufgaben:Exercise 3.09: Basics of the Viterbi Algorithm - Revision history

Guenter at 13:08, 18 November 2022

2022-11-18T13:08:41Z

Guenter at 10:41, 18 November 2022

2022-11-18T10:41:09Z

Guenter at 10:40, 18 November 2022

2022-11-18T10:40:02Z

Guenter at 10:06, 18 November 2022

2022-11-18T10:06:41Z

Noah at 20:47, 17 October 2022

2022-10-17T20:47:15Z

Show changes

Guenter at 12:14, 10 October 2022

2022-10-10T12:14:16Z

Guenter: Guenter moved page Aufgaben:Aufgabe 3.09: Grundlegendes zum Viterbi–Algorithmus to Aufgaben:Exercise 3.09: Basics of the Viterbi Algorithm

2022-10-10T12:04:51Z

Guenter moved page Aufgabe 3.09: Grundlegendes zum Viterbi–Algorithmus to Exercise 3.09: Basics of the Viterbi Algorithm

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

2021-05-28T14:31:48Z

Text replacement - "„" to """

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

2021-05-28T14:26:06Z

Text replacement - "”" to """

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

2021-03-23T12:53:34Z

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

@@ Line 2: / Line 2: @@
 [[File:P_ID2659__KC_A_3_8.png|right|frame|Trellis to be analyzed]]
-The graph shows a trellis diagram and simultaneously defines the accumulated error values&nbsp; $($"metrics"$)$ &nbsp; ${\it \Gamma}_i(S_0)$&nbsp; and&nbsp; ${\it \Gamma}_i(S_1)$&nbsp; at times&nbsp; $i = 0$&nbsp; to&nbsp; $i = 5$.
+The graph shows a trellis diagram and simultaneously defines the cumulative error values&nbsp; $($"metrics"$)$ &nbsp; ${\it \Gamma}_i(S_0)$&nbsp; and&nbsp; ${\it \Gamma}_i(S_1)$&nbsp; at times&nbsp; $i = 0$&nbsp; to&nbsp; $i = 5$.
 From this trellis can be read,&nbsp; for example:

← Older revision		Revision as of 10:41, 18 November 2022
Line 108:		Line 108:


−	'''(5)''' <u> None of the proposed solutions</u> is correct, as can be seen from the ~~examples below~~.	+	'''(5)''' <u> None of the proposed solutions</u> is correct, as can be seen from the second graphic.

	{{ML-Fuß}}		{{ML-Fuß}}

@@ Line 68: / Line 68: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Correct are the <u>solutions 1 and 3</u>:
+'''(1)'''&nbsp; Correct are the&nbsp; <u>solutions 1 and 3</u>:
-*There are $2^{k \cdot m} = 2$ states here. It follows that $k = 1$ and $m = 1$.
+*There are &nbsp; $2^{k \cdot m} = 2$ &nbsp; states here.&nbsp; It follows that&nbsp; $k = 1$&nbsp; and&nbsp; $m = 1$.
 *Per coding step, $n = 2$ code bits are output &nbsp; &#8658; &nbsp; $R = 1/2$.
-*The information sequence length is $L = 4$.
+*Per coding step,&nbsp; $n = 2$&nbsp; code bits are output &nbsp; &#8658; &nbsp; $R = 1/2$.
-*Only by one (since $m = 1$) additional termination bit one arrives at the total length $L' = 5$.
-'''(2)'''&nbsp; The free distance $d_{\rm F}$ is defined as the number of codebits in which two sequences $\underline{x}$ and $\underline{x'}$ differ. We choose the zero sequence as the reference sequence:
+'''(2)'''&nbsp; The free distance&nbsp; $d_{\rm F}$&nbsp; is defined as the number of code bits in which two sequences&nbsp; $\underline{x}$&nbsp; and&nbsp; $\underline{x'}$&nbsp; differ.&nbsp;
 :$$\underline{x}\hspace{0.03cm}' = \underline{0} = \big (00\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, ... \hspace{0.1cm} \big ) \hspace{0.05cm},$$
-expressed with the sequence of states: &nbsp; $S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; \ \text{...} \ $
+:expressed with the sequence of states: &nbsp; $S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; \ \text{...} \ $
-*One of the sequences $\underline{x} &ne; \underline{0}$, which differs from $\underline{0}$ only in the minimum number of codebits, follows the path $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; \text{...} \ $:
+*One of the sequences&nbsp; $\underline{x} &ne; \underline{0}$,&nbsp; which differs from &nbsp; $\underline{0}$ &nbsp; only in the minimum number of code bits,&nbsp; follows the path&nbsp; $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; \text{...} \ $:
 :$$\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 00\hspace{0.05cm}, 00\hspace{0.05cm}, ... \hspace{0.1cm} \big )
 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} d_{\rm F}\hspace{0.1cm}\underline{ = 3}
@@ Line 86: / Line 90: @@
-'''(3)'''&nbsp; Only <u>proposition 3</u> is correct here, because the event "No transmission error" is much more likely than three errors at exactly specified positions. Consider the following graphic:
+'''(3)'''&nbsp; Only&nbsp; <u>proposition 3</u>&nbsp; is correct here,&nbsp; because the event&nbsp; "No transmission error"&nbsp; is much more likely than three errors at exactly specified positions.&nbsp; Consider the graph:
-[[File:P_ID2660__KC_A_3_9c.png|center|frame|Trellis without error/with three transmission errors]]
+*For the lower trellis,&nbsp; we also assume&nbsp; $\underline{u} = (0, \, 0, \, 0, \, 0 \, 0) &nbsp; &#8658; &nbsp; \underline{x} = (00, \, 00, \, 00, \, 00, \, 00)$.
-*If the zero sequence is sent and this is also received, the Viterbi decoding can be illustrated by the upper trellis.
+*However,&nbsp; $\underline{y} = (00, \, 00, \, 00, \, 11, \, 01)$&nbsp; is received now.&nbsp;
 '''(5)'''&nbsp;<u> None of the proposed solutions</u> is correct, as can be seen from the examples below.
 {{ML-Fuß}}

@@ Line 2: / Line 2: @@
 [[File:P_ID2659__KC_A_3_8.png|right|frame|Trellis to be analyzed]]
-The graph shows a trellis diagram and simultaneously defines the branch metrics&nbsp; ${\it \Gamma}_i(S_0)$&nbsp; and&nbsp; ${\it \Gamma}_i(S_1)$&nbsp; at times&nbsp; $i = 0$&nbsp; to&nbsp; $i = 5$.
+The graph shows a trellis diagram and simultaneously defines the accumulated error values&nbsp; $($"metrics"$)$ &nbsp; ${\it \Gamma}_i(S_0)$&nbsp; and&nbsp; ${\it \Gamma}_i(S_1)$&nbsp; at times&nbsp; $i = 0$&nbsp; to&nbsp; $i = 5$.
-From this trellis can be read, for example:
+From this trellis can be read,&nbsp; for example:
 * the code rate&nbsp; $R$,
 * the memory&nbsp; $m$,
 * the free distance&nbsp; $d_{\rm F}$,
 * the information sequence length&nbsp; $L$,
 * the sequence length&nbsp; $L\hspace{0.05cm}'$&nbsp; including the termination.
 In the exercise it is further necessary to clarify:
-* the meaning of the final value&nbsp; ${\it \Gamma}_5(S_0)$,
+* the meaning of the final error value&nbsp; ${\it \Gamma}_5(S_0)$,
@@ Line 23: / Line 25: @@
-Hint:
+<u>Hint:</u>&nbsp; This exercise belongs to the chapter&nbsp; [[Channel_Coding/Decoding_of_Convolutional_Codes| "Decoding of Convolutional Codes"]].
@@ Line 37: / Line 38: @@
 {Which of the following statements are confirmed by the trellis?
 |type="[]"}
-+ It is a rate 1/2 convolutional code.
++ It is a rate-1/2 convolutional code.
 - The memory of the code is&nbsp; $m = 2$.
 + The convolutional code is terminated.
@@ Line 46: / Line 47: @@
 $d_{\rm F} \ = \ ${ 3 3% }
-{What statements does the final value&nbsp; ${\it \Gamma}_5(S_0) = 0$&nbsp; of the branch metric allow?
+{What statements does the final value&nbsp; ${\it \Gamma}_5(S_0) = 0$&nbsp; of the metric allow?
 |type="[]"}
 - No transmission error has occurred.
-- The decoding result&nbsp; $\underline{v}$&nbsp; is certainly correct $($equal&nbsp; $\underline{u})$.
+- The decoding result &nbsp; $\underline{v}$ &nbsp; is certainly correct&nbsp; $($equal&nbsp; $\underline{u})$.
-+ The decoding result minimizes the probability&nbsp; ${\rm Pr}(\underline{v} &ne; \underline{u})$.
++ The decoding result minimizes the probability &nbsp; ${\rm Pr}(\underline{v} &ne; \underline{u})$.
-{Which statements are true <u>in the case of a single</u> transmission error?
+{Which statements are true&nbsp; <u>in the case of a single</u>&nbsp; transmission error?
 |type="[]"}
-+ The final branch metric is&nbsp; ${\it \Gamma}_5(S_0) = 1$.
++ The final metric is&nbsp; ${\it \Gamma}_5(S_0) = 1$.
 + The decoding result&nbsp; $\underline{v}$&nbsp; is certainly correct&nbsp; $($equal&nbsp; $\underline{u})$.
-+ The decoding result minimizes the probability&nbsp; ${\rm Pr}(\underline{v} &ne; \underline{u})$.
++ The decoding result minimizes the probability &nbsp; ${\rm Pr}(\underline{v} &ne; \underline{u})$.
-{Which statements are true <u>in the case of two</u> transmission errors?
+{Which statements are true&nbsp; <u>in the case of two</u>&nbsp; transmission errors?
 |type="[]"}
-- The final branch metric is&nbsp; ${\it \Gamma}_5(S_0) = 2$.
+- The final metric is&nbsp; ${\it \Gamma}_5(S_0) = 2$.
 - The decoding result&nbsp; $\underline{v}$&nbsp; is certainly correct&nbsp; $($equal&nbsp; $\underline{u})$.
 - The decoding result&nbsp; $\underline{v}$&nbsp; is certainly false&nbsp; $($unequal&nbsp; $\underline{u})$.

← Older revision		Revision as of 12:14, 10 October 2022
Line 108:		Line 108:


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

← Older revision		Revision as of 14:31, 28 May 2021
Line 86:		Line 86:


−	'''(3)'''  Richtig ist hier nur der <u>Vorschlag 3</u>, weil das Ereignis ~~&bdquo;~~Kein Übertragungsfehler" sehr viel wahrscheinlicher ist als drei Fehler an genau vorgegebenen Positionen. Betrachten Sie hierzu die folgende Grafik:	+	'''(3)'''  Richtig ist hier nur der <u>Vorschlag 3</u>, weil das Ereignis "Kein Übertragungsfehler" sehr viel wahrscheinlicher ist als drei Fehler an genau vorgegebenen Positionen. Betrachten Sie hierzu die folgende Grafik:

	[[File:P_ID2660__KC_A_3_9c.png\|center\|frame\|Trellis ohne Fehler/mit drei Übertragungsfehlern]]		[[File:P_ID2660__KC_A_3_9c.png\|center\|frame\|Trellis ohne Fehler/mit drei Übertragungsfehlern]]

← Older revision		Revision as of 14:26, 28 May 2021
Line 86:		Line 86:


−	'''(3)'''  Richtig ist hier nur der <u>Vorschlag 3</u>, weil das Ereignis &bdquo;Kein Übertragungsfehler~~”~~ sehr viel wahrscheinlicher ist als drei Fehler an genau vorgegebenen Positionen. Betrachten Sie hierzu die folgende Grafik:	+	'''(3)'''  Richtig ist hier nur der <u>Vorschlag 3</u>, weil das Ereignis &bdquo;Kein Übertragungsfehler" sehr viel wahrscheinlicher ist als drei Fehler an genau vorgegebenen Positionen. Betrachten Sie hierzu die folgende Grafik:

	[[File:P_ID2660__KC_A_3_9c.png\|center\|frame\|Trellis ohne Fehler/mit drei Übertragungsfehlern]]		[[File:P_ID2660__KC_A_3_9c.png\|center\|frame\|Trellis ohne Fehler/mit drei Übertragungsfehlern]]

← Older revision		Revision as of 12:53, 23 March 2021
Line 108:		Line 108:


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