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
View Answer
Explanation: The formula for calculating N point DFT is given as
X(k)=\(\sum_{n=0}^{N-1} x(n)e^{-j2πkn/N}\)
From the formula given at every step of computing we are performing N complex multiplications and N-1 complex additions. So, in a total to perform N-point DFT we perform N2 complex multiplications and N(N-1) complex additions.
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
View Answer
Explanation: The formula for calculating N point DFT is given as
X(k)=\(\sum_{n=0}^{N-1} x(n)e^{-j2πkn/N}\)
From the formula given at every step of computing we are performing N complex multiplications and N-1 complex additions. So, it requires 4N real multiplications and 4N-2 real additions for any value of ‘k’ to compute DFT of the sequence.
3. WNk+N/2=?
a) WNk
b) -WNk
c) WN-k
d) None of the mentioned
View Answer
Explanation: According to the symmetry property, we get WNk+N/2=-WNk.
4. What is the real part of the N point DFT XR(k) of a complex valued sequence x(n)?
a) \(\sum_{n=0}^{N-1} [x_R (n) cos\frac{2πkn}{N} – x_I (n) sin\frac{2πkn}{N}]\)
b) \(\sum_{n=0}^{N-1} [x_R (n) sin\frac{2πkn}{N} + x_I (n) cos\frac{2πkn}{N}]\)
c) \(\sum_{n=0}^{N-1} [x_R (n) cos\frac{2πkn}{N} + x_I (n) sin\frac{2πkn}{N}]\)
d) None of the mentioned
View Answer
Explanation: For a complex valued sequence x(n) of N points, the DFT may be expressed as
XR(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) 2N2 evaluations of trigonometric functions
b) 4N2 real multiplications
c) 4N(N-1) real additions
d) All of the mentioned
View Answer
Explanation: The expression for XR(k) is given as
XR(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 XR(k) requires 2N2 evaluations of trigonometric functions, 4N2 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
View Answer
Explanation: 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
View Answer
Explanation: 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 WNmqL?
a) WMmq
b) WLmq
c) WNmq
d) None of the mentioned
View Answer
Explanation: We know that if N=LM, then WNmqL = WN/Lmq = WMmq.
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)
View Answer
Explanation: 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 LM2 complex multiplications, second require LM and finally third requires ML2. 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)
View Answer
Explanation: 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 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
View Answer
Explanation: According to one of the algorithm describing the divide and conquer method, if we store the signal in column wise, then compute the M-point DFT of each row and multiply the resulting array by the phase factors WNlq and then compute the L-point DFT of each column and read the result row wise.
12. If we store the signal row wise then the result must be read column wise.
a) True
b) False
View Answer
Explanation: According to the second algorithm of divide and conquer approach, if the input signal is stored in row wise, then the result must be read column wise.
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
View Answer
Explanation: According to the second algorithm of divide and conquer approach, if the input signal is stored in row wise, then we calculate the L point DFT of each column and we multiply the resulting array by the factor WNpm.
Sanfoundry Global Education & Learning Series – Digital Signal Processing.
To practice all areas of Digital Signal Processing, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Get Free Certificate of Merit in Digital Signal Processing
- Participate in Digital Signal Processing Certification Contest
- Become a Top Ranker in Digital Signal Processing
- Take Digital Signal Processing Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
