DFTLX,(1) X,(1) DFT 图4.2.3N点DFT的第二次时域抽取分解图(N=8) A(0) xX(1) X(2) X(5) 图4.2.4N点DI一FT运算流图(N=8) 423 DIT-FFT算法与直接计算DFT运算量的比较 1、 DIT-FFT算法的运算量 由 DIT-FFT算法的分解过程可见,N=2M时,其运算流图应有M级蝶形, 每一级都由N2次复数城和N次复数加(每个蝶形需要两次复数加),所以,M 级运算总共需要的复数乘次数为 N C(2 复数加次数为 CA(2)=NM=Nlog? 2、根据定义直接计算的运算量 直接计算N点DFT需N2次复数乘,N(N-1)次复数加。当N>>1时,N/4点 DFT W N 1 2 W N 1 2 W N 0 W N 1 W N 2 W N 3 X1 (0) X1 (1) X1 (2) X1 (3) X2 (0) X2 (1) X2 (2) X2 (3) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) x(0) X3 (0) X3 (1) X4 (0) X4 (1) x(4) x(2) x(6) x(1) x(5) x(3) x(7) N/4点 DFT N/4点 DFT N/4点 DFT W N 0 2 W N 0 2 图 4.2.3 N 点 DFT 的第二次时域抽取分解图(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.2.4 N 点 DIT―FFT 运算流图(N=8) 4.2.3 DIT-FFT 算法与直接计算 DFT 运算量的比较 1、DIT-FFT 算法的运算量 由 DIT-FFT 算法的分解过程可见， 2 M N = 时，其运算流图应有 M 级蝶形， 每一级都由 N/2 次复数城和 N 次复数加（每个蝶形需要两次复数加），所以，M 级运算总共需要的复数乘次数为 ( ) 2 2 log 2 2 N M N N C M =  = 复数加次数为 ( ) 2 2 logN C N M N A =  = 2、根据定义直接计算的运算量 直接计算 N 点 DFT 需 2 N 次复数乘， N N( −1) 次复数加。当 N>>1 时