DFT Algorithm Computation

This set of Digital Signal Processing Multiple Choice Questions & Answers (MCQs) focuses on “Efficient Computation of DFT FFT Algorithms-1′.

1. Which of the following is true regarding the number of computations required to compute an N-point DFT?
a) N2 complex multiplications and N(N-1) complex additions
b) N2 complex additions and N(N-1) complex multiplications
c) N2 complex multiplications and N(N+1) complex additions
d) N2 complex additions and N(N+1) complex multiplications

2. Which of the following is true regarding the number of computations required to compute DFT at any one value of ‘k’?
a) 4N-2 real multiplications and 4N real additions
b) 4N real multiplications and 4N-4 real additions
c) 4N-2 real multiplications and 4N+2 real additions
d) 4N real multiplications and 4N-2 real additions

3. WNk+N/2=?
a) WNk
b) -WNk
c) WN-k
d) None of the mentioned

4. What is the real part of the N point DFT XR(k) of a complex valued sequence x(n)?
a) ∑N−1n=0[xR(n)cos2πknN–xI(n)sin2πknN]
b) ∑N−1n=0[xR(n)sin2πknN+xI(n)cos2πknN]
c) ∑N−1n=0[xR(n)cos2πknN+xI(n)sin2πknN]
d) None of the mentioned

5. The computation of XR(k) for a complex valued x(n) of N points requires _____________
a) 2N2 evaluations of trigonometric functions
b) 4N2 real multiplications
c) 4N(N-1) real additions
d) All of the mentioned

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

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

8. If N=LM, then what is the value of WNmqL?
a) WMmq
b) WLmq
c) WNmq
d) None of the mentioned

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)

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)

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 WNlq.
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

12. If we store the signal row wise then the result must be read column wise.
a) True
b) False

13. If we store the signal row wise and compute the L point DFT at each column, the resulting array must be multiplied by which of the following factors?
a) WNlq
b) WNpq
c) WNlq
d) WNpm

14. If we split the N point data sequence into two N/2 point data sequences f1(n) and f2(n) corresponding to the even numbered and odd numbered samples of x(n), then such an FFT algorithm is known as decimation-in-time algorithm.
a) True
b) False

15. If we split the N point data sequence into two N/2 point data sequences f1(n) and f2(n) corresponding to the even numbered and odd numbered samples of x(n) and F1(k) and F2(k) are the N/2 point DFTs of f1(k) and f2(k) respectively, then what is the N/2 point DFT X(k) of x(n)?
a) F1(k)+F2(k)
b) F1(k)-WNk F2(k)
c) F1(k)+WNk F2(k)
d) None of the mentioned
.

16. If X(k) is the N/2 point DFT of the sequence x(n), then what is the value of X(k+N/2)?
a) F1(k)+F2(k)
b) F1(k)-WNk F2(k)
c) F1(k)+WNk F2(k)
d) None of the mentioned

17. How many complex multiplications are required to compute X(k)?
a) N(N+1)
b) N(N-1)/2
c) N2/2
d) N(N+1)/2

18. The total number of complex multiplications required to compute N point DFT by radix-2 FFT is?
a) (N/2)log2N
b) Nlog2N
c) (N/2)logN
d) None of the mentioned

19. The total number of complex additions required to compute N point DFT by radix-2 FFT is?
a) (N/2)log2N
b) Nlog2N
c) (N/2)logN
d) None of the mentioned

20. The following butterfly diagram is used in the computation of __________

a) Decimation-in-time FFT
b) Decimation-in-frequency FFT
c) All of the mentioned
d) None of the mentioned

21. For a decimation-in-time FFT algorithm, which of the following is true?
a) Both input and output are in order
b) Both input and output are shuffled
c) Input is shuffled and output is in order
d) Input is in order and output is shuffled

22. The following butterfly diagram is used in the computation of __________

a) Decimation-in-time FFT
b) Decimation-in-frequency FFT
c) All of the mentioned
d) None of the mentioned

23. For a decimation-in-time FFT algorithm, which of the following is true?
a) Both input and output are in order
b) Both input and output are shuffled
c) Input is shuffled and output is in order
d) Input is in order and output is shuffled