Question

What is the speed improvement factor in calculating 64-point DFT of a sequence using direct computation and FFT algorithm?

Answer 1

The speed improvement factor in 64-point DFT using direct computation and FFT algorithm:

Explanation:

• The ratio between the no.of additions and multiplications required to compute the algorithms, and the direct computation cost of computing these algorithms.
• The no.of complex multiplications required using FFT = N/2 log2N = 64/2log264=192.
• The Speed improvement factor is = 4096/192= 21.33 17.

Answer 2

Answer:

21.33

Explanation:

Number of complex multiplications required using direct computation = $N^{2} =64^{2} =4096$

Number of complex multiplications required using FFT = $\frac{N}{2}log_{2}N=\frac{64}{2}log_{2}64=192$

∴ Speed improvement factor = $\frac{4096}{192} =21.33$