4.2快速付立叶变换(FFT) 计算DFT的运算次数按N2快速增长。设N可以被2整除， 把x(n)分成两个子序列x1(n)和x2(n), x(n)=[x(0),x(2),…x(W-2)] n=0,…,(N-1)/2 x2(n)=[x(1),x(3),…(N-1)] 则原序列的DFT可写成（设N1=N/2): X(m)=x(0)W8+x(2)W2m+…+x(N-2)W-2》m+ +x(1)W+x(3)Wm+...+x(N-1)WW-Im =Ow8+w%++x1(N1-Dw-m+ +[xO)W9+x2④w双++x2(W1-1)w-m 10 10 4.2 快速付立叶变换(FFT) • 计算DFT的运算次数按N 2快速增长。设N可以被2整除， 把x(n)分成两个子序列x1(n)和x2(n)， 则原序列的DFT可写成(设N1=N/2)： 1 2 ( ) [ (0), (2), ( 2)] 0, ,( 1) / 2 ( ) [ (1), (3), ( 1)] x n x x x N n N x n x x N = −   = − = −  0 2 ( 2 3 ( 1) ( ) (0) (2) ( 2) (1) (3) ( 1) m N m N N N m m N m N N N X m x W x W x N W x W x W x N W − − = + + + − + + + + + − ） N m N m N N m N N m N m N N W x W x W x N W x W x W x N W ( 1) 2 2 1 0 2 ( 1) 1 1 1 0 1 1 1 1 1 1 1 1 1 [ (0) (1) ( 1) (0) (1) ( 1) − − + + + + − = + + + − +  