frage by wurm
[sigproz.git] / ausarb1.txt
1 Ausarbeitung der typischen Prüfungsfragen zur Vorlesung "Signalprozessoren"
2 Teil 1/2 - von Sebastian Falbesoner <e0725433@student.tuwien.ac.at>
3
4 1 -- Welcher Unterschied besteht zwischen linearer und zirkulärer Faltung.
5      Erklären Sie an Hand eines Beispiels, z.B.: f = [2 1 2 1] und g = [1 2 3 4]
6         lineare Faltung (auch "normale" oder aperiodische Faltung genannt): Im
7         Zeitbereich gilt fuer die laenge des Eregbnisvektors
8         > len(f*g) == ((len g) + (len f)- 1)
9
10         zirkuläre Faltung (auch zyklische oder periodische Faltung genannt):
11         Zirkuläre Faltung entsteht ueber den Umweg ueber den Frequenzbereich
12         > idft(dft(f) x dft(g))
13         Hier bleibt die Laenge des Ergebnisvektors gegenueber der Laenge der
14         Parameter erhalten, also es gilt
15         > len(idft(dft(f) x dft(g))) == len(g) == len(f)
16         und dementsprechend unterscheidet sich das Ergebnis zur linearen Faltung.
17         Abhilfe dabei schafft das Auffuellen von Nullen:
18         > fnew = [f zeros(1,length(g)-1)]
19         > gnew = [g zeros(1,length(f)-1)]
20         und zwar entspricht die Anzahl der Nullen die Laenge minus eins des zweiten
21         Parameters der Faltung. Durch dieses Auffuellen erreichen wir, dass das
22         Ergebnis der zirkulären Faltung wieder dem Ergebnis der periodischen
23         Faltung entspricht. Weiters ist darauf zu achten, dass
24         > len(g) == len(f)
25         entspricht, sonst kann die Multiplikation im Frequenzbereich nicht
26         funktionieren. (??? stimmt das?)
27
28         TODO konkreter unterschied?
29         Achtung:
30         * ... entspricht Faltung
31         x ... Multikplikation
32
33 2 -- Die schnelle Faltung wird über den Frequenzbereich berechnet:
34      * Beschreiben Sie die grundsätzliche Vorgangsweise.
35      * Welches Ergebnis erhalten Sie, wenn Sie f und g über den Frequenzbereich
36         falten?
37      * Worauf müssen Sie bei der schnellen Faltung achten?
38         Hinweis: schnelle Faltung ist nicht nur schneller, sondern auch
39         genauer, da Rundungsfehler von der Zahl der Operationen abhängen -
40         weniger Operationen, weniger Rundungsfehler!
41
42         Vorgehensweise: f und g mit Hilfe der FFT in den Frequenzbereich
43         transformieren, sie dort miteinander multiplizieren, und auf das
44         Ergebnis die iFFT anwenden.
45         Problem: FFT arbeitet intern mit der periodischen Faltung, es muss
46         verhindert werden dass Fehler durch die periodische Faltung entstehen.
47         Lösung: Overlap-Add-Verfahren; dabei wird die Eingangsfolge in einander
48         überlappende Teilfolgen zerlegt und die Überlappungsbereiche
49         aufaddiert. Es werden Teilfolgen der Länge L gebildet, wobei diese mit
50         Nullen der Laenge M-1 aufgefüllt werden und umgekehrt (Zero-Padding).  L
51         steht dabei ueblicherweise fuer die Laenge der Signalabschnitte und M fuer
52         die Laenge der Impulsantwort, koennen aber auch beliebig andere
53         Zahlenfolgen sein.
54
55 3 -- Berechnen Sie die Impulsantwort des folgenden IIR-Filters und skizzieren
56      Sie das Blockdiagramm der Direkten Form II 
57      y[n] = 1/4 y[n-2] + 5 x[n] - 4 x[n-1]
58
59          Impulsantwort: in z-Bereich transformieren, und dort H(z) =
60          \frac{Y(z)}{X(z)} = Systemfunktion berechnen. Um die Impulsantwort zu
61          erhalten muss H(z) in den Zeitbereich transformiert werden (h[n]).
62          Y(z) = 1/4 z^{-2} Y(z) + 5 X(z) - 4 z^{-1} X(z)
63          Y(z) (1 - 1/4 z^{-2}) = X(z) (5 - 4 z^{-1})
64          H(z) = \frac{Y(z)}{X(z)} = \frac{5 - 4 z^{-1}}{1 - 1/4 z^{-2}}
65
66          die Transformation zurueck in den Zeitbereich bleibt dem Leser als Uebung
67          (Hinweis: Partialbruchzerlegung)
68
69         TODO!
70         Blockdiagramm siehe IIR-Foliensatz ab Seite 10
71         
72
73 4 -- Welche Bedeutung haben Fenster bei FIR-Filtern? Welche Fenster kennen Sie
74      welche Auswirkungen haben sie?
75
76          Filterdesign (von WP): Dabei wird der gewuenschte Frequenzgang des Filters
77          definiert und per inverse Fouriertransformation die (ideale) Impulsantwort
78          ermittelt.  Das Resultat dabei ist in der Regel unendlich lang, um also
79          eine gewuenschte Filterlaenge N (=Ordnung) zu erhalten, wird durch eine
80          Fensterfunktion ein Ausschnitt der unendlichen Impulsantwort ausgewaehlt.
81          Der tatsaechliche Frequenzgang des Filters entspricht somit der Faltung
82          des gewuenschten Frequenzganges mit der der Fouriertransformierten der
83          Fensterfunktion!
84
85          Im Filterdesign fuehren breite (selektive) Fensterfunktionen zu steilen
86          Uebergaengen (='B') zwischen Durchlass- und Sperrbereich, aber zu geringer
87          Sperrdaempfung (='A'). Schmale (nicht selektive) Fensterfunktionen fuehren
88          zu flachen Uebergaengen zwischen Durchlass- und Sperrbereich, dafuer aber
89          zu grosser Sperrdaempfung.
90
91
92          verschiedene Fenster (nach Selektivitaet geordnet):
93          o Rechteckfenster      B=4pi/(2M+1)    A=-13dB
94          o Hannfenster          B=8pi/(2M+1)    A=-32dB
95          o Hammingfenster       B=8pi/(2M+1)    A=-43dB
96          o Blackmann            B=12pi/(2M+1)   A=-58dB
97
98          weitere: Dreieckfenster, Kaiserfenster (hat Parameter \beta !)
99
100
101 5 -- Welche Approximationsansätze für den Frequenzgang kennen Sie bei IIR-
102      Filtern? Beschreiben und vergleichen Sie die Ansätze.
103         - Potenz- oder Butterworthfilter
104                 - geringste Flankensteilheit    
105                 - ungefähre lineare Phase
106                 - benötigt vergleichsweise höchste Ordnung
107         - Tschebyscheff 
108                 - bessere Flankensteilheit als Butterworth, schlechtere
109                   als bei Elliptisch oder Cauer
110                 - Lineare Phase schlechter als bei Butterworth, aber besser
111                   als bei Elliptisch oder Cauer
112                 - Tschebyscheff Typ 1: höhere Welligkeit im Durchlassbereich
113                 - Tschebyscheff Typ 2: höhere Welligkeit im Sperrbereich
114         - Elliptisch oder Cauer
115                 - beste Flankensteilheit, jedoch Welligkeit in
116                   Durchlass- und in Sperrbereich
117                 - benötigt vergleichsweise niedrigste Ordnung
118
119 6 -- Berechnen Sie den Frequenzgang des FIR-Filters mit den Koeffizieten
120      [1 2 3 3 2 1]
121         Formel für Frequenzgang von FIR-Filtern allgemein:
122         [ w^ = w * T_s
123           w^  ... normierte Kreisfrequenz
124           T_s ... Abtastperiode ]
125         H(w^) = \sum_{k=0}^{M} b_k e^{-j w^ k}
126         hergeleitet in dem komplexe Exponentialfolge x[n] in die allgemeine
127         Gleichung für FIR-Filter eingesetzt wurde!
128
129         Herleitung:
130         x[n] = A e^{j \phi} e^{j w^ n}
131         in y[n] einsetzen ... kommt dann auf
132         y[n] = (\sum_{k=0}^{M} b_k e^{-j w^ k}) A e^{j \phi} e^{j w^ n}
133         wobei der Term in der Klammer H(w^) entspricht!
134
135         in unserem Fall also:
136         x = [1 2 3 3 2 1]
137         H(w^) = 1 + 2*e^{-j w^ 1} + 3*e^{-j w^ 2} + 3*e^{-j w^ 3} +
138                   + 2*e^{-j w^ 4} + 1*e^{-j w^ 5}
139
140 7 -- Welche Bedeutung haben Filter mit linearer Phase? Woran erkennen Sie sie?
141         Lineares Phasenverhalten erzeugt Phasenverschiebungen die
142         frequenzproportional sind, d.h. die Kurvenform bleibt erhalten!
143         Steckt die relevante Information in den Frequenzen, und nicht in der
144         Kurvenform, so ist die lineare Phase nicht von Bedeutung.
145
146         Die lineare Phase ist nur bei FIR-Filtern möglich ist und kann daran
147         erkannt werden, dass die Koeffizienten symmetrisch sind. Hierbei
148         gibt es verschiedene Arten von Symmetrien (gerade oder ungerade) und
149         noch jeweils die Unterscheidung ob die Anzahl der Koeffizienten gerade
150         oder ungerade ist, was insgesamt zu vier verschiedenen Typen führt:
151         - Gerade Symmetrie, d.h. b_k = b_{L-1-k}
152                 - Typ 1: L ist ungeradzahlig (z.B. [1 2 3 2 1])
153                 - Typ 2: L ist geradzahlig (z.B. [1 2 3 3 2 1])
154         - Ungerade Symmetrie, d.h. b_k = -b_{L-1-k}
155                 - Typ 3: L ist ungeradzahlig und b_{(L-1)/2} = 0
156                         (z.B. [-1, -2, 0, 2, 1])
157                 - Typ 4: L ist geradzahlig (z.B. [-1 -2 -3 3 2 1])
158
159         Folgendes gilt dabei für die Typen:
160                 Typ 1 ist die allgemeinste Form, alle Filtertypen sind möglich
161                 Typ 2 kann kein Hochpass sein
162                 Typ 3 kann weder Hochpass noch Tiefpass sein
163                 Typ 4 kann kein Tiefpass sein
164      
165 8 -- Schreiben Sie die allgemeine Differenzengleichung eines IIR-Filters
166      höherer Ordnung an und zeichnen Sie das zugehörige Blockdiagramm.
167         y[n] = b_0 x[n] + b_1 x[n-1] + b_2 x[n-2] + ... + b_{L-1} x[n-(L-1)] +
168              + a_1 y[n-1] + a_2 y[n-2] + ... + a_{M-1} y[n-(M-1)] =
169                \sum_{k=0}{L-1} b_k x[n-k] + \sum_{m=1}{M-1} a_m y[n-m]
170
171         Blockdiagramm siehe IIR-Foliensatz ab Seite 10
172
173 9 -- Welche Bedeutung hat die Impulsantwort für die Analyse von diskreten
174      Filtern?
175         Die Impulsantwort ist das Ausgangssignal eines Systems, bei dem am
176         Eingang ein Dirac-Impuls zugeführt wird. Mit Hilfe dieser lässt sich
177         ein LTI-System vollständig charakterisisieren (z.B. Bestimmung von
178         Übertragungsfunktion und Frequenzgang). Die Wirkung des Filters kann
179         durch Faltung der Eingangsfolge mit der Impulsantwort im Zeitbereich
180         bestimmt werden.
181         Da jedes Eingangssignal als Überlagerung von gewichteten,
182         zeitverzögerten Einheitsimpulsen dargestellt werden kann, können die
183         entsprechenden Ausgangssignale von gewichteten und zeitverzögerten
184         Versionen der Impulsantwort gebildet werden.
185
186 10 - Welche Bedeutung hat das Pol/Nullstellendiagramm?
187         Aus einem Pol/Nullstellendiagramm kann unter anderem auf den Betrags-
188         und Phasenverlauf eines Systems, sowie auf dessen Impuls- und Sprung-
189         antwort geschlossen werden.
190         Aus der Lage der Pole kann man unter anderem erkennen, ob ein System
191         kausal oder stabil ist. Stabilität ist dann gegeben, wenn alle Pole
192         in der offenen linken Halbebene des Diagramms liegen. Realisierbare
193         (kausale) Systeme besitzen mehr Pole als Nullstellen.
194         Weitere Bedeutung hat das Diagramm zum Bestimmen der Koeffizienten
195         bei der Entwicklung von IIR-Filtern; bei dieser Methode werden die
196         Pole und Nullstellen des Filters mit dem gewünschten Verhalten in dem
197         Diagramm platziert und dann wird entsprechend fortgefahren.
198         (TODO) by wurm: und wie wird fortgefahren?
199
200
201 by wurm:
202
203         Durch das PN-Diagramm ist die Systemfunktion H(z) eindeutig ermittelbar.
204         Nullstellen auf dem Einheitskreis bedeuten, dass die zueghoerige
205         Frequenzkomponente am Ausgang des Systems nicht auftritt, also vollstaendig
206         unterdrueckt wird.
207         Fuer stabile Systeme muessen die Polstellen im z-Bereich innerhalb des
208         Einheitskreises liegen (zum Vergleich: bei zeit-kontinuierlichen Systemen
209         gilt, dass die Pole in der linken offenen Halbebene des s-Bereiches liegen
210         muessen).
211         (fuer z-bereich: Das folgt aus der Analyse von Differenzengleichungen, siehe seite 13 ET-Text/IIR)
212
213 11 - Wie hängen Impulsantwort und Systemfunktion zusammen?
214         Die Systemfunktion (auch Übertragungsfunktion genannt) H[z] ist die 
215         z-Transformierte der Impulsantwort h[n].
216
217         Zusammenhänge:
218                 Zeitbereich: y[n] = x[n] x h[n] (x = Faltungsoperator!)
219                 z-Bereich:   H(z) = Y(z)/X(z)
220                              Y(z) = X(z) * H(z) (* = Multiplikationsoperator!)
221
222 12 - Schreiben Sie die DFT und die inverse DFT an. Wie berechnet man die inverse
223      DFT mit Hilfe der DFT?
224          DFT: X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2 \pi n}{N} k}
225         iDFT: x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2 \pi k}{N} n}
226
227         Die inverse DFT unterscheidet sich von der DFT lediglich durch den
228         Faktor 1/N und das negative Vorzeichen.
229
230         Ausgehend von der Formel für die iDFT kann man beide Seiten konjugiert
231         komplex machen, wodurch sich die gleiche Formel wie für die DFT ergibt,
232         nur dass noch ein Faktor von 1/N davorsteht und die einzelnen Werte
233         X[k] jeweils konjugiert komplex sein müssen!
234
235         x[n]  =  \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2 \pi k}{N} n}
236         x[n]* = (\frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2 \pi k}{N} n})* =
237                  \frac{1}{N} \sum_{k=0}^{N-1} X[k]* e^{-j\frac{2 \pi k}{N} n}
238             [konjugiert komplexen Operator nochmal auf beiden Seiten anwenden]
239         x[n]  = (\frac{1}{N} \sub_{k=0}^{N-1} X[k]* e^{-j\frac{2 \pi k}{N} n)*
240
241         Also folgende Vorgehensweise um mit DFT iDFT zu berechnen:
242                 1. Eingangsfolge komplex konjugieren
243                 2. DFT auf diese modifizierte Folge anwenden
244                 3. Ausgangsfolge mit 1/N skalieren
245                 4. Ausgangsfolge nochmals komplex konjugieren
246         Das komplex konjugieren kann bei reellen Zeitfolgen entfallen!
247
248 13 - Wodurch entsteht der Leck-Effekt bei der DFT? Wie können seine Auswirkungen
249      beeinflusst werden und welche Vor- und Nachteile treten dabei auf?
250         Wenn eine gegebene Frequenz nicht auf dem Frequenzraster liegt (Abstand
251         zwischen Spektrallinien betraegt \frac{f_s}{N}), so muss sie durch
252         benachbarte Frequenzen dargestellt werden.
253
254         Man kann diesen Effekt vermindern, indem man N groesser waehlt;
255         vollstaendig verhindert kann der Leck-Effekt nicht werden, da in der
256         Praxis ueblicherweise die Spektralkomponenten der (praktischen) Signale
257         nicht am Raster liegen werden.