Fast Fourier Transform (FFT) (Part 3)

Part 1234567891011

FFT stands for fast Fourier Transform. The DFT (Discret Fourier Transform) applies to vectors containing any number of signal samples. But it is sssssssssllllllllllllllllllllllloooooooooooooowwwwwwww due to the repeated number of operation. Computing a DFT of n points takes n^2 arithmetical operations, while an FFT can compute the same result in only n log2(n) operations. The implemented algorithm is the “Cooley–Tukey” algorithm which is the far most popular. The “only” limitation is that the number of samples in the signal must be a power of two. However, if the number of samples is less than that, it is possible to replace missing data with 0 values without dramatic alteration of the final result: this is the zero padding. As a result of padding zeros to the existing data, the spectral resolution will be degraded.

Next post on same subject


  1. JRicardo says:

    what does the function exponent ???

  2. Didier says:

    This function computes the exponent from a value which is the result of powering a mantissa value of 2.
    ex. exponent(8)=3, so as to say exponent(2^3)=3

    It is equivalent to Log(x)/Log(mantissa) but far simpler 😉

  3. JRicardo says:

    I need to implement this function or it is recognized by the Arduino?

  4. kevin says:


    is this the complete code of this compute function?
    what is “12 <" mean in last line?


  5. theinem says:


    I’m from Colombia. Thanks for make a great job with signal analysis. I’m triying to learn about your code, given that I have not found a way to download. I want to apply it in EMG signal analysis in real time.

    While I’m reading the code, I don’t understand the lines 12 to 15.

    12 while (k>= 1;
    13 }
    14 j += k;
    15 }

    I supose you have a mistake or I’m a fool with this. I would like to clarify that part.

    My english isn’t the best, excuse me if it sounds weird or rude.

    Thank you in advance.

  6. Didier says:

    Oooops ! For some reasons the code is “broken”.
    On my TODO list, thanks for the feedback 🙂

  7. SyedShoeb says:

    Codes are still broken.
    Also DFT = Discrete Fourier Transform (not Direct)
    And thanks for amazing blog.

  8. arifoyong says:

    Thanks a lot for the great information.
    I’m looking for the FFT.compute. Is there any information on this algorithm?

Leave a Reply

You must be logged in to post a comment.