Difference between revisions of "Aufgaben:Exercise 3.5: Recursive Filters for GF(2)"
From LNTwww
(24 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Channel_Coding/Algebraic_and_Polynomial_Description}} |
− | [[File:P_ID2647__KC_A_3_5.png|right|frame| | + | [[File:P_ID2647__KC_A_3_5.png|right|frame|General recursive filter (above) <br>and considered realization (below)]] |
− | + | The upper of the two circuits on the right shows a second order recursive filter in general form. With | |
:$$A(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} a_0 + a_1 \cdot D + a_2 \cdot D^2 \hspace{0.05cm},$$ | :$$A(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} a_0 + a_1 \cdot D + a_2 \cdot D^2 \hspace{0.05cm},$$ | ||
:$$B(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 + b_1 \cdot D + b_2 \cdot D^2 $$ | :$$B(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 + b_1 \cdot D + b_2 \cdot D^2 $$ | ||
− | + | one obtains for the transfer function | |
:$$G(D) = \frac{A(D)}{B(D)} = \frac{a_0 + a_1 \cdot D + a_2 \cdot D^2}{1 + b_1 \cdot D + b_2 \cdot D^2} \hspace{0.05cm}.$$ | :$$G(D) = \frac{A(D)}{B(D)} = \frac{a_0 + a_1 \cdot D + a_2 \cdot D^2}{1 + b_1 \cdot D + b_2 \cdot D^2} \hspace{0.05cm}.$$ | ||
− | + | * It should be noted that all arithmetic operations refer to ${\rm GF(2)}$. | |
+ | |||
+ | * Thus, the filter coefficients $a_0, \ a_1, \ a_2, \ b_1, \ b_2$ are also binary $(0$ or $1)$. | ||
− | |||
− | + | The bottom graph shows the filter specific to the exercise at hand: | |
− | + | # A filter coefficient results in $a_i = 1$ if the connection is through $(0 ≤ i ≤ 2)$. | |
− | + | # Otherwise, $a_i = 0$. The same system applies to the coefficients $b_1$ and $b_2$. | |
− | |||
− | + | In the subtasks '''(1)''', ... , '''(3)''' you are to determine the respective output sequence $\underline{x}$ for different input sequences | |
− | * | + | * $\underline{u} = (1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$, |
+ | |||
+ | * $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$, | ||
+ | |||
+ | * $\underline{u} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$ | ||
+ | |||
+ | |||
+ | using the given circuit. It should be taken into account: | ||
+ | * If the input sequence $\underline{u}$ consists of a "$1$" followed by all zeros, this specific output sequence $\underline{x}$ is the [[Linear_and_Time_Invariant_Systems/System_Description_in_Time_Domain#Impulse_response|"impulse response"]] $\underline{g}$, and it holds: | ||
:$$\underline{g} \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.15cm}{G}(D)\hspace{0.05cm}. $$ | :$$\underline{g} \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.15cm}{G}(D)\hspace{0.05cm}. $$ | ||
− | * | + | * Otherwise, the output sequence results as the [[Signal_Representation/The_Convolution_Theorem_and_Operation|"convolution product"]] between the input sequence and the impulse response: |
:$$\underline{x} = \underline{u} * \underline{g} \hspace{0.05cm}.$$ | :$$\underline{x} = \underline{u} * \underline{g} \hspace{0.05cm}.$$ | ||
− | * | + | * The convolution operation can be bypassed with the [[Channel_Coding/Algebraic_and_Polynomial_Description#GF.282.29_description_forms_of_a_digital_filter|"D-transform"]] . |
+ | |||
+ | |||
+ | |||
− | |||
− | |||
+ | Hints: | ||
+ | * This exercise belongs to the chapter [[Channel_Coding/Algebraic_and_Polynomial_Description| "Algebraic and Polynomial Description"]]. | ||
− | === | + | * Reference is made in particular to the section [[Channel_Coding/Algebraic_and_Polynomial_Description#Filter_structure_with_fractional.E2.80.93rational_transfer_function| "Filter structure with fractional–rational transfer function"]] |
+ | |||
+ | |||
+ | |||
+ | ===Questions=== | ||
<quiz display=simple> | <quiz display=simple> | ||
− | { | + | {What statements hold for the impulse response $\underline{g}$ of the recursive filter? |
|type="[]"} | |type="[]"} | ||
− | - | + | - It holds $\underline{g} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$. |
− | + | + | + It holds $\underline{g} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$. |
− | + | + | + The impulse response $\underline{g}$ is infinitely extended. |
− | { | + | {Let now $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, 1)$. Which statements are true? |
|type="[]"} | |type="[]"} | ||
− | + | + | + The output sequence is: $\underline{x} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$. |
− | - | + | - The output sequence is: $\underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$. |
− | + | + | + The output sequence $\underline{x}$ extends to infinity. |
− | { | + | {Now apply $\underline{u} = (1, \, 1, \, 1)$. Which statements are true? |
|type="[]"} | |type="[]"} | ||
− | + | + | + The output sequence $\underline{x}$ starts with $(1, \, 0, \, 1)$. |
− | - | + | - The output sequence $\underline{x}$ begins with $(1, \, 1, \, 1)$. |
− | - | + | - The output sequence $\underline{x}$ extends to infinity. |
− | { | + | {What statements are valid for the transfer function $G(D)$? |
|type="[]"} | |type="[]"} | ||
− | + | + | + It holds $G(D) = (1 + D^2)/(1 + D + D^2)$. |
− | - | + | - It holds $G(D) = (1 + D + D^2)/(1 + D^2)$. |
− | + | + | + It holds $G(D) = 1 + D + D^2 + D^4 + D^5 + D^7 + D^8 + \hspace{0.05cm} \text{...}\hspace{0.05cm} $ . |
</quiz> | </quiz> | ||
− | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' | + | '''(1)''' Correct are the <u>proposed solutions 2 and 3</u>: |
+ | [[File:P_ID2643__KC_A_3_5a.png|right|frame|For calculation of the impulse response $\underline{g}$]] | ||
+ | [[File:P_ID2644__KC_A_3_5b.png|right|frame|For calculation of the output sequence $\underline{x}$]] | ||
− | + | *The impulse response $\underline{g}$ is equal to the sequence $\underline{x}$ for the input sequence $\underline{u} = (1, \, 0, \, 0, \, \text{...})$. | |
+ | *Based on the filter structure, $w_0 = w_{-1} = 0$ and the equations | ||
:$$w_i \hspace{-0.2cm} \ = \ \hspace{-0.2cm} u_i + w_{i-1} + w_{i-2} \hspace{0.05cm},$$ | :$$w_i \hspace{-0.2cm} \ = \ \hspace{-0.2cm} u_i + w_{i-1} + w_{i-2} \hspace{0.05cm},$$ | ||
:$$x_i \hspace{-0.2cm} \ = \ \hspace{-0.2cm} w_i + w_{i-2} $$ | :$$x_i \hspace{-0.2cm} \ = \ \hspace{-0.2cm} w_i + w_{i-2} $$ | ||
− | + | :the result is $\underline{g} = \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...})$ corresponding to <u>proposed solution 2</u>, as shown in the adjacent calculation. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | *But additionally the <u>proposed solution 3</u> is correct, because one recognizes from this calculation scheme further following periodicities of the impulse response $\underline{g}$ $($up to infinity$)$ because of in each case same register assignment: | ||
+ | |||
+ | :$$g_3 \hspace{-0.2cm} \ = \ \hspace{-0.2cm} g_6 = g_9 = \hspace{0.05cm}\text{...} \hspace{0.05cm}= 1 \hspace{0.05cm},$$ | ||
+ | :$$g_4 \hspace{-0.2cm} \ = \ \hspace{-0.2cm} g_7 = g_{10} =\hspace{0.05cm} \text{...} \hspace{0.05cm}= 0 \hspace{0.05cm},$$ | ||
+ | :$$g_5 \hspace{-0.2cm} \ = \ \hspace{-0.2cm} g_8 = g_{11} =\hspace{0.05cm} \text{...} \hspace{0.05cm}= 1 \hspace{0.05cm}.$$ | ||
− | '''(2)''' | + | <br><br><br><br> |
+ | '''(2)''' After similar calculations as in subtask '''(1)''' one recognizes the correctness of <u>solutions 1 and 3</u>: | ||
+ | *The initial sequence $\underline{x}$ also extends to infinity. Periodicities show up again. | ||
− | + | *The same result is obtained by adding the impulse responses $\underline{g} = (1, \, 0, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...} \hspace{0.05cm})$ in the Galois field ${\rm GF(2)}$ shifted by one, three, six, and seven positions $($to the right, respectively$)$: | |
− | :$$\underline{x} | + | :$$\underline{x} = (0\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} 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} \text{...}\hspace{0.05cm}) \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} 1\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}1\hspace{0.05cm},\hspace{0.05cm} \text{...}\hspace{0.05cm}) \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} 0\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} \text{...}\hspace{0.05cm}) \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} 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}1\hspace{0.05cm},\hspace{0.05cm} \text{...}\hspace{0.05cm}) $$ |
− | + | :$$\Rightarrow \hspace{0.3cm}\underline{x} = (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} 1\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} \text{...}\hspace{0.05cm}) \hspace{0.05cm}. $$ | |
− | |||
− | |||
− | :$$\ | ||
− | + | *Due to the linearity of the system under consideration, this is allowed. | |
− | '''(3)''' | + | '''(3)''' Here we choose the way over the D–transforms: |
:$$\underline{u}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad | :$$\underline{u}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad | ||
U(D) = 1+ D + D^2 \hspace{0.05cm}.$$ | U(D) = 1+ D + D^2 \hspace{0.05cm}.$$ | ||
− | + | *With the transfer function $G(D) = (1 + D^2)/(1 + D + D^2)$ one thus obtains for the D–transform of the output sequence: | |
− | :$$X(D) = {U(D)} \cdot G(D) = {1+D+D^2} \cdot \frac{1+D^2}{1+D+D^2} = 1+D^2 \hspace{0.05cm} | + | :$$X(D) = {U(D)} \cdot G(D) = {1+D+D^2} \cdot \frac{1+D^2}{1+D+D^2} = 1+D^2 \hspace{0.05cm}\hspace{0.3cm} |
− | \Rightarrow \hspace{0.3cm}\underline{x} = (1\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} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0. | + | \Rightarrow \hspace{0.3cm}\underline{x} = (1\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} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.01cm} \text{...}\hspace{0.05cm} \hspace{0.05cm} ) \hspace{0.05cm}.$$ |
− | + | *Only the <u>proposed solution 1</u> is correct here: Despite infinitely long impulse response $\underline{g}$, for this input sequence $\underline{u}$ the output sequence $\underline{x}$ is limited to three bits. | |
− | |||
− | |||
− | |||
− | |||
+ | *The same result is again obtained by adding shifted impulse responses: | ||
+ | :$$\underline{x} = (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} 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} \text{...}\hspace{0.05cm}) + (0\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} 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} \text{...}\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} 1\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} \text{...}\hspace{0.05cm}) = (1\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} 0 \hspace{0.05cm}\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}. $$ | ||
− | '''(4)''' | + | |
+ | '''(4)''' Correct are the <u>proposed solutions 1 and 3</u>: | ||
+ | *On the data sheet, the general transfer function of a second–order recursive filter is given as follows. | ||
+ | [[File:P_ID2645__KC_A_3_5e.png|right|frame|$\rm GF(2)$ polynomial division $(1 + D^2)/(1 + D + D^2)$]] | ||
:$$G(D) = \frac{a_0 + a_1 \cdot D + a_2 \cdot D^2}{1 + b_1 \cdot D + b_2 \cdot D^2} \hspace{0.05cm}.$$ | :$$G(D) = \frac{a_0 + a_1 \cdot D + a_2 \cdot D^2}{1 + b_1 \cdot D + b_2 \cdot D^2} \hspace{0.05cm}.$$ | ||
− | + | *The filter considered here is determined by the coefficients $a_0 = a_2 = b_1 = b_2 = 1$ and $a_1 = 0$. Thus one obtains the result according to the <u>solution suggestion 1</u>: | |
:$$G(D) = \frac{1 + D^2}{1 + D + D^2} \hspace{0.05cm}. $$ | :$$G(D) = \frac{1 + D^2}{1 + D + D^2} \hspace{0.05cm}. $$ | ||
− | + | *At the same time, $G(D)$ is also the D–transformed of the impulse response: | |
− | + | :$$\underline{g}= (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} 1\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}0 ,\hspace{0.05cm} \text{ ...}\hspace{0.05cm}) \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.15cm} | |
− | :$$\underline{g}= (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} 1\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}0 ,\hspace{0.05cm} | + | {G}(D)$$ |
− | {G}(D)= 1 + D + D^2 + D^4+ D^5 +... | + | :$$\Rightarrow\hspace{0.3cm} |
+ | {G}(D)= 1 + D + D^2 + D^4+ D^5 +\text{...} | ||
\hspace{0.1cm}. $$ | \hspace{0.1cm}. $$ | ||
− | + | *This means: The <u>proposed solution 3</u> is also correct. | |
− | + | ||
− | + | *The same result would have been obtained by dividing the two polynomials $1 + D^2$ and $1 + D + D^2$, as the calculation opposite shows. | |
− | |||
{{ML-Fuß}} | {{ML-Fuß}} | ||
− | [[Category: | + | [[Category:Channel Coding: Exercises|^3.2 Polynomial Description^]] |
Latest revision as of 14:04, 11 November 2022
The upper of the two circuits on the right shows a second order recursive filter in general form. With
- $$A(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} a_0 + a_1 \cdot D + a_2 \cdot D^2 \hspace{0.05cm},$$
- $$B(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 + b_1 \cdot D + b_2 \cdot D^2 $$
one obtains for the transfer function
- $$G(D) = \frac{A(D)}{B(D)} = \frac{a_0 + a_1 \cdot D + a_2 \cdot D^2}{1 + b_1 \cdot D + b_2 \cdot D^2} \hspace{0.05cm}.$$
- It should be noted that all arithmetic operations refer to ${\rm GF(2)}$.
- Thus, the filter coefficients $a_0, \ a_1, \ a_2, \ b_1, \ b_2$ are also binary $(0$ or $1)$.
The bottom graph shows the filter specific to the exercise at hand:
- A filter coefficient results in $a_i = 1$ if the connection is through $(0 ≤ i ≤ 2)$.
- Otherwise, $a_i = 0$. The same system applies to the coefficients $b_1$ and $b_2$.
In the subtasks (1), ... , (3) you are to determine the respective output sequence $\underline{x}$ for different input sequences
- $\underline{u} = (1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$,
- $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$,
- $\underline{u} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$
using the given circuit. It should be taken into account:
- If the input sequence $\underline{u}$ consists of a "$1$" followed by all zeros, this specific output sequence $\underline{x}$ is the "impulse response" $\underline{g}$, and it holds:
- $$\underline{g} \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.15cm}{G}(D)\hspace{0.05cm}. $$
- Otherwise, the output sequence results as the "convolution product" between the input sequence and the impulse response:
- $$\underline{x} = \underline{u} * \underline{g} \hspace{0.05cm}.$$
- The convolution operation can be bypassed with the "D-transform" .
Hints:
- This exercise belongs to the chapter "Algebraic and Polynomial Description".
- Reference is made in particular to the section "Filter structure with fractional–rational transfer function"
Questions
Solution
(1) Correct are the proposed solutions 2 and 3:
- The impulse response $\underline{g}$ is equal to the sequence $\underline{x}$ for the input sequence $\underline{u} = (1, \, 0, \, 0, \, \text{...})$.
- Based on the filter structure, $w_0 = w_{-1} = 0$ and the equations
- $$w_i \hspace{-0.2cm} \ = \ \hspace{-0.2cm} u_i + w_{i-1} + w_{i-2} \hspace{0.05cm},$$
- $$x_i \hspace{-0.2cm} \ = \ \hspace{-0.2cm} w_i + w_{i-2} $$
- the result is $\underline{g} = \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...})$ corresponding to proposed solution 2, as shown in the adjacent calculation.
- But additionally the proposed solution 3 is correct, because one recognizes from this calculation scheme further following periodicities of the impulse response $\underline{g}$ $($up to infinity$)$ because of in each case same register assignment:
- $$g_3 \hspace{-0.2cm} \ = \ \hspace{-0.2cm} g_6 = g_9 = \hspace{0.05cm}\text{...} \hspace{0.05cm}= 1 \hspace{0.05cm},$$
- $$g_4 \hspace{-0.2cm} \ = \ \hspace{-0.2cm} g_7 = g_{10} =\hspace{0.05cm} \text{...} \hspace{0.05cm}= 0 \hspace{0.05cm},$$
- $$g_5 \hspace{-0.2cm} \ = \ \hspace{-0.2cm} g_8 = g_{11} =\hspace{0.05cm} \text{...} \hspace{0.05cm}= 1 \hspace{0.05cm}.$$
(2) After similar calculations as in subtask (1) one recognizes the correctness of solutions 1 and 3:
- The initial sequence $\underline{x}$ also extends to infinity. Periodicities show up again.
- The same result is obtained by adding the impulse responses $\underline{g} = (1, \, 0, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...} \hspace{0.05cm})$ in the Galois field ${\rm GF(2)}$ shifted by one, three, six, and seven positions $($to the right, respectively$)$:
- $$\underline{x} = (0\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} 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} \text{...}\hspace{0.05cm}) \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} 1\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}1\hspace{0.05cm},\hspace{0.05cm} \text{...}\hspace{0.05cm}) \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} 0\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} \text{...}\hspace{0.05cm}) \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} 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}1\hspace{0.05cm},\hspace{0.05cm} \text{...}\hspace{0.05cm}) $$
- $$\Rightarrow \hspace{0.3cm}\underline{x} = (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} 1\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} \text{...}\hspace{0.05cm}) \hspace{0.05cm}. $$
- Due to the linearity of the system under consideration, this is allowed.
(3) Here we choose the way over the D–transforms:
- $$\underline{u}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad U(D) = 1+ D + D^2 \hspace{0.05cm}.$$
- With the transfer function $G(D) = (1 + D^2)/(1 + D + D^2)$ one thus obtains for the D–transform of the output sequence:
- $$X(D) = {U(D)} \cdot G(D) = {1+D+D^2} \cdot \frac{1+D^2}{1+D+D^2} = 1+D^2 \hspace{0.05cm}\hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{x} = (1\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} 0 \hspace{0.05cm}\hspace{0.05cm},\hspace{0.01cm} \text{...}\hspace{0.05cm} \hspace{0.05cm} ) \hspace{0.05cm}.$$
- Only the proposed solution 1 is correct here: Despite infinitely long impulse response $\underline{g}$, for this input sequence $\underline{u}$ the output sequence $\underline{x}$ is limited to three bits.
- The same result is again obtained by adding shifted impulse responses:
- $$\underline{x} = (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} 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} \text{...}\hspace{0.05cm}) + (0\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} 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} \text{...}\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} 1\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} \text{...}\hspace{0.05cm}) = (1\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} 0 \hspace{0.05cm}\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}. $$
(4) Correct are the proposed solutions 1 and 3:
- On the data sheet, the general transfer function of a second–order recursive filter is given as follows.
- $$G(D) = \frac{a_0 + a_1 \cdot D + a_2 \cdot D^2}{1 + b_1 \cdot D + b_2 \cdot D^2} \hspace{0.05cm}.$$
- The filter considered here is determined by the coefficients $a_0 = a_2 = b_1 = b_2 = 1$ and $a_1 = 0$. Thus one obtains the result according to the solution suggestion 1:
- $$G(D) = \frac{1 + D^2}{1 + D + D^2} \hspace{0.05cm}. $$
- At the same time, $G(D)$ is also the D–transformed of the impulse response:
- $$\underline{g}= (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} 1\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}0 ,\hspace{0.05cm} \text{ ...}\hspace{0.05cm}) \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.15cm} {G}(D)$$
- $$\Rightarrow\hspace{0.3cm} {G}(D)= 1 + D + D^2 + D^4+ D^5 +\text{...} \hspace{0.1cm}. $$
- This means: The proposed solution 3 is also correct.
- The same result would have been obtained by dividing the two polynomials $1 + D^2$ and $1 + D + D^2$, as the calculation opposite shows.