Difference between revisions of "Aufgaben:Exercise 3.5: Recursive Filters for GF(2)"

From LNTwww
Line 1: Line 1:
 
{{quiz-Header|Buchseite=Channel_Coding/Algebraic_and_Polynomial_Description}}
 
{{quiz-Header|Buchseite=Channel_Coding/Algebraic_and_Polynomial_Description}}
  
−
[[File:P_ID2647__KC_A_3_5.png|right|frame|General recursive filter and considered realization]]
+
[[File:P_ID2647__KC_A_3_5.png|right|frame|General recursive filter&nbsp; (above) <br>and considered realization&nbsp; (below)]]
−
The upper of the two circuits shown shows a second order recursive filter in general form. With
+
The upper of the two circuits on the right shows a second order recursive filter in general form.&nbsp; 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 $$
Line 9: Line 9:
 
:$$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&nbsp; ${\rm GF(2)}$&nbsp;. Thus, the filter coefficients&nbsp; $a_0, \ a_1, \ a_2, \ b_1$&nbsp; and&nbsp; $b_2$&nbsp; are also binary $($entweder &nbsp;$0$&nbsp; or&nbsp; $1)$.
+
* It should be noted that all arithmetic operations refer to&nbsp; ${\rm GF(2)}$.&nbsp;
 +
 +
* Thus,&nbsp; the filter coefficients &nbsp; $a_0, \ a_1, \ a_2, \ b_1, \ b_2$ &nbsp; are also binary $(0$&nbsp; or&nbsp; $1)$.
 +
 
  
 
The bottom graph shows the filter specific to the exercise at hand:  
 
The bottom graph shows the filter specific to the exercise at hand:  
−
*A filter coefficient results in&nbsp; $a_i = 1$ if the connection is through&nbsp; $(0 &#8804; i &#8804; 2)$.  
+
# &nbsp; A filter coefficient results in &nbsp; $a_i = 1$ &nbsp; if the connection is through&nbsp; $(0 &#8804; i &#8804; 2)$.  
−
*Otherwise,&nbsp; $a_i = 0$. The same system applies to the coefficients&nbsp; $b_1$&nbsp; and&nbsp; $b_2$.  
+
# &nbsp; Otherwise,&nbsp; $a_i = 0$. &nbsp; The same system applies to the coefficients&nbsp; $b_1$&nbsp; and&nbsp; $b_2$.  
  
  
−
In the subtasks '''(1)''', ... , '''(3)''' you are to determine the respective output sequence&nbsp; $\underline{x}$&nbsp; for different input sequences
+
In the subtasks&nbsp; '''(1)''', ... , '''(3)'''&nbsp; you are to determine the respective output sequence&nbsp; $\underline{x}$&nbsp; for different input sequences
 
* $\underline{u} = (1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$,
 
* $\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} = (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})$
 
* $\underline{u} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$
  
  
−
using the given circuit. It should be taken into account:  
+
using the given circuit.&nbsp; It should be taken into account:  
−
* If the input sequence&nbsp; $\underline{u}$&nbsp; consists of a one followed by all zeros, this specific output sequence&nbsp; $\underline{x}$&nbsp; is called the&nbsp; [[Linear_and_Time_Invariant_Systems/System_Description_in_Time_Domain#Impulse_response|"Impulse Response"]]&nbsp; $\underline{g}$, and it holds:
+
* If the input sequence&nbsp; $\underline{u}$&nbsp; consists of a&nbsp; "$1$"&nbsp; followed by all zeros,&nbsp; this specific output sequence&nbsp; $\underline{x}$&nbsp; is the&nbsp; [[Linear_and_Time_Invariant_Systems/System_Description_in_Time_Domain#Impulse_response|"impulse response"]]&nbsp; $\underline{g}$,&nbsp; 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&nbsp; [[Signal_Representation/The_Convolution_Theorem_and_Operation|"Convolution Product"]]&nbsp; between input sequence and impulse response:
+
* Otherwise,&nbsp; the output sequence results as the&nbsp; [[Signal_Representation/The_Convolution_Theorem_and_Operation|"convolution product"]]&nbsp; 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 by&nbsp; [[Channel_Coding/Algebraic_and_Polynomial_Description#GF.282.29_description_forms_of_a_digital_filter| "$D$ transform"]]&nbsp;.  
+
* The convolution operation can be bypassed with the&nbsp; [[Channel_Coding/Algebraic_and_Polynomial_Description#GF.282.29_description_forms_of_a_digital_filter|"D-transform"]]&nbsp;.  
  
  
Line 37: Line 42:
 
Hints:
 
Hints:
 
* This exercise belongs to the chapter&nbsp; [[Channel_Coding/Algebraic_and_Polynomial_Description| "Algebraic and Polynomial Description"]].
 
* This exercise belongs to the chapter&nbsp; [[Channel_Coding/Algebraic_and_Polynomial_Description| "Algebraic and Polynomial Description"]].
−
* Reference is made in particular to the page&nbsp; [[Channel_Coding/Algebraic_and_Polynomial_Description#Filter_structure_with_fractional.E2.80.93rational_transfer_function| "Filter structure with fractional&ndash;rational transfer function"]]
+
 
 +
* Reference is made in particular to the section&nbsp; [[Channel_Coding/Algebraic_and_Polynomial_Description#Filter_structure_with_fractional.E2.80.93rational_transfer_function| "Filter structure with fractional&ndash;rational transfer function"]]
 
   
 
   
  

Revision as of 21:26, 10 November 2022

General recursive filter  (above)
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},$$
$$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:

  1.   A filter coefficient results in   $a_i = 1$   if the connection is through  $(0 ≤ i ≤ 2)$.
  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:


Solution

1

What statements hold for the impulse response  $\underline{g}$  of the recursive filter?

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.

2

Let now  $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, 1)$. Which statements are true?

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.

3

Now apply  $\underline{u} = (1, \, 1, \, 1)$. Which statements are true?

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.

4

What statements are valid for the transfer function  $G(D)$?

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} $ .


Solution

Solution

(1)  Correct are the proposed solutions 2 and 3:

To calculate the impulse response $\underline{g}$
  • 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 $\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},$$
For calculation of the output sequence $\underline{x}$
$$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})$ n 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}. $$


$\rm GF(2)$ polynomial division $(1 + D^2)/(1 + D + D^2)$

(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}.$$
  • Das hier betrachtete Filter ist durch die Koeffizienten $a_0 = a_2 = b_1 = b_2 = 1$ und $a_1 = 0$ bestimmt. Somit erhält man das Ergebnis entsprechend dem Lösungsvorschlag 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.

Retrieved from "http://en.lntwww.de/index.php?title=Aufgaben:Exercise_3.5:_Recursive_Filters_for_GF(2)&oldid=49996"
  • Powered by MediaWiki