1 Crore+ students have signed up on EduRev. Have you? 
If we split the N point data sequence into two N/2 point data sequences f_{1}(n) and f_{2}(n) corresponding to the even numbered and odd numbered samples of x(n), then such an FFT algorithm is known as decimationintime algorithm.
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 f_{1}(n) and f_{2}(n) corresponding to the even numbered and odd numbered samples of x(n), respectively, that is
f_{1}(n)=x(2n)
f_{2}(n)=x(2n+1) ,n=0,1,2…N/21
Thus f_{1}(n) and f_{2}(n) are obtained by decimating x(n) by a factor of
2, and hence the resulting FFT algorithm is called a decimationintime algorithm.
If we split the N point data sequence into two N/2 point data sequences f_{1}(n) and f_{2}(n) corresponding to the even numbered and odd numbered samples of x(n) and F_{1}(k) and F_{2}(k) are the N/2 point DFTs of f_{1}(k) and f_{2}(k) respectively, then what is the N/2 point DFT X(k) of x(n)?
Explanation: From the question, it is given that
f_{1}(n)=x(2n)
f_{2}(n)=x(2n+1) ,n=0,1,2…N/21
If X(k) is the N/2 point DFT of the sequence x(n), then what is the value of X(k+N/2)?
Explanation: We know that, X(k) = F_{1}(k)+W_{N}^{k} F_{2}(k)
We know that F_{1}(k) and F_{2}(k) are periodic, with period N/2, we have F_{1}(k+N/2)= F_{1}(k) and F_{2}(k+N/2)= F_{2}(k). In addition, the factor W_{N}^{k+N/2}= W_{N}^{k}.
Thus we get, X(k+N/2)= F_{1}(k) W_{N}^{k} F_{2}(k).
How many complex multiplications are required to compute X(k)?
Explanation: We observe that the direct computation of F_{1}(k) requires (N/2)^{2} complex multiplications. The same applies to the computation of F_{2}(k). Furthermore, there are N/2 additional complex multiplications required to compute W_{N}^{k}. Hence it requires N(N+1)/2 complex multiplications to compute X(k).
The total number of complex multiplications required to compute N point DFT by radix2 FFT is:
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=2^{v}, this decimation can be performed v=log_{2}N times. Thus the total number of complex multiplications is reduced to (N/2)log_{2}N.
The total number of complex additions required to compute N point DFT by radix2 FFT is:
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=2^{v}, this decimation can be performed v=log_{2}N times. Thus the total number of complex additions is reduced to Nlog_{2}N.
The following butterfly diagram is used in the computation of:
Explanation: The above given diagram is the basic butterfly computation in the decimationintime FFT algorithm.
For a decimationintime FFT algorithm, which of the following is true?
Explanation: In decimationintime FFT algorithm, the input is taken in bit reversal order and the output is obtained in the order.
The following butterfly diagram is used in the computation of:
Explanation: The above given diagram is the basic butterfly computation in the decimationinfrequency FFT algorithm.
For a decimationintime FFT algorithm, which of the following is true?
Explanation: In decimationinfrequency FFT algorithm, the input is taken in order and the output is obtained in the bit reversal order.
32 videos76 docs63 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
32 videos76 docs63 tests








