则x(n)的DFT X(k)=∑x(n)W=∑x(n)W+∑x(nW n为偶数n为奇数 N/2-1 ∑x(2n)W3+∑x(2x+1)w r=0 N/2-1 N/2-1 ∑x1()V3)+H∑x2()V3) r=0 N/2-1 ∑x()WM2+W∑x()WM2 r=0 X1()+WX2()F,k=0,1,N/2-1则x(n)的DFT: 1 1 1 0 0 0 N N N nk nk nk N N N n n n X k x n W x n W x n W n为偶数 n为奇数 / 2 1 / 2 1 2 2 1 0 0 2 2 1 N N rk r k N N r r x r W x r W / 2 1 / 2 1 2 2 1 2 0 0 N N rk rk k N N N r r x r W W x r W / 2 1 / 2 1 1 / 2 2 / 2 0 0 N N rk k rk N N N r r x r W W x r W 1 2 k X N k W X k r,k 0,1,...N / 2 1