1
4.9kviews
Explain the speed improvement in calculating the DFT using FFT.
1 Answer
2
519views

Computational benefits of FFT over DFT are

$\begin{array}{|c|c|c|}\hline & {\text { Complex Multiplication }} & {\text { Complex Addition }} \\ \hline \text { DFT } & {N^{2}} & {\mathrm{N}(\mathrm{N}-1)} \\ \hline \mathrm{FFT} & {\frac{N}{2} \log _{2} N} & {N \log _{2} N} \\ \hline\end{array}$

Speed Improvement Factor for complex multiplication in Radix-2 $\mathrm{FFT}=\frac{4 N^{2}}{2 N \log _{2} N}=\frac{2 N}{\log _{2} N}=2 N \log _{N} 2$

For example, Consider a computer which can execute 1 multiplication operation in 1 nano-seconds. We assume that the amount of time to compute a DFT is determined by the amount of time to perform all the multiplications.

Let us consider a DT signal having total of $N=10^{9}$ points Time required for evaluating DFT by direct method on the given Computer $=N^{2}=\left(10^{9}\right)^{2}=10^{18}$ Nano-sconds, which is approximately 31 years.

Time required for evaluating $\mathrm{FFT}=\frac{N}{2} \log _{2} N=\frac{10^{9}}{2} \log _{2} 10^{9} \approx 15 \times 10^{9}$Nano-seconds approximately 15 secs.

Please log in to add an answer.