快速傅里叶变换原理
在一维的傅里叶变换中，算法的复杂度是O(N2)，而在快速傅里叶变换中，算法的复杂度为O(Nlog2N)，因此快速傅里叶变换能够实现更快的计算速度。
快速傅里叶变换基于逐次加倍的方法，其中原始的一维傅里叶变换公式（1）能够写成两个递推的公式（2）、（3）：
其中M=2n=2K，
，且
从递推公式来看，其实快速傅里叶变换的工作原理是，将一个M点的变换分成两个部分来计算，其中奇部和偶部的和能得到F(u)的前M/2个值，而奇部和偶部的差能得到F(u)的后M/2个值。换句话说，对于任意M=2n的离散傅里叶变换计算，可以通过计算M/2个点的值，来计算M个点的DFT，最后从2个单点的DFT出发，递推得到4个单点的DFT、8个单点的DFT，直到M个点的DFT。而二维的傅里叶变换可由连续2次一维傅里叶变换得到。
快速傅里叶变换的代码实现
快速傅里叶变换的算法主要分成两步：
（1）根据M个点的顺序的二进制值进行按位倒序。举个例子，在8点的快速傅里叶变换中，f(1)的顺序是1，原地址写成二进制是001，按照按位倒序，倒序后的新地址值是100，写成十进制是4，即在顺序1号位应该放置f(4)。这种做法其实是完成多次奇偶分组后的结果，将0作为偶分组，1作为奇分组。
（2）蝶形运算。以8点计算来说，蝶形运算如图1所示：
图 1 蝶形运算的图示
其中，在每一次计算后，蝶形运算时的地址增量是2n，其中M=2n+1.
具体的代码实现如图2所示：
图 2 快速傅里叶变换具体步骤的代码实现
而傅里叶逆变换的过程，实际上是在频域中取了共轭之后，再进行快速傅里叶变换并最后除以总点数，即完成傅里叶的逆变换。
