大家好，我是通信M班长，热爱分享通信与互联网技术。
Fast Fourier Transform (FFT)，快速傅里叶变换。
在FFT之前，我们一定知道离散傅里叶变换Discrete Fourier Transform (DFT)，DFT是一种傅里叶变换，在时域和频域上都呈离散的形式。
算法复杂度
DFT由于在时域和频域上都是离散的形式，那么很适合用计算机去处理。但是DFT的算法法复杂度达到了Ο(n^2)，我们取n=1024，那么计算DFT需要1048576即一百多万次复数乘法运算。在实际的处理过程中，会遇到更大的N，运算量将异常的大，很难满足实际的信号处理需求。
快速算法
快速傅里叶变换(FFT)是序列离散傅里叶变换DFT的快速算法,它简化了DFT的运算过程。FFT的算法复杂度为O(nlog n)}，在实践中，计算时间可减少几个数量级。
快速傅里叶变换被广泛地应用于工程、科学和数学领域，基本思想是1965年提出的。1994年，Gilbert Strang ，将FFT描述为"我们一生中最重要的数值算法"；FFT并被IEEE"科学与工程计算"杂志列入20世纪前10大算法。
库利-图基FFT算法
我们大部分教材上介绍的都是库利-图基FFT算法，它的主要思想是把输入序列在时域奇偶顺序分组，然后再利用对称性、周期性质简化运算。也称为时域抽取的FFT算法。
与此对应的另一种办法是在频域按奇偶顺序分组，称为桑德-图基算法。
从FFT算法诞生至今，各种改进或派生的算法层出不穷。例如：Prime-factor FFT algorithm, Bruun's FFT algorithm, Rader's FFT algorithm, Bluestein's FFT algorithm, and Hexagonal Fast Fourier Transform。
感兴趣的读者，可以下载相关论文或者搜索学习。
如果你喜欢班长的回答，欢迎您在评论区留言讨论，为文章点赞哦！ |
