1)选择L≥N+M-1,且L=2m 2)形成L点序列g(m) (3N 8(n)=4 W2x(n)0snsN-I 0 N<n<L-1 系数 A W n2/2 Cn1=AmnW(m2=AwWn2WwW2A)=CnDn D=W WA=W WWA=WD D=WA C=1 求其L点FFT: (L/2*log2L) G()=FIg(m)=∑g(m)0≤r5L-12 2 ( ) 0 1 ( ) 0 1 n n g n A W x n n N N n L             1 2 0 ( ) [ ( )] ( ) L j rn L n G r FFT g n g n e        0  r  L 1 L  N  M 1 2 m 1) 选择 ，且 L  2) 形成L点序列g(n)： (3N) 求其L点FFT： ( L/2*log2L) 2 n n / 2 Cn A W  系数  2 2 ( 1) ( 1) / 2 / 2 1/ 2 1 1 ( ) n n n n n Cn A W A W W W A CnDn           1/ 2 1 1 1/ 2 1 1 n n Dn W W A W W W A WDn         1/ 2 1 0 0 D W A C 1   