For an N-point FFT algorithm with N = 2m, which one of the following statements is TRUE?

It is not possible to construct a signal flow graph with both input and output in normal order
The number of butterflies in the mn state is $$rac{N}{m}$$
In-place computation requires storage of only 2N node data
Computation of a butterfly requires only one complex multiplication

The correct answer is: B. The number of butterflies in the mn state is $\frac{N}{m}$.

A butterfly is a basic operation in the Fast Fourier Transform (FFT) algorithm. It consists of two complex multiplications and two complex additions. The number of butterflies in the mn state is equal to the number of complex numbers in the input sequence, which is $\frac{N}{m}$.

Option A is incorrect because it is possible to construct a signal flow graph with both input and output in normal order. This is done by using a butterfly network.

Option C is incorrect because in-place computation requires storage of all $N$ node data. This is because the input sequence is stored in the same memory locations as the output sequence.

Option D is incorrect because computation of a butterfly requires two complex multiplications and two complex additions.

Exit mobile version