Question

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.

(a) True

(b) False

The question was posed to me by my school teacher while I was bunking the class.

My question is based upon Efficient Computation of DFT FFT Algorithms topic in division DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Correct choice is (a) True

The best I can explain: Let us consider the computation of the N=2^v 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

f1(n)=x(2n)

f2(n)=x(2n+1), n=0,1,2…N/2-1

Thus f1(n) and f2(n) are obtained by decimating x(n) by a factor of 2, and hence the resulting FFT algorithm is called a decimation-in-time algorithm.