Digitale Signalverarbeitung, Vorlesung 12 - Schnelle ... · Kombiniert man alle bisher diskutierten DIT-Zerlegungsschritte mit den optimierten Butter ies, dann erh alt man den Radix-2

Schnelle Fouriertransformation (FFT) Inverse FFT (IFFT) Spezialfalle (Noch schneller!) Und weiter?

Digitale Signalverarbeitung,Vorlesung 12 - Schnelle Fouriertransformation

(FFT)

Arbeitsgruppe Digitale Signalverarbeitung

8. Februar 2016

Siehe Skript “Digitale Signalverarbeitung”, Abschnitt 10.2


Digitale Signalverarbeitung, Vorlesung 12 - Schnelle Fouriertransformation (FFT)


Motivation und Anwendungen:

Schnelle DFT-Berechnung ist wichtig fur

Schnelle Faltung zur Filterung (z.B. Bildverarbeitung:Kantenscharfung, Rauschbefreiung)Spektralanalyse von Signalen (z.B. Musikanalyse)Quellencodierung (z.B. MP3)Nachrichtenubertragung (z.B. OFDM (Orthogonal FrequencyDivision Multiplexing), benutzt u.A. fur ADSL (AsymmetricDigital Subscriber Line))Mustererkennung (z.B. Spracherkennung, Bilderkennung)

Aufwand der DFT kann von O(N2) auf O(N log2N) reduziertwerden.




Aufwand der DFT

Das DFT-Spektrums eines komplexwertigen Signalvektors mit denElementen v (k) , k = 0, . . . ,N − 1, erhalt man aus

V = WNv. (1)

Dabei ist die Matrix WN elementweise mit der Zeilennummer lund der Spaltennummer m definiert:

[WN ]lm = W lmN ; l ,m = 0, 1, 2, . . . ,N − 1. (2)

Diese Berechnung erfordert genau N2 komplexe (4N2 reelle)Multiplikationen und N (N − 1) komplexe (2N (N − 1) reelle)Additionen (ohne Berucksichtigung der Einsen in der ersten Zeileund Spalte der DFT-Matrix).




Verbesserungspotential

Weil WN symmetrisch ist, und ein paar weitere nutzlicheEigenschaften besitzt, enthalt die Berechnung der DFTRedundanzen.

Durch Elimination dieser Redundanz kann der Rechenaufwandmerklich verringert werden.

Ziel ist eine maximal effiziente Berechnung mit moglichstgroßer Elimination der Redundanz – die Fast FourierTransform (FFT) ist ein Verfahren, das genau das leistet.




Prinzip

Die Vorgehensweise der FFT besteht darin, die DFT-Matrix(2) in moglichst kleine Teil-DFT-Matrizen zu zerlegen.

Dafur ist die Faktorisierbarkeit der Dimension N (Lange derDFT) die Voraussetzung.

Das hochste Einsparpotenzial ergibt sich fur

N = 2I =I∏

i=1

2, I ∈ N. (3)

Wenn N in seine I Primfaktoren (alle vom Wert 2) zerlegtwird, bezeichnet man den resultierenden Algorithmus alsRadix-2 FFT.




Prinzip

Wegen der Voraussetzung (3) ist sowohl N als auch jederTeil-(Prim-)Faktor eine gerade Zahl. Damit ist es moglich, dieEingangsfolge v (k) , k = 0, . . . ,N − 1, folgendermaßen in zweiverschachtelte Folgen der jeweils halben Lange N/2 zu zerlegen:

v1 (k) = v (2k) , k = 0, . . . ,N/2− 1, (4)

v2 (k) = v (2k + 1) , k = 0, . . . ,N/2− 1. (5)

Da in jeder der beiden Teilfolgen jeder zweite Wert eliminiert ist,kann man diesen Zerlegungsvorgang als Reduktion derAbtastfrequenz um den Faktor zwei interpretieren [1], was dieBezeichnung Decimation in Time erklart.




Prinzip

Die DFT kann jetzt aus den beiden Teilfolgen (4) und (5)bestimmt werden:

V (n) =N−1∑k=0

v (k)W knN

=

N/2−1∑k=0

v (2k)W 2knN +

N/2−1∑k=0

v (2k + 1)W(2k+1)nN

=

N/2−1∑k=0

v1 (k)(W 2

N

)kn+ W n

N

N/2−1∑k=0

v2 (k)(W 2

N

)kn, (6)

wobei n = 0, . . . ,N − 1. Es gilt auch:

W 2N =

(e−j

2πN

)2= e−j2

2πN = e

−j 2πN/2 = WN/2. (7)




Prinzip

Deswegen lasst sich

V (n) =

N/2−1∑k=0

v1 (k)(W 2

N

)kn+ W n

N

N/2−1∑k=0

v2 (k)(W 2

N

)kn(8)

wie folgt umformen:

V (n) =

N/2−1∑k=0

v1 (k)W knN/2 + W n

N

N/2−1∑k=0

v2 (k)W knN/2. (9)




Prinzip

Wie man sieht, reprasentieren die beiden Summenterme die DFTender beiden Teilfolgen v1 (k) und v2 (k):

V i (n) =

N/2−1∑k=0

v i (k)W knN/2, i = 1, 2, n = 0, . . . ,

N

2− 1. (10)

Deshalb kann (9) auch einfacher dargestellt werden:

V (n) = V 1

((n)N/2

)+W n

NV 2

((n)N/2

), n = 0, . . . ,N − 1. (11)

Die Schreibweise V i

((n)N/2

)soll andeuten, dass die beiden

Teilfolgen-DFTs jeweils periodisch mit N/2 sind.




Prinzip

Decimation in Time

Figure : Erster DIT-Schritt zur Zerlegung der DFT fur N = 8.




Prinzip

Ergebnis der ersten Zerlegung

Durch diesen ersten Zerlegungsschritt wurde die N-Punkte DFT inzwei N/2-Punkte DFTen zerlegt, deren Ergebnisse durch einigeZusatzoperationen verknupft werden. Daraus ergibt sich die in derTabelle zusammengestellte Aufwandsverringerung:

N-DFT 2× N/2-DFT

Multipl. Add. Multipl. Add.

Allgemein N2 N (N − 1) 2(N2

)2+ N 2N

2

(N2 − 1

)+ N

N = 8 64 56 40 32

N = 210 220 220 − 210 219 + 210 219

≈ 106 ≈ 106 ≈ 12106 ≈ 1

2106




Prinzip

Ergebnis der ersten Zerlegung

Die beiden Zahlenbeispiele zeigen, dass bei genugend großerLange N der DFT der Rechenaufwand etwa auf die Halftevermindert wird.

Diese Abhangigkeit der Aufwandseinsparung von N istdadurch bedingt, dass die N Zusatzoperationen zurVerknupfung der beiden DFT-Ergebnisse mit wachsendem Nimmer weniger ins Gewicht fallen.




Prinzip

Zweite Stufe

Momentan betrachten wir nur Folgen der Lange N = 2I .

Deswegen konnen wir die beiden Teil-DFTs der halben LangeN/2 auf genau dieselbe Weisen wieder halbieren, und sie mitHilfe von zwei N/4-DFTs schneller berechnen.




Prinzip

Zweite StufeFur die zweite Zerlegung berechnet man also in

V (n) = V 1

((n)N/2

)+ W n

NV 2

((n)N/2

)(12)

einerseits

V 1(n) =

N/2−1∑k=0

v1 (k)(WN/2

)kn=

N/4−1∑l=0

v1 (2l)(WN/2

)2ln+

N/4−1∑l=0

v1 (2l + 1)(WN/2

)(2l+1)n

=

N/4−1∑l=0

v1 (2l)(WN/4

)ln+(WN/2

)n N/4−1∑l=0

v1 (2l + 1)(WN/4

)lnArbeitsgruppe Digitale Signalverarbeitung



Prinzip

Zweite Stufe

Fur die zweite Zerlegung berechnet man also in

V (n) = V 1

((n)N/2

)+ W n

NV 2

((n)N/2

)(13)

andererseits

V 2(n) =

N/2−1∑k=0

v2 (k)(WN/2

)kn=

N/4−1∑l=0

v2 (2l)(WN/4

)ln+(WN/2

)n N/4−1∑l=0

v2 (2l + 1)(WN/4

)lnum so auf die folgende Struktur zu kommen:




Prinzip

Figure : Zweiter DIT-Schritt zur Zerlegung der DFT;N = 8,W 2i

N = W iN/2




Prinzip

Die Zerlegung der Sequenz in ihre Halften wird solange fortgesetzt,bis von der DFT-Stufe nur noch Transformationen von 2Datenpunkten auszufuhren sind. Das ist fur N = 8 im drittenZerlegungsschritt der Fall.Eine 2-Punkt DFT braucht wegen

V (0) = v (0) + W 02 v (1) = v (0) + W 0

Nv (1) = v (0) + v (1) (14)

und

V (1) = v (0)+W 12 v (1) = v (0)+W

N/2N v (1) = v (0)−v (1) (15)

keine Multiplikation, sondern nur zwei komplexe Additionen.




Prinzip

2-Punkte DFT

Hier ist der letzte Zerlegungsschritt der Radix-2-FFT:

Figure : (a) Blockdiagramm (b) Signalflussgraf. W 12 = W

N/2N = −1. Da

dieser Signalflussgraf an einen Schmetterling erinnert, wird diese Strukturals Butterfly bezeichnet.




Weitere Optimierung

Optimierung

Und ein bisschen mehr lasst sich auch noch machen...

Figure : Butterfly als Element des FFT-Algorithmus (a) ursprungliche,(b) optimierte, effiziente Form;

Wi+N/2N = W i

NWN/2N = −W i

N , i = 0, . . . ,N/2− 1




Weitere Optimierung

Optimierung

Eine genauere Analyse des Signalflussgrafen fur Schritt 1 und2 zeigt, dass der Graph ausschließlich aus Butterfliesaufgebaut ist, die die auf der vorigen Seite in (a) dargestellteForm aufweisen.

Wie Teil (b) zeigt, braucht man fur eine effiziente Realisierungdieses allgemeinen Butterfly’s nur eine komplexeMultiplikation mit dem Drehfaktor (twiddle factor)W i

N , i = 0, . . . ,N/2− 1, und zwei komplexe Additionen.




Weitere Optimierung

Komplette Radix-2-FFTKombiniert man alle bisher diskutierten DIT-Zerlegungsschritte mitden optimierten Butterflies, dann erhalt man den Radix-2FFT-Algorithmus, der hier fur N = 8 gezeigt ist:




Weitere Optimierung

Komplette Radix-2-FFT

Der FFT-Signalflussgraf hat also eine sehr regelmaßigeStruktur mit ld N (= 3) kaskadierten Stufen.

Die N-dimensionalen Signalvektoren werden von Stufe zuStufe sequenziell weitergegebenen und parallel verarbeitet.

Damit ist es moglich, dass die N Ausgangswerte einer Stufe indie N Speicher abgelegt werden konnen, in denen ursprunglichdie N Eingangswerte der Stufe zwischengespeichert waren.Das bezeichnet man als in-place-Eigenschaft [2].




Weitere Optimierung

Rechenaufwand

Multiplikation Die N/2 vielen 2-Punkte DFTen benotigen amEingang keine Multiplikation.In den restlichen ld N − 1 = ld N/2DIT-Zerlegungsstufen sind je N/2 komplexeMultiplikationen notig. (Zur Vereinfachung derAnalyse wird der twiddle factor W 0

N zu denkomplexen Multiplikation gezahlt.)

Addition In jeder der ld N Stufen findet fur jedes der NErgebnisse eine Addition statt.




Weitere Optimierung

N-DFT Radix-2 N-FFT

Multipl. Add. Multipl. Add.

Allgemein N2 N (N − 1) (N/2) ld (N/2) N ld N

N = 8 64 56 8 24

N = 210 220 220 − 210 9 · 29 10 · 210≈ 106 ≈ 106 ≈ 1

2104 ≈ 104

Table : Vergleich des Rechenaufwands von DFT und Radix-2-FFT:komplexe Multiplikationen und Additionen

Wie man sieht benotigt die vollstandige Berechnung einer1024-Punkte FFT nur etwa 1% des Rechenaufwands einerentsprechenden DFT bzw. der Rechenzeit bei sequenziellarbeitenden Prozessoren!




Weitere Optimierung

Es gibt auch Nachteile...

Bei dem Radix-2 FFT-Algorithmus ist die Reihenfolge derElemente des Eingangsvektors durch die fortgesetzte Umsortierungnach geraden und ungeraden Indizes verandert.Die Elemente v (k) des Eingangsvektors mussen deswegen in,,bitreverser“ Reihenfolge eingespeist werden.Diese Anordnung kann man relativ leicht dadurch bekommen, dassman die Binaradressen der Elemente umkehrt, wie in der nachstenTabelle gezeigt wird. Auch diese relativ elegante Umsortierungerfordert aber zusatzlichen Aufwand.




Weitere Optimierung

Bitreverse Adressierung

Vektorindex k Binar bitreversal DIT-FFT-Index k ′

0 000 000 0

1 001 100 4

2 010 010 2

3 011 110 6

4 100 001 1

5 101 101 5

6 110 011 3

7 111 111 7

Table : Umsortierung der Elemente v (k) , k = 0, . . . ,N − 1, desEingangsvektors fur die DIT-FFT durch bitreversal




IFFT

Der Vergleich von

V (n) = DFT {v(k)} =N−1∑k=0

v(k)W knN , (16)

und

v(k) = IDFT {V (n)} =1

N

N−1∑n=0

V (n)W−knN . (17)

zeigt zwei Unterschiede zwischen DFT und IDFT:

Die Drehfaktoren W±nkN haben im Exponenten umgekehrte

Vorzeichen.

Die IDFT ist mit dem Faktor 1/N skaliert.




IFFT

Wegen dieser großen Ahnlichkeit kann die IDFT mitvernachlassigbarem Zusatzaufwand direkt mit der DFTausgefuhrt werden. Dies ist wichtig, weil man so fur die IDFTdie vielen effizienten FFT-Algorithmen verwenden kann [2],von denen wir hier nur einen Radix-2 Algorithmus (DIT)betrachtet haben.

Im Signalprozessor kann man fur DFT und IDFT dasselbeProgramm verwenden, im ASIC dasselbeHardware-Subsystem!




Fur die unskalierte inverse DFT gilt mit (17) und −j2 = 1:

N · v (k) = N · IDFT {V (n)} = −j2N−1∑n=0

V (n)W−knN

= j

[N−1∑n=0

[−jV (n)]W−knN

]∗∗= j

[N−1∑n=0

[jV ∗ (n)]W+knN

]∗.

Es folgt in Operatorschreibweise:

N · IDFT {V (n)} = j [DFT {jV ∗ (n)}]∗ . (18)




N · IDFT {V (n)} = j [DFT {jV ∗ (n)}]∗ (19)

Die in (19) zweimal auszufuhrende Operation

jA∗ = j (AR − jAI) = AI + jAR (20)

erfordert nur die Vertauschung von Real- und Imaginarteil. Nachdiesem Verfahren ist also

1 beim ruckzutransformierenden Linienspektrum V (n) Realteilund Imaginarteil zu vertauschen,

2 von dem so modifizierten Spektrum die FFT zu berechnen und

3 beim Ergebnis wieder Real- und Imaginarteil zu vertauschen.




Inverse FFT mittels “normaler” FFT

Blockdiagramm zu

1 Vertauschung von Realteil und Imaginarteil

2 FFT

3 erneute Vertauschung von Real- und Imaginarteil im Ergebnis




Andere Realisierungen


Zusatzlich zu den Radix-2 FFT-Algorithmen gibt es viele weitereFFT-Algorithmen.

Das Ziel, die Anzahl der komplexen Multiplikationen zuvermindern, wird immer durch die Zerlegung der Lange N inPrimfaktoren oder andere geeignete ganze Zahlen erreicht.

Beispielsweise gibt es effiziente Radix-I Algorithmen mitI ∈ [2, 3, 4, 5, 8, 16] oder auch mixed-radix Verfahren, beidenen N in unterschiedliche (Prim-)Faktoren zerlegt wird.

Erklarungen zu diesen Verfahren gibt es unter anderem in[2, 3, 4, 5].





Lernziele

Sie sollten den Decimation-in-Time-Algorithmus der Radix-2FFT verstehen.

den Rechenaufwand einer direkt implementierten DFT (ohnestrukturelle Optimierungen) und einer Radix-2-FFTbestimmen konnen,

und mit Hilfe einer FFT-Implementierung auch die IFFTausfuhren konnen.




Klausur

Klausurrelevante Themen und Fragen

Vorlesungsstoff 2016/2017

Ubungsaufgaben 2016/2017

Matlab-Ubungen 2016/2017




Klausur

Termin

Schriftliche Prufung 9.3.2017, 16:30.

Dauer 120minRaum HZO 30

Die Extrapunkte aus den Moodle-Aufgaben werden nur in dieserPrufung gewertet.




Klausur

Erlaubte Hilfsmittel

Taschenrechner (nicht programmierbar!)

1 DIN-A4-Blatt, selbst doppelseitig beschrieben, nicht kopiert,nicht gedruckt

Stifte (nicht Rot, keine Wertung von Abgaben in Bleistift)




Veranstaltungen des IKA

Weiterfuhrende Lehrveranstaltungen

Sommersemester 2017:

Grundlagen der automatischen Spracherkennung

Master-Projekt DSP

Master-Seminar Sprach- und Mustererkennung

Wintersemester 2017/18:

Master-Seminar Kognitive Signalverarbeitung




Abschlussarbeiten

Abschlussarbeiten

BSc- und MSc-Arbeiten, Themen:

Audiovisuelle Sprecheridentifikation

Mensch-Roboter-Interaktion (NAO):

Oft Praktika, z.B. in Kooperation mit Honda Research, Offenbach- siehe Aushange - und (nicht nur) im kommenden Sommer wiederneue Promotionsstellen




Abschlussarbeiten

Vielen Dank fur Ihre Aufmerksamkeit!




Abschlussarbeiten

Heinz Gunther Gockler and Alexandra Groth.Multiratensysteme.Wilburgstetten: Schlembach Fachverlag, 2004.

Karl Dirk Kammeyer and Kristian Kroschel.Digitale Signalverarbeitung.5. Auflage, Stuttgart: Teubner, 2002.

S. K. Mitra and J. F. Kaiser.Handbook for Digital Signal Processing.New York: John Wiley & Sons, 1993.

Alan V. Oppenheim and Ronald W. Schafer.Discrete-Time Signal Processing.Englewood-Cliffs: Prentice-Hall, 1989.

Hans Wilhelm Schußler.




Abschlussarbeiten

Digitale Signalverarbeitung, volume 1.4. Auflage, Berlin: Springer, 1994.



Documents

Digitale Signalverarbeitung, Vorlesung 12 - Schnelle ... · Kombiniert man alle bisher diskutierten DIT-Zerlegungsschritte mit den optimierten Butter ies, dann erh alt man den Radix-2