测试技术(5) 王伯雄
测试技术(5) 王伯雄
六、快速傅里叶变换(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 − =
◆快速傅里叶变换(FFT, Fast Fourier Transform)算法的本质:充分利用因子W的周 q期性和对称性。 对称性:W2=-W (4204) 周期性:W"=W (4205) ◆FT算法的基本思想:避免运算中的重复运算 将长序列的DF分割为短序列的DF的线性组 合,从而达到整体降低运算量的目的。 ◆效果:使原来的N点DF的乘法计算量从N次 降至为N/2og厶N次,如N=1024,则计算量现 在为5120次,仅为原计算量的488%
快速傅里叶变换(FFT，Fast Fourier Transform)算法的本质:充分利用因子WN的周 期性和对称性。 ◼ 对称性： ◼ 周期性： FFT算法的基本思想：避免运算中的重复运算， 将长序列的DFT分割为短序列的DFT的线性组 合，从而达到整体降低运算量的目的。 效果：使原来的N点DFT的乘法计算量从N2次 降至为N/2log2N次，如N=1024，则计算量现 在为5120次，仅为原计算量的4.88% 。 nk N N nk WN = −W + 2 nk N N nk WN = W + （4.204） （4.205）
◆时间抽取基2算法 对式(4202),令N=2M将X(n)序列分割成 长度各为N2的奇序列和偶序列,即令n=2r 和n=2r+1,「=0,1,…N2-1则式(4202) 重写为、 k)=∑x(2)W3+∑ 2 1 x(2r+1)W(2k r=0 N ∑x(2)形+∑x(2r+1 4.206) r=0 r=0 2丌 e 式中 W 这是因为
时间抽取基2算法 对式(4.202)，令N=2M ,将x(n)序列分割成 长度各为N/2的奇序列和偶序列，即令n=2r 和n=2r+1,，r=0,1, …,N/2-1则式（4.202） 重写为 式中 这是因为( ) ( ) ( ) ( ) ( ) ( ) − = − = − = − = + = + + = + + 1 2 2 1 2 2 1 2 1 2 2 2 1 2 2 1 2 2 1 N r o r k N N r o k N r k N N r o N r o r N r k N x r W W x r W X k x r W x r W k （4.206） ( ) N N j j N W e e 4 2 2 2 − − = = ( ) 2 2 2 2 2 2 N N j N j WN = e = e = W − −
令 x(2r)w k=0.1 (4.207) Blk x(2r+1)W k=01,…,Ny-1 (4208) r=0 则式(4206)可改写为 X(k)=a(k)+Wrb(k) =0.1.…N (4209) 而 A2+k|=4(k)B|+k|=B(k) 因此将式(4.209)完整地写成 X(k)=A(k)+WkB(k k=0.1.2,N x|k+|=4(k)+W2B(k) (4210) 2
令 则式（4.206）可改写为 而 因此将式（4.209）完整地写成 ( ) ( ) − = = = − 1 2 2 1 2 2 0,1, N r o r k N A k x r W k N ( ) ( ) − = = + = − 1 2 2 1 2 2 1 0,1, , N r o r k N B k x r W k N （4.207） （4.208） X (k ) = A(k )+W B(k ) k = 0,1, N −1 k N （4.209） ( ) k B(k ) N k A k B N A = = + + 2 2 ( ) ( ) ( ) ( ) ( ) 1 2 0,1,2, 2 2 = − = + + = + + k N A k W B k N X k X k A k W B k N k N k N （4.210）