The Fast Fourier Transform explained (#000)
Channel: Digital Signal Processing
Date: 2013-10-15

The Fast Fourier Transform uses a simple trick: divide the time series in odd/even sequences and perform DFTs on them. Then repeat this until we have two point DFTs which are just X(0) = x(0) + x(1), X(1) = x(0) - x(1). Then recombine the results and we have computed the DFT much quicker.