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

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

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

Answer: D
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

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

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

Answer: D

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)

Answer: B

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, the second step does not require any additions and finally, the third step requires ML(L-1) complex additions.

So, a total number of complex additions=N(L+M-2).

Scroll to Top