数字信号处理(五)快速傅里叶变换FFT的由来基2FFT算法IDFT的快速算法
FFT的由来DFT的计算量因此当N比较大时，计算量太大，所以在快速傅里叶变换出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的降低运算量的途径把N点DFT分解为几个较短的DDFT，可使乘法次数大大减少，另外，利用旋转因子WNmW_N^mWNm的周期性、对称性和可约性来减少DFT的运算次数WNm+lN=e−j2πN(m+lN)=e−j2πN(m)<−周期性W_N^{m+lN}=e^{-j\frac{2\pi}N(m+lN)}=e^{-j\frac{2\pi}N(m)}
