The Fast Fourier Transform (10 pts) What is a twiddle factor? Part II (2 pts) How would you use the Radix II FFT to find the FFT of a sequence

of length N = 1001? Part III (2 pts) Elaborate on why – or why not – the FFT does or does not compute the DFT exactly? You should consider the Cooley-Tukey FFT. Part IV (2 pts) The FFT butterfly structure shown is known as the decimation-in-time FFT. Part V (2 pts) Describe why the FFT that computes small DFTS is more efficient than computing the original N point DFT.

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5

Fig: 6

Fig: 7