How does the FFT work, and what are its applications?
The Fourier transform of a signal produces an array/list of the strengths of frequencies in it. The Discrete Fourier Transform (DFT) is a mathematical tool that operates on a short window of a signal, so we know that in a particular time interval certain frequencies are present. The FFT (fast Fourier transform) is an algorithm to compute a discrete transform. It is very efficient and is the reason much of the real-time signal processing all around us exists today, from cell-phones to digital TV to effects boxes.
