The DFT equation is

$X(K) = \sum_{n=0}^{N-1} x(n) W_N^{nK} \hspace{1cm} K=0,1,2,…..N-1$

In decimation-in-time technique ,we split the input x(n) into odd and even parts.

$X(K) = \sum_{n→even} x(n) W_N^{nK} + \sum_{n→odd} x(n) W_N^{nK} \\ X(K) = \sum_{n=0}^{N/2-1} x(2n) W_N^{2nK} + \sum_{n=0}^{N/2-1} x(2n) W_N^{2n+1}K \\ X(K) = \sum_{n=0}^{N/2-1} x(2n) W_N^{2nK} + \sum_{n=0}^{N/2-1} x(2n) W_N^{2nK} W_N^K \\ Now,W_N^2= W_{N/2} \\ X(K) =\sum_{n=0}^{N/2-1} x(2n) W_{N/2}^{nK} +W_N^K \sum_{n=0}^{N/2-1} x(2n+1) W_{N/2}^{nK} \\ Let F1(K) =\sum_{n=0}^{N/2-1} x(2n) W_{N/2}^{nK} \\ F2(K) = \sum_{n=0}^{N/2-1} x(2n+1) W_{N/2}^{nK} \\ Therefore , X(K) = F1(K)+W_N^K F2(K)$

Since F1(K) and F2 (K) are periodic with period N/2 we can write

$F1(K+N/2) = F1(K) and F2(K+N/2) = F2(K) \\ Also W_{N/2}^{nK}= -W_N^K$

Therefore, We get,

$X(K) = F_1(K)+W_N^K F_2(K) \hspace{1cm} K=0,1,2,……N/2 - 1 \\ X(K+N/( 2)) = F_1(K) -W_N^K F_2(K)$

Hence, the computation of X(K) requires complex multiplications which is almost half the computations required by the conventional method,

$2X(N/2)2 + N/2 = N^2/2 +N/2$

As stated earlier,F1(K) and F2(K) are N/2 point DFT’s (4 point DFT’s if N = 8).These can be further split up into odd and even parts.

$i.e.X(K) = \sum_{n=0}^{N/2-1} x(2n) W_{N/2}^{nK} + W_N^K \sum_{n=0}^{N/2-1} x(2n+1) W_{N/2}^{nK} \\ (A) 2 \ parts \ of \ N/4 \ each \hspace{1cm} (B) \ 2 \ parts \ of \ N/4 \ each \\ (A): = \sum_{n=0}^{N/2-1} x(2n) W_{N/2}^{nK} = \sum_{n=0}^{N/4-1} x(4n) W_{N/2}^{2nK} + \sum_{n=0}^{N/2-1} x(4n+2) W_{N/2}^{(2n+1)K} \\ \hspace{4.8cm} = \sum_{n=0}^{N/4-1} x(4n) W_{N/4}^{nK} + \sum_{n=0}^{N/4-1} x(4n+2) W_{N/2}^{(2nk+k)} \hspace{4.8cm} = \sum_{n=0}^{N/4-1} x(4n) W_{N/4}^{nK} + W_{N/2}^K \sum_{n=0}^{N/4-1} x(4n+2) W_{N/4}^{nK} \\ Therefore, \ F1(K) = \sum_{n=0}^{N/4-1} x(4n) W_{N/4}^{nK} + W_{N/2}^K \sum_{n=0}^{N/4-1} x(4n+2) W_{N/4}^{nK} \\ Let, ∑\sum_{n=0}^{N/4-1} x(4n) W_{N/4}^{nK} = G_1(K) and \sum_{n=0}^{N/4-1} x(4n+2) W_{N/4}^{nK} = G_2(K) \\ Then, F_1(K) = G_1(K) + W_{N/2}^K G_2(K) \\ Similarly, F_2(K) = H_1(K) + W_{N/2}^K H_2(K)$

Hence, the final signal flow graph is ,

This is called 8-point butterfly diagram.

The DIT-FFT refers to the method in which the input samples are broken into odd and even parts. his time decimation leads to the scrambled order of the input.