# Fast Fourier Transform Algorithm MCQ Quiz – Objective Question with Answer for Fast Fourier Transform Algorithm

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

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

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

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

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
D. All of the mentioned

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

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

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

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

A. N(L+M+2)
B. N(L+M-2)
C. N(L+M-1)
D. N(L+M+1)

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, 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?

A. N(L+M+2)
B. N(L+M-2)
C. N(L+M-1)
D. N(L+M+1)

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}$$