FFT

Question 1

The computation procedure of DFT is very lengthy and cumbersome. To improve this we can use ——-

Answer 1

twiddle factor

Question 2

is a very efficient method for computing the DFT coefficients. It reduces the number of complex multiplications from N^2 in case of DFT to simply (N /2 )log2(N) In the case of FFT.

Answer 2

Fast Fourier Transform (FFT)

Question 3

• Shuffling of the input sequence x(n) (bit-reversed indexing).
• Frequency samples X(k) are in normal order.

Answer 3

Decimation-in-Time method

Question 4

• Input sequence x(n) is in normal order.
• frequency samples X(k) are in bit-reversed indexing.

Answer 4

Decimation-in-Frequency method

Question 5

The complexity of the decimation-in-frequency FFT is the same as the decimation-in-time, and the computations performed in place.

READINGS

Question 6

is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms).

Answer 6

Butterfly Diagram