# 18.4.1 Fast Fourier Transform (FFT)

A discrete Fourier transform (DFT) converts a signal in the time domain into its counterpart in frequency domain. Let ($x_i$) be a sequence of length N, then its DFT is the sequence ($F_n$) given by

$F_n=\sum_{i=0}^{N-1}x_ie^{-\frac{2\pi j}{N}ni}$

A fast Fourier transform (FFT) is an efficient way to compute the DFT. By using FFT instead of DFT, the computational complexity can be reduced from O($n^2$) to O(n log n). Note that the input signal of the FFT in Origin can be complex and of any size.

The result of the FFT contains the frequency data and the complex transformed result. Meanwhile, it can also provide the magnitude, amplitude, phase, power density, and other computation results. The power density estimation can be made by three different methods:MSA, SSA, and TISA. Furthermore, both two-sided and one-sided powers can be computed.

When the FFT is used, attention should be paid to leakage, which is caused by the FFT's assumption that the input signal repeats periodically and that the periodic length is equal to the length of the actual input. However, if the true signal is not periodic or if the assumed periodic length is not correct, leakage will occur. This will cause both the amplitude and position of a frequency measurement to be inaccurate. Origin supports the use of window functions to mitigate leakage. Several window functions are supported, including Triangular, Rectangle, Bartlett, Welch, Hanning, Hamming, and Blackman, each of which has its own unique advantages and disadvantages. A specific window function should be selected according to the kind of signals being analyzed.

##### To Use FFT Tool
1. Make a workbook or a graph active.
2. Select Analysis: Signal Processing: FFT: FFT from the Origin menu.
 Topics covered in this section: