The aim of this experiment was to perform Fast Fourier transform of a DT signal. A function in C was executed to perform Radix-2 Cooley and Tuckey's DITFFT algorithm which took the length of the signal as one of its arguments(length taken must be in exponential powers of 2).A counter was also implemented to calculate total number of real and complex multiplications and additions. The results obtained were verified mathematically using formulae for the same. Bit reversal was observed and the fact that FFT is a computationally faster algorithm than DFT was understood.
DITFFT and DIFFFT have the same computational complexity.
ReplyDeleteYes both are essentially the same technique developed by Cooley and Tuckey.
DeleteFFT is faster than DFT because FFT has less number of computations.
ReplyDeleteYes decimation reduces calculation.
DeleteRadix two is algorithms are preferred because of lesser computations involved
ReplyDeleteYes..this is because value of twiddle factor for different values of k is easier to compute.
DeleteBit reversal..As in x(100) gives output y(001)Where binary numbers are used for representation of numbers.
ReplyDeleteYes that means X(4) corresponds to Y(1).
DeleteNumber of computations in FFT is less than that of DFT. This makes FFT computationally faster.
ReplyDeleteYes for FFT complex multiplications are N/2*log(N) with base 2
Deleteand in DFT complex multiplications are square(N) where N is the order.