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

第4章 快速傅里叶变换(FFT)

4.2 基2FFT算法?4.2.1 直接计算DFT的特点及减少运算量的基本途径?有限长序列x(n)的N点DFT为

????

kn X (k ) x(n)WN n 0

N 1

k 0, 1, , N 1 (4.2.1)

考虑x(n)为复数序列的一般情况，对某一个k值， 直接按(4.2.1)式计算X(k)的1个值需要N次复数乘法和 (N-1)次复数加法。因此，计算X(k)的所有N个值，共 需N2次复数乘法和N(N-1)次复数加法运算。