Test: DFT Algorithm Computation - 2 - Electronics and Communication Engineering (ECE) MCQ

Explanation: Let us consider the computation of the N=2v point DFT by the divide and conquer approach. We select M=N/2 and L=2. This selection results in a split of N point data sequence into two N/2 point data sequences f₁(n) and f₂(n) corresponding to the even numbered and odd numbered samples of x(n), respectively, that is
f₁(n)=x(2n)
f₂(n)=x(2n+1) ,n=0,1,2…N/2-1
Thus f₁(n) and f₂(n) are obtained by decimating x(n) by a factor of
2, and hence the resulting FFT algorithm is called a decimation-in-time algorithm.

Explanation: From the question, it is given that
f₁(n)=x(2n)
f₂(n)=x(2n+1) ,n=0,1,2…N/2-1

Explanation: We know that, X(k) = F₁(k)+W_N^k F₂(k)
We know that F₁(k) and F₂(k) are periodic, with period N/2, we have F₁(k+N/2)= F₁(k) and F₂(k+N/2)= F₂(k). In addition, the factor W_N^k+N/2= -W_N^k.
Thus we get, X(k+N/2)= F₁(k)- W_N^k F₂(k).

Explanation: We observe that the direct computation of F₁(k) requires (N/2)² complex multiplications. The same applies to the computation of F₂(k). Furthermore, there are N/2 additional complex multiplications required to compute W_N^k. Hence it requires N(N+1)/2 complex multiplications to compute X(k).

Explanation: The decimation of the data sequence should be repeated again and again until the resulting sequences are reduced to one point sequences. For N=2^v, this decimation can be performed v=log₂N times. Thus the total number of complex multiplications is reduced to (N/2)log₂N.

Explanation: The decimation of the data sequence should be repeated again and again until the resulting sequences are reduced to one point sequences. For N=2^v, this decimation can be performed v=log₂N times. Thus the total number of complex additions is reduced to Nlog₂N.

Explanation: The above given diagram is the basic butterfly computation in the decimation-in-time FFT algorithm.

Explanation: In decimation-in-time FFT algorithm, the input is taken in bit reversal order and the output is obtained in the order.

Explanation: The above given diagram is the basic butterfly computation in the decimation-in-frequency FFT algorithm.

Explanation: In decimation-in-frequency FFT algorithm, the input is taken in order and the output is obtained in the bit reversal order.