首页 > 代码库 > 准零基础搞懂FFT快速傅里叶变换及其实现程序(二)

准零基础搞懂FFT快速傅里叶变换及其实现程序(二)

准零基础搞懂FFT快速傅里叶变换及其实现程序(二)

上一篇文章我们了解了DFT的原理,FFT是基于DFT的更适合计算机运算的算法,本文我们就正式开始学习FFT的原理。

首先我么先来宏观的看一下FFT。如果我们把整个FFT的算法看成一个黑盒子的话,那么它的输入就是时间波形信号,比如声音波形(横轴为时间,纵轴为振幅)。外什么FFT要比DFT速度更快呢?下面(图1)解释了FFT和DFT的(对于计算机的)算法复杂度

FFT N Log(N) Operations

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