快速傅里叶变换(FFT),直接计算DFT的问题及改进的途径,按时间抽取的基2-FFT算法,按频率抽取的基2-FFT算法,快速傅里叶逆变换(IFFT)算法,4.1 引言,DFT在实际应用中很重要: 可以计算信号的频谱、功率谱和线性卷积等。 直接按DFT变换进行计算，当序列长度N很大时，计算量非常大，所需时间会很长。 FFT并不是一种与DFT不同的变换，而是DFT的一种快速计算的算法。,4.2.1 直接计算DFT的问题及改进的途径,DFT的运算量,k=0，N-1,（1）计算一个X(k) 值的运算量,复数乘法次数： N,复数加法次数：N1,（2）计算全部N个X(k) 值的运算量,复数乘法次数：N2,复数加法次数：N(N1),减少运算量的途径,4.2.1 直接计算DFT的问题及改进的途径,主要原理是利用系数 的以下特性对DFT进行分解：,（1）对称性,（2）周期性,（3）可约性,另外，,FFT的基本思想在于, 将原有的N点序列分成两个较短的序列,这两个序列的DFT组合起来,得出原序列的DFT。,4.2.2 时域抽取法基2 FFT基本原理,FFT算法分为两大类,时域抽取法(DIT),频域抽
