Aufgaben:Exercise 3.3Z: Convolution and D-Transformation

• Return to book

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  $\underline{x}$  denotes the filter input,  $\underline{y}$  the filter output, and the impulse response is called  $h$ .

In general, for the output sequence corresponding to the  "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 mit} \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}$, viz.

• using the convolution
• by means of the $D$ transformation,

shall be demonstrated for the digital filter outlined above.

Hints:

• The exercise belongs to the chapter  "Algebraic and Polynomial Description".
• Refer in particular to the  "GF(2) Description Forms of a Digital Filter" page.
• 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 initial 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 initial 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 initial 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 back 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 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$.