DIT-FFT Digital Signal Processing--DFT/FFT Algorithms DFT[X(n)]=X(k)=∑x(n)W+∑x(n)W n= N72 W/2-1 ∑x(2r)w+∑x(2r+1)w2+ r= =0 N/2-1 N/2-1 (rW2+m∑x(r)W r=0 三0 2π JN W 22k 二e JN =e 2 =W2 N/2-1 N/2-1 .X(k)=∑ x(rW+Wx(rW2=X(k)+WX(k) r=0 上游充通大￥Digital Signal Processing—— DFT/FFT Algorithms DIT-FFT DFT [x(n)]= /2 1 /2 1 2 (2 1) 0 0 /2 1 /2 1 2 2 1 2 0 0 ( ) ( ) ( ) (2 ) (2 1) ( ) ( ) kn kn N N n n N N kr k r N N r r N N kr k kr N N N r r X k x n W x n W x r W x r W x r W W x r W                         ∵ 2 2 2 2 2 / 2 j kr N j kr kr kr N W e e W N N        ∴ / 2 1 / 2 1 1 / 2 2 / 2 1 2 0 0 ( ) ( ) ( ) ( ) ( ) N N kr k kr k N N N N r r X k x r W W x r W X k W X k          