基本理论
FFT算法的基本概念
离散傅立叶变换（DFT）是信号分析与处理中的一种重要的变换。DFT 的计算，需要作 N^2次复数乘法运算和 N（N－1）次复数加法运算，当N较大时，计算量太大，为了快速计算 DFT，近半个世纪以来，人们对离散傅立叶变换的计算进行了大量的研究，提出了很多有效的快速计算 DFT 的方法。这些算法，称之为快速傅立叶变换（Fast Fourier Transform，FFT）。快速博里叶变换并不是与DF T 不同的另外一种变换，而是为减少 DFT 计算次数的一种快速有效的算法。其突出的优点在于能快速高效地和比较精确地完成 DFT 的计算。
离散傅里叶变换（DFT）
随着科学技术的进步，人们越来越正视频率分析技术的发展与应用。以前要进行一次频率分析，其计算的工作量大的惊人。现在，电子计算机的飞速发展使得计算的速度加快。但是，电子计算机不可能对连续的信号进行处理，它只能处理有限的离散数据。为了便于利用电子计算机进行傅立叶级数与傅立叶积分交换的运算，需要对连续信号进行采样，从而得到一系列离散数据。这种对离散量的傅立叶变换，称为离散傅立叶变换，记作 DFT。
DFT 的定义：
设是一个长度为 N 的有限长序列，定义x(n)的 N 点离散傅立叶变换为
 （1．2.1）
其中k=0，1,…，N－1
X(k)的傅立叶反变换为
 （1．2.2）
其中 n = 0,1,…,N-1
在(1-2-1)式和(1-2-2)式中，x(n) 和 X(k)均可以是复数。因为在(1-2-1)式和(1-2-2)式的右边仅在W_N指数上差一个符号，并相差一个比例因子1⁄N，所以有关(1-2-1)式计算步骤的讨论稍加修改可以直接用于(1-2-2)式。
DFT隐含周期性，在DFT变换对中，x(n) 和 X(k)均为有限长序列，设
= ，由 的周期性，使得x(n) 和 X(k)隐含周期性，且周期为 N。
快速傅里叶变换（FFT）
从前一节的讨论中知道，DFT 的计算，需要作N^2次复数乘法运算和 N（N－1）次复数加法运算，运算量大。为了快速计算 DFT，近半个世纪以来，人们对离散傅立叶变换的计算进行了大量的研究，提出了很多有效的快速计算 DFT 的方法。这些算法，称之为快速傅立叶变换（Fast Fourier Transform，FFT）。快速博里叶变换并不是与DF T 不同的另外一种变换，而是为减少 DFT 计算次数的一种快速有效的算法。其突出的优点在于能快速高效地和比较精确地完成 DFT 的计算。
快速傅里叶变换算法如下：
X(n)=∑_(K=0)^(N=1)▒x_0 （k）e^(πnk/(N ))           n=0,1,2⋯N-1     (1)
由(1)式可知，对每一个n，计算X(ｎ)须作N次复数乘法及N-1次复数加法，要完成这组变换共需N^█(2@   )次乘法及N(N-1)次复数加法。但以下介绍的快速傅里叶变换的算法，可大大减少运算次数，提高工作效率。
当 时，n和k可用二进制数表示：

又记　 ,则（1）式可改写为       （2）
式中：        (3)
因为 所以（2）可改成     （4）
则式（５）即为式（４）的分解形式。将初始数据代入式（５）的第一个等式，可得每一组计算数据，一般将痗L-1组计算数据代入式（５）的第L个等式，计算后可得第L组计算数据（L＝１，２，…，γ），计算公式也可表示为
  =
         （6）
式中                                （7） VC++的FFT编程设计+文献综述(3):http://www.youerw.com/wenxian/lunwen_18242.html