运算规律及编程思想
1.原位计算
N=2^M点的FFT共进行M级运算，每级运算，每级N/2个蝶形运算组成。同一级中，每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据结点又同在一条水平线上，这就意味着计算完一个蝶形后，所得输出数据可立即存入原输入数据所占用的存储单元(数组元素)。这样，经过M级运算后，原来存放输入序列数据的N个存储单元(数组A)中便依次存放X(k)的N个值。这种利用同一存储单元存储蝶形 计算输入输出数据的方法称为原位(址)计算。原位计算可节省大量内存，从而使设备成本降低。
2.旋转因子的变化规律
在DFT-FFT运算流图中，每级都有N/2个蝶形，每个蝶形都要乘以旋转因子
，p为旋转因子的指数。但各级的旋转因子和循环方式都有所不同。在编写计算程序前，应该先找出旋转因子
与运算级数M的关系。第L级共有2^(L-1)个不同的旋转因子。
3.蝶形运算规律
公式：
式中：
为第L级运算后的值，
为第L级运算前的值，B(与旋转因子数量相同为
)为两个输入数据相距多少个点，
为旋转因子
4.编程思想
先从输入端开始，逐级进行，共进行M次运算。再进行第L级运算时，依次求出B个不同的旋转因子，每求出一个旋转因子，就计算完它对应所有
个蝶形。这样就可以利用三重循环程序实现DIT-FFT运算。
5.福利
有需要FFT源码的同学可关注新浪微博 __程鹏，回复私信“FFT”，可得到FFT源代码。
以上是学习傅里叶变换时的一些理解和记录，其中不足之处还请看官指出，谢谢支持。