Exercise 3.3Z: Convolution and D-Transformation

Vorgegebene Filter

In dieser Aufgabe beschreiben wir an einem einfachen Beispiel

die endliche Impulsantwort 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 Eingangssequenz 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 Ausgangssequenz 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 „Einführung in die Kanalcodierung” 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 Faltung (englisch: Convolution):

$$\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–Variablen $D$ und nennen diese die $D$–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$–Transformation,

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

Hinweis:

Die Aufgabe bezieht sich auf den Lehrstoff von 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}.$$

Fragebogen

Musterlösung

Solution

(1) (2) (3) (4) (5)

	$\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, \, ...)$ ⇒ „Dauer–Einsfolge”.

	$\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, \, ...)$ ⇒ „Dauer–Einsfolge”.

	$\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, \, ...)$ ⇒ „Dauer–Einsfolge”.

	$\underline{u} = (1, \, 1, \, 1, \, 1, \, ...)$ ⇒ „Dauer–Einsfolge”
	$\underline{u} = (1, \, 0, \, 1, \, 0, \, 1, \, 0, \, ...)$ ⇒ alternierende Folge, beginnend mit $1$.
	$\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, ...)$ ⇒ alternierende Folge, beginnend mit $0$.