Fast Fourier Transform (FFT) (Part 3)

Posted on 11 Oct 2010, 07:50, by Didier, under Applications, Programming.

Part 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

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

Tags: , ,
Comment (RSS)  |  Trackback

13 Comments

  1. JRicardo says:
    19 Oct 2010 at 03:11

    what does the function exponent ???

  2. Didier says:
    19 Oct 2010 at 07:51

    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:
    23 Oct 2010 at 00:17

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

  4. kevin says:
    08 Apr 2013 at 10:12

    hello

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

    thx

  5. theinem says:
    05 Oct 2015 at 00:33

    Hello.

    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:
    05 Oct 2015 at 15:21

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

  7. SyedShoeb says:
    08 Dec 2015 at 15:00

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

  8. arifoyong says:
    28 Dec 2015 at 15:45

    Hi,
    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.

«
»