快速傅立叶变换(FFT)算法(原来这就是蝶形变换) | 您所在的位置:网站首页 › 快速傅立叶变换例题 › 快速傅立叶变换(FFT)算法(原来这就是蝶形变换) |
快速傅立叶变换(FFT)算法(原来这就是蝶形变换)
为了实现FFT的海面模拟,不得不先撸个FFT算法实现。 离散傅立叶变换(DFT)学习FFT之前,首先要先了解什么是DFT,我们都知道傅立叶变换是将时域转换为频域。但是我们计算机是没办法处理连续的点,因此就有了离散傅立叶变换DFT。 标准DFT公式: 我们令: W的一些性质 证明:
证明方法同上。 快速傅立叶变换(FFT) 我们将X(k)按照奇偶组合,在 因为 即: 我们令
可得 我们这里发现F,G为X的递归函数。
然后计算
根据以上公式: 我们发现想要求
我们令N=4,这时候出现了一幅熟悉的图,4-point FFT蝴蝶变换图: 说实话,我第一次看这个看了半天没看懂,就像瞎比划出来的东西,然而,我们只要举个例子就明白了: 我们首先计算k=0的情况:
其中 所以我们的
首先公式:
过程如下图所示(其中
下面两条公式:
图解为: 由于我们求出 到这里,就是我们标准的傅立叶变换了,我们的算法复杂度从 bitreverse算法 然而,我们的FFT还可以使用非递归的版本,如我们的4-point FFT计算X[0],X[1],X[2],X[3]最后对应的输入为x[0],x[2],x[1],x[3]。 再看8-point FFT计算过程x的位置变化: 0 1 2 3 4 5 6 7 0 2 4 6 1 3 5 7 0 4 2 6 1 5 3 7 bitreverse算法则是从中发现了x[i]在几号位,只要将i转化为 所以我们的FFT便可以写成迭代的版本了(即上面蝶形变换图从左往右推)。贴上代码: //其中a为x[i],omg为WNk void fft(cp *a, cp *omg){ int lim = 0; while((1 > j) & 1) t |= (1 |
CopyRight 2018-2019 实验室设备网 版权所有 |