Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
Decimation in Time
Figure: Erster DIT-Schritt zur Zerlegung der DFT fur N = 8.
12 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
Figure: Zweiter DIT-Schritt zur Zerlegung der DFT; N = 8,W 2iN = W i
N/2
18 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere 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
21 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere 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.
22 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere Optimierung
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere 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].
24 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere 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.
25 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere 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!
26 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere 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.
27 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
PrinzipWeitere 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
28 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
Andere Realisierungen
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
Andere Realisierungen
Andere Realisierungen
Figure: Rechenaufwand der Matlab-FFT als Funktion von N, aus [4].
37 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
Andere Realisierungen
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
KlausurVeranstaltungen des IKAAbschlussarbeiten und Stellen
Klausurrelevante Themen und Fragen
Vorlesungsstoff 2018/2019
Ubungsaufgaben 2018/2019
Matlab-Ubungen 2018/2019
40 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
KlausurVeranstaltungen des IKAAbschlussarbeiten und Stellen
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
KlausurVeranstaltungen des IKAAbschlussarbeiten und Stellen
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
KlausurVeranstaltungen des IKAAbschlussarbeiten und Stellen
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
KlausurVeranstaltungen des IKAAbschlussarbeiten und Stellen
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
KlausurVeranstaltungen des IKAAbschlussarbeiten und Stellen
Vielen Dank fur Ihre Aufmerksamkeit!
45 / 45
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
KlausurVeranstaltungen des IKAAbschlussarbeiten und Stellen
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
Schnelle Fouriertransformation (FFT)Inverse FFT (IFFT)
Spezialfalle (Noch schneller!)Und weiter?
KlausurVeranstaltungen des IKAAbschlussarbeiten und Stellen
4. Auflage, Berlin: Springer, 1994.
45 / 45