The expression for N point DFT is given as

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-frequency FFT algorithm.

The expression for XR(k) is given as

We observe that the direct computation of F1(k) requires (N/2)2 complex multiplications. The same applies to the computation of F2(k). Furthermore, there are N/2 additional complex multiplications required to compute WNk. Hence it requires N(N+1)/2 complex multiplications to compute X(k).

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

We know that if N=LM, then WNmqL = WN/Lmq = WMmq.

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.

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

In decimation-in-time FFT algorithm, the input is taken in bit reversal order and the output is obtained in the order.