Fast Fourier Transform (FFT) (Part 1)
The huge popularity of PlainDSP (merge of PlainFFT and PlainADC libraries) and the numerous requests for help drove me to think about a convenient solution for all designers, artists, students, professors, R&D people, prototypists who need to understand, experiment, create systems which feature advanced Digital Signal Processing on Arduino. The result of intense thoughts, design and writing is the collection of PlainDSP kits, starting with the audio kit.
So please, pay a visit to plaindsp web site. By getting one of these kits you not only get a desirable product but you also support a private initiative for popularizing science. Thank you.
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