主题：傅立叶变换(FFT)是在大学那门课讲的？ -- HAL

讲老实话，我从大学一年级就学了它，一直到现在快二十年了，一直在

用它。但是国内的教材也好，书籍也好，总是把我搞得晕头转向，可能

是我笨的缘故。直到大概七年前，不经意看到一个对FFT的介绍，才恍

然大悟，原来是这样！什么蝴蝶图，什么倒置，什么级数，什么复变，

都见鬼去吧。

简单讲，这个算法就是：

FFT_{N}(k,f) = \sum_{n=0}^{N-1}f(n)e^{-i 2\pi kn/N }

= \sum_{n=0}^{N/2-1}f(n)e^{-i 2\pi kn/N } +

\sum_{n=N/2}^{N-1}f(n)e^{-i 2\pi kn/N }

= \sum_{n=0}^{N/2-1}f(n)e^{-i 2\pi kn/N } +

\sum_{n=0}^{N/2-1}f(n+N/2)e^{-i 2\pi k(n+N/2)/N }

= \sum_{n=0}^{N/2-1}(f(n)+f(n+N/2)e^{-i\pi k})e^{-i 2\pi kn /N}

= \sum_{n=0}^{N/2-1}(f(n)+f(n+N/2)})(-1)^{k}{-i 2\pi kn /N}

这是什么？这是两个新的，但是只有原来长度一半的FFT，而这两个又可以进一步这么分下去，于是就有了递归的FFT算法出来了，呵呵呵呵呵

这个网站：

http://www.engineeringproductivitytools.com/stuff/T0001/

让偶真正理解了FFT，各种各样的FFT。。。强推！