Fourier Transform DFT, FFT

[Dipl Phys Ernst Winter]

Diskrete Fourier Transformation DFT
Eine periodische Funktion der normierten Periode 2Pi sei mit n = 2q äquidistanten Stützstellen f(xi) i = 0..n-1 im Intervall 0..2Pi gegeben. Stützstellenabstand dx = 2Pi/n, x0 = 0, xn-1 = 2Pi - dx.

Delphi-Quellcode:

Wir interpolieren sie mit:
            q - 1 
f(x) = a0 + Summe (ai*cos(mx) + bi*sin(mx)) + aq*cos(qx) 
             m =1
wobei wir b(q) = 0 setzen, um die Zahl der Parameter an die Zahl der Stützstellen anzupassen.
Brechen wir die Summe mit weniger Gliedern ab, so erhalten wir eine Approximation mit minimalem quadratischen Fehler. Für die n + 1 Koeffizienten ergibt sich

         n - 1 
a0 = 1/n Summe yk
         k = 0

         n - 1 
ai = 2/n Summe yk*cos(i*xk)         i = 1, 2,..., q-1
         k = 0

         n - 1 
bi = 2/n Summe yk*sin(i*xk)         i = 1, 2,..., q-1
         k = 0

         n - 1 
aq = 1/n Summe yk*cos(q*xk)         
         k = 0

FFT Fast Fourier Transform
Die Rechenzeiten der DFT wachsen mit Stützstellenzahl N quadratisch an: t ~ N^2. Es wurden verschiedene Verfahren zur schnellen Fourier-Transformation FFT entwickelt, deren die Rechenzeit nur mit t ~ Ln(N)*N anwächst.
Sie beruhen alle auf der sukzessiven Zerlegung einer Transformation mit n Stützstellen in zwei Transformationen mit n/2 Stützstellen.

Das Demo zur DFT zeigt den Aufbau der Näherungen aus den Oberwellen graphisch an.

FFT-Demo1 demonstriert den Zeitgewinn der FFT gegenüber der DFT. Vorsicht: Die DFT kann bei großem nMax sehr lange dauern. Es enthält eine Implementation der FFT nach dem Tukey-Algorithmus.

Das Demo2 zur FFT enthält eine Implementation der FFT die reelle Werte wahlweise in der Frequenzbereich bzw. von dort wieder zurück in die Zeitdarstellung transformatiert.

[R2009]

Hi Sirius,

ich bin nur ein Ingenieur für allgemeine E-Technik, hab also von FFT und der entsprechenden Mathematik nicht sehr viel Ahnung.
Eine FFT mach ich doch um ein Amplituden-Spektrum zu bekommen.
Ziel meiner FFT ist es also die Amplitudenwerte für einzelne Frequenzen zu erhalten.
Bei meiner Implementation der FFT ist das auf jeden Fall so. (Hab ich nicht selbst gemacht und somit auch nicht komplett verstanden).

Grüsse
Rainer