一、对 FFT 的介绍1. FFT（Fast Fourier Transformation）,即为快速傅里叶变换，是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅里叶变换的算法进行改进获得的。2.FFT 算法的基本原理 FFT 算法是把长序列的 DFT 逐次分解为较短序列的 DFT。 根据抽取方式的不同可分为 DIT-FFT(按时间抽取)和 DIF-FFT(按频率抽取)算法。按蝶形运算的构成不同可分为基 2，基 4，基8，以及任意因子的类型。3.迭代关系4、本次程序的基本过程我们这次所讨论的是数字信号处理中的 FFT 算法，我们这次所用的数字信号是复数类型的。(1)所以首先，我们先定义了一个复数结构体，因为是进行复数的运算，我们又相继定义复数的加减乘运算的函数。(2)紧接着，我们定义了进行 FFT 计算的 fft()快速傅里叶变换函数initW() 初始化变换核函数即旋转因子的计算，change() 变址函数，output()输出傅里叶变换的结果的函数。(3)定义主函数，并调用定义好的相关子函数，利用 fft()中的蝶形运算以及 change()函数来完成从时间域上选取的 DIT-FFT。EbodE。二、FFT 中码位倒置排序1、码位倒置的实现方法： (1)简单的利用按位与、或循环实现 (2)利用公式推导的迭代方法2、为什么要进行码位倒置 因为由于 FFT 的计算特性，假如根据正常顺序输入，而没有进行码位倒置的话，就会以乱序输出，就不便于我们后续对信号的相关性质进行讨论了，所以 DIT-FFT 算法就是在进行 FFT 计算之前，进行分奇偶后的码位倒置运算，即二进制数的倒位。 3、倒位序由奇偶分组造成，以 N=8 为例，说明如下：rAY2v。三、蝶形运算由根据上述公式的规律进行逐级分解，直到 2 点 DFT，如下是 N=8 时的蝶形算法分析图：四、FFT 算法中蝶形算法的基本思想分析（1）我们知道 N 点 FFT 运算可以分成 log2（N）级，每一级都有 N/2个碟形，FFT 的基本思想是用 3 层循环完成全部运算(N 点 FFT)。（2）第一层循环：由于 N=2^m 需要 m 级计算,第一层循环对运算的级数进行控制。（stages）（3）第二层循环：由于第 L 级有 2^(L-1)个蝶形因子（乘数），第二层循环根据乘数进行控制，保证对于每一个蝶形因子第三层循环要执行一次，这样，第三层循环在第二层循环控制下，每一级要进行 2^(L-1)次循环计算.(选择 W)（4）第三层循环：由于第 L 级共有 N/2^L 即 2^（n-L）个群，并且同一级内不同群的乘数分布相同，当第二层循...
