傅里叶变换或者FFT的理论参考：

[1] http://www.dspguide.com/ch12/2.htm

      The Scientist and Engineer's Guide to Digital Signal Processing,   By Steven W. Smith, Ph.D.

[2] http://blog.csdn.net/v_JULY_v/article/details/6196862，可当作[1]的中文参考

[3] 任意一本数字信号处理教材，上面都有详细的推导DCT求解转换为FFT求解的过程

[4] TI文档：基于TMS320C64x+DSP的FFT实现。 使用baidu/google可以搜索到。

另外，FFT的开源代码可参考：

[1] FFTW: http://www.fftw.org/ 最快，最好的开源FFT。

[2] FFTReal: http://ldesoras.free.fr/prod.html#src_fftreal 轻量级FFT算法实现

[3] KISS FFT: http://sourceforge.net/projects/kissfft/ 简单易用的FFT的C语言实现

关于FFT这里只想提到两点：

（1）DFT变换对的表达式（必须记住）

          —— 称旋转因子

（2）FFT用途——目标只有一个，加速DFT的计算效率。

DFT计算X(k)需要N^2次复数乘法和N(N-1)次复数加法；FFT将N^2的计算量降为。

“FFT其实是很难的东西，即使常年在这个领域下打拼的科学家也未必能很好的写出FFT的算法。”——摘自参考上面提供的参考文献[1]

因此，我们不必太过纠结于细节，当明白FFT理论后，将已有的算法挪过来用就OK了，不必为闭着教材写不出FFT而郁闷不堪。

FFT的BASIC程序伪代码如下：

IFFT的BASIC程序伪代码如下（IFFT通过调用FFT计算）：

FFT算法的流程图如下图，总结为3过程3循环：

（1）3过程：单点时域分解（倒位序过程） + 单点时域计算单点频谱 + 频域合成

（2）3循环：外循环——分解次数，中循环——sub-DFT运算，内循环——2点蝶形算法

分解过程或者说倒位序的获得参考下图理解：

下面为本人使用C语言实现的FFT及IFFT算法实例，能计算任意以2为对数底的采样点数的FFT，算法参考上面给的流程图。