文档介绍:FFT快速傅里叶变换(蝶形算法)详解本章目录直接计算DFT的问题及改进的途径按的基2-FFT算法按频率抽取的基2-FFT算法快速傅里叶逆变换(IFFT):可以计算信号的频谱、功率谱和线性卷积等。直接按DFT变换进行计算,当序列长度N很大时,计算量非常大,所需时间会很长。FFT并不是一种与DFT不同的变换,而是DFT的一种快速计算的算法。(n)长度为N点,其DFT为k=0,,…,N-1(1)计算一个X(k)值的运算量复数乘法次数:N复数加法次数:N-(2)计算全部N个X(k)值的运算量复数乘法次数:N2复数加法次数:N(N-1)(3)对应的实数运算量5一次复数乘法:4次实数乘法2次实数加法+一个X(k):4N次实数乘法+2N+2(N-1)=2(2N-1)次实数加法所以整个N点DFT运算共需要:N×2(2N-1)=2N(2N-1)实数乘法次数:4N2实数加法次数:6DFT运算量的结论N点DFT的复数乘法次数举例结论:当N很大时,其运算量很大,对实时性很强的信号处理来说,要求计算速度快,因此需要改进DFT的计算方法,以大大减少运算次数。:(1)对称性(2)周期性(3)可约性另外,8大家有疑问的,可以询问和交流可以互相讨论下,-FFT算法算法原理按时间抽取基-2FFT算法与直接计算DFT运算量的比较按时间抽取的FFT算法的特点按时间抽取FFT算法的其它形式流程图10