为什么需要FFT

Advertisements

简单的说,为了速度。我们承认DFT很有用,但是我们发现他的速度不是很快,1D的DFT原始算法的时间复杂度是 $O(n^2)$ ,这个可以通过公式观察出来,对于2D的DFT其时间复杂度是 $O(n^4)$ ,这个速度真的很难接受,也就是说,你计算一幅1024×768的图像时,你将等大概。。。大概。。。我也没试过,反正很久。不信的自己去试试。所以找到一种快速方法的方法计算FFT势在必行。 以下为DFT公式
Center      
计算一个4点DFT。计算量如下:
Center 1

如何得到FFT

通过观察DFT公式,我们发现DFT计算每一项 $X[u]$ 的时候都遍历了完整的 $x[n]$ 所以,我们的想法就是能不能通过其他的 $X[u+m]$(m为一个整数,可正可负)得到 $X[u]$ ,也就是充分利用之间的计算结构来构建现在的结果,这种方法就很容易表现成迭代的形式。本文介绍基2的FFT,及离散信号 $x[n]$ 的个数为2的k次方,即如果完整的离散信号中有N个信分量 ${x_1,x_2,x_3….x_N}$ 其中 $N=1<<k$。

数学基础

FFT的数学基础其实就是:

Center 2

Center 3

旋转因子具有以下性质:

Center 4

这些性质使得我们可以利用前面的计算结果来完成出后续的计算。

Center 5

最终算法

Center 6

8-FFT

废话不多说,和上面一样:

计算过程为:

Center 7

结果为:

Center 8

$2^n$-FFT

同理,推广到2^n,可以得到类似的结果,不过我们发现,为了使输出结果为顺序结果,输入的顺序经过了一系列的调整,而且每一步WN的幂次参数也是变化,我们必须得到其变化规律才能更好的编写程序:

观察WN的变化规律为:

Center 9

节点距离(设为z)就是从WN的0次幂开始连续加到$W_N$的z次幂。然后间隔为z个式子,再次从0次幂加到z次。重复以上过程:

Center 10

例如第二级,间隔z=2,节点为实心黑色点,节点0,1,不做操作,节点$2W_8^0$,节点 $3W_8^2$ ,节点4,5不做操作。。

其内在规律就是节点i是否乘以WN:

节点 $i*W_N^{step}$

step每次增加的数量由当前的所在的计算级决定

输入参数重新排序

Center 11

i行表示数组下标,蓝色数字表示实际数据:其内在规律就是,下标为偶数的将被映射到自己本身下标的 $\frac{1}{2}$ 处,下表为奇数时被映射到数组后半段 $(size_{n/2})$ 的(下标-1)$\frac{1}{2}$处,将排列后的数据分为前后两个部分,递归次过程,直到只有两个元素。则停止。过程如下:

Center 12
Center 13
Center 14
Center 15
Center 16

观察算法

观察至此,我们已经基本把FFT蝶形算法的所有特征都搞定了,接下来就是使用代码来实现了。

Center 17

实现代码

测试结果

Center 18
Center 19

其中时间都为s,FFT优势明显

最后修改日期:2019年3月14日

说点什么

avatar
  Subscribe  
提醒