准零基础搞懂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”，由于我在英国上的学，不知道中文这个叫什么，读者可以百度      下。