Fast Fourier Transform (FFT) (Part 1)
Due to the huge popularity of the PlainFFT library along with the complementary PlainADC (Data acquisition library), I merged both libraries in the PlainDSP library for sake of efficiency and comfort of use. All the principles described in early posts which relate to the Fast Fourier Transform remain valid and I strongly suggest to the people who are not feeling comfortable with advanced math to carefully read the series of post dedicated to FFT (starting here) and data acquisition.
Conceptually speaking FFT is pretty simple. Practically, FFT is tough! So that I will not go into all the details of this algorithm and I will stay focused on its use and applications. This series of posts will end up with a fully featured library that you will able to use for all sorts of applications, without bothering about the maths.
The plot on an oscilloscope shows a wave which is made of samples which are characterized by their intensities (Ordinates) and their sampling time (Abscissa). We are in the time domain.
The simpler the signal (e.g. a single sine wave), the simpler the characterization. The Fourier Transform proposes to decompose any signal into a sum of sin and cos. To each data point from the FFT power spectrum corresponds a magnitude (Ordinates) and a frequency (Abscissa). We are now in the frequency domain.
The more complex the signal (e.g. signal + harmonics + noise)…
… the more complex the characterization.
And guess what? The FFT algorithm can be executed in reverse mode, so that starting from a FFT you can rebuild a real life signal. We may study later how this property can be used to denoise signals.
Check the following links for a global explanation, and a more detailed information related to the algorithm itself. They are many papers dedicated to FFT, and you may also like to learn by doing, using this applet, or this very nice one.
FFT applies to vectors containing n samples, where n must be a power of 2. Executing the algorithm on this data may lead to unexpected results. The reason being that the vector truncates the signal information and may contain incompletely described waves (e.g. low frequency waves). This side effect may be corrected by weighing the signal, giving less importance to the leading and tailing data. This is the windowing function. The weighing function in the windowing depends upon the type of signal to be analysed:
- Transients whose duration is shorter than the length of the window : Rectangular (Box car)
- Transients whose duration is longer than the length of the window : Exponential, Hann
- General-purpose applications : Hann
- Spectral analysis (frequency-response measurements) : Hann (for random excitation), Rectangular (for pseudorandom excitation)
- Separation of two tones with frequencies very close to each other but with widely differing amplitudes : Kaiser-Bessel
- Separation of two tones with frequencies very close to each other but with almost equal amplitudes : Rectangular
- Accurate single-tone amplitude measurements : Flat top
- Sine wave or combination of sine waves : Hann
- Sine wave and amplitude accuracy is important : Flat top
- Narrowband random signal (vibration data) : Hann
- Broadband random (white noise) : Uniform
- Closely spaced sine waves : Uniform, Hamming
- Excitation signals (hammer blow) : Force
- Response signals : Exponential
- Unknown content : Hann
Once the windowing is executed, you can run the FFT. The result of this algorithm lies in to vectors containing the real and imaginary computed values. You need then to apply some math to convert them into a vector of intensities.
Window type Rectangle (box car)
Window type Hamming:
Window type Flat top
All plots exported from my DSP tool box “Panorama”
Links of interest