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

From LNTwww
 
(26 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
{{quiz-Header|Buchseite=Kanalcodierung/Algebraische und polynomische Beschreibung}}
+
{{quiz-Header|Buchseite=Channel_Coding/Algebraic_and_Polynomial_Description}}
  
−
[[File:P_ID2647__KC_A_3_5.png|right|frame|Rekursive Filter]]
+
[[File:P_ID2647__KC_A_3_5.png|right|frame|General recursive filter&nbsp; (above) <br>and considered realization&nbsp; (below)]]
−
Die obere der beiden dargestellten Schaltungen zeigt ein rekursives Filter zweiter Ordnung in allgemeiner Form. Mit
+
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 $$
  
−
erhält man für die Übertragungsfunktion
+
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}.$$
  
−
Zu beachten ist, dass sich alle Rechenoperationen auf ${\rm GF(2)}$ beziehen. Damit sind auch die Filterkoeffizienten $a_0, a_1, a_2, b_1$ und $b_2$ binär (entweder $0$ oder $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)$.
  
−
Die untere Grafik zeigt das für die vorliegende Aufgabe spezifische Filter. Ein Filterkoeffizient ergibt sich zu $a_i = 1$, wenn die Verbindung durchgeschaltet ist $(0 &#8804; i &#8804; 2)$. Andernfalls ist $a_i = 0$. Die gleiche Systematik gilt für die Koeffizienten $b_1$ und $b_2$.
 
  
−
In den Teilaufgaben (1), ... , (3) sollen Sie für verschiedene Eingangssequenzen
+
The bottom graph shows the filter specific to the exercise at hand:
−
* $\underline{u} = (1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, ...)$,
+
# &nbsp; A filter coefficient results in &nbsp; $a_i = 1$ &nbsp; if the connection is through&nbsp; $(0 &#8804; i &#8804; 2)$.
−
* $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, 1, \, ...)$,
+
# &nbsp; Otherwise,&nbsp; $a_i = 0$. &nbsp; The same system applies to the coefficients&nbsp; $b_1$&nbsp; and&nbsp; $b_2$.  
−
* $\underline{u} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, ...)$
 
  
  
−
die jeweilige Ausgangssequenz $\underline{x}$ anhand der vorgegebenen Schaltung ermitteln. Es ist zu berücksichtigen:  
+
In the subtasks&nbsp; '''(1)''', ... , '''(3)'''&nbsp; you are to determine the respective output sequence&nbsp; $\underline{x}$&nbsp; for different input sequences
−
* Besteht die Eingangssequenz $\underline{u}$ aus einer Eins gefolgt von lauter Nullen, so bezeichnet man diese spezifische Ausgangssequenz $\underline{x}$ als die <i>Impulsantwort</i> $\underline{g}$, und es gilt:
+
* $\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.&nbsp; It should be taken into account:  
 +
* 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}. $$
−
* Andernfalls ergibt sich die Ausgangssequenz als das [[Signaldarstellung/Faltungssatz_und_Faltungsoperation| Faltungsprodukt]] zwischen Eingangssequenz und Impulsantwort:
+
* 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}.$$
−
* Die Faltungsoperation lässt sich mit dem Umweg über die [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#GF.282.29.E2.80.93Beschreibungsformen_eines_Digitalen_Filters| $D$&ndash;Transformation]] umgehen.  
+
* 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;.  
 +
 
 +
 
 +
 
 +
 
 +
 
  
  
−
''Hinweis:''
+
Hints:
−
* Die Aufgabe bezieht sich auf die [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Filterstruktur_bei_gebrochen.E2.80.93rationaler_.C3.9Cbertragungsfunktion| letzte Seite]] des Kapitels Algebraische und polynomische Beschreibung.
+
* This exercise belongs to the chapter&nbsp; [[Channel_Coding/Algebraic_and_Polynomial_Description| "Algebraic and Polynomial Description"]].
  
 +
* 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"]]
 +
  
  
−
===Fragebogen===
+
===Questions===
 
<quiz display=simple>
 
<quiz display=simple>
−
{Welche Aussagen gelten für die Impulsantwort $\underline{g}$ des rekursiven Filters?
+
{What statements hold for the impulse response&nbsp; $\underline{g}$&nbsp; of the recursive filter?
 
|type="[]"}
 
|type="[]"}
−
- Es gilt $\underline{g} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, ...)$.
+
- It holds&nbsp; $\underline{g} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$.
−
+ Es gilt $\underline{g} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, ...)$.
+
+ It holds&nbsp; $\underline{g} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$.
−
+ Die Impulsantwort $\underline{g}$ ist unendlich weit ausgedehnt.
+
+ The impulse response&nbsp; $\underline{g}$&nbsp; is infinitely extended.
  
−
{Es sei nun $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, 1)$. Welche Aussagen treffen zu?
+
{Let now&nbsp; $\underline{u} = (0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, 1)$.&nbsp; Which statements are true?
 
|type="[]"}
 
|type="[]"}
−
+ Die Ausgangssequenz lautet: $\underline{x} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, ...)$.
+
+ The output sequence is:&nbsp; $\underline{x} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$.
−
- Die Ausgangssequenz lautet: $\underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, ...)$.
+
- The output sequence is:&nbsp; $\underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$.
−
+ Die Ausgangssequenz $\underline{x}$ reicht bis ins Unendliche.
+
+ The output sequence&nbsp; $\underline{x}$&nbsp; extends to infinity.
  
−
{Nun gelte $\underline{u} = (1, \, 1, \, 1)$. Welche Aussagen treffen zu?
+
{Now apply&nbsp; $\underline{u} = (1, \, 1, \, 1)$.&nbsp; Which statements are true?
 
|type="[]"}
 
|type="[]"}
−
+ Die Ausgangssequenz $\underline{x}$ beginnt mit $(1, \, 0, \, 1)$.
+
+ The output sequence&nbsp; $\underline{x}$&nbsp; starts with&nbsp; $(1, \, 0, \, 1)$.
−
- Die Ausgangssequenz $\underline{x}$ beginnt mit $(1, \, 1, \, 1)$.
+
- The output sequence&nbsp; $\underline{x}$&nbsp; begins with&nbsp; $(1, \, 1, \, 1)$.
−
- Die Ausgangssequenz $\underline{x}$ reicht bis ins Unendliche.
+
- The output sequence&nbsp; $\underline{x}$&nbsp; extends to infinity.
  
−
{Welche Aussagen gelten für die Übertragungsfunktion $G(D)$?
+
{What statements are valid for the transfer function&nbsp; $G(D)$?
 
|type="[]"}
 
|type="[]"}
−
+ Es gilt $G(D) = (1 + D^2)/(1 + D + D^2)$.
+
+ It holds&nbsp; $G(D) = (1 + D^2)/(1 + D + D^2)$.
−
- Es gilt $G(D) = (1 + D + D^2)/(1 + D^2)$.
+
- It holds&nbsp; $G(D) = (1 + D + D^2)/(1 + D^2)$.
−
+ Es gilt $G(D) = 1 + D + D^2 + D^4 + D^5 + D^7 + D^8 + \ ... \ $ .
+
+ It holds&nbsp; $G(D) = 1 + D + D^2 + D^4 + D^5 + D^7 + D^8 + \hspace{0.05cm} \text{...}\hspace{0.05cm} $ .
 
</quiz>
 
</quiz>
  
−
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
−
'''(1)'''&nbsp;  
+
'''(1)'''&nbsp; Correct are the&nbsp; <u>proposed solutions 2 and 3</u>:
−
'''(2)'''&nbsp;  
+
[[File:P_ID2643__KC_A_3_5a.png|right|frame|For calculation of the impulse response&nbsp; $\underline{g}$]]
−
'''(3)'''&nbsp;  
+
[[File:P_ID2644__KC_A_3_5b.png|right|frame|For calculation of the output sequence $\underline{x}$]]
−
'''(4)'''&nbsp;  
+
 
−
'''(5)'''&nbsp;  
+
*The impulse response&nbsp; $\underline{g}$&nbsp; is equal to the sequence&nbsp; $\underline{x}$&nbsp; for the input sequence&nbsp; $\underline{u} = (1, \, 0, \, 0, \, \text{...})$.&nbsp;
 +
 
 +
*Based on the filter structure,&nbsp; $w_0 = w_{-1} = 0$&nbsp; 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&nbsp; $\underline{g} = \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...})$ &nbsp; corresponding to&nbsp; <u>proposed solution 2</u>,&nbsp; as shown in the adjacent calculation.
 +
 
 +
*But additionally the&nbsp; <u>proposed solution 3</u>&nbsp; is correct,&nbsp; because one recognizes from this calculation scheme further following periodicities of the impulse response&nbsp; $\underline{g}$ &nbsp; $($up to infinity$)$&nbsp; 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}.$$
 +
 
 +
<br><br><br><br>
 +
'''(2)'''&nbsp;After similar calculations as in subtask&nbsp; '''(1)'''&nbsp; one recognizes the correctness of&nbsp; <u>solutions 1 and 3</u>:
 +
*The initial sequence&nbsp; $\underline{x}$&nbsp; also extends to infinity.&nbsp; Periodicities show up again.
 +
 
 +
*The same result is obtained by adding the impulse responses &nbsp; $\underline{g} = (1, \, 0, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, \text{...} \hspace{0.05cm})$ &nbsp; in the Galois field&nbsp; ${\rm GF(2)}$&nbsp; shifted by one,&nbsp; three,&nbsp; six,&nbsp; and seven positions&nbsp; $($to the right,&nbsp; 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,&nbsp; this is allowed.
 +
 
 +
 
 +
'''(3)'''&nbsp; Here we choose the way over the D&ndash;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 &nbsp; $G(D) = (1 + D^2)/(1 + D + D^2)$ &nbsp; one thus obtains for the D&ndash;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&nbsp; <u>proposed solution 1</u>&nbsp; is correct here:&nbsp; Despite infinitely long impulse response&nbsp; $\underline{g}$,&nbsp; for this input sequence&nbsp; $\underline{u}$&nbsp; the output sequence&nbsp; $\underline{x}$&nbsp; 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)'''&nbsp; Correct are the&nbsp; <u>proposed solutions 1 and 3</u>:
 +
*On the data sheet,&nbsp; the general transfer function of a second&ndash;order recursive filter is given as follows.
 +
[[File:P_ID2645__KC_A_3_5e.png|right|frame|$\rm GF(2)$&nbsp; polynomial division&nbsp; $(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}.$$
 +
 
 +
*The filter considered here is determined by the coefficients&nbsp; $a_0 = a_2 = b_1 = b_2 = 1$&nbsp; and&nbsp; $a_1 = 0$.&nbsp; Thus one obtains the result according to the&nbsp; <u>solution suggestion 1</u>:
 +
:$$G(D) =  \frac{1 +  D^2}{1 +  D + D^2} \hspace{0.05cm}. $$
 +
*At the same time,&nbsp; $G(D)$&nbsp; is also the D&ndash;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:&nbsp;  The&nbsp; <u>proposed solution 3</u>&nbsp; is also correct.
 +
 +
*The same result would have been obtained by dividing the two polynomials&nbsp; $1 + D^2$&nbsp; and&nbsp; $1 + D + D^2$,&nbsp; as the calculation opposite shows.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
−
[[Category:Aufgaben zu  Kanalcodierung|^3.2 Algebraische und polynomische Beschreibung^]]
+
[[Category:Channel Coding: Exercises|^3.2 Polynomial Description^]]

Latest revision as of 14:04, 11 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:


Questions

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:

For calculation of the impulse response  $\underline{g}$
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},$$
$$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.
$\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}.$$
  • 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.

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