第4章快速傅立叶变换(FFT) A(0) 4(0) 4(0) 4(0) x(0) X0) 4(1) A(1) A(1) x(4) W& X1) A(2) A(2) A(2) x(2) n X2) A(3) A3) A(3) x(6 w& 你 X3) A(4) A(4) A(4) x(1) X4) A(5) A(5) A(5) x(5) w& X5) A(6) A(6) A(6 x(3) wx X6) A(7) A(7) A(7) x(7) A7) w& wk X(T) 图4.2.4N点DT一FFT运算流图N=8)
图4.2.4 N点DIT―FFT运算流图(N=8) W N 0 W N 1 W N 2 W N 3 W N 0 W N 2 W N 0 W N 2 W N 0 W N 0 W N 0 W N 0 x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0) A(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) 4.2.3 DIT一FFT算法与直接计算DFT运算量的比较 )每一级运算都需要N/2次复数乘和N次复数加（每个蝶 形需要两次复数加法)。所以，M级运算总共需要的复 数乘次数为 N N CM= .M= 2 2 C4=N·M=Nlog2N 例如，N=210=1024时 N2 1048576 204.8 倍 (N/2)log,N 5120
4.2.3 DIT―FFT算法与直接计算DFT运算量的比较 ⚫ 每一级运算都需要N/2次复数乘和N次复数加(每个蝶 形需要两次复数加法)。所以，M级运算总共需要的复 数乘次数为 2 2 2 2 log log = = = = M A N N C M N C N M N N 复数加次数为 例如，N=2 10=1024时 2 2 1048576 204.8 ( / 2)log 5120 N N N = = 第4章 快速傅立叶变换（FFT） 倍
第4章 快速傅立叶变换(FFT) 1024 直接计算 (000江人)效大 512 256 FFT算法 128 64128256 512 1024 N(取样点数) 图4.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线
图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线 第4章 快速傅立叶变换（FFT）
L=1时 W状=WW4=W J=0 L=2时 WR-WN/2-W3 J=0,1 L=3时 W状-W入=W J=0,1,2,3 对N=2M的一般情况，第L级的旋转因子为 WW=W,J=0,1,2,24-1-1 2=2M×2-M=N.2-M W=W24w=W2w,J=0,2,21-1 p=J.2M-L
对N=2M的一般情况，第L级的旋转因子为 0, 1, 2, 3 3 0, 1 2 0 1 2 / 2 2 / 4 2 = = = = = = = = = = = = W W W J L W W W J L W W W J L J J N p N J J N p N J J N p N L L L 时 时 时 2 1 2 0 1 2 2 1 2 , , , , , M L L M P J J L N N N M L W W W J p J − − − − = = = − = 1 2 , 0,1,2, ,2 1 2 2 2 2 − − − = = − = = L p J L N L M L M L M W W J N
4.编程思想及程序框图 开后 送入x(n),M 三层循环的功能是： N=2 最外层（大）循环完成M次迭代过程即 L=1,2,M级，即每次循环为一级。 L=1M 中间（中）循环完成在一级中共有B个不 B←24-1 同因子WNk对应2ML个蝶形运算，同一个旋 J=0B-1 P=M-LJ 转因子对应着相隔2L点的2ML个蝶形。 k=J,N-1,2 最里层（小）循环完成同一个旋转因子 X(k)X(k)+(k+B)W X(k+B)(k)-X(k+B)W 不同蝶形的运算；其循环体为一个蝶形运 算。 输出 图4.2.6DIT一FFT运算和程序框图
4. 编程思想及程序框图 图4.2.6 DIT―FFT运算和程序框图 送 入x(n)，M N＝ 2 M L＝ 1 , M Ｊ＝ 0 , B－ 1 P＝ 2 M －L J k＝ J , N－ 1 , 2L p N p N X k B X k X k B W X k X k X k B W ( ) ( ) ( ) ( ) ( ) ( ) + − + + + 输 出 B 2 L－ 1 ◼三层循环的功能是： 最外层（大）循环完成M次迭代过程即 L=1,2, .,M 级，即每次循环为一级。 中间（中）循环完成在一级中共有B个不 同因子WN k对应2 M-L个蝶形运算，同一个旋 转因子对应着相隔2 L点的2 M-L个蝶形。 最里层（小）循环完成同一个旋转因子 不同蝶形的运算；其循环体为一个蝶形运 算