Basic principle of DIT-FFT Digital Signal Processing--DFT/FFT Algorithms FFT Algorithm has 2 types Decimation In Time FFT,(DIT-FFT) and Decimation In Frequency FFT(DIF-FFT)。First DIF-FFT。 Length of x(n)is N,and N=2M,M∈N Depended on odd-even of n,x(n)is divided into two N/2-point sub-sequence N x(r)=x(2r), r=0,1,.-1 2 x2(r)=x(2r+1),r=0,1,. 上游交通大学Digital Signal Processing—— DFT/FFT Algorithms Basic principle of DIT-FFT FFT Algorithm has 2 types ： Decimation In Time FFT,(DIT-FFT) and Decimation In Frequency FFT(DIF―FFT)。First DIF―FFT。 Length of x(n) is N，and Depended on odd-even of n, x(n) is divided into two N/2-point sub-sequence 2 , M N M  ∈N 1 2 ( ) (2 ), 0,1, 1 2 ( ) (2 1), 0,1, 1 2 N x r x r r N x r x r r         