FFT algorithm was implemented by creating a function for it. The signal was divided into two parts i.e odd and even part. Then computations were carried out on these two parts seperately. The even parts being added directly whereas the odd part was multipled was appropriate twiddle factor and then added.
By sepearating the signal into odd and even parts and then coputing FFT reduces the total number of computations and also reduces the total time required for calculation.
NOTE:Similar to the DFT code in this code too sine and cosine functions are used for computation of FFT and hence including this library is mandatory.
eg. gcc sample.c -lm
where "-lm" is the command used to include math library.
Without this the code wouldn't compile even if the entire code is right.
NOTE:Similar to the DFT code in this code too sine and cosine functions are used for computation of FFT and hence including this library is mandatory.
eg. gcc sample.c -lm
where "-lm" is the command used to include math library.
Without this the code wouldn't compile even if the entire code is right.
FFT reduces the complexity of computing from f(n²) to f(nlogn) as compared to DFT
ReplyDeleteThanks for the addition
Deletethanks kartik. the note was helpful
ReplyDeleteYeah indeed! We tend to forget the little things!
ReplyDeleteA small spelling error in "coputinf FFT". And in higher order FFT the even part of the signals are also multiplied by twiddle factors (like the "j" in 4point FFT)
ReplyDeleteoops .. didn't notice the spelling error... Thanks for the correction..
DeleteFFT cannot be used that well for real time applications.
ReplyDeleteComputation in FFT varies logarithmically and all the input in FFT have to be given simultaneously.
ReplyDelete