第4意快速傅里叶夜换(H 42基2FFT算法 42.1直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为 X(k)=∑x(m)WM,k=0,1…,N (4.2.1) 考虑x(n)为复数序列的一般情况,对某一个k值, 直接按(4,2.1)式计算X(k)值需要N次复数乘法、(N-1)次 复数加法。第4章 快速傅里叶变换(FFT) 4.2 基2FFT算法 4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为 考虑x(n)为复数序列的一般情况，对某一个k值， 直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次 复数加法。 1 0 ( ) ( ) , 0,1, , 1 N kn N n X k x n W k N − = = =  −  (4.2.1)