1、FFT介绍
快速傅里叶变换：理解为实现DFT的快速算法，只是单纯的让数字信号处理器DSP跑DFT算法更快点。
傅里叶变换将信号转换到频域上去分析，学术研究可以用连续信号，模拟域的傅里叶变换去分析问题，但是计算机是无法分析在模拟域分析问题。DFT将频域离散分析问题，一般书本上都会对FFT做描述，为什么有FFT产生，最重要的原因的就是运算量，书本上对DFT的运算复杂度都作了详细介绍。
2、FFT算法核心
FFT实现的核心在于旋转因子具有的性质：
1）周期性：
2）对称性:
和
3）可约性:
和 
对照下图理解以上3个性质是理解FFT抽取过程，旋转因子变化的原理。以8点DFT举例，
连续对应下图，N=8；
现在只关心旋转因子就可以。以k=1为例
1）周期性应该比较好理解，直观去看第k*n点，与转了k圈或是n圈的重合。
2）对称性从图上很容易看出，点1与点5满足第一个公式，点1与点7共轭对称满足
3）可约性从旋转因子的公式容易得出
上述性质就是实现蝶形运算的关键。
FFT实现另一个的关键点：将长序列分解成短序列计算
每一级运算都是2点DFT，经过3级运算最终得到8点DFT结果。
这是利用理论公式计算出来的结果
以下图片摘抄网页，公式敲起来太麻烦了。
注意:每级奇偶抽取是针对相对应子序列的自然顺序的奇偶，不是n的奇偶。例如第二次抽取x(2),x(6)是对应子序列的奇数项。
