The FFT (Fast Fourier Transform) is rightfully regarded as the most important numerical algorithm of our lifetime . Whether it's used to monitor signals coming from the depths of the earth or search for heavenly life forms, the algorithm is widely used in all scientific and engineering fields. But,what exactly is an FFT? Why does it matter in signal-processing projects?
Named after the late 18th century French mathematician Jean-Baptiste Joseph Fourier, the Fourier Transform is a mathematical operation that converts a signal from the time (spatial) domain to the frequency domain. According to Fourier theorem, a signal is a composition of a number of sinusoidal functions with given amplitude, frequency, and phase. The Fourier series equation formulates the theorem for a periodic signal, x(t):
In these equations, P stands for the signal's period and Cn is called the Fourier coefficients of the signal x(t). The coefficients are calculated by:
For a sine wave, there is only one coefficient. If, however, the signal contains an infinite number of frequencies, such as is the case for an ideal square wave, a finite N results in an error. Figures 1 and 2 compare the original signal with its representation based on Fourier series coefficients for N=3 (green signal) and N=15 (blue signal.) As we can see, the accuracy of the transformation depends on the nature of the signal and the number of terms in the series.
Figure 1. An ideal square wave function.
Figure 2. The Fourier series reconstruction of the square wave for N=3 and N=15. Plot calculated by: https://www.desmos.com/calculator.
Most signals, however, aren't periodic. Nonperiodic signals don't have a Fourier series. This fact greatly disappointed Fourier, who needed almost 20 years to develop a general formula that would work for any function. Now, any signal could be transformed from the time domain to the frequency domain by the following equation:
[Note that O is discrete frequency.]
This equation is much