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.
Zitat
Baum-Darstellung
