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
Answer: A
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
Answer: D
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 the DFT of the sequence.
3. WNk+N/2=?
A. WNk
B. -WNk
C. WN-k
D. None of the mentioned
Answer: B
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
Answer: C
For a complex valued sequence x(n) of N points, the DFT may be expressed as
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
Answer: A
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
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
Answer: A
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 the divide-and-conquer method if N=LM
The first step involves L DFTs, each of M points. Hence this step requires LM2 complex multiplications, the second requires 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 the divide-and-conquer method if N=LM?
The first step involves L DFTs, each of M points. Hence this step requires LM(M-1) complex additions, the second step does not require any additions and finally, the third step requires ML(L-1) complex additions.