准零基础搞懂FFT快速傅里叶变换及其实现程序（二）
上一篇文章我们了解了DFT的原理，FFT是基于DFT的更适合计算机运算的算法，本文我们就正式开始学习FFT的原理。
首先我么先来宏观的看一下FFT。如果我们把整个FFT的算法看成一个黑盒子的话，那么它的输入就是时间波形信号，比如声音波形（横轴为时间，纵轴为振幅）。外什么FFT要比DFT速度更快呢？下面（图1）解释了FFT和DFT的（对于计算机的）算法复杂度
图1
从上面的数学表达式可以看出，一个1024采样点的FFT比DFT块了102.4倍。如果傅里叶变换的数量级更大，FFT的速度优势会更明显。这就是为什么要发明FFT的意义。
要理解FFT，我们大致分为以下几步：
1. 学习“Danielson-Lanczos Lemma”,期间需用到要有些略微复杂的数学公式，但是这是FFT非常重要的一部分内容、
2.理解 “twiddle factor”。关于旋转因子，在上一篇DFT的文章中已经提到。
3.掌握“Butterfly Diagram”。蝶形运算，这也是FFT最具特点的一个算法。
4.掌握“reverse bit pattern”，由于我在英国上的学，不知道中文这个叫什么，读者可以百度 下。
准零基础搞懂FFT快速傅里叶变换及其实现程序（二）,布布扣,bubuko.com
原文：http://www.cnblogs.com/oshushu/p/3819129.html