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-time FFT algorithm, the input is taken in bit reversal order and the output is obtained in the order.
Question 2
Marks : +2 | -2
Pass Ratio : 100%
If X(k) is the N/2 point DFT of the sequence x(n), then what is the value of X(k+N/2)?
F1(k)+F2(k)
F1(k)-WNk F2(k)
F1(k)+WNk F2(k)
None of the mentioned
Explanation:
We know that, X(k) = F1(k)+WNk F2(k)
Question 3
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 4
Marks : +2 | -2
Pass Ratio : 100%
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.
True
False
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.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
How many complex multiplications 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 6
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), then such an FFT algorithm is known as decimation-in-time algorithm.
True
False
Explanation:
Let us consider the computation of the N=2v point DFT by the divide and conquer approach. We select M=N/2 and L=2. This selection results in a split of 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), respectively, that is
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-frequency FFT algorithm, the input is taken in order and the output is obtained in the bit reversal order.
Question 8
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
Question 9
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 10
Marks : +2 | -2
Pass Ratio : 100%
The total number of complex multiplications 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 multiplications is reduced to (N/2)log2N.