15.9. Fast Fourier Transform (FFT)
From the mathematical expressions of DTFT, it is clear that for all the values of k, approximately N2 complex multiplications and N(N − 1) complex additions are required to be done. To reduce this computational complexity to about N(log2N) computations, efficient algorithm is used called Fast Fourier Transform (FFT) algorithm. This algorithm uses the periodicity and symmetry properties of complex number 
and thus reduces the computational complexity. The two main categories of FFT algorithms are as follows:
Decimation in time FFT algorithm
Decimation in frequency FFT algorithm
In MATLAB, for calculating DFT with ...
Get MATLAB® and Its Applications in Engineering: [Based on MATLAB 7.5 (R2007b)] now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
