Algorithmen (FFT)

IFFT ist ein schneller Algorithmus, um inverse (oder rückwärts gerichtete) Fourier-Transformation (IDFT) durchzuführen, die den Prozess der DFT rückgängig macht. Die IDFT einer Sequenz { $F_n$ } kann definiert werden als:

$x_i=\frac{1}{N}\sum _{n=0}^{N-1}F_ne^{\frac{2\pi j}{N}ni}$

Die Vorgänge der FFT und inversen FFT werden in Origin mit Hilfe der FFTW-Bibliothek ausgeführt. In FFTW wird die Berechnung der FFT von einem ausführenden Element durchgeführt, das aus C-Code-Blöcken besteht, die so genannten "Codelets". Jedes Codelet ist für einen Teil der Transformation spezialisiert. Mit diesen Codelets implementiert das ausführende Element den FFT-Algorithmus nach Cooley-Turkey, der die Größe des Eingangssignals (bezeichnet als N) in $N_1$ und $N_2$ in Faktoren zerlegt. Durch rekursive Faktorzerlegung wird das Signal in kürzere Teile gebrochen. Die Ergebnisse der Transformationen der kurzen Teile werden multipliziert; schließlich wird die Transformation des ursprünglichen Signals berechnet. Weitere Informationen zu FFTW finden Sie unter http://fftw.org/.