数字信号处理-西电第4章(15)

第4章 快速傅里叶变换(FFT)由图4.2.1可见，要完成一个蝶形运算，需要一次复数乘法和两次复数加法运算。由图4.2.2容易看出，经过 一次分解后，计算1个N点DFT共需要计算两个N/2点DFT 和N/2个蝶形运算。而计算一个N/2点DFT需要(N/2)2次复 数乘法和N/2(N/2-1)次复数加法。所以，按图4.2.2计算N

点DFT时，总共需要的复数乘法次数为

N N N ( N 1) 2 2 2 2 2

N2 2 N 1