对别人的一个能用的FFT算法的拆解

   快速傅里叶算法，像许多算法一样，都是有背景的，这里我们不谈这个，因为离那个时代有些遥远。

   快速傅里叶算法，在数字信号处理中的理论部分已然有些不方便理解。对这类涉及计算的理论，个人建议，与其证明，不如验算。验算也不用硬拉着所有点全上，非得穷举不成。事实上，取一点足矣，把自已骗过去就行。前天看别人的博客里转载的文章，说有个数学家说，验算比证明更快。还举了一例：“在宴会上，有个人提醒你，在某某角落的那不是谁谁谁某某某吗？你立刻放眼过去，一看准是！如果你从进门开始，没人指点的去找她，势必你会看见许多不同表情的脸，势必要与你心中的她进行对比，反复地。”

   快速傅里叶算法，用程序实现起来是需要分步骤的。这种分步的思想应用的很广泛，本山大叔的小品就用此思想而把大像和人忽悠了一下。

   具体到快速傅里叶算法的步骤上，本人是这样分的：

   （1）位倒序，将原始的时域序列进行倒序。由倒序的时域序列算出的频谱值恰是按自然顺序排列的，与理论上说明的惊人的相似。

   （2）初始化变换核

       其中n为时域序列的排列的顺序值，k为频域序列排列的顺序值，在下面要介绍的程序里， 初始化变换核中不含有k项，它是这样的:

C语言中表示复数是将复数分为实部与虚部。按照欧拉公式，分解上面的式子：

     初始变换核要做的工作就是算出N项类似

这样的核，n=( 0, 1, 2, ……，N-1 )

        在这里遇到一个问题,就圆周率pi值的计算。在程序中一般是这样实现的

       double PI;

       PI = atan( 1 ) * 4;/*利用1的反正切值为pi/4而来*/

      前提是添加了<math.h>头文件

（3）进入FFT算法

    ……未完待续