View source for Aufgaben:Exercise 3.3Z: Convolution and D-Transformation

{{quiz-Header|Buchseite=Kanalcodierung/Algebraische und polynomische Beschreibung}}

[[File:P_ID2628__KC_Z_3_3.png|right|frame|Vorgegebene Filter]]

In dieser Aufgabe beschreiben wir an einem einfachen Beispiel
* die endliche <span style="color: rgb(204, 0, 0);"><b>Impulsantwort</b></span> eines Filters:
:$$\underline{g} = \left (g_0, g_1, \hspace{0.05cm}...\hspace{0.1cm}, g_l, \hspace{0.05cm}...\hspace{0.1cm}, g_m \right )
\hspace{0.05cm},\hspace{0.2cm}g_l \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}, $$
* die <span style="color: rgb(204, 0, 0);"><b>Eingangssequenz</b></span> des Filters:
:$$\underline{u} = \left (u_0, u_1, \hspace{0.05cm}...\hspace{0.1cm}, u_i, \hspace{0.05cm}...\hspace{0.1cm} \right )
\hspace{0.05cm},\hspace{0.2cm}u_i \in {\rm GF(2) } = \{ 0, 1 \}\hspace{0.05cm}, $$
* die <span style="color: rgb(204, 0, 0);"><b>Ausgangssequenz</b></span> des Filters:
:$$\underline{x} = \left (x_0, x_1, \hspace{0.05cm}...\hspace{0.1cm}, x_i, \hspace{0.05cm}...\hspace{0.1cm} \right )
\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 &bdquo;Einführung in die Kanalcodierung&rdquo; angepasst. In anderen Büchern bezeichnet oft $\underline{x}$ den Filtereingang, $\underline{y}$ den Filterausgang, und die Impulsantwort wird $h$ genannt.

Allgemein gilt für die Ausgangssequenz entsprechend der [[Signaldarstellung/Faltungssatz_und_Faltungsoperation#Faltung_im_Zeitbereich| Faltung]] (englisch: <i>Convolution</i>):
:$$\underline{x} = \underline{u}* \underline{g} = \left (x_0, x_1, \hspace{0.05cm}...\hspace{0.1cm}, x_i, \hspace{0.05cm}...\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 $\underline{g}, \ \underline{u}$ und $\underline{x}$ durch Polynome in einer Dummy&ndash;Variablen $D$ und nennen diese die $D$&ndash;Transformierten:
:$$\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 + ... + 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 + ... \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 + ... \hspace{0.05cm}.$$

Damit wird aus der (komplizierteren) Faltung eine Multiplikation:
:$$\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}.$$

Formal lässt sich dieser Zusammenhang wie folgt nachweisen:
:$${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} = $$
:$$ \ = \ \hspace{-0.15cm}  \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}\hspace{0.3cm}\Rightarrow \hspace{0.3cm}{X}(D) = U(D) \cdot G(D)
 \hspace{0.05cm}.$$

Hierbei wurde berücksichtigt, dass alle $u_j$ für $j < 0$ nicht existieren und zu $0$ gesetzt werden können.

Beide Vorgehensweisen zur Berechnung der Ausgangssequenz $\underline{x}$, nämlich
* über die Faltung
* mit Hilfe der $D$&ndash;Transformation,


sollen für das oben skizzierte Digitale Filter demonstriert werden.

''Hinweis:''
* Die Aufgabe bezieht sich auf den Lehrstoff von [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#GF.282.29.E2.80.93Beschreibungsformen_eines_Digitalen_Filters| Seite 4]] des Kapitels Algebraische und polynomische Beschreibung.
* Berücksichtigen Sie bei der Lösung die folgende Identität für Berechnungen in GF(2):
:$$1 + D + D^2 + D^3  + \hspace{0.05cm}... \hspace{0.1cm}= \frac{1}{1+D} \hspace{0.05cm}.$$
* Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.



===Fragebogen===
<quiz display=simple>
{Wie lauten die vorliegenden Filterkoeffizienten?
|type="{}"}
$g_0 \ = \ ${ 1 3% }
$g_1 \ = \ ${ 1 3% }
$g_2 \ = \ ${ 0 3% }

{Die Sequenz $\underline{u} = (1, \, 0, \, 0, \, 1)$ sei endlich. Wie lautet die Ausgangssequenz?
|type="[]"}
- $\underline{x} = (1, \, 0, \, 0, \, ...)$.
- $\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, ...)$.
+ $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, ...)$.
- $\underline{x} = (1, \, 1, \, 1, \, 1, \, ...)$ &nbsp;&#8658;&nbsp; &bdquo;Dauer&ndash;Einsfolge&rdquo;.

{Die Sequenz $\underline{u} = (1, \, 1, \, 1)$ sei endlich. Wie lautet die Ausgangssequenz?
|type="[]"}
- $\underline{x} = (1, \, 0, \, 0, \, ...)$.
+ $\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, ...)$.
- $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, ...)$.
- $\underline{x} = (1, \, 1, \, 1, \, 1, \, ...)$ &nbsp;&#8658;&nbsp; &bdquo;Dauer&ndash;Einsfolge&rdquo;.

{Wie lautet die Ausgangssequenz für $\underline{u} = (1, \, 1, \, 1, \, 1, \, ...)$ &nbsp;&#8658;&nbsp; &bdquo;Dauer&ndash;Einsfolge&rdquo;?
|type="[]"}
+ $\underline{x} = (1, \, 0, \, 0, \, ...)$.
- $\underline{x} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, ...)$.
- $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, ...)$.
- $\underline{x} = (1, \, 1, \, 1, \, 1, \, ...)$ &nbsp;&#8658;&nbsp; &bdquo;Dauer&ndash;Einsfolge&rdquo;.

{Für welchen Vektor $\underline{u}$ tritt am Ausgang die Folge $\underline{x} = (1, \, 1, \, 1, \, 1, \ ...)$ auf?
|type="[]"}
- $\underline{u} = (1, \, 1, \, 1, \, 1, \, ...)$ &nbsp;&#8658;&nbsp; &bdquo;Dauer&ndash;Einsfolge&rdquo;
+ $\underline{u} = (1, \, 0, \, 1, \, 0, \, 1, \, 0, \, ...)$ &nbsp;&#8658;&nbsp; alternierende Folge, beginnend mit $1$.
- $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, ...)$ &nbsp;&#8658;&nbsp; alternierende Folge, beginnend mit $0$.
</quiz>

===Musterlösung===
{{ML-Kopf}}
'''(1)'''&nbsp; Die beiden einzigen von $0$ verschiedenen Filterkoeffizienten sind $g_0 \ \underline{= 1}$ und $g_1 \ \underline{= 1}$. Daraus folgt für die $D$&ndash;Transformierte der Impulsantwort:
:$$\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)'''&nbsp; Die Impulsantwort des betrachteten Filters ist $\underline{g} = (1, \, 1, \, 0, \, 0, \, ...)$. Für die Ausgangssequenz erhält man deshalb das Faltungsprodukt
:$$\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}) =$$
:$$\ = \ \hspace{-0.15cm} (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}.$$

Zum gleichen Ergebnis kommt man über die $D$&ndash;Transformierten $U(D) = 1 + D^3$ und $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}.$$

Die Rücktransformation führt wieder zum Ergebnis $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, ...)$ &nbsp;&#8658;&nbsp; <u>Lösungsvorschlag 3</u>.


'''(3)'''&nbsp; Hier verwenden wir sofort den Weg über die $D$&ndash;Transformierten:
:$${X}(D) =  ( 1+D+D^2) \cdot (1+D) = 1 +D + D +D^2 +D^2 +D^3 = 1+ D^3$$
:$$\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} ...\hspace{0.05cm}) 
 \hspace{0.05cm}.$$

Das Ergebnis entspricht dem <u>Lösungsvorschlag 2</u>. Die folgende Berechnung soll den Weg im Zeitbereich veranschaulichen:
:$$(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} ...\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}(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} ...\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} ... \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} ...\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} ...\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} ...\hspace{0.05cm}) \hspace{0.05cm}.$$

Da die Faltung eine lineare Operation ist, ergibt sich im Galoisfeld ${\rm GF}(2)$ aus der 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} ...\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.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} ...\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, \, ...)$ erhalten.


'''(4)'''&nbsp; Die Musterlösung zur Teilaufgabe (3) lässt bereits vermuten, dass hier der <u>Lösungsvorschlag 1</u> richtig ist. Der Weg über die $D$&ndash;Transformierten bestätigt dieses Ergebnis:
:$$\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} ... \hspace{0.05cm})  \hspace{0.25cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.25cm}
{U}(D)= 1+ D + D^2+ D^3 + ... \hspace{0.15cm}.$$

Mit der für Berechnungen in ${\rm GF}(2)$ gültigen Gleichung
:$$1 + D + D^2 + D^3  + \hspace{0.05cm}... \hspace{0.1cm}= \frac{1}{1+D}$$

erhält man weiter:
:$${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} ... \hspace{0.05cm})
\hspace{0.05cm}.$$


'''(5)'''&nbsp; Der Weg über die $D$&ndash;Transformierten führt zum <u>Lösungsvorschlag 2</u>. Für diese alternierende Folge $\underline{u}$, beginnend mit 1, erhält man:
:$${X}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 \cdot (1+D)  + D^2 \cdot (1+D) + D^4 \cdot (1+D) + ... =$$
$$\ = \ \hspace{-0.15cm} 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} ... \hspace{0.05cm})
\hspace{0.05cm}.$$

Auch bei direkter Anwendung der Faltung wie in Teilaufgabe (2) kann man dieses Ergebnis ablesen. Mit $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, ...)$ erhält man dagegen $\underline{x} = (0, \, 1, \, 1, \, 1, \, 1, \, 1, \, ...)$. Diese unterscheidet sich von der &bdquo;Dauer&ndash;Einsfolge&rdquo; nur im ersten Bit. Es ist dann $x_1 = 0$ statt $x_1 = 1$.
{{ML-Fuß}}


[[Category:Aufgaben zu  Kanalcodierung|^3.2 Algebraische und polynomische Beschreibung^]]