西西河

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

共:💬32 🌺13
全看分页树展 · 主题 跟帖
家园 关于FFT

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

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

是我笨的缘故。直到大概七年前,不经意看到一个对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。。。强推!

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河