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.

The above given diagram is the basic butterfly computation in the decimation-in-time FFT algorithm.

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.

The formula for calculating N point DFT is given as

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

According to the symmetry property, we get WNk+N/2=-WNk.

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.

We know that, X(k) = F1(k)+WNk F2(k)

From the question, it is given that

The above given diagram is the basic butterfly computation in the decimation-in-frequency FFT algorithm.