This set of Digital Signal Processing Multiple Choice Questions & Answers (MCQs) focuses on “Efficient Computation of DFT FFT Algorithms-1′.

1. Which of the following is true regarding the number of computations required to compute an N-point DFT?

a) N^{2} complex multiplications and N(N-1) complex additions

b) N^{2} complex additions and N(N-1) complex multiplications

c) N^{2} complex multiplications and N(N+1) complex additions

d) N^{2} complex additions and N(N+1) complex multiplications

View Answer

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 N

^{2}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

View Answer

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

a) W_{N}^{k}

b) -W_{N}^{k}

c) W_{N}^{-k}

d) None of the mentioned

View Answer

Explanation: According to the symmetry property, we get W

_{N}k+N/2=-W

_{N}

^{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

View Answer

Explanation: For a complex valued sequence x(n) of N points, the DFT may be expressed as

X

_{R}(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) 2N^{2} evaluations of trigonometric functions

b) 4N^{2} real multiplications

c) 4N(N-1) real additions

d) All of the mentioned

View Answer

Explanation: The expression for X

_{R}(k) is given as

X

_{R}(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 X

_{R}(k) requires 2N

^{2}evaluations of trigonometric functions, 4N

^{2}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

View Answer

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

View Answer

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 W_{N}^{mqL}?

a) W_{M}^{mq}

b) W_{L}^{mq}

c) W_{N}^{mq}

d) None of the mentioned

View Answer

Explanation: We know that if N=LM, then W

_{N}

^{mqL}= W

_{N/L}

^{mq = 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)

View Answer

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

^{2}complex multiplications, second require LM and finally third requires ML

^{2}. 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)

View Answer

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

11. Which is the correct order of the following steps to be done in one of the algorithm of divide and conquer method?

i) Store the signal column wise

ii) Compute the M-point DFT of each row

iii) Multiply the resulting array by the phase factors W_{N}^{lq}.

iv) Compute the L-point DFT of each column.

v) Read the result array row wise.

a) i-ii-iv-iii-v

b) i-iii-ii-iv-v

c) i-ii-iii-iv-v

d) i-iv-iii-ii-v

View Answer

Explanation: According to one of the algorithm describing the divide and conquer method, if we store the signal in column wise, then compute the M-point DFT of each row and multiply the resulting array by the phase factors W

_{N}

^{lq}and then compute the L-point DFT of each column and read the result row wise.

12. If we store the signal row wise then the result must be read column wise.

a) True

b) False

View Answer

Explanation: According to the second algorithm of divide and conquer approach, if the input signal is stored in row wise, then the result must be read column wise.

13. If we store the signal row wise and compute the L point DFT at each column, the resulting array must be multiplied by which of the following factors?

a) W_{N}^{lq}

b) W_{N}^{pq}

c) W_{N}^{lq}

d) W_{N}^{pm}

View Answer

Explanation: According to the second algorithm of divide and conquer approach, if the input signal is stored in row wise, then we calculate the L point DFT of each column and we multiply the resulting array by the factor W

_{N}

^{pm}.

**Sanfoundry Global Education & Learning Series – Digital Signal Processing.**

To practice all areas of Digital Signal Processing, __here is complete set of 1000+ Multiple Choice Questions and Answers__.

**Next Steps:**

- Get Free Certificate of Merit in Digital Signal Processing
- Participate in Digital Signal Processing Certification Contest
- Become a Top Ranker in Digital Signal Processing
- Take Digital Signal Processing Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**