FFT rapidly computes transformations by factorising the DFT matrix into a product of a sparse factors. As a result the complexity of the computation is reduced.
In this experiment, we applied the FFT algorithm to a 4 point and an 8 point sequence. We calculated the number of real multiplications and real additions.
FFT is preferred over DFT as it is computationally faster.
ReplyDeleteFFT is based on Divide And Conquer. So rather than working with big size Signals, we divide our signal into smaller ones, and perform DFT of these smaller signals. At the end we add all the smaller DFT to get actual DFT of the big signal.
DeleteNice explanation
DeleteRadix-2 is most popularly used
ReplyDeleteFFT is faster due to decomposition
ReplyDeleteIn FFT, N pt DFT is decomposed into two N/2 pt DFT’s, N/2 pt DFT is decomposed into N/4 pt DFT’s and so on...Decomposition reduces calculations.FFT algorithms are implemented using parallel processing techniques. Because calculations are done in parallel, FFT produces fast results.
ReplyDelete