250+ TOP MCQs on Efficient Computation of DFT FFT Algorithms – 1 & Answers

Answer: C
Clarification: For a complex valued sequence x(n) of N points, the DFT may be expressed as
X_R(k)=(sum_{n=0}^{N-1} [x_R (n) cos⁡frac{2πkn}{N} + x_I (n) sin⁡frac{2πkn}{N}])

5. The computation of XR(k) for a complex valued x(n) of N points requires _____________
A. 2N² evaluations of trigonometric functions
B. 4N² real multiplications
C. 4N(N-1) real additions
D. All of the mentioned
Answer: D
Clarification: The expression for X_R(k) is given as
X_R(k)=(sum_{n=0}^{N-1} [x_R (n) cos⁡frac{2πkn}{N} + x_I (n) sin⁡frac{2πkn}{N}])
So, from the equation we can tell that the computation of X_R(k) requires 2N² evaluations of trigonometric functions, 4N² real multiplications and 4N(N-1) real additions.

6. Divide-and-conquer approach is based on the decomposition of an N-point DFT into successively smaller DFTs. This basic approach leads to FFT algorithms.
A. True
B. False
Answer: A
Clarification: The development of computationally efficient algorithms for the DFT is made possible if we adopt a divide-and-conquer approach. This approach is based on the decomposition of an N-point DFT into successively smaller DFTs. This basic approach leads to a family of computationally efficient algorithms known collectively as FFT algorithms.

7. If the arrangement is of the form in which the first row consists of the first M elements of x(n), the second row consists of the next M elements of x(n), and so on, then which of the following mapping represents the above arrangement?
A. n=l+mL
B. n=Ml+m
C. n=ML+l
D. none of the mentioned
Answer: B
Clarification: If we consider the mapping n=Ml+m, then it leads to an arrangement in which the first row consists of the first M elements of x(n), the second row consists of the next M elements of x(n), and so on.

8. If N=LM, then what is the value of W_N^mqL?
A. W_M^mq
B. W_L^mq
C. W_N^mq
D. None of the mentioned
Answer: A
Clarification: We know that if N=LM, then W_N^mqL = W_N/L^{mq = W_Mmq.}

9. How many complex multiplications are performed in computing the N-point DFT of a sequence using divide-and-conquer method if N=LM?
A. N(L+M+2)
B. N(L+M-2)
C. N(L+M-1)
D. N(L+M+1)
Answer: D
Clarification: The expression for N point DFT is given as
X(p,q)=(sum_{l=0}^{L-1}{W_N^{lq}[sum_{m=0}^{M-1}x(l,m) W_M^{mq}]} W_L^{lp})
The first step involves L DFTs, each of M points. Hence this step requires LM² complex multiplications, second require LM and finally third requires ML². So, Total complex multiplications = N(L+M+1).

10. How many complex additions are performed in computing the N-point DFT of a sequence using divide-and-conquer method if N=LM?
A. N(L+M+2)
B. N(L+M-2)
C. N(L+M-1)
D. N(L+M+1)
Answer: B
Clarification: The expression for N point DFT is given as
X(p,q)=(sum_{l=0}^{L-1}{W_N^{lq}[sum_{m=0}^{M-1}x(l,m) W_M^{mq}]} W_L^{lp})
The first step involves L DFTs, each of M points. Hence this step requires LM(M-1) complex additions, second step do not require any additions and finally third step requires ML(L-1) complex additions. So, Total number of complex additions=N(L+M-2).

11. Which is the correct order of the following steps to be done in one of the algorithm of divide and conquer method?
i) Store the signal column wise
ii) Compute the M-point DFT of each row
iii) Multiply the resulting array by the phase factors W_N^lq.
iv) Compute the L-point DFT of each column.
v) Read the result array row wise.
A. i-ii-iv-iii-v
B. i-iii-ii-iv-v
C. i-ii-iii-iv-v
D. i-iv-iii-ii-v