快速付立叶变换(FFT) ·设它们的傅立叶变换分别为X1(m)和X2(m),其周 期为N1=NW2: X(om-∑x0m哪，；m空既 N-1 n=0 =0 则xn)的傅立叶变换X(m)可表为： X(m)=X(m)+WwX2(m)m=0,1,…,N-1 如果N=8,则N1=4,故X(m)周期是8，而X1(m)和X2(m) 周期是4，即X1(4)=X1(0),X1(5)=X1(1),.。依次 取m=0,1,.7,上式对应于右方的运算图。 11
11 快速付立叶变换(FFT) • 设它们的傅立叶变换分别为X1(m)和X2(m)，其周 期为N1=N/2： 则x(n)的傅立叶变换X(m)可表为： 如果N=8,则N1=4, 故X(m)周期是8 ,而X1(m)和X2(m) 周期是4, 即X1(4)=X1(0), X1(5)=X1(1),… 。依次 取m=0,1,…7，上式对应于右方的运算图。 1 2 ( ) ( ) ( ) 0,1, , 1 m X m X m W X m m N = + = − N 1 1 1 1 1 0 ( ) ( ) ; N mn N n X m x n W − = = − = = 1 0 2 2 1 1 ( ) ( ) N n m n n WN X m x
快速付立叶变换(FFT) X[0=X2] X]=X14] X.O] 4 X[11=XI3] X[山=X] X山 21 X1201=X1z2] X[21=XI6] X2 w -(61 X21=X12z3] Xd[3]=X[] X3] X21f0]=X2[2] 7 Xz0=X24] 1w4X4 X21I1]=X23] X2I=X25] X{5] X2z01=X2z2] Xz[2]=X2I6] W6 X6创 [7月 X221]=X223] x23]=X2[7] X(7 图4.2.1 对N=8的FFT流程 12
12 快速付立叶变换(FFT)
快速付立叶变换(FFT) X1(m)和X2(m)是N1点的DFT,它们的计算又可 以用类似方法化为两个更短的N2=N1/2点的DFT, 一直分解下去，直到2为止，这就构成了上述 FFT的全部运算图。 。 粗算其中每一根线条代表一次乘法，线条的合 成点代表一次加法。则每一级要N次乘法和加 法。N=8时，需10g28=3级，故共要24次乘法和 加法。原来要N2=64次。若N=1024,需要10242 次乘法，而用FFT,需分解为log21024=9级，只 需1024×9次乘法，加快了100多倍。 13
13 快速付立叶变换(FFT) • X1(m)和X2(m)是N1点的DFT，它们的计算又可 以用类似方法化为两个更短的N2=N1/2点的DFT, 一直分解下去，直到2为止，这就构成了上述 FFT的全部运算图。 • 粗算其中每一根线条代表一次乘法，线条的合 成点代表一次加法。则每一级要N次乘法和加 法。N=8时，需log28=3级，故共要24次乘法和 加法。原来要N2=64次。若N=1024，需要10242 次乘法，而用FFT, 需分解为log21024=9级，只 需1024×9次乘法，加快了100多倍
快速付立叶变换(FT) 把上述运算次数的估计精确化： (1).每次分解的乘法次数为N,共1og2N次， 乘法次数=N·log2N (2).考虑到蝶形运算，又把乘法次数减半。 在FFT运算图中，基本单元为如右图所示的蝶形结 构，实际上不需要 四次乘法，而只需 r+a 要两次乘法即可完 X,[] 成。 义r+1] -w 14
14 快速付立叶变换(FFT) 把上述运算次数的估计精确化： (1). 每次分解的乘法次数为N，共log2N次， 乘法次数＝N·log2N (2). 考虑到蝶形运算，又把乘法次数减半。 在FFT运算图中，基本单元为如右图所示的蝶形结 构，实际上不需要 四次乘法，而只需 要两次乘法即可完 成。 m WN
蝶形运算节省一半乘法 考虑到 W=e2v;W2=eπ=-1 W+w/2)=W2W=-W 在算X(k)=X()+WX2(k) k=0,1,…,N-1 时，把m和N/2+m两点成组来进行，即构成上图的 蝶形运算，就节省一半乘法 X(m)=X (m)+W"X2 (m) (m=0,…,N/2-1) X(m+N/2)=X,(m)-WX2(m) 15
15 蝶形运算节省一半乘法 考虑到 在算 时，把m和N/2+m两点成组来进行，即构成上图的 蝶形运算，就节省一半乘法 2 / / 2 ( / 2) / 2 ; 1 k j k N N j N N k N N k k N N N N W e W e W W W W − − + = = = − = = − 1 2 ( ) ( ) ( ) 0,1, , 1 k X k X k W X k k N = + = − N 1 2 1 2 ( ) ( ) ( ) ( 0, , / 2 1) ( / 2) ( ) ( ) m N m N X m X m W X m m N X m N X m W X m = + = − + = −