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%
If N=LM, then what is the value of WNmqL?
WMmq
WLmq
WNmq
None of the mentioned
Explanation:
We know that if N=LM, then WNmqL = WN/Lmq = WMmq.
Question 3
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 4
Marks : +2 | -2
Pass Ratio : 100%
What is the real part of the N point DFT XR(k) of a complex valued sequence x(n)?
\\(\\sum_{n=0}^{N-1} [x_R (n) cos⁡\\frac{2Ï€kn}{N} – x_I (n) sin⁡\\frac{2Ï€kn}{N}]\\)
\\(\\sum_{n=0}^{N-1} [x_R (n) sin⁡\\frac{2πkn}{N} + x_I (n) cos⁡\\frac{2πkn}{N}]\\)
\\(\\sum_{n=0}^{N-1} [x_R (n) cos⁡\\frac{2πkn}{N} + x_I (n) sin⁡\\frac{2πkn}{N}]\\)
None of the mentioned
Explanation:
For a complex valued sequence x(n) of N points, the DFT may be expressed as
Question 5
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 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%
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?
n=l+mL
n=Ml+m
n=ML+l
none of the mentioned
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.
Question 8
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 9
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 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