六、快速傅里叶变换(FFT) 离散傅里叶变换的计算公式为: DFT:X(k)=∑x(m)eN=∑x(n)W (4202) n=0 1=0 IDFT:x(n)=1∑X(k)e=∑X(k)Wx (4.203) k: k=0,1,…,N-1n=0,1,…,N-1 式中W ◆N个点的X(k)需做N次复数乘法和N(N-1)次复数加法 而做一次复数乘法需要做四次实数相乘和两次实数 相加,做一次复数加法需要做两次实数相加。 例:N=1024时,则需要总共1,048576次复数乘, 即4194304次实数乘法六、快速傅里叶变换（FFT） 离散傅里叶变换的计算公式为： 式中 N个点的X(k)需做N2次复数乘法和N(N-1)次复数加法。 而做一次复数乘法需要做四次实数相乘和两次实数 相加，做一次复数加法需要做两次实数相加。 例：N=1024时，则需要总共1,048,576次复数乘， 即4,194,304次实数乘法。 ( )  ( )  ( ) − = − = − = = 1 1 2 : N n o n k N N n o n k N j DFT X k x n e x n W  ( )  ( )  ( ) − = − − = = = 1 1 2 1 1 : N k o n k N N k o n k N j X k W N X k e N IDFT x n  k = 0,1,  , N −1 n = 0,1,  , N −1 （4.202） （4.203） N j N W e 2 − =