用c语言实现的FFT

《用c语言实现的FFT》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、对FFT的介绍1.FFT（FastFourierTransformation）,即为快速傅里叶变换，是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅里叶变换的算法进行改进获得的。2.FFT算法的基本原理   FFT算法是把长序列的DFT逐次分解为较短序列的DFT。   按照抽取方式的不同可分为DIT-FFT(按时间抽取)和DIF-FFT(按频率抽取)算法。按蝶形运算的构成不同可分为基2，基4，基8，以及任意因子的类型。3.迭代关系4、本次程序的基本过程我们这次所研究的

2、是数字信号处理中的FFT算法，我们这次所用的数字信号是复数类型的。(1)所以首先，我们先定义了一个复数结构体，因为是进行复数的运算，我们又相继定义复数的加减乘运算的函数。(2)紧接着，我们定义了进行FFT计算的fft()快速傅里叶变换函数initW() 初始化变换核函数即旋转因子的计算，change()变址函数，output()输出傅里叶变换的结果的函数。(3)定义主函数，并调用定义好的相关子函数，利用fft()中的蝶形运算以及change()函数来完成从时间域上选取的DIT-FFT。二、FFT中码位倒置

3、排序1、码位倒置的实现方法：    (1)简单的利用按位与、或循环实现    (2)利用公式推导的迭代方法2、为什么要进行码位倒置 因为由于FFT的计算特性，如果按照正常顺序输入，而没有进行码位倒置的话，就会以乱序输出，就不便于我们后续对信号的相关性质进行研究了，所以DIT-FFT算法就是在进行FFT计算之前，进行分奇偶后的码位倒置运算，即二进制数的倒位。    3、倒位序由奇偶分组造成，以N=8为例，说明如下：三、蝶形运算由按照上述公式的规律进行逐级分解，直到2点DFT，如下是N=8时的蝶形算法分析图：

4、四、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）第三层循环：由于第

5、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

6、算法如下：#include#include#include#defineN1000/*定义复数类型*/typedefstruct{doublereal;doubleimg;}complex;complexx[N],*W;/*输入序列,变换核*/intsize_x=0;/*输入序列的大小，在本程序中仅限2的次幂*/doublePI;/*圆周率*/voidfft();/*快速傅里叶变换*/voidi

7、nitW();/*初始化变换核*/voidchange();/*变址*/voidadd(complex,complex,complex*);/*复数加法*/voidmul(complex,complex,complex*);/*复数乘法*/voidsub(complex,complex,complex*);/*复数减法*/voidoutput();/*输出快速傅里叶变换的结果*/intmain(){inti;/*输出结果*/system("cls");PI=atan(1)*4;printf("输出DIT方

8、法实现的FFT结果");printf("Pleaseinputthesizeofx:");//输入序列的大小scanf("%d",&size_x);printf("Pleaseinputthedatainx[N]:");//输入序列的实部和虚部for(i=0;i