一、对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。
二、FFT中码位倒置排序
1、码位倒置的实现方法：
        (1)简单的利用按位与、或循环实现
        (2）利用公式推导的迭代方法
2、为什么要进行码位倒置
  因为由于FFT的计算特性,如果按照正常顺序输入，而没有进行码位倒置的话,就会以乱序输出，就不便于我们后续对信号的相关性质进行研究了，所以DIT—FFT算法就是在进行FFT计算之前，进行分奇偶后的码位倒置运算，即二进制数的倒位。       
3、倒位序由奇偶分组造成，以N=8为例，说明如下：
三、蝶形运算
printf怎么实现的由
按照上述公式的规律进行逐级分解,直到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）个,并且同一级内不同的乘数分布相同,当第二层循环确定某一乘数后，第三层循环要将本级中每个中具有这一乘数的蝶形计算一次,即第三层循环每执行完一次要进行N/2^L个碟形计算.（执行不同group中具有相同W的蝶形运算）
(5）可以得出结论：在每一级中,第三层循环完成N/2^L个碟形计算；第二层循环使第三层循
环进行 2^（L-1）次，因此，第二层循环完成时，共进行2^(L-1) ＊N/2^L=N/2个碟形计算。实质是:第二、第三层循环完成了第L级的计算。
五、用c语言实现的FFT算法如下：
〈span style=”font—size：18px;"〉＃include 〈stdio。h>
＃include <math.h>
＃include <stdlib.h>
＃define N 1000
/＊定义复数类型＊/
typedef struct{
double real；
double img；
}complex;
complex x[N］， *W； /*输入序列，变换核*/
int size_x=0;      /*输入序列的大小，在本程序中仅限2的次幂*/
double PI；        /＊圆周率*/
void fft();    /＊快速傅里叶变换*/
void initW（）;  /＊初始化变换核＊/

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。