第4章 快速傅里叶变换(FFT)当 N 1 时，N(N-1)≈N2。由上述可见，N点DFT的乘法和加法运算次数均为N2。当N较大时，运算量相 当可观。例如N=1024时，N2=1 048 576。这对于实时信
号处理来说，必将对处理设备的计算速度提出难以实现的要求。所以，必须减少其运算量，才能使DFT在各 种科学和工程计算中得到应用。? 如前所述，N点DFT的复乘次数等于N2。显然，把 N点DFT分解为几个较短的DFT,可使乘法次数大大减 少。另外，旋转因子具有明显的周期性和对称性。其 周期性表现为 ?? ??m WN lN e j 2π ( m lN ) N j 2π m N
e
m WN
(4.2.2)