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. WN^{k+N/2}=?

A. WN^{k}
B. -WN^{k}
C. WN^{-k}
D. None of the mentioned

Answer: B

According to the symmetry property, we get WN^{k+N/2}=-WN^{k}.

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.