测试技术(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）
又因为Wx=1,因此最终可得 X(k)=A(k)+WFB(k) A(k)-WkB(k) k=0,1,2,… (2.211) A(0) X(0) X(1) A(2 X(2) A(3) B(0) X(4) B(1) X(5) B(2) X(6) B(3) X(7) 图498分割一次后的A(k)、B(k)及X(k)之间的关系(N=8)
又因为 2 = −1 ，因此最终可得 N WN ( ) ( ) ( ) ( ) ( ) 1 2 0,1,2, 2 = − = − + = + k N A k W B k N X k X k A k W B k k N k N （2.211） 图4.98 分割一次后的A(k)、B(k)及X(k)之间的关系（N=8）
按照上述思路继续对A(k)和B(k)作奇偶序列分解 令r=2,r=2+1,|=0,1,…N4-1,则有: A(k)=∑x(41)W4+∑x(41+2m241 =0 ∑x(4)W+W∑x(41+2)w =0 令 C()=∑x(4)W k=0.1..N (4212) % D(k)=∑x(4C+2) k=0.1.… 4.213) A(k=c(k)+wk dth )k=01,…M (4214) N Alk =C(k)-Wk∠D(k)k=0,1 1(4215)
按照上述思路继续对A(k)和B(k)作奇偶序列分解。 令r=2l，r=2l+1，l=0,1, …,N/4-1，则有： 令 则 ( ) ( ) ( ) ( ) ( ) ( ) − = − = − = + − = = + + = + + 1 4 0 2 4 1 2 0 4 1 4 0 2 1 2 1 4 0 2 2 4 4 2 4 4 2 N l l k N k N N l l k N N l l k N N l l k N x l W W x l W A k x l W x l W ( ) ( ) 1 4 4 0,1, , 4 1 4 = = − − = C k x W k k N N N o （4.212） ( ) ( ) 1 4 4 2 0,1, , 4 1 4 = + = − − = D k x W k k N N N o （4.213） ( ) ( ) ( ) 1 4 0,1, 2 A k = C k +W D h k = N − k N （4.214） ( ) ( ) 1 4 0,1, 4 2 = − = − + C k W D k k N N A k k N （4.215）
同样,令 E(k)=∑x(4+1)W k=0.1 4.216) Flk x(4C+3)W ck k=0,1,… (4217) 则有: B(k)=E(k)+WF(k)k=0,1,… 4218) k+ N\=E( )-WkF(k)k=0,…y4-1 4.219)
同样，令 则有：( ) ( ) 1 4 4 1 0,1, 4 1 4 = + = − −= E k x W k k N N N o ( ) ( ) 1 4 4 3 0,1, 4 1 4 = + = − −= F k x W k k N N N o （4.216 ） （4.217 ） ( ) ( ) ( ) 1 4 0,1, 2 B k = E k + W F k k = N − kN （4.218 ） ( ) ( ) 1 4 0,1, 4 2 = − = − + E k W F k k N N B k kN （4.219 ）
对于一个N=8的序列,此时的C(k)、D(k)、E(k)和 F(k)均已为两点的序列,无需再分,此时有 x(0) C(0) A(0) X(0) (4) C(1) A(1) X(1) D(0) A(2) X(2) x(6) D(1) A(3) ECo) WR 1B(0) X(3) x(1) X(4) x(5) E(1) B(1)W8 F(0) b(2)W X(5) F(1)W X(6) x(7) B(3)W X(7) 图499FFT时间抽取算法信号流图(N=8) C(0)=x(0)+x(4),E(0)=x(1)+x(5) C(1)=x(0)-x(4),E(1)=x(1)-x(5) D(O)=x(2)+x(6),F(0)=X(3)+x(7) D(1)=x(2)-x(6),F(1)=x(3)-x(7)
对于一个N=8的序列，此时的C(k)、D(k)、E(k)和 F(k)均已为两点的序列，无需再分，此时有 图4.99 FFT时间抽取算法信号流图（N=8） C(0)=x(0)+x(4)，E(0)=x(1)+x(5) C(1)=x(0)-x(4)，E(1)=x(1)-x(5) D(0)=x(2)+x(6)，F(0)=x(3)+x(7) D(1)=x(2)-x(6)，F(1)=x(3)-x(7)
在F「T的整个运算过程中,每两个等式的运算过程 可以用一个形似蝴蝶结的“X形结构图来表示,八 个等式对应于四个蝶形结构,因此这种信号流程图 称为F「的蝶形运算流程图,将这种运算的基本单 元称为蝶形运算单元。 p xm(q) 图4100蝶形运算单元
在FFT的整个运算过程中，每两个等式的运算过程 可以用一个形似蝴蝶结的“X”形结构图来表示，八 个等式对应于四个蝶形结构，因此这种信号流程图 称为FFT的蝶形运算流程图，将这种运算的基本单 元称为蝶形运算单元。 图4.100 蝶形运算单元