After understanding the complications involved in computing DFT it is time to understand its faster version i.e. the Fast Fourier Transform(FFT) algorithm (i.e.it is not a mathematical concept, it is a way to reduce calculations used in DFT) . FFT is implemented using two algorithms namely Decimation in Time FFT(DITFFT) and Decimation in Frequency FFT(DIFFFT). Both these algorithms take the same time for execution as same number of assembly instructions(after conversion from C program) are same overall. In case of DITFFT, after accepting the input, the samples are re-arranged whereas in case of DIFFFT the samples are taken as it is, but the output is re-arranged. After implementation of both algorithms, the outputs, execution time and computations involved were exactly the same.
In FFT, the number of computation done is in the power of 2 to accelerate computation.
ReplyDeleteThere is an inherent property of sinusoidal signals which is used to reduce computations.
DeleteFFT is faster than DFT
ReplyDeleteHence, it is preferred.
DeleteYou have correctly highlighted the difference between DITFFT and DIFFFT.Can you explain which one is easier to implement and why?
ReplyDeleteThey are computationally same. The choice is upto the programmer.For practical implementation on DSPs, memory can become a constraint and in these cases,the optimum method must be selected.
DeleteDITFFT & DIFFFT are computationally same, requiring same amount of calculation
ReplyDeleteFFT is not practically implementable
ReplyDeleteLong point FFT is difficult. FFT of small signals can be performed.
DeleteFFT is faster due to decomposition of the signal
ReplyDeleteYes. It performs decomposition till the length of the signal is reduced to a number below 10.
DeleteDIFFFT and DITFFT are computationally equal
ReplyDeleteThe choice of selection is upto the user.
DeleteGilbert Strang described the FFT as "the most important numerical algorithm of our lifetime"
ReplyDeleteRightly said.
DeleteFFT is used in practical systems for frequency domain analysis
ReplyDeleteIt is easier to implement than DFT.
DeleteFFT is used for faster frequency domain analysis of a discrete time signals.
ReplyDelete