Fast Fourier Transform (FFT) (Part 1)

Part 1234567891011

——————————————————————————

Important notice:

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.

plaindsp_audio_kit_s
Each kit contains a 120 pages guide to DSP, written in the spirit of arduinoos posts, containing many original illustrations and experiments that anyone can replay at home, at university or in his lab. Along with this book comes an original audio shield which reads and amplifies the lowest up to the loudest signals from various inputs. Ultimately the kit comes with an access code to the latest versions of plaindsp libraries. And we offer a web base support for all questions regarding the use of plaindsp kits.

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.

——————————————————————————

FFT

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

Next post on same subject

20 Comments

  1. John Boxall says:

    Howdy
    Thanks for that clear and simple explanation, I was never entirely sure about FFT until reading this. Thank you very much
    john

  2. baruchli says:

    Thank you for sharing your knowledge and for clear article.
    May I ask a dumb question? What may be use of FFT except noise filtering?

    May it be used, for example, for recognition of sound, like cellular telephone ring?

    Baruch.

    • Didier says:

      Sound analysis is probably one of the most exciting application for FFT: from filtering up to denoising. Detecting a ring bell from a noisy environment is definitely a good example, alike catching one frequency spectrum (Fundamlentals and harmonics) from an accelerometer signal.
      Any other ideas?

  3. baruchli says:

    I am still wondering if recognition of particular cell phone ring is possible in limitation of Arduiono memory? Can you suggest any ground theoretical article about recognition of 3-4 seconds harmony sound via FFS?

    Thank you in advance.

    Baruch

  4. Didier says:

    Picking one specific frequency is not so hard. Recognize an harmony (so as to say, a sequence of frequencies) may not be harder, except that, as you mentionned it, we may lack some memory space. This is definetly a nice challenging project!

  5. baruchli says:

    Thank you.

  6. Mihasi says:

    Great article!

    In your opinion, is it possible to make a good estimation of distance based on sound? My idea was to make a base station transmit a certain frequency that’s inaudible to the human ear, have sensors in different placed filter out this frequency and get it’s amplitude and then send this “Received Sound Strength” back to a computer to calculate their position (in the same way RSS is used for localization with WiFi). The more speaker stations there are, the better the estimation of course.

    Thanks,

    Daniel

  7. Didier says:

    Wind and noise (not to talk about air density changes) may affect the strengh and cleaness of the audio signal in between the emitter and receptor. On the other hand, if you plan to use your system in a closed and large enough room this may work. Emiiting at least three different frequencies may also help positionning the receiver… And filtering them may prevent sound mix (You may try FIR filtering instead a FFT)
    Why not finally…
    Does it help?

  8. Fenar123 says:

    Hello, man i wanna the library PlainFFT to work with your code, can you send it to my mail. Thanks

  9. saurabh says:

    Hi Didier,
    Really nice work appreciation is implicit :).

    My field is computer science so not good in electronics and electrical concepts. I understood FFT algorithm.
    We do require N (no. of points) only to execute this algorithm but doubt is why we are passing samplingfrequency to the functions?

  10. Didier says:

    Thanks for your comment,

    So far, these are the funciton which required the sampling frequency argument
    void MajorPeak(double *vData, uint16_t samples, double samplingFrequency, struct strPeakProperties *result);
    void MajorPeak(double *vData, uint16_t samples, double samplingFrequency, double loFrequency, double upFrequency, struct strPeakProperties *result);
    void Normalize(double *vData, uint16_t samples, double normalizingValue);
    void TargetPeak(double *vData, uint16_t samples, double samplingFrequency, double targetPosition, double tolerance, struct strPeakProperties *result);
    Each of them retourn a time domain information, thus the need for sampling frequency value.

    None of the other functions require this arguments. Your understanding is fine, but your question is ambiguous…
    HTH

  11. saurabh says:

    Thanks Didier for your frequent reply,
    Let me put it in right manner. Suppose you are getting some voice analog sample. You are discretizing it using sampling frequency am i right? Then out of those discrete samples you are considering N points to apply FFT on it.

    Considering your microLS project. You are considering sampling frequency = 16000Hz and no. of samples 64. That means it is considering 64 points for applying FFT right? My question is out of large no. of sampled points which points it gonna use to apply FFT? My understanding is correct?

  12. Y3G says:

    Hi,
    I am quite new to Adruino and I would like to know how to get out from approx 1024 samples (Voltage levels), Sampled at Fs=44.1 kHz = 20 ms of sample time a Spectrum.
    I have used before the Soundcard of my PC , Mic-In (16 bit,44100 Hz) and did the postprocess in MATLAB.
    Do you have any sketch ready? I would like to see it in the Monitor
    Many Thanks in advance
    Y3G

    • Didier says:

      1024 samples
      If you are using an Arduino UNO, like most users, you will have to save one byte data (-127 to 127 counts) in order to fit the 2k RAM. You may also decide to compress your data as described in Arduinoos posts. I did not maintain this option as the result depends very much on the signal shape.
      44.1kHz
      No big deal with PlainADC which can be pushed to 130kHz when recording 2 bytes integers and to 80Khz when recording 32 bits floats.

      PlainADC does the job; on the other hand, as you are new to Arduino, you may follow the latest series of post dedicated to PlainDDS which is a combo of the PlainADC and PlainFFT libraries.
      HTH

  13. Vemund says:

    Hi. I’m planning on creating a target tracking device based on a beacon attached to the target and measurement of signal strength on 4 different microphones (tdoa is thought to involve a higher cost in terms of components both in the beacon and in the receiver, and I don’t need great accuracy). Is the arduino capable of performing FFT on 4 different channels simultaneously?

    • Didier says:

      Not simultaneously, unless you have 4 arduinos! Running sequentially 4 FFT’s may take time and depending upon the speed of your target, you may loose it in blue sky ;-)
      I suggest that you look after the FIR which is way faster and should fit your needs as far as I understand them.

  14. Brielle says:

    Hello Didier

    First, thank you for all the information and code you put up on this website. I read them and it was helpful learning that I can implement FFT algorithm with Arduino board.
    I’m an engineering student who is trying to use Arduino board for my degree project. I’ve been using MATLAB to use FFT algorithm and filter the sound I have. Now, implementing the data to real product is the problem. I was planning to use Arduino board, but I don’t know which board I should buy. I’m trying to receive sound as an input source through microphone sensors and filter it so data will have certain frequencies, and send the output signal to vibration motors and LED light panel. Do you think I’ll be able to program these with Arduino board? There is no one who can help me with this in my school!!!!
    Please help me!

Leave a Reply

You must be logged in to post a comment.