Difference between revisions of "Aufgaben:Exercise 3.3Z: Convolution and D-Transformation"

From LNTwww
m (Text replacement - "”" to """)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
{{quiz-Header|Buchseite=Kanalcodierung/Algebraische und polynomische Beschreibung}}
+
{{quiz-Header|Buchseite=Channel_Coding/Algebraic_and_Polynomial_Description}}
  
−
[[File:P_ID2628__KC_Z_3_3.png|right|frame|Vorgegebene Filterstruktur]]
+
[[File:P_ID2628__KC_Z_3_3.png|right|frame|Predefined filter structure]]
  
−
In dieser Aufgabe beschreiben wir an einem einfachen Beispiel
+
In this exercise, we use a simple example to describe
−
* die endliche&nbsp; <b>Impulsantwort</b> &nbsp;eines Filters:
+
* the finite&nbsp; &raquo;<b>impulse response</b>&laquo; &nbsp;of a filter:
 
:$$\underline{g} = \left (g_0, g_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, g_l, \hspace{0.05cm}\text{...}\hspace{0.1cm}, g_m \right )
 
:$$\underline{g} = \left (g_0, g_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, g_l, \hspace{0.05cm}\text{...}\hspace{0.1cm}, g_m \right )
 
\hspace{0.05cm},\hspace{0.2cm}g_l \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}, $$
 
\hspace{0.05cm},\hspace{0.2cm}g_l \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}, $$
−
* die&nbsp; <b>Eingangssequenz</b>&nbsp; des Filters:
+
 
 +
* the&nbsp; &raquo;<b>input sequence</b>&laquo;&nbsp; of the filter:
 
:$$\underline{u} = \left (u_0, u_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, u_i, \hspace{0.05cm}\text{...}\hspace{0.1cm} \right )
 
:$$\underline{u} = \left (u_0, u_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, u_i, \hspace{0.05cm}\text{...}\hspace{0.1cm} \right )
 
\hspace{0.05cm},\hspace{0.2cm}u_i \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}, $$
 
\hspace{0.05cm},\hspace{0.2cm}u_i \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}, $$
−
* die&nbsp; <b>Ausgangssequenz</b>&nbsp; des Filters:
+
* the&nbsp; &raquo;<b>output sequence</b>&laquo;&nbsp; of the filter:
 
:$$\underline{x} = \left (x_0, x_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, x_i, \hspace{0.05cm}\text{...}\hspace{0.1cm} \right )
 
:$$\underline{x} = \left (x_0, x_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, x_i, \hspace{0.05cm}\text{...}\hspace{0.1cm} \right )
 
\hspace{0.05cm},\hspace{0.2cm}x_i \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}. $$
 
\hspace{0.05cm},\hspace{0.2cm}x_i \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}. $$
  
−
Die Nomenklatur für diese (digitale) Filterbeschreibung haben wir an das Buch "Einführung in die Kanalcodierung" angepasst. In anderen&nbsp; $\rm LNTwww$&ndash;Büchern bezeichnet oft&nbsp; $\underline{x}$&nbsp; den Filtereingang,&nbsp; $\underline{y}$&nbsp; den Filterausgang, und die Impulsantwort wird&nbsp; $h$&nbsp; genannt.
+
We have adapted the nomenclature for this&nbsp; $($digital$)$&nbsp; filter description to the book&nbsp; "Introduction to Channel Coding".&nbsp; In other&nbsp; $\rm LNTww$ books often&nbsp;  
 +
# &nbsp;$\underline{x}$&nbsp; denotes the filter input,&nbsp;
 +
# &nbsp;$\underline{y}$&nbsp; the filter output,&nbsp; and
 +
# &nbsp;the impulse response is called&nbsp; $\underline{h}$.
  
−
Allgemein gilt für die Ausgangssequenz entsprechend der&nbsp; [[Signal_Representation/The_Convolution_Theorem_and_Operation#Faltung_im_Zeitbereich| Faltung]]&nbsp; (englisch: &nbsp;<i>Convolution</i>&nbsp;):
 
−
:$$\underline{x} = \underline{u}* \underline{g} = \left (x_0, x_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, x_i, \hspace{0.05cm}\text{...}\hspace{0.1cm} \right )\hspace{0.05cm},\hspace{0.1cm} {\rm mit} \hspace{0.2cm} x_i = \sum_{l = 0}^{m} g_l \cdot u_{i-l}\hspace{0.05cm}.$$
 
  
−
Wir repräsentieren nun die Zeitfunktionen&nbsp; $\underline{g}, \ \underline{u}$&nbsp; und&nbsp; $\underline{x}$&nbsp; durch Polynome in einer Dummy&ndash;Variablen&nbsp; $D$&nbsp; und nennen diese die&nbsp; $D$&ndash;Transformierten:
+
In general,&nbsp; for the output sequence corresponding to the&nbsp; [[Signal_Representation/The_Convolution_Theorem_and_Operation#Convolution_in_the_time_domain| $\text{convolution}$]]&nbsp;:
 +
:$$\underline{x} = \underline{u}* \underline{g} = \left (x_0, x_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, x_i, \hspace{0.05cm}\text{...}\hspace{0.1cm} \right )\hspace{0.05cm},\hspace{0.1cm} {\rm with} \hspace{0.2cm} x_i = \sum_{l = 0}^{m} g_l \cdot u_{i-l}\hspace{0.05cm}.$$
 +
 
 +
*We now represent the time functions &nbsp; $\underline{g}, \ \underline{u}$ &nbsp; and &nbsp; $\underline{x}$&nbsp; by polynomials in a dummy variable&nbsp; $D$&nbsp; and call these the&nbsp; D&ndash;transforms:
 
:$$\underline{g}  \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm}
 
:$$\underline{g}  \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm}
 
{G}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \sum_{l = 0}^{m} g_l \cdot D\hspace{0.03cm}^l = g_0 + g_1 \cdot D + g_2 \cdot D^2 + \text{...} + g_m \cdot D\hspace{0.03cm}^m\hspace{0.05cm},$$
 
{G}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \sum_{l = 0}^{m} g_l \cdot D\hspace{0.03cm}^l = g_0 + g_1 \cdot D + g_2 \cdot D^2 + \text{...} + g_m \cdot D\hspace{0.03cm}^m\hspace{0.05cm},$$
Line 27: Line 32:
 
{X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.03cm}^i = x_0 + x_1 \cdot D + x_2 \cdot D^2 + \text{...} \hspace{0.05cm}.$$
 
{X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.03cm}^i = x_0 + x_1 \cdot D + x_2 \cdot D^2 + \text{...} \hspace{0.05cm}.$$
  
−
Damit wird aus der (komplizierteren) Faltung eine Multiplikation:
+
*Thus the&nbsp; $($more complicated$)$&nbsp; convolution becomes a multiplication:
 
:$$\underline{x} = \underline{u}* \underline{g}  \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm}
 
:$$\underline{x} = \underline{u}* \underline{g}  \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm}
 
{X}(D) = U(D) \cdot G(D) \hspace{0.05cm}.$$
 
{X}(D) = U(D) \cdot G(D) \hspace{0.05cm}.$$
  
−
Formal lässt sich dieser Zusammenhang wie folgt nachweisen:
+
*Formally,&nbsp; this relationship can be demonstrated as follows:
 
:$${X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.03cm}^i = \sum_{i = 0}^{\infty} \sum_{l = 0}^{m}\hspace{0.1cm}
 
:$${X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.03cm}^i = \sum_{i = 0}^{\infty} \sum_{l = 0}^{m}\hspace{0.1cm}
 
  g_l \cdot u_{i-l} \cdot D\hspace{0.03cm}^{i} =  \sum_{l = 0}^{m} \hspace{0.1cm} g_l \cdot \sum_{j = -l}^{\infty} \hspace{0.1cm}
 
  g_l \cdot u_{i-l} \cdot D\hspace{0.03cm}^{i} =  \sum_{l = 0}^{m} \hspace{0.1cm} g_l \cdot \sum_{j = -l}^{\infty} \hspace{0.1cm}
Line 39: Line 44:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
−
Hierbei wurde berücksichtigt, dass alle&nbsp; $u_j$&nbsp; für&nbsp; $j < 0$&nbsp; nicht existieren und zu Null gesetzt werden können.
+
*Here it was considered that all &nbsp; $u_j$ &nbsp; for&nbsp; $j < 0$&nbsp; do not exist and can be set to zero.
−
 
 
−
Beide Vorgehensweisen zur Berechnung der Ausgangssequenz&nbsp; $\underline{x}$, nämlich
 
−
* über die Faltung
 
−
* mit Hilfe der $D$&ndash;Transformation,
 
−
 
 
  
−
sollen für das oben skizzierte Digitale Filter demonstriert werden.
+
*Both procedures for computing the initial sequence&nbsp; $\underline{x}$&nbsp; shall be demonstrated for the digital filter outlined above,&nbsp; viz.
 +
# &nbsp; using the convolution,
 +
# &nbsp; by means of the D&ndash;transformation.
  
  
Line 52: Line 54:
  
  
 +
<u>Hints:</u>
 +
* The exercise belongs to the chapter&nbsp; [[Channel_Coding/Algebraic_and_Polynomial_Description| "Algebraic and Polynomial Description"]].
  
 +
* Refer in particular to the&nbsp; [[Channel_Coding/Algebraic_and_Polynomial_Description#GF.282.29_description_forms_of_a_digital_filter|"GF(2) Description Forms of a Digital Filter"]]&nbsp; section.
  
−
''Hinweise:''
+
* In the solution,&nbsp; consider the following identity for calculations in&nbsp; $\rm GF(2)$:
−
* Die Aufgabe gehört zum Kapitel&nbsp; [[Channel_Coding/Algebraische_und_polynomische_Beschreibung| Algebraische und polynomische Beschreibung]].
 
−
* Bezug genommen wird insbesondere auf die Seite&nbsp; [[Channel_Coding/Algebraische_und_polynomische_Beschreibung#GF.282.29.E2.80.93Beschreibungsformen_eines_Digitalen_Filters|GF(2)&ndash;Beschreibungsformen eines Digitalen Filters]].
 
−
* Berücksichtigen Sie bei der Lösung die folgende Identität für Berechnungen in&nbsp; $\rm GF(2)$:
 
 
:$$1 + D + D^2 + D^3  + \hspace{0.05cm}\text{...}\hspace{0.1cm}= \frac{1}{1+D} \hspace{0.05cm}.$$
 
:$$1 + D + D^2 + D^3  + \hspace{0.05cm}\text{...}\hspace{0.1cm}= \frac{1}{1+D} \hspace{0.05cm}.$$
 
   
 
   
Line 63: Line 65:
  
  
−
===Fragebogen===
+
===Questions===
 
<quiz display=simple>
 
<quiz display=simple>
−
{Wie lauten die vorliegenden Filterkoeffizienten?
+
{What are the present filter coefficients?
 
|type="{}"}
 
|type="{}"}
 
$g_0 \ = \ ${ 1 }
 
$g_0 \ = \ ${ 1 }
Line 71: Line 73:
 
$g_2 \ = \ ${ 0. }
 
$g_2 \ = \ ${ 0. }
  
−
{Die Sequenz&nbsp; $\underline{u} = (1, \, 0, \, 0, \, 1)$&nbsp; sei endlich. Wie lautet die Ausgangssequenz?
+
{The sequence&nbsp; $\underline{u} = (1, \, 0, \, 0, \, 1)$&nbsp; let be finite.&nbsp; What is the output sequence?
 
|type="()"}
 
|type="()"}
 
- $\underline{x} = (1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
+ $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
+ $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
−
- $\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; "Dauer&ndash;Einsfolge".
+
- $\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; "sequence of ones".
  
−
{Die Sequenz&nbsp; $\underline{u} = (1, \, 1, \, 1)$&nbsp; sei endlich. Wie lautet die Ausgangssequenz?
+
{The sequence&nbsp; $\underline{u} = (1, \, 1, \, 1)$&nbsp; let be finite.&nbsp; What is the output sequence?
 
|type="()"}
 
|type="()"}
 
- $\underline{x} = (1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
+ $\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
+ $\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
−
- $\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; "Dauer&ndash;Einsfolge".
+
- $\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; "sequence of ones".
  
−
{Wie lautet die Ausgangssequenz für&nbsp; $\underline{u} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm}.)$ &nbsp; &#8658; &nbsp; "Dauer&ndash;Einsfolge"?
+
{What is the output sequence for&nbsp; $\underline{u} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm}.)$ &nbsp; &#8658; &nbsp; "sequence of ones"?
 
|type="()"}
 
|type="()"}
 
+ $\underline{x} = (1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
+ $\underline{x} = (1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \,\text{...}\hspace{0.05cm})$.
 
- $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \,\text{...}\hspace{0.05cm})$.
−
- $\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; "Dauer&ndash;Einsfolge".
+
- $\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; "sequence of ones".
  
−
{Für welchen Vektor&nbsp; $\underline{u}$&nbsp; tritt am Ausgang die Folge&nbsp; $\underline{x} = (1, \, 1, \, 1, \, 1, \ \text{...}\hspace{0.05cm})$&nbsp; auf?
+
{For which vector&nbsp; $\underline{u}$&nbsp; does the sequence&nbsp; $\underline{x} = (1, \, 1, \, 1, \, 1, \ \text{...}\hspace{0.05cm})$&nbsp; occur at the output?
 
|type="()"}
 
|type="()"}
−
- $\underline{u} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; "Dauer&ndash;Einsfolge"
+
- $\underline{u} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; "sequence of ones"
−
+ $\underline{u} = (1, \, 0, \, 1, \, 0, \, 1, \, 0, \,\text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; alternierende Folge, beginnend mit $1$.
+
+ $\underline{u} = (1, \, 0, \, 1, \, 0, \, 1, \, 0, \,\text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; alternating sequence, starting with&nbsp; "$1$".
−
- $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; alternierende Folge, beginnend mit $0$.
+
- $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; alternating sequence, starting with&nbsp; "$0$".
 
</quiz>
 
</quiz>
  
−
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
−
'''(1)'''&nbsp; Die beiden einzigen von $0$ verschiedenen Filterkoeffizienten sind $g_0 \ \underline{= 1}$ und $g_1 \ \underline{= 1}$.  
+
'''(1)'''&nbsp; The only two filter coefficients different from&nbsp; $0$&nbsp; are&nbsp; $g_0 \ \underline{= 1}$&nbsp; and&nbsp; $g_1 \ \underline{= 1}$.  
−
*Daraus folgt $g_2 \ \underline{= 0}$ und für die $D$&ndash;Transformierte der Impulsantwort:
+
*From this follows&nbsp; $g_2 \ \underline{= 0}$&nbsp; and for the D&ndash;transform of the impulse response:
 
:$$\underline{g} = (1\hspace{0.05cm},\hspace{0.05cm} 1)  \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm}
 
:$$\underline{g} = (1\hspace{0.05cm},\hspace{0.05cm} 1)  \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm}
 
{G}(D) = 1+ D \hspace{0.05cm}.$$
 
{G}(D) = 1+ D \hspace{0.05cm}.$$
Line 108: Line 110:
  
  
−
'''(2)'''&nbsp; Die Impulsantwort des betrachteten Filters ist $\underline{g} = (1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.  
+
'''(2)'''&nbsp; The impulse response of the considered filter is&nbsp; $\underline{g} = (1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.  
−
*Für die Ausgangssequenz erhält man deshalb das Faltungsprodukt
+
*For the output sequence,&nbsp; therefore,&nbsp; we obtain the convolution product
 
:$$\underline{x} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \underline{u}* \underline{g} =  
 
:$$\underline{x} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \underline{u}* \underline{g} =  
 
(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}\hspace{0.05cm},\hspace{0.05cm} 0\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}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} ...\hspace{0.05cm}) *  
Line 115: Line 117:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
−
*Zum gleichen Ergebnis kommt man über die $D$&ndash;Transformierten $U(D) = 1 + D^3$ und $G(D) = 1 + D$:
+
*The same result is obtained using the D&ndash;transforms&nbsp; $U(D) = 1 + D^3$&nbsp; and&nbsp; $G(D) = 1 + D$:
 
:$${X}(D) = U(D) \cdot G(D) = ( 1+D^3) \cdot (1+D) = 1 +D + D^3 +D^4
 
:$${X}(D) = U(D) \cdot G(D) = ( 1+D^3) \cdot (1+D) = 1 +D + D^3 +D^4
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
−
*Die Rücktransformation führt wieder zum Ergebnis $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$ &nbsp;&#8658;&nbsp; <u>Lösungsvorschlag 3</u>.
+
*The inverse transformation leads again to the result&nbsp; $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; <u>Proposed solution 3</u>.
  
  
  
−
'''(3)'''&nbsp; Hier verwenden wir sofort den Weg über die $D$&ndash;Transformierten:
+
'''(3)'''&nbsp; Here we immediately use the path over the D&ndash;transforms:
 
:$${X}(D) =  ( 1+D+D^2) \cdot (1+D) = 1 +D + D +D^2 +D^2 +D^3 = 1+ D^3\hspace{0.3cm}  
 
:$${X}(D) =  ( 1+D+D^2) \cdot (1+D) = 1 +D + D +D^2 +D^2 +D^3 = 1+ D^3\hspace{0.3cm}  
 
\Rightarrow \hspace{0.3cm} \underline{x}  =  
 
\Rightarrow \hspace{0.3cm} \underline{x}  =  
Line 129: Line 131:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
−
*Das Ergebnis entspricht dem <u>Lösungsvorschlag 2</u>. Die folgende Berechnung soll den Weg im Zeitbereich veranschaulichen:
+
*The result corresponds to the&nbsp; <u>proposed solution 2</u>.&nbsp; The following calculation is to illustrate the path in the time domain:
 
:$$(1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm}) *  
 
:$$(1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm}) *  
 
(1\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})\hspace{-0.15cm} \ = \ \hspace{-0.15cm}(1\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},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm},$$
 
(1\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})\hspace{-0.15cm} \ = \ \hspace{-0.15cm}(1\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},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm},$$
Line 137: Line 139:
 
(1\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} ... \hspace{0.05cm})\hspace{-0.15cm} \ = \ \hspace{-0.15cm}(0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm}.$$
 
(1\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} ... \hspace{0.05cm})\hspace{-0.15cm} \ = \ \hspace{-0.15cm}(0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm}.$$
  
−
*Da die Faltung eine lineare Operation ist, ergibt sich im Galoisfeld ${\rm GF}(2)$ aus der Summation:
+
*Since the convolution is a linear operation,&nbsp; in the Galois field&nbsp; ${\rm GF}(2)$&nbsp; results from summation:
 
:$$(1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm}) *  
 
:$$(1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm}) *  
 
(1\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})\hspace{0.08cm}=\hspace{0.08cm}(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}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm}.$$
 
(1\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})\hspace{0.08cm}=\hspace{0.08cm}(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}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm}.$$
  
−
*Hätte man die Faltung nicht in ${\rm GF}(2)$, sondern für reelle Zahlen durchgeführt, so hätte man das Ergebnis $\underline{x} = (1, \, 2, \, 2, \, 1, \, 0, \, 0, \, \text{...})$ erhalten.
+
*If the convolution had been performed not in&nbsp; ${\rm GF}(2)$&nbsp; but for real numbers,&nbsp; we would have obtained the result&nbsp; $\underline{x} = (1, \, 2, \, 2, \, 1, \, 0, \, 0, \, \text{...})$.
  
  
  
−
'''(4)'''&nbsp; Die Musterlösung zur Teilaufgabe '''(3)''' lässt bereits vermuten, dass hier der <u>Lösungsvorschlag 1</u> richtig ist.  
+
'''(4)'''&nbsp; The sample solution to the subtask&nbsp; '''(3)'''&nbsp; already suggests that the&nbsp; <u>proposed solution 1</u>&nbsp; is correct here.  
−
*Der Weg über die $D$&ndash;Transformierten bestätigt dieses Ergebnis:
+
*The way over the D&ndash;transforms confirms this result:
 
:$$\underline{u} = (1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm})  \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm}
 
:$$\underline{u} = (1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm})  \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm}
 
{U}(D)= 1+ D + D^2+ D^3 + \text{...}\hspace{0.15cm}.$$
 
{U}(D)= 1+ D + D^2+ D^3 + \text{...}\hspace{0.15cm}.$$
  
−
*Mit der für Berechnungen in ${\rm GF}(2)$ gültigen Gleichung
+
*Using the equation valid for calculations in&nbsp; ${\rm GF}(2)$
 
:$$1 + D + D^2 + D^3  + \hspace{0.05cm}\text{...} \hspace{0.1cm}= \frac{1}{1+D}$$
 
:$$1 + D + D^2 + D^3  + \hspace{0.05cm}\text{...} \hspace{0.1cm}= \frac{1}{1+D}$$
  
−
:erhält man weiter:
+
:one further obtains:
 
:$${X}(D) = U(D) \cdot G(D) = \frac{1}{1+D} \cdot (1+D) = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
:$${X}(D) = U(D) \cdot G(D) = \frac{1}{1+D} \cdot (1+D) = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
\underline{x} = (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})
 
\underline{x} = (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})
Line 160: Line 162:
  
  
−
'''(5)'''&nbsp; Der Weg über die $D$&ndash;Transformierten führt zum <u>Lösungsvorschlag 2</u>.  
+
'''(5)'''&nbsp; The path over the D&ndash;transforms leads to&nbsp; <u>solution 2</u>.  
−
*Für diese alternierende Folge $\underline{u}$, beginnend mit 1, erhält man:
+
*For this alternating sequence&nbsp; $\underline{u}$,&nbsp; starting with&nbsp; $1$,&nbsp; one obtains:
 
:$${X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 \cdot (1+D)  + D^2 \cdot (1+D) + D^4 \cdot (1+D) + \text{...} = 1 + D + D^2 + D^3 + D^4 + D^5 +\hspace{0.05cm} ...  
 
:$${X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 \cdot (1+D)  + D^2 \cdot (1+D) + D^4 \cdot (1+D) + \text{...} = 1 + D + D^2 + D^3 + D^4 + D^5 +\hspace{0.05cm} ...  
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
Line 167: Line 169:
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
−
*Auch bei direkter Anwendung der Faltung wie in Teilaufgabe (2) kann man dieses Ergebnis ablesen.  
+
*This result can also be read by direct application of the convolution as in subtask&nbsp; '''(2)'''.
−
*Mit $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...})$ erhält man dagegen $\underline{x} = (0, \, 1, \, 1, \, 1, \, 1, \, 1, \,\text{...})$.  
+
−
*Diese unterscheidet sich von der "Dauer&ndash;Einsfolge" nur im ersten Bit. Es ist dann $x_1 = 0$ statt $x_1 = 1$.
+
*With&nbsp; $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...})$&nbsp; you get&nbsp; $\underline{x} = (0, \, 1, \, 1, \, 1, \, 1, \, 1, \,\text{...})$.
 +
 +
*This differs from the&nbsp; "sequence of ones"&nbsp; only in the first bit.&nbsp; It is then&nbsp; $x_1 = 0$&nbsp; instead of&nbsp; $x_1 = 1$.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
−
[[Category:Channel Coding: Exercises|^3.2 Polynomische Beschreibung^]]
+
[[Category:Channel Coding: Exercises|^3.2 Polynomial Description^]]

Latest revision as of 18:47, 10 November 2022

Predefined filter structure

In this exercise, we use a simple example to describe

  • the finite  »impulse response«  of a filter:
$$\underline{g} = \left (g_0, g_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, g_l, \hspace{0.05cm}\text{...}\hspace{0.1cm}, g_m \right ) \hspace{0.05cm},\hspace{0.2cm}g_l \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}, $$
  • the  »input sequence«  of the filter:
$$\underline{u} = \left (u_0, u_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, u_i, \hspace{0.05cm}\text{...}\hspace{0.1cm} \right ) \hspace{0.05cm},\hspace{0.2cm}u_i \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}, $$
  • the  »output sequence«  of the filter:
$$\underline{x} = \left (x_0, x_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, x_i, \hspace{0.05cm}\text{...}\hspace{0.1cm} \right ) \hspace{0.05cm},\hspace{0.2cm}x_i \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}. $$

We have adapted the nomenclature for this  $($digital$)$  filter description to the book  "Introduction to Channel Coding".  In other  $\rm LNTww$ books often 

  1.  $\underline{x}$  denotes the filter input, 
  2.  $\underline{y}$  the filter output,  and
  3.  the impulse response is called  $\underline{h}$.


In general,  for the output sequence corresponding to the  $\text{convolution}$ :

$$\underline{x} = \underline{u}* \underline{g} = \left (x_0, x_1, \hspace{0.05cm}\text{...}\hspace{0.1cm}, x_i, \hspace{0.05cm}\text{...}\hspace{0.1cm} \right )\hspace{0.05cm},\hspace{0.1cm} {\rm with} \hspace{0.2cm} x_i = \sum_{l = 0}^{m} g_l \cdot u_{i-l}\hspace{0.05cm}.$$
  • We now represent the time functions   $\underline{g}, \ \underline{u}$   and   $\underline{x}$  by polynomials in a dummy variable  $D$  and call these the  D–transforms:
$$\underline{g} \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm} {G}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \sum_{l = 0}^{m} g_l \cdot D\hspace{0.03cm}^l = g_0 + g_1 \cdot D + g_2 \cdot D^2 + \text{...} + g_m \cdot D\hspace{0.03cm}^m\hspace{0.05cm},$$
$$\underline{u} \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm} {U}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \sum_{i = 0}^{\infty} u_i \cdot D\hspace{0.03cm}^i = u_0 + u_1 \cdot D + u_2 \cdot D^2 + \text{...} \hspace{0.05cm},$$
$$\underline{x} \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm} {X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.03cm}^i = x_0 + x_1 \cdot D + x_2 \cdot D^2 + \text{...} \hspace{0.05cm}.$$
  • Thus the  $($more complicated$)$  convolution becomes a multiplication:
$$\underline{x} = \underline{u}* \underline{g} \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm} {X}(D) = U(D) \cdot G(D) \hspace{0.05cm}.$$
  • Formally,  this relationship can be demonstrated as follows:
$${X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.03cm}^i = \sum_{i = 0}^{\infty} \sum_{l = 0}^{m}\hspace{0.1cm} g_l \cdot u_{i-l} \cdot D\hspace{0.03cm}^{i} = \sum_{l = 0}^{m} \hspace{0.1cm} g_l \cdot \sum_{j = -l}^{\infty} \hspace{0.1cm} u_{j} \cdot D\hspace{0.03cm}^{j+l} = \sum_{l = 0}^{m} \hspace{0.1cm} g_l \cdot D\hspace{0.03cm}^l \hspace{0.1cm} \cdot \hspace{0.1cm} \sum_{j = 0}^{\infty} \hspace{0.1cm} u_{j} \cdot D\hspace{0.03cm}^{j}$$
$$\Rightarrow \hspace{0.3cm}{X}(D) = U(D) \cdot G(D) \hspace{0.05cm}.$$
  • Here it was considered that all   $u_j$   for  $j < 0$  do not exist and can be set to zero.
  • Both procedures for computing the initial sequence  $\underline{x}$  shall be demonstrated for the digital filter outlined above,  viz.
  1.   using the convolution,
  2.   by means of the D–transformation.



Hints:

  • In the solution,  consider the following identity for calculations in  $\rm GF(2)$:
$$1 + D + D^2 + D^3 + \hspace{0.05cm}\text{...}\hspace{0.1cm}= \frac{1}{1+D} \hspace{0.05cm}.$$



Questions

1

What are the present filter coefficients?

$g_0 \ = \ $
$g_1 \ = \ $
$g_2 \ = \ $

2

The sequence  $\underline{u} = (1, \, 0, \, 0, \, 1)$  let be finite.  What is the output sequence?

$\underline{x} = (1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
$\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
$\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
$\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$   ⇒   "sequence of ones".

3

The sequence  $\underline{u} = (1, \, 1, \, 1)$  let be finite.  What is the output sequence?

$\underline{x} = (1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
$\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
$\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
$\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$   ⇒   "sequence of ones".

4

What is the output sequence for  $\underline{u} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm}.)$   ⇒   "sequence of ones"?

$\underline{x} = (1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
$\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.
$\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \,\text{...}\hspace{0.05cm})$.
$\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$   ⇒   "sequence of ones".

5

For which vector  $\underline{u}$  does the sequence  $\underline{x} = (1, \, 1, \, 1, \, 1, \ \text{...}\hspace{0.05cm})$  occur at the output?

$\underline{u} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$   ⇒   "sequence of ones"
$\underline{u} = (1, \, 0, \, 1, \, 0, \, 1, \, 0, \,\text{...}\hspace{0.05cm})$   ⇒   alternating sequence, starting with  "$1$".
$\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$   ⇒   alternating sequence, starting with  "$0$".


Solution

Solution

(1)  The only two filter coefficients different from  $0$  are  $g_0 \ \underline{= 1}$  and  $g_1 \ \underline{= 1}$.

  • From this follows  $g_2 \ \underline{= 0}$  and for the D–transform of the impulse response:
$$\underline{g} = (1\hspace{0.05cm},\hspace{0.05cm} 1) \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm} {G}(D) = 1+ D \hspace{0.05cm}.$$


(2)  The impulse response of the considered filter is  $\underline{g} = (1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$.

  • For the output sequence,  therefore,  we obtain the convolution product
$$\underline{x} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \underline{u}* \underline{g} = (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}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} ...\hspace{0.05cm}) * (1\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} ... \hspace{0.05cm}) =(1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} ...\hspace{0.05cm}) \hspace{0.05cm}.$$
  • The same result is obtained using the D–transforms  $U(D) = 1 + D^3$  and  $G(D) = 1 + D$:
$${X}(D) = U(D) \cdot G(D) = ( 1+D^3) \cdot (1+D) = 1 +D + D^3 +D^4 \hspace{0.05cm}.$$
  • The inverse transformation leads again to the result  $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$   ⇒   Proposed solution 3.


(3)  Here we immediately use the path over the D–transforms:

$${X}(D) = ( 1+D+D^2) \cdot (1+D) = 1 +D + D +D^2 +D^2 +D^3 = 1+ D^3\hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x} = (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}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm}.$$
  • The result corresponds to the  proposed solution 2.  The following calculation is to illustrate the path in the time domain:
$$(1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm}) * (1\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})\hspace{-0.15cm} \ = \ \hspace{-0.15cm}(1\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},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\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},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.05cm}) * (1\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})\hspace{-0.15cm} \ = \ \hspace{-0.15cm}(0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm},$$
$$(0\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},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} \text{...}\hspace{0.05cm}) * (1\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} ... \hspace{0.05cm})\hspace{-0.15cm} \ = \ \hspace{-0.15cm}(0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm}.$$
  • Since the convolution is a linear operation,  in the Galois field  ${\rm GF}(2)$  results from summation:
$$(1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm}) * (1\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})\hspace{0.08cm}=\hspace{0.08cm}(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}\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0,\hspace{0.05cm} \text{...}\hspace{0.05cm}) \hspace{0.05cm}.$$
  • If the convolution had been performed not in  ${\rm GF}(2)$  but for real numbers,  we would have obtained the result  $\underline{x} = (1, \, 2, \, 2, \, 1, \, 0, \, 0, \, \text{...})$.


(4)  The sample solution to the subtask  (3)  already suggests that the  proposed solution 1  is correct here.

  • The way over the D–transforms confirms this result:
$$\underline{u} = (1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm}) \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm} {U}(D)= 1+ D + D^2+ D^3 + \text{...}\hspace{0.15cm}.$$
  • Using the equation valid for calculations in  ${\rm GF}(2)$
$$1 + D + D^2 + D^3 + \hspace{0.05cm}\text{...} \hspace{0.1cm}= \frac{1}{1+D}$$
one further obtains:
$${X}(D) = U(D) \cdot G(D) = \frac{1}{1+D} \cdot (1+D) = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x} = (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}) \hspace{0.05cm}.$$


(5)  The path over the D–transforms leads to  solution 2.

  • For this alternating sequence  $\underline{u}$,  starting with  $1$,  one obtains:
$${X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 \cdot (1+D) + D^2 \cdot (1+D) + D^4 \cdot (1+D) + \text{...} = 1 + D + D^2 + D^3 + D^4 + D^5 +\hspace{0.05cm} ... \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x} = (1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} \text{...} \hspace{0.05cm}) \hspace{0.05cm}.$$
  • This result can also be read by direct application of the convolution as in subtask  (2).
  • With  $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...})$  you get  $\underline{x} = (0, \, 1, \, 1, \, 1, \, 1, \, 1, \,\text{...})$.
  • This differs from the  "sequence of ones"  only in the first bit.  It is then  $x_1 = 0$  instead of  $x_1 = 1$.

Retrieved from "http://en.lntwww.de/index.php?title=Aufgaben:Exercise_3.3Z:_Convolution_and_D-Transformation&oldid=49991"
  • Powered by MediaWiki