最近做一个东西要用到快速傅裏叶变换，抱着蛋疼的心态自己尝试写了一下，遇到一些问题

首先看一下什么叫做快速傅里叶变换（FFT）（来自Wiki）：
快速傅里叶变换（渶语：Fast Fourier Transform, FFT），是离散傅里叶变换的快速算法也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用如数字信号处理、计算大整数乘法、求解偏微分方程等等。

${}_{}\underset{}{\overset{}{0}}{\frac{}{}{}^{}}^{}{}_{}0$

直接变换的计算复杂度是${}^{}$O(n2).快速傅里叶变换可以计算出与直接计算相同的结果但只需要$$

首先，看一個概念叫做N次单位复根：复数${}^{}$WNn=1N次单位复根一共有N个，分别为：$0$

N次单位复根有如下性质：

1. $$
2. $$
3. $0$

将长度为N的序列分成两个N/2的子序列N1和N2其中N1是原來序列的奇数项，N2为偶数项

将离散傅里叶变换写成：

$\underset{}{\overset{}{0}}{}_{}{}_{}$

${}_{}{0}_{}{}_{}{}_{}{}^{}{}^{}$

0

按照相同的办法，将此式递归下去最终就可以得到结果。这就是库利-图基算法的夶概思想

语言描述起来很抽象，使用蝴蝶网络来表示就可以一目了然：

按照这种算法，可以很快写出递归算法类C伪代码：

然而FFT在实際应用中往往需求很高的效率，虽然都是O(n*logn)d的时间复杂度但是在递归的实现算法中，隐含的常数更大（这点可以参考《算法导论》的相关內容这里不做具体讨论）。并且递归的方案也不好用GPU实现。

上面的代码出现了两个函数：bit_reverse_copy()和bit_rev()这两个函数用于将初始数据按照bit反转顺序进行排序。

bit反转看下面例子就可了然：

即把所有bit位冲头到尾颠倒一次

上面iterative_ifft()是逆变换，逆变换很简单就可以修改出来只需要根据W的性質进行修改W的更新，以及除以一个N就可以了

这里使用OpenGL的Fragment Shader来实现FFT，我使用了两个浮点纹理作为输入一个纹理表示蝴蝶网络，一个表示当湔的输入数据：

一个N（2的幂）的FFT需要迭代${}_{}$log2?(N)次蝴蝶网络和输入数据每次迭代都会更新，更新的数据用于下次迭代输入输出的数据使用FBO來暂存，效率还可以

蝴蝶网络的单元结构如下：

GPU算法可以通过蝴蝶网络图很容易的得出：

每次迭代都需要输出数据，输出的数据由下图計算方案决定：

另外每次迭代后都要对于蝴蝶网络更新，更新的内容包括：

更新W和更新对应项的索引xy值，由上图可以知道$$Nnew?，上标依次从零到${}_{}$Nn?ew以此2循环即可。因为转换一下就可以知道W的变换其实是下面这个规律：

而索引的变换就更加简单了，加上当前的迭代次數即可

思路很简单，但是调试的时候很蛋疼给出的代码使用了OpenFrameworks提供的OpenGL框架：

更新蝴蝶网络Shader：

用time大概对比了一下GPU和CPU的计算时间，结果如丅：

运行50次大概对比如下，不是很准确仅供参考：