Ausarbeitung der typischen Prüfungsfragen zur Vorlesung "Signalprozessoren" Teil 1/2 - von Sebastian Falbesoner 1 -- Welcher Unterschied besteht zwischen linearer und zirkulärer Faltung. Erklären Sie an Hand eines Beispiels, z.B.: f = [2 1 2 1] und g = [1 2 3 4] lineare Faltung (auch "normale" oder aperiodische Faltung genannt): Im Zeitbereich gilt fuer die laenge des Eregbnisvektors > len(f*g) == ((len g) + (len f)- 1) zirkuläre Faltung (auch zyklische oder periodische Faltung genannt): Zirkuläre Faltung entsteht ueber den Umweg ueber den Frequenzbereich > idft(dft(f) x dft(g)) Hier bleibt die Laenge des Ergebnisvektors gegenueber der Laenge der Parameter erhalten, also es gilt > len(idft(dft(f) x dft(g))) == len(g) == len(f) und dementsprechend unterscheidet sich das Ergebnis zur linearen Faltung. Abhilfe dabei schafft das Auffuellen von Nullen: > fnew = [f zeros(1,length(g)-1)] > gnew = [g zeros(1,length(f)-1)] und zwar entspricht die Anzahl der Nullen die Laenge minus eins des zweiten Parameters der Faltung. Durch dieses Auffuellen erreichen wir, dass das Ergebnis der zirkulären Faltung wieder dem Ergebnis der periodischen Faltung entspricht. Weiters ist darauf zu achten, dass > len(g) == len(f) entspricht, sonst kann die Multiplikation im Frequenzbereich nicht funktionieren. (??? stimmt das?) TODO konkreter unterschied? Achtung: * ... entspricht Faltung x ... Multikplikation 2 -- Die schnelle Faltung wird über den Frequenzbereich berechnet: * Beschreiben Sie die grundsätzliche Vorgangsweise. * Welches Ergebnis erhalten Sie, wenn Sie f und g über den Frequenzbereich falten? * Worauf müssen Sie bei der schnellen Faltung achten? Hinweis: schnelle Faltung ist nicht nur schneller, sondern auch genauer, da Rundungsfehler von der Zahl der Operationen abhängen - weniger Operationen, weniger Rundungsfehler! Vorgehensweise: f und g mit Hilfe der FFT in den Frequenzbereich transformieren, sie dort miteinander multiplizieren, und auf das Ergebnis die iFFT anwenden. Problem: FFT arbeitet intern mit der periodischen Faltung, es muss verhindert werden dass Fehler durch die periodische Faltung entstehen. Lösung: Overlap-Add-Verfahren; dabei wird die Eingangsfolge in einander überlappende Teilfolgen zerlegt und die Überlappungsbereiche aufaddiert. Es werden Teilfolgen der Länge L gebildet, wobei diese mit Nullen aufgefüllt werden (Zero-Padding). 3 -- Berechnen Sie die Impulsantwort des folgenden IIR-Filters und skizzieren Sie das Blockdiagramm der Direkten Form II y[n] = 1/4 y[n-2] + 5 x[n] - 4 x[n-1] Impulsantwort: in z-Bereich transformieren, und dort H(z) = \frac{Y(z)}{X(z)} = Systemfunktion berechnen. Um die Impulsantwort zu erhalten muss H(z) in den Zeitbereich transformiert werden (h[n]). Y(z) = 1/4 z^{-2} Y(z) + 5 X(z) - 4 z^{-1} X(z) Y(z) (1 - 1/4 z^{-2}) = X(z) (5 - 4 z^{-1}) H(z) = \frac{Y(z)}{X(z)} = \frac{5 - 4 z^{-1}}{1 - 1/4 z^{-2}} die Transformation zurueck in den Zeitbereich bleibt dem Leser als Uebung (Hinweis: Partialbruchzerlegung) TODO! Blockdiagramm siehe IIR-Foliensatz ab Seite 10 4 -- Welche Bedeutung haben Fenster bei FIR-Filtern? Welche Fenster kennen Sie welche Auswirkungen haben sie? Filterdesign (von WP): Dabei wird der gewuenschte Frequenzgang des Filters definiert und per inverse Fouriertransformation die (ideale) Impulsantwort ermittelt. Das Resultat dabei ist in der Regel unendlich lang, um also eine gewuenschte Filterlaenge N (=Ordnung) zu erhalten, wird durch eine Fensterfunktion ein Ausschnitt der unendlichen Impulsantwort ausgewaehlt. Der tatsaechliche Frequenzgang des Filters entspricht somit der Faltung des gewuenschten Frequenzganges mit der der Fouriertransformierten der Fensterfunktion! Im Filterdesign fuehren breite (selektive) Fensterfunktionen zu steilen Uebergaengen (='B') zwischen Durchlass- und Sperrbereich, aber zu geringer Sperrdaempfung (='A'). Schmale (nicht selektive) Fensterfunktionen fuehren zu flachen Uebergaengen zwischen Durchlass- und Sperrbereich, dafuer aber zu grosser Sperrdaempfung. verschiedene Fenster (nach Selektivitaet geordnet): o Rechteckfenster B=4pi/(2M+1) A=-13dB o Hannfenster B=8pi/(2M+1) A=-32dB o Hammingfenster B=8pi/(2M+1) A=-43dB o Blackmann B=12pi/(2M+1) A=-58dB weitere: Dreieckfenster, Kaiserfenster (hat Parameter \beta !) 5 -- Welche Approximationsansätze für den Frequenzgang kennen Sie bei IIR- Filtern? Beschreiben und vergleichen Sie die Ansätze. - Potenz- oder Butterworthfilter - geringste Flankensteilheit - ungefähre lineare Phase - benötigt vergleichsweise höchste Ordnung - Tschebyscheff - bessere Flankensteilheit als Butterworth, schlechtere als bei Elliptisch oder Cauer - Lineare Phase schlechter als bei Butterworth, aber besser als bei Elliptisch oder Cauer - Tschebyscheff Typ 1: höhere Welligkeit im Durchlassbereich - Tschebyscheff Typ 2: höhere Welligkeit im Sperrbereich - Elliptisch oder Cauer - beste Flankensteilheit, jedoch Welligkeit in Durchlass- und in Sperrbereich - benötigt vergleichsweise niedrigste Ordnung 6 -- Berechnen Sie den Frequenzgang des FIR-Filters mit den Koeffizieten [1 2 3 3 2 1] Formel für Frequenzgang von FIR-Filtern allgemein: [ w^ = w * T_s w^ ... normierte Kreisfrequenz T_s ... Abtastperiode ] H(w^) = \sum_{k=0}^{M} b_k e^{-j w^ k} hergeleitet in dem komplexe Exponentialfolge x[n] in die allgemeine Gleichung für FIR-Filter eingesetzt wurde! Herleitung: x[n] = A e^{j \phi} e^{j w^ n} in y[n] einsetzen ... kommt dann auf y[n] = (\sum_{k=0}^{M} b_k e^{-j w^ k}) A e^{j \phi} e^{j w^ n} wobei der Term in der Klammer H(w^) entspricht! in unserem Fall also: x = [1 2 3 3 2 1] H(w^) = 1 + 2*e^{-j w^ 1} + 3*e^{-j w^ 2} + 3*e^{-j w^ 3} + + 2*e^{-j w^ 4} + 1*e^{-j w^ 5} 7 -- Welche Bedeutung haben Filter mit linearer Phase? Woran erkennen Sie sie? Lineares Phasenverhalten erzeugt Phasenverschiebungen die frequenzproportional sind, d.h. die Kurvenform bleibt erhalten! Steckt die relevante Information in den Frequenzen, und nicht in der Kurvenform, so ist die lineare Phase nicht von Bedeutung. Die lineare Phase ist nur bei FIR-Filtern möglich ist und kann daran erkannt werden, dass die Koeffizienten symmetrisch sind. Hierbei gibt es verschiedene Arten von Symmetrien (gerade oder ungerade) und noch jeweils die Unterscheidung ob die Anzahl der Koeffizienten gerade oder ungerade ist, was insgesamt zu vier verschiedenen Typen führt: - Gerade Symmetrie, d.h. b_k = b_{L-1-k} - Typ 1: L ist ungeradzahlig (z.B. [1 2 3 2 1]) - Typ 2: L ist geradzahlig (z.B. [1 2 3 3 2 1]) - Ungerade Symmetrie, d.h. b_k = -b_{L-1-k} - Typ 3: L ist ungeradzahlig und b_{(L-1)/2} = 0 (z.B. [-1, -2, 0, 2, 1]) - Typ 4: L ist geradzahlig (z.B. [-1 -2 -3 3 2 1]) Folgendes gilt dabei für die Typen: Typ 1 ist die allgemeinste Form, alle Filtertypen sind möglich Typ 2 kann kein Hochpass sein Typ 3 kann weder Hochpass noch Tiefpass sein Typ 4 kann kein Tiefpass sein 8 -- Schreiben Sie die allgemeine Differenzengleichung eines IIR-Filters höherer Ordnung an und zeichnen Sie das zugehörige Blockdiagramm. y[n] = b_0 x[n] + b_1 x[n-1] + b_2 x[n-2] + ... + b_{L-1} x[n-(L-1)] + + a_1 y[n-1] + a_2 y[n-2] + ... + a_{M-1} y[n-(M-1)] = \sum_{k=0}{L-1} b_k x[n-k] + \sum_{m=1}{M-1} a_m y[n-m] Blockdiagramm siehe IIR-Foliensatz ab Seite 10 9 -- Welche Bedeutung hat die Impulsantwort für die Analyse von diskreten Filtern? Die Impulsantwort ist das Ausgangssignal eines Systems, bei dem am Eingang ein Dirac-Impuls zugeführt wird. Mit Hilfe dieser lässt sich ein LTI-System vollständig charakterisisieren (z.B. Bestimmung von Übertragungsfunktion und Frequenzgang). Die Wirkung des Filters kann durch Faltung der Eingangsfolge mit der Impulsantwort im Zeitbereich bestimmt werden. Da jedes Eingangssignal als Überlagerung von gewichteten, zeitverzögerten Einheitsimpulsen dargestellt werden kann, können die entsprechenden Ausgangssignale von gewichteten und zeitverzögerten Versionen der Impulsantwort gebildet werden. 10 - Welche Bedeutung hat das Pol/Nullstellendiagramm? Aus einem Pol/Nullstellendiagramm kann unter anderem auf den Betrags- und Phasenverlauf eines Systems, sowie auf dessen Impuls- und Sprung- antwort geschlossen werden. Aus der Lage der Pole kann man unter anderem erkennen, ob ein System kausal oder stabil ist. Stabilität ist dann gegeben, wenn alle Pole in der offenen linken Halbebene des Diagramms liegen. Realisierbare (kausale) Systeme besitzen mehr Pole als Nullstellen. Weitere Bedeutung hat das Diagramm zum Bestimmen der Koeffizienten bei der Entwicklung von IIR-Filtern; bei dieser Methode werden die Pole und Nullstellen des Filters mit dem gewünschten Verhalten in dem Diagramm platziert und dann wird entsprechend fortgefahren. by wurm: Durch das PN-Diagramm ist die Systemfunktion H(z) eindeutig ermittelbar. Nullstellen auf dem Einheitskreis bedeuten, dass die zueghoerige Frequenzkomponente am Ausgang des Systems nicht auftritt, also vollstaendig unterdrueckt wird. Fuer stabile Systeme muessen die Polstellen im z-Bereich innerhalb des Einheitskreises liegen (zum Vergleich: bei zeit-kontinuierlichen Systemen gilt, dass die Pole in der linken offenen Halbebene des s-Bereiches liegen muessen). (fuer z-bereich: Das folgt aus der Analyse von Differenzengleichungen, siehe seite 13 ET-Text/IIR) 11 - Wie hängen Impulsantwort und Systemfunktion zusammen? Die Systemfunktion (auch Übertragungsfunktion genannt) H[z] ist die z-Transformierte der Impulsantwort h[n]. Zusammenhänge: Zeitbereich: y[n] = x[n] x h[n] (x = Faltungsoperator!) z-Bereich: H(z) = Y(z)/X(z) Y(z) = X(z) * H(z) (* = Multiplikationsoperator!) 12 - Schreiben Sie die DFT und die inverse DFT an. Wie berechnet man die inverse DFT mit Hilfe der DFT? DFT: X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2 \pi n}{N} k} iDFT: x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2 \pi k}{N} n} Die inverse DFT unterscheidet sich von der DFT lediglich durch den Faktor 1/N und das negative Vorzeichen. Ausgehend von der Formel für die iDFT kann man beide Seiten konjugiert komplex machen, wodurch sich die gleiche Formel wie für die DFT ergibt, nur dass noch ein Faktor von 1/N davorsteht und die einzelnen Werte X[k] jeweils konjugiert komplex sein müssen! x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2 \pi k}{N} n} x[n]* = (\frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2 \pi k}{N} n})* = \frac{1}{N} \sum_{k=0}^{N-1} X[k]* e^{-j\frac{2 \pi k}{N} n} [konjugiert komplexen Operator nochmal auf beiden Seiten anwenden] x[n] = (\frac{1}{N} \sub_{k=0}^{N-1} X[k]* e^{-j\frac{2 \pi k}{N} n)* Also folgende Vorgehensweise um mit DFT iDFT zu berechnen: 1. Eingangsfolge komplex konjugieren 2. DFT auf diese modifizierte Folge anwenden 3. Ausgangsfolge mit 1/N skalieren 4. Ausgangsfolge nochmals komplex konjugieren Das komplex konjugieren kann bei reellen Zeitfolgen entfallen! 13 - Wodurch entsteht der Leck-Effekt bei der DFT? Wie können seine Auswirkungen beeinflusst werden und welche Vor- und Nachteile treten dabei auf?