Algorithmus (FFT2)

Aufgrund der Trennbarkeit der 2D-DFT kann ihre Definition wie folgt neu geschrieben werden:

F(u,v) = \frac{1}{{MN}}\sum_{x = 0}^{M-1} {\sum_{y = 0}^{N-1} {f(x,y)} } e^{ - i2\pi(ux/M + vy/N)} 
 = \frac{1}{M}\sum_{x = 0}^{M - 1} {e^{ - i2\pi xu/M} } (\frac{1}{N}\sum_{y = 0}^{N - 1} {f(x,y)e^{ - i2\pi yv/N} })

Dies zeigt, dass eine 2D-FFT in eine Reihe von 1D-Fourier-Transformationen heruntergebrochen werden kann. Zum Berechnen einer 2D-FFT wird eine 1D-Fourier-Transformation auf jede einzelne Zeile der Eingabematrix angewendet und dann auf jede einzelne Spalte.

Origin verwendet die FFTW-Bibliothek für den Code der Fast-Fourier-Transformation.