第4章快速傅里叶夜换(ED 则x(m)的DFT为 X()=∑x(m)W+∑x(n)W如 N/2-1 2 kr (2r)WN"+ x(2r+1)W2r+1) ∑x(m)+W∑x(r) 2 由于 r=0 r=0 2kr 2 N/2 所以 N/2 N/2-1 r)r2 +W2 x2(r)WNr 2=X,(k)+WX2 (k)第4章 快速傅里叶变换(FFT) 则x(n)的DFT为 / 2 1 / 2 1 2 (2 1) 0 0 / 2 1 / 2 1 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 k kr N N r r X k x n W x n W x r W x r W x r W x r W = = − − + = = − − = = = + = + + = +       由于 2 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 − − = = = + = +  