Digital Signal Processing

Efficient Computation of DFT FFT Algorithms

Question 1
Marks : +2 | -2
Pass Ratio : 100%
For a decimation-in-time FFT algorithm, which of the following is true?
Both input and output are in order
Both input and output are shuffled
Input is shuffled and output is in order
Input is in order and output is shuffled
Explanation:
In decimation-in-frequency FFT algorithm, the input is taken in order and the output is obtained in the bit reversal order.
Question 2
Marks : +2 | -2
Pass Ratio : 100%
The computation of XR(k) for a complex valued x(n) of N points requires _____________
2N2 evaluations of trigonometric functions
4N2 real multiplications
4N(N-1) real additions
All of the mentioned
Explanation:
The expression for XR(k) is given as
Question 3
Marks : +2 | -2
Pass Ratio : 100%
How many complex additions are performed in computing the N-point DFT of a sequence using divide-and-conquer method if N=LM?
N(L+M+2)
N(L+M-2)
N(L+M-1)
N(L+M+1)
Explanation:
The expression for N point DFT is given as
Question 4
Marks : +2 | -2
Pass Ratio : 100%
If we split the N point data sequence into two N/2 point data sequences f1(n) and f2(n) corresponding to the even numbered and odd numbered samples of x(n) and F1(k) and F2(k) are the N/2 point DFTs of f1(k) and f2(k) respectively, then what is the N/2 point DFT X(k) of x(n)?
F1(k)+F2(k)
F1(k)-WNk F2(k)
F1(k)+WNk F2(k)
None of the mentioned
Explanation:
From the question, it is given that
Question 5
Marks : +2 | -2
Pass Ratio : 100%
WNk+N/2=?
WNk
-WNk
WN-k
None of the mentioned
Explanation:
According to the symmetry property, we get WNk+N/2=-WNk.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
The following butterfly diagram is used in the computation of __________
Decimation-in-time FFT
Decimation-in-frequency FFT
All of the mentioned
None of the mentioned
Explanation:
The above given diagram is the basic butterfly computation in the decimation-in-time FFT algorithm.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
For a decimation-in-time FFT algorithm, which of the following is true?
Both input and output are in order
Both input and output are shuffled
Input is shuffled and output is in order
Input is in order and output is shuffled
Explanation:
In decimation-in-time FFT algorithm, the input is taken in bit reversal order and the output is obtained in the order.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
Which of the following is true regarding the number of computations required to compute DFT at any one value of ‘k’?
4N-2 real multiplications and 4N real additions
4N real multiplications and 4N-4 real additions
4N-2 real multiplications and 4N+2 real additions
4N real multiplications and 4N-2 real additions
Explanation:
The formula for calculating N point DFT is given as
Question 9
Marks : +2 | -2
Pass Ratio : 100%
The total number of complex additions required to compute N point DFT by radix-2 FFT is?
(N/2)log2N
Nlog2N
(N/2)logN
None of the mentioned
Explanation:
The decimation of the data sequence should be repeated again and again until the resulting sequences are reduced to one point sequences. For N=2v, this decimation can be performed v=log2N times. Thus the total number of complex additions is reduced to Nlog2N.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
Which of the following is true regarding the number of computations required to compute an N-point DFT?
N2 complex multiplications and N(N-1) complex additions
N2 complex additions and N(N-1) complex multiplications
N2 complex multiplications and N(N+1) complex additions
N2 complex additions and N(N+1) complex multiplications
Explanation:
The formula for calculating N point DFT is given as