Digitale Signalverarbeitung, Vorlesung 12 - Schnelle ... · DIT-Zerlegungsstufen sind je N=2...

Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)

Spezialfalle (Noch schneller!)Und weiter?

Digitale Signalverarbeitung,Vorlesung 12 - Schnelle Fouriertransformation

(FFT)

Arbeitsgruppe Digitale Signalverarbeitung

28. Januar 2019

Siehe Skript “Digitale Signalverarbeitung”, Abschnitt 10.2

1 / 45



PrinzipWeitere Optimierung

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.

3 / 45




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).

4 / 45




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.

5 / 45




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.

6 / 45




Zwei alternative Wege zur FFT

Es existieren zwei Zerlegungsstrategien:

Reduktion im Zeitbereich (DIT: Decimation in Time) -Strategie der heutigen VL.

Reduktion im Frequenzbereich (DIF: Decimation inFrequency).

Beide Methoden folgen dem Divide-and-Conquer-Prinzip, eine imZeit-, die andere im Frequenzbereich.

7 / 45




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.

8 / 45




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)

9 / 45




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)

10 / 45




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.

11 / 45




Decimation in Time

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

12 / 45




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

13 / 45




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.

14 / 45




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.

15 / 45




Zweite Stufe

Fur 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

)ln16 / 45




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:

17 / 45




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

N/2

18 / 45




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.

19 / 45




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.

20 / 45




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

21 / 45




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.

22 / 45




Komplette Radix-2-FFT

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

23 / 45




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].

24 / 45




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.

25 / 45




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!

26 / 45




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.

27 / 45




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

28 / 45



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.

30 / 45



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!

31 / 45



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)

32 / 45



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.

33 / 45



Inverse FFT mittels “normaler” FFT

Blockdiagramm zu

1 Vertauschung von Realteil und Imaginarteil

2 FFT

3 erneute Vertauschung von Real- und Imaginarteil im Ergebnis

34 / 45



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].

36 / 45





Figure: Rechenaufwand der Matlab-FFT als Funktion von N, aus [4].

37 / 45




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.

38 / 45



KlausurVeranstaltungen des IKAAbschlussarbeiten und Stellen

Klausurrelevante Themen und Fragen

Vorlesungsstoff 2018/2019

Ubungsaufgaben 2018/2019

Matlab-Ubungen 2018/2019

40 / 45




Termin

Schriftliche Prufung 28.02.2019, 8:30.

Dauer 120minRaum HGD 30

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

41 / 45




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)

42 / 45




Weiterfuhrende Lehrveranstaltungen

Sommersemester 2019:

Grundlagen der automatischen Spracherkennung

Master-Projekt DSP

Master-Seminar Sprach- und Mustererkennung

Wintersemester 2019/20:

Master-Seminar Kognitive Signalverarbeitung

43 / 45




Abschlussarbeiten und Stellen

BSc- und MSc-Arbeiten, WHK-StellenAktuelle Beispielthemen:

IT-Sicherheit in maschinellen Lernsystemen, z.B. in derautomatischen Spracherkennung

Mensch-Roboter-Interaktion (NAO):

Oft Praktika, z.B. in Kooperation mit Honda Research, Offenbach- siehe Aushange - und Promotionsstellen.

44 / 45




Vielen Dank fur Ihre Aufmerksamkeit!

45 / 45




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.Digitale Signalverarbeitung, volume 1.

45 / 45




4. Auflage, Berlin: Springer, 1994.

45 / 45

Date post:	21-Nov-2019
Category:	Documents
Upload:	others
View:	1 times
Download:	0 times

Digitale Signalverarbeitung, Vorlesung 12 - Schnelle ... · DIT-Zerlegungsstufen sind je N=2...

Documents