Difference between revisions of "Aufgaben:Exercise 3.3Z: Convolution and D-Transformation"
From LNTwww
| Line 1: | Line 1: | ||
| − | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Channel_Coding/Algebraic_and_Polynomial_Description}} |
| − | [[File:P_ID2628__KC_Z_3_3.png|right|frame| | + | [[File:P_ID2628__KC_Z_3_3.png|right|frame|Predefined filter structure]] |
| − | In | + | In this exercise, we use a simple example to describe |
| − | * | + | * the finite <b>impulse response</b> 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}, $$ | ||
| − | * | + | * the <b>input sequence</b> 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}, $$ | ||
| − | * | + | * the <b>output sequence</b> 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}. $$ | ||
| − | + | 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 [[Signal_Representation/The_Convolution_Theorem_and_Operation#Convolution_in_the_time_domain| "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}.$$ | :$$\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} | :$$\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 27: | ||
{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}.$$ | ||
| − | + | 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} | :$$\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}.$$ | ||
| − | + | 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} | :$${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 39: | ||
\hspace{0.05cm}.$$ | \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. | |
| Line 54: | Line 54: | ||
| − | + | Hints: | |
| − | * | + | * The exercise belongs to the chapter [[Channel_Coding/Algebraic_and_Polynomial_Description| "Algebraic and Polynomial Description"]]. |
| − | * | + | * Refer in particular to the [[Channel_Coding/Algebraic_and_Polynomial_Description#GF.282.29_description_forms_of_a_digital_filter|"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}.$$ | :$$1 + D + D^2 + D^3 + \hspace{0.05cm}\text{...}\hspace{0.1cm}= \frac{1}{1+D} \hspace{0.05cm}.$$ | ||
| Line 63: | Line 63: | ||
| − | === | + | ===Questions=== |
<quiz display=simple> | <quiz display=simple> | ||
| − | { | + | {What are the present filter coefficients? |
|type="{}"} | |type="{}"} | ||
$g_0 \ = \ ${ 1 } | $g_0 \ = \ ${ 1 } | ||
| Line 71: | Line 71: | ||
$g_2 \ = \ ${ 0. } | $g_2 \ = \ ${ 0. } | ||
| − | { | + | {The sequence $\underline{u} = (1, \, 0, \, 0, \, 1)$ let be finite. What is the initial 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})$ ⇒ " | + | - $\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ ⇒ "sequence of ones". |
| − | { | + | {The sequence $\underline{u} = (1, \, 1, \, 1)$ let be finite. What is the initial 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})$ ⇒ " | + | - $\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ ⇒ "sequence of ones". |
| − | { | + | {What is the output sequence for $\underline{u} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm}.)$ ⇒ "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})$ ⇒ " | + | - $\underline{x} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ ⇒ "sequence of ones". |
| − | { | + | {For which vector $\underline{u}$ does the sequence $\underline{x} = (1, \, 1, \, 1, \, 1, \ \text{...}\hspace{0.05cm})$ occur at the output? |
|type="()"} | |type="()"} | ||
| − | - $\underline{u} = (1, \, 1, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$ ⇒ " | + | - $\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})$ ⇒ | + | + $\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})$ ⇒ | + | - $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$ ⇒ alternating sequence, starting with $0$. |
</quiz> | </quiz> | ||
| − | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' | + | '''(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} | :$$\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 108: | ||
| − | '''(2)''' | + | '''(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} = | :$$\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 115: | ||
\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 | :$${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}.$$ | ||
| − | * | + | *The back transformation leads again to the result $\underline{x} = (1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$ ⇒ <u>Proposed solution 3</u>. |
| − | '''(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} | :$${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 129: | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | * | + | *The result corresponds to the <u>proposed solution 2</u>. 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 137: | ||
(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}.$$ | ||
| − | * | + | *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} 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}.$$ | ||
| − | * | + | *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)''' | + | '''(4)''' The sample solution to the subtask '''(3)''' already suggests that the <u>proposed solution 1</u> 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} | :$$\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}.$$ | ||
| − | * | + | *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}$$ | :$$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} | :$${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 160: | ||
| − | '''(5)''' | + | '''(5)''' The path over the $D$ transforms leads to <u>solution 2</u>. |
| − | * | + | *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} ... | :$${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 167: | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | * | + | *This result can also be read by direct application of the convolution as in subtask (2). |
*Mit $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...})$ erhält man dagegen $\underline{x} = (0, \, 1, \, 1, \, 1, \, 1, \, 1, \,\text{...})$. | *Mit $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...})$ erhält man dagegen $\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$. |
{{ML-Fuß}} | {{ML-Fuß}} | ||
[[Category:Channel Coding: Exercises|^3.2 Polynomial Description^]] | [[Category:Channel Coding: Exercises|^3.2 Polynomial Description^]] | ||
Revision as of 22:03, 23 September 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 $\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
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).
- Mit $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 1, \, \text{...})$ erhält man dagegen $\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$.
