源：FFT初解
一．前言
首先申明俺不是一个算法工程师，俺是一个底层驱动工程师，有人会发问一个底层驱动工程师需要这个吗？但是我不幸的告诉你，确实是需要的，不过我们不要像算法工程师那样搞得很精通，但是还是需要去了解这是个什么东西。说实话，这个东西在大学时候学过，还好好的去理解了一样，不过到现在忘的差不多了，这愈发的让我明白一句话，好记性不如烂笔头，如果以前有好好记录的好习惯，那现在只要把以前的东西拿出来看看再印证一下就可以了。不过历史不可以如果。为了不让明天继续懊悔今天，在这里记录下本人学习的一些记录。
二．FFT的数学基础
FFT是什么，额，说白了就是一种时域和频域变换的手段。什么是时域什么是频域，额，你google吧，鄙视百度！
这里说明一下，相比较FFT而言，我们更加关心离散傅里叶变换(DTF),因为我们底层驱动工程师面对的是一个一个离散的数据。也许大家还是对FFT的变换的概念还不理解，那我们举个例子来说吧：
1、AD在一个1Hz正弦波周期采集了1024个数据(即你的采样频率为1024Hz)，从时域上看1s内采集了1024数据，那1024个数据做1024点的FFT变换。我们以数据的下标作为横轴，而数据的值作为纵轴，你会发现第一个点的值最大，我们可以从该值计算出我们被采样的频率为1Hz，值是这样算出来的1024(Hz)/1024*1 = 1Hz,如果最大的值点是第8个点，那被采样频率是8Hz。不过要满足乃奎斯定律，即采样频率大于被采样频率的两倍。
为什么会有东西出现呢，主要是时域的信号好采样，至于频域的信号难以采样，于是傅里叶这个天才就发明了这个东东，不过这可是现代数字信号处理的基础。
闲话不说了，还是来看DFT的数学基础(下面的内容不少拷贝wiki的)：
...
8点快速傅里叶变换
主要是蝶形算法
FFT算法图