Fast Fourier Transform (FFT)

Wie angekündigt, habe ich immer mal wieder an meinem Fouriertrafo-Projekt gearbeitet und bin am Anfang des zweiten Levels, der schnellen Fouriertransformation, angekommen. Und mit schnell meine ich hier richtig, richtig schnell! Ich habe wieder das Testsignal vom letzten Mal ausgepackt, an das Programm verfüttert und die Rechenzeit gemessen: 2,426 Sekunden!! Um das nochmal klarer zu machen: Ich erhalte jetzt in 0,1% der Zeit, die ich vor zwei Wochen benötigt habe, das selbe Ergebnis:

Das ist doch mal ziemlich praktisch! Jetzt kann man endlich alle Vorteile der Fouriertransformation auch auf großen Datensätzen nutzen.

Demnächst erkläre ich nochmal genauer, wie die FFT so funktioniert. Im Moment nur soviel: Die Anzahl Datenpunkte N muss eine Zweierpotzen sein, weshalb ich das Eingangssignal von 58014 Punkten auf 65536 = 2^16 Punkte mit Nullen gefüllt habe. Dann kann man nämlich die zu berechnenden Summen so geschickt zerteilen, dass man anstelle von etwa N*N Multiplikationen bloß N*log2(N) Stück benötigt. Setzt man mal große N ein und vergleicht die beiden Werte, so sieht man schnell ein, weshalb sich das Verfahren »Schnelle Fouriertransformation« nennen darf.

Implementiert habe ich das Ganze zur Zeit auch nur rekursiv, da die Programmstruktur da einfacher zu verstehen ist. Deshalb sind die nächsten Level:
– Iterative Implementierung der FFT
– Zweidimensionale FFTs
– evtl. Radix4 oder Radix8 (N ist 4er oder 8er Potenz –> noch mehr Multiplikationen sparen)

Kategorie: Allgemein, Physik studieren 7 Kommentare »

7 Reaktionen zu “Fast Fourier Transform (FFT)”

  1. Markus Osterhoff

    schön 🙂

  2. Julius

    Ja das Thema ist im Semester ein wenig eingeschlafen…
    aber vll mache ich demnächst mal weiter;)

    Die Theorie dahinter ist wirklich nicht so schwer, die Implementierung der iterativen Methode hab ich irgendwie noch nicht so recht geschafft (ich hab aber auch nicht extrem lange dran gearbeitet).

    gruß
    julius

Zur Werkzeugleiste springen