## Fast Fourier Transform (FFT) (Part 3)

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.

what does the function exponent ???

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 😉

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

hello

is this the complete code of this compute function?

what is “12 <" mean in last line?

thx

No, this is the top part of the code.

This is not 12, but l2 (“L” in lower caps and “2”) which is commonly used for “butterflying” data.

where can i find the other part of this code?

btw can u send me the complete library?

because i got many error when i compile in Arduino…QQ

THANK U!!!

plz read my req. pol.

thkU

(I hate SMS writing style!)

Regards

D

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.

Oooops ! For some reasons the code is “broken”.

On my TODO list, thanks for the feedback 🙂

Codes are still broken.

Also DFT = Discrete Fourier Transform (not Direct)

And thanks for amazing blog.

Thanks for your comments 😉

Hi,

Thanks a lot for the great information.

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

http://www.arduinoos.com/2010/10/fast-fourier-transform-fft/

Regards

Didier