图3-2 DIT-FFT蝶形运算流图符号
以此类推，还可以把x1(n)和x2(n)按n值得奇偶分为两个序列，这样就达到了降N得目的，从而减少了运算量。FFT对DFT的数学运算量改进：
直接采用DFT进行计算，运算量为N2次复数乘法和N*(N-1)次复数乘法。 当采用M次FFT时，由N=2M求得M=logN，运算流图有M级蝶形，每一级都由N/2个蝶形运算构成，这样每一级蝶形运算都需要N/2次复数乘法和N次复数加法。M级运算共需要复数乘法次数为C=N/2*M，复数加法次数为C=N*M。
当N值较大时，FFT减少运算量的特点表现的越明显。
3.3 DIT-FFT算法的运算规律及编程思想
为了编写DIT-FFT算法的运算程序，首先要分析其运算规律，总结编程思想并绘出程序框图。
1.原位计算
对N 2点的FFT共进行M级运算，每级由N/2个蝶形运算组成。在同一级中，每个蝶的输入数据只对本蝶有用，且输出节点与输入节点在同一水平线上，这就意味着每算完一个蝶后，所得数据可立即存入原输入数据所占用的数组元素（存储单元）中，这种原位（址）计算的方法可节省大量内存。
2.蝶形运算
实现FFT运算的核心是蝶形运算，找出蝶形运算的规律是编程的基础。蝶形运算是分级进行的，每级的蝶形运算可以按旋转因子的指数大小排序进行，如果指数大小一样则可从上往下依次蝶算。对N 2点的FFT共有M级运算，用L表示从左到右的运算级数(L=1，2，…，M )。第L级共有B 2L 1个不同指数的旋转因子，用R表示这些不同指数旋转因子从上到下的顺序(R=0，1，…，B-1)。第R个旋转因子的指数P 2M LR，旋转因子指数为P的第一个蝶的第一节点标号k从R开始，由于本级中旋转因子指数相同的蝶共有2M L个，且这些蝶的相邻间距为2L，故旋转因子指数为P的最后一个蝶的第一节点标号k为：
(2M L 1) 2L R N 2L R，本级中各蝶的第二个节点与第一个节点都相距
M
M
B点。
应用原位计算，蝶形运算可表示成如下形式：
P
AL(J)= AL-1(J)+ AL-1(J+B)*WN
AL (J+B)= AL-1(J)-AL-1(J+B)*WN
P
总结上述运算规律，可采用如下运算方法进行DIT-FFT
运算。首先读入数