# 18.4.2.2 Algorithms (IFFT)

IFFT is a fast algorithm to perform inverse (or backward) Fourier transform (IDFT), which undoes the process of DFT. IDFT of a sequence { $F_n$} that can be defined as: $x_i=\frac{1}{N}\sum _{n=0}^{N-1}F_ne^{\frac{2\pi j}{N}ni}$

FFT and inverse FFT operations in Origin are carried out using the FFTW library. In FFTW, the computation of FFT is performed by an executor that is comprised of blocks of C code called "codelets". Each codelet specializes in one part of the transformation. With these codelets, the executor implements the Cooley-Turkey FFT algorithm, which factors the size of the input signal (denoted by N) into $N_1$ and $N_2$. By recursive factoring, the signal is broken into shorter parts. The results of the transforms of the short parts are multiplied; and finally the transform of the original signal is computed. More information on FFTW is available at http://fftw.org/.

For the details of the automatic computation of the sampling interval, please refer to the algorithm of the FFT tool.

Windows

Windows are used to suppress leakage. Different types of windows are defined as follows in Origin.

Rectangular Window: $w[n]=1\,\!$ for $0\leq n\leq N-1$ and zero otherwise.

Welch Window: $w[n]=1-\left( \frac{n-\frac 12(N-1)}{\frac 12(N+1)}\right) ^2$

Triangular Window: $w(n)=\frac 2N(\frac N2-|n-\frac N2|)$

Bartlett Window: $w(n)=\frac 2{N-1}(\frac{N-1}2-|n-\frac{N-1}2|)$

Hanning Window: $w[n]=\frac 12[1-\cos (\frac{2\pi n}{N-1})]$

Hamming Window: $w[n]=0.54-0.46\cos (\frac{2\pi n}{N-1})$

Blackman Window: $w[n]=0.42-0.5\cos (\frac{2\pi n}{N-1})+0.08\cos (\frac{4\pi n}{N-1})$