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

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

数加法次数为 ?? ??

N 2N N 2 N 1 2 2 2

由此可见，仅仅经过一次分解，就使运算量减少近一半。

既然这样分解对减少DFT的运算量是有效的，且N=2M,N/2仍然是偶数，故可以对N/2点DFT再作进一步分解。 与第一次分解相同，将x1(r)按奇偶分解成两个N/4点

的子序列x3(l)和x4(l),即

x3 (l ) x2 (2l )

x4 (l ) x1 (2l 1)

N l 0, 1, , 1 4