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