Aufgaben:Exercise 4.08: Repetition to the Convolutional Codes - Revision history

Guenter at 15:59, 19 December 2022

2022-12-19T15:59:46Z

Guenter at 13:42, 14 December 2022

2022-12-14T13:42:38Z

Guenter at 10:47, 14 December 2022

2022-12-14T10:47:36Z

Guenter at 09:46, 14 December 2022

2022-12-14T09:46:30Z

Guenter at 09:05, 14 December 2022

2022-12-14T09:05:59Z

Guenter at 09:02, 14 December 2022

2022-12-14T09:02:44Z

Noah at 18:44, 29 November 2022

2022-11-29T18:44:02Z

Noah at 20:20, 26 November 2022

2022-11-26T20:20:44Z

Noah at 20:20, 26 November 2022

2022-11-26T20:20:29Z

Noah at 18:36, 26 November 2022

2022-11-26T18:36:39Z

Show changes

@@ Line 106: / Line 106: @@
 G^{(2)}(D) =  1+  D^2\hspace{0.05cm}. $$
-[[File:P_ID3038__KC_A_4_8c_v1.png|right|frame|Three examples of rate 1/2 convolutional encoders]]
+[[File:EN_KC_A_4_8c_v1.png|right|frame|Three examples of rate 1/2 convolutional encoders]]
 Going beyond the question,&nbsp; we also consider here the filter structure at hand.&nbsp; In the diagram,&nbsp; the encoder considered here is shown as coder&nbsp; $\rm A$&nbsp; on the left.

← Older revision		Revision as of 13:42, 14 December 2022
Line 14:		Line 14:


−	In the state transition diagram,  ~~the start state  $S_0$  is always assumed.  Two~~ arrows go from each state.  The label is  "$u_i \hspace{0.05cm}\|\hspace{0.05cm} x_i^{(1)}x_i^{(2)}$".  For a systematic code,  this holds:	+	In the state transition diagram,  two arrows go from each state.  The label is  "$u_i \hspace{0.05cm}\|\hspace{0.05cm} x_i^{(1)}x_i^{(2)}$".  For a systematic code,  this holds:
	* The first encoded bit is identical to the information bit:   $\ x_i^{(1)} = u_i ∈ \{0, \, 1\}.$		* The first encoded bit is identical to the information bit:   $\ x_i^{(1)} = u_i ∈ \{0, \, 1\}.$

@@ Line 108: / Line 108: @@
 [[File:P_ID3038__KC_A_4_8c_v1.png|right|frame|Three examples of rate 1/2 convolutional encoders]]
-Going beyond the question,&nbsp; we also consider here the filter structure at hand.[[File:P_ID3038__KC_A_4_8c_v1.png|center|frame|Three examples of rate 1/2 convolutional encoders]]
+Going beyond the question,&nbsp; we also consider here the filter structure at hand.&nbsp; In the diagram,&nbsp; the encoder considered here is shown as coder&nbsp; $\rm A$&nbsp; on the left.
- In the diagram, the encoder considered here is shown as coder $\rm A$ on the left.
+* This is systematic like the encoder&nbsp; $\rm B$.&nbsp;  But,&nbsp; unlike encoder&nbsp; $\rm B$,&nbsp; it is based on a non-recursive filter.
 '''(4)'''&nbsp; Correct are the <u>proposed solutions 2 and 3</u>:
-*The exercise could be solved in the same way as subtask (2).
+'''(4)'''&nbsp; Correct are the&nbsp; <u>proposed solutions 2 and 3</u>:
-*However, we choose here for a change the way about the $D$&ndash;transform:
+*The exercise could be solved in the same way as subtask&nbsp; '''(2)'''.&nbsp; However,&nbsp; we choose here for a change the way about the $D$&ndash;transform:
 :$$\underline{u}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad
 U(D) =  1+  D^2 + D^5$$
@@ Line 128: / Line 125: @@
-'''(5)'''&nbsp; The free distance $d_{\rm F}$ of a convolutional encoder is equal to the minimum number of bits by which any two sequences of this code differ.
+'''(5)'''&nbsp; The free distance&nbsp; $d_{\rm F}$&nbsp; of a convolutional encoder is equal to the minimum number of bits by which any two sequences of this code differ.
-*If we take as a reference the zero sequence, as is commonly done&nbsp; $\underline{0} \ \Rightarrow \ S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; \ \text{ ...} \ $&nbsp; off, then $d_{\rm F}$ is simultaneously obtained as the minimum Hamming weight (number of ones) of an admissible code sequence&nbsp; $\underline{x} &ne; \underline{0}$.
+*If we take as a reference the zero sequence&nbsp; $\underline{0}\ \Rightarrow \ S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; \ \text{ ...} \ $,&nbsp; &nbsp; as is commonly done then&nbsp; $d_{\rm F}$&nbsp; is simultaneously obtained as the minimum Hamming weight&nbsp; $($number of&nbsp; "ones"$)$&nbsp; of an admissible encoded sequence&nbsp; $\underline{x} &ne; \underline{0}$.
-*From the state transition diagram, we can see that the free distance for example is given by the path.
+*From the state transition diagram,&nbsp; we can see that the free distance e.g. is given by the path
 :$$ S_0 &#8594; S_0 &#8594; S_1 &#8594; S_2 &#8594; S_0 &#8594; S_0 &#8594; \text{ ...}$$
-:thus identified by the code sequence $00 \hspace{0.1cm} 11 \hspace{0.1cm} 00 \hspace{0.1cm} 01 \hspace{0.1cm} 00 \text{ ...} \ .$
+:thus identified by the encoded sequence&nbsp; $00 \hspace{0.1cm} 11 \hspace{0.1cm} 00 \hspace{0.1cm} 01 \hspace{0.1cm} 00 \text{ ...} \ .$
-*Accordingly, for the free distance of this non-recursive code, $\hspace{0.2cm} d_{\rm F} \ \underline{= 3}$.
+*Accordingly,&nbsp; for the free distance of this non-recursive code &nbsp; &rArr; &nbsp;  $\hspace{0.2cm} d_{\rm F} \ \underline{= 3}$.
 {{ML-Fuß}}

@@ Line 68: / Line 68: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Correct is the <u>proposed solution 2</u>:
+'''(1)'''&nbsp; Correct is the&nbsp; <u>proposed solution 2</u>:
-*The impulse response $\underline{g}$ is equal to the output sequence $\underline{p}$ for the input sequence $\underline{u} = (1, \, 0, \, 0, \, 0, \text{ ...})$.
+*The impulse response&nbsp; $\underline{g}$&nbsp; is equal to the output sequence &nbsp; $\underline{p}$ &nbsp; for the input sequence&nbsp; $\underline{u} = (1, \, 0, \, 0, \, 0, \text{ ...})$.
 *Based on the state $S_0$, the state transition diagram results in the following transitions:
 :$$S_0 &#8594; S_1 &#8594; S_2 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; \text{ ...} \hspace{0.6cm} \Rightarrow \hspace{0.5cm} {\rm impulse\:response} \text{:} \hspace{0.2cm} \underline{g} = (1, \, 0, \, 1, \, 0, \, 0) \, .$$
-*For a non-recursive filter with memory $m$, $g_i &equiv; 0$ holds for $i > m$. In our example, $m = 2$.
+*For a non-recursive filter with memory&nbsp; $m$ &nbsp; &rArr; &nbsp;  $g_i &equiv; 0$&nbsp; holds for&nbsp; $i > m$.&nbsp; In our example,&nbsp; $m = 2$.
-*In contrast, the proposed solution 1 applies to the recursive filter (RSC) corresponding to [[Aufgaben:Exercise_4.09:_Recursive_Systematic_Convolutional_Codes| "Exercise 4.9"]].
-'''(2)'''&nbsp; Let $\underline{u} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, u_7)$ and $\underline{g} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, ...)$. Then the following holds for the parity-check sequence due to linearity:
+'''(2)'''&nbsp; Let be &nbsp; $\underline{u} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, u_7)$ &nbsp; and &nbsp; $\underline{g} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, ...)$.&nbsp;
 :$$\underline{p} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}
 (\hspace{0.05cm}1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \hspace{0.05cm} 0,\hspace{0.05cm} u_7\hspace{0.05cm} )
@@ Line 86: / Line 89: @@
   \hspace{0.05cm}.$$
-Correct are therefore the <u>proposed solutions 1 and 2</u> in contrast to the answer 3:
+*Correct are therefore the&nbsp; <u>proposed solutions 1 and 2</u>&nbsp; in contrast to the answer 3:
-*For $u_7 = 1$ gilt $p_7 = 1, \ p_8 = 0, \ p_9 = 1$ and $p_i &equiv; 0$ for $i > 9$.
-'''(3)'''&nbsp; Correct is the <u>proposed solution 2</u>:
+'''(3)'''&nbsp; Correct is the&nbsp; <u>proposed solution 2</u>:
-*From the state transition diagram one can see the code parameters $k = 1$ and $n = 2$.
+*From the state transition diagram one can see the code parameters&nbsp; $k = 1$&nbsp; and&nbsp; $n = 2$.
-*This means: the transfer function matrix $\mathbf{G}(D)$ consists of two elements &nbsp; &#8658; &nbsp; the proposition 3 is wrong.
-* The first component of $\mathbf{G}(D)$ is actually 1, since there is a systematic code: $\ \underline{x}^{(1)} &equiv; \underline{z}$.
+*This means:&nbsp; The transfer function matrix&nbsp; $\mathbf{G}(D)$&nbsp; consists of two elements &nbsp; &#8658; &nbsp; the proposition 3 is wrong.
-* The second component of $\mathbf{G}(D)$ is equal to the $D$&ndash;transform of the impulse response $\underline{g}$, where the dummy&ndash;variable $D$ indicates a delay of one bit:
 :$$\underline{g}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} \text{ ...}\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad
 G^{(2)}(D) =  1+  D^2\hspace{0.05cm}. $$
-Going beyond the question, we also consider here the filter structure at hand:
+Going beyond the question,&nbsp; we also consider here the filter structure at hand.[[File:P_ID3038__KC_A_4_8c_v1.png|center|frame|Three examples of rate 1/2 convolutional encoders]]
+ In the diagram, the encoder considered here is shown as coder $\rm A$ on the left.
 * This is systematic like the encoder $\rm B$, and
 * but, unlike coder $\rm B$, is based on a non-recursive filter.

@@ Line 11: / Line 11: @@
 #[[Channel_Coding/Code_Description_with_State_and_Trellis_Diagram#Definition_of_the_free_distance|"Definition of the free distance"]]
 #[[Channel_Coding/Algebraic_and_Polynomial_Description#GF.282.29_description_forms_of_a_digital_filter|"GF(2) description forms of a digital filter"]]
-#[[Channel_Coding/Algebraic_and_Polynomial_Description#Application_of_the_D.E2.80.93transform_to_rate_.7F.27.22.60UNIQ-MathJax160-QINU.60.22.27.7F_convolution_encoders| "Application of $D$&ndash;transform to rate&nbsp; $1/n$&nbsp; convolutional codes."]]
+#[[Channel_Coding/Algebraic_and_Polynomial_Description#Application_of_the_D.E2.80.93transform_to_rate_.7F.27.22.60UNIQ-MathJax158-QINU.60.22.27.7F_convolution_encoders| "Application of $D$&ndash;transform to rate&nbsp; $1/n$&nbsp; convolutional codes."]]

@@ Line 3: / Line 3: @@
 [[File:P_ID3033__KC_A_4_8_v2.png|right|frame|State transition diagram of a non-recursive code]]
-The turbo codes are based on convolutional codes, which are discussed in detail in the chapter&nbsp; [[Channel_Coding/Basics_of_Convolutional_Coding| "Basics of Convolutional Coding"]]&nbsp;.
+The turbo codes are based on convolutional codes,&nbsp; which are discussed in detail in the chapter&nbsp; [[Channel_Coding/Basics_of_Convolutional_Coding| "Basics of Convolutional Coding"]].
-Starting from the adjacent state transition diagram, essential properties and characteristics of the considered rate $1/2$ convolutional code shall be determined, and we explicitly refer to the following theory pages:
+Starting from the adjacent state transition diagram,&nbsp; essential properties and characteristics of the considered rate&nbsp; $1/2$&nbsp; convolutional code shall be determined,&nbsp; and we explicitly refer to the following theory sections:
 #[[Channel_Coding/Algebraic_and_Polynomial_Description#Systematic_convolutional_codes|"Systematic convolutional codes"]]
@@ Line 11: / Line 11: @@
 #[[Channel_Coding/Code_Description_with_State_and_Trellis_Diagram#Definition_of_the_free_distance|"Definition of the free distance"]]
 #[[Channel_Coding/Algebraic_and_Polynomial_Description#GF.282.29_description_forms_of_a_digital_filter|"GF(2) description forms of a digital filter"]]
-#[[Channel_Coding/Algebraic_and_Polynomial_Description#Application_of_the_D.E2.80.93transform_to_rate_.7F.27.22.60UNIQ-MathJax160-QINU.60.22.27.7F_convolution_encoders| "Application of $D$&ndash;transform to rate 1/n convolutional codes."]]
+#[[Channel_Coding/Algebraic_and_Polynomial_Description#Application_of_the_D.E2.80.93transform_to_rate_.7F.27.22.60UNIQ-MathJax160-QINU.60.22.27.7F_convolution_encoders| "Application of $D$&ndash;transform to rate&nbsp; $1/n$&nbsp; convolutional codes."]]
-In the state transition diagram, the state&nbsp; $S_0$&nbsp; is always assumed. Two arrows go from each state. The label is "$u_i \hspace{0.05cm}|\hspace{0.05cm} x_i^{(1)}x_i^{(2)}$". For a systematic code, this holds:
+In the state transition diagram,&nbsp; the start state&nbsp; $S_0$&nbsp; is always assumed.&nbsp; Two arrows go from each state.&nbsp; The label is&nbsp; "$u_i \hspace{0.05cm}|\hspace{0.05cm} x_i^{(1)}x_i^{(2)}$".&nbsp; For a systematic code,&nbsp; this holds:
-* The first code bit is identical to the information bit: &nbsp; $\ x_i^{(1)} = u_i &#8712; \{0, \, 1\}$
+* The first encoded bit is identical to the information bit: &nbsp; $\ x_i^{(1)} = u_i &#8712; \{0, \, 1\}.$
-* The second code bit is the parity-check bit: &nbsp; $\ x_i^{(2)} = p_i &#8712; \{0, \, 1\}$.
@@ Line 25: / Line 26: @@
 Hints:
 * The exercise refers to the chapter&nbsp; [[Channel_Coding/The_Basics_of_Turbo_Codes| "Basics of Turbo Codes"]].
 * The following semi&ndash;infinite vectors are used in the questions for this exercise:
 :* information sequence&nbsp; $\ \underline{u} = (u_1, \, u_2, \text{ ...})$,
 :* parity-check sequence&nbsp; $\ \underline{p} = (p_1, \, p_2, \text{ ...})$,
-:* impulse response&nbsp; $\ \underline{g} = (g_1, \, g_2, \text{ ...})$; this is equal to the parity-check sequence&nbsp; $\underline{p}$&nbsp; for&nbsp; $\underline{u} = (1, \, 0, \, 0, \text{ ...})$.
+:* impulse response&nbsp; $\ \underline{g} = (g_1, \, g_2, \text{ ...})$;&nbsp; this is equal to the parity-check sequence &nbsp; $\underline{p}$ &nbsp; for &nbsp; $\underline{u} = (1, \, 0, \, 0, \text{ ...})$.
@@ Line 38: / Line 40: @@
 {What is the impulse response&nbsp; $\underline{g}&nbsp;$?
 |type="()"}
-- $\underline{g} = (1, \, 1, \,1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \text{ ...})$ holds.
+- $\underline{g} = (1, \, 1, \,1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \text{ ...})$.
-+ $\underline{g} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \text{ ...})$ holds.
++ $\underline{g} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \text{ ...})$.
-{Now let&nbsp; $\underline{u} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, u_7)$&nbsp; with&nbsp; $u_7 &#8712; \{0, \, 1\}$. Which statements are true for the parity-check sequence&nbsp; $\underline{p}$&nbsp;?
+{Now let&nbsp; $\underline{u} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, u_7)$&nbsp; be with&nbsp; $u_7 &#8712; \{0, \, 1\}$.&nbsp; Which statements are true for the parity-check sequence &nbsp; $\underline{p}$&nbsp;?
 |type="[]"}
 + The first six bits of the parity-check sequence are&nbsp; "$1, \, 0, \, 1, \, 1, \, 0, \, 1$".
@@ Line 53: / Line 55: @@
 - It holds&nbsp; $\mathbf{G}(D) = \big [1 + D^2 \big ]$.
-{Now consider the bounded input sequence&nbsp; $\underline{u} = (1, \, 0, \, 1, \, 0, \, 0, \, 1)$. Which statements hold for the then also bounded parity-check sequence&nbsp; $\underline{p}$?
+{Now consider the limited input sequence &nbsp; $\underline{u} = (1, \, 0, \, 1, \, 0, \, 0, \, 1)$.&nbsp; Which statements hold for the then also limited parity-check sequence &nbsp; $\underline{p}$?
 |type="[]"}
-- The first eight bits of the parity-check sequence are&nbsp; "$1, \, 0, \, 1, \, 1, \, 1, \, 0, \, 1, \, 0$."
+- The first eight bits of the parity-check sequence are &nbsp; "$1, \, 0, \, 1, \, 1, \, 1, \, 0, \, 1, \, 0$".
-+ The first eight bits of the parity-check sequence are&nbsp; "$1, \, 0, \, 0, \, 0, \, 1, \, 1, \, 0, \, 1$".
++ The first eight bits of the parity-check sequence are &nbsp; "$1, \, 0, \, 0, \, 0, \, 1, \, 1, \, 0, \, 1$".
-+ It holds&nbsp; $p_i = 0$&nbsp; for &nbsp;$i &#8805; 9$.
++ It holds &nbsp; $p_i = 0$ &nbsp; for &nbsp;$i &#8805; 9$.
 {What is the free distance&nbsp; $d_{\rm F}$&nbsp; of the considered convolutional code?

@@ Line 121: / Line 121: @@
-'''(5)'''&nbsp; Die freie Distanz $d_{\rm F}$ eines Faltungscoders ist gleich der Anzahl der Bits, durch die sich zwei beliebigen Sequenzen dieses Codes mindestens unterscheiden.
+'''(5)'''&nbsp; The free distance $d_{\rm F}$ of a convolutional encoder is equal to the minimum number of bits by which any two sequences of this code differ.
-*Gehen wir wie allgemein üblich als Bezugsgröße von der Nullsequenz&nbsp; $\underline{0} \ \Rightarrow \ S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; \ \text{ ...} \ $&nbsp; aus, so ergibt sich $d_{\rm F}$ gleichzeitig als das minimale Hamming&ndash;Gewicht (Anzahl der Einsen) einer zulässigen Codesequenz&nbsp; $\underline{x} &ne; \underline{0}$.
+*If we take as a reference the zero sequence, as is commonly done&nbsp; $\underline{0} \ \Rightarrow \ S_0 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; \ \text{ ...} \ $&nbsp; off, then $d_{\rm F}$ is simultaneously obtained as the minimum Hamming weight (number of ones) of an admissible code sequence&nbsp; $\underline{x} &ne; \underline{0}$.
-*Aus dem Zustandsübergangsdiagramm erkennt man, dass die freie Distanz zum Beispiel durch den Pfad
+*From the state transition diagram, we can see that the free distance for example is given by the path.
 :$$ S_0 &#8594; S_0 &#8594; S_1 &#8594; S_2 &#8594; S_0 &#8594; S_0 &#8594; \text{ ...}$$
-:gekennzeichnet ist, also durch die Codesequenz $00 \hspace{0.1cm} 11 \hspace{0.1cm} 00 \hspace{0.1cm} 01 \hspace{0.1cm} 00 \text{ ...} \  .$
+:thus identified by the code sequence $00 \hspace{0.1cm} 11 \hspace{0.1cm} 00 \hspace{0.1cm} 01 \hspace{0.1cm} 00 \text{ ...} \ .$
-*Dementsprechend gilt für die freie Distanz dieses nichtrekursiven Codes: $\hspace{0.2cm} d_{\rm F} \ \underline{= 3}$.
+*Accordingly, for the free distance of this nonrecursive code, $\hspace{0.2cm} d_{\rm F} \ \underline{= 3}$.
 {{ML-Fuß}}