FFT算法设计与实现

《FFT算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、FFT算法研究报告1、程序设计背景(FFT算法理解)FFT(fastfouriertransformation),快速傅里叶变换。是对DFT算法的改进，其利用了WNnk的周期性、共轭对称性和可约性，使得DFT中有些项可以合并，大大减小了计算量。按输入序列在时间上的次序是属于偶数还是奇数来分解称为“按时间抽取法”(DIT)。另一种是把输出序列X(k)按顺序的奇偶分解为越来越短的序列，称为按频率抽样的FFT算法（DIF）。DIT算法是先作复乘后作加减，而DIF的复乘只出现在减法之后。本次程序采用DIT算法实现FFT。用c语言实现FFT

2、的难点在于数据倒位序的处理，以及各级蝶形运算的实现。倒位序的实现可以使用“反向进位加法”，即倒位序二进制数的下面一个数是上面一个数在最高位加一并由高位向低位进位而得到的。对于点数为N=2^L的FFT运算，可以分解为L阶蝶形图级联，第M阶蝶形图内又分为2^(L-M)个蝶形组，每个蝶形组内包含2^(M-1)个蝶形。而且旋转因子与蝶形阶数和蝶形分组内的蝶形个数存在关联。因此我们就可以构造循环来实现蝶形运算。2、FFT算法流程图输入数组指针a，长度n倒位序流程图：n=0?Yi=0Ni

3、emp[(n+i)/2]=a[i]Yi=i+1a=tempn=n/2结束Y1、FFT程序代码#include#include#include#include#definePI3.141592653#defineSIZE16#defineMAX10//定义复数结构体typedefstructComplex{doublereal;doubleimag;}comp;//定义复数乘法，加法，减法voidAdd_(comp*a1,comp*a2,comp*b){b->im

4、ag=a1->imag+a2->imag;b->real=a1->real+a2->real;}voidSub_(comp*a1,comp*a2,comp*b){b->imag=a1->imag-a2->imag;b->real=a1->real-a2->real;}voidMul_(comp*a1,comp*a2,comp*b){doubler1=0.0,r2=0.0;doublei1=0.0,i2=0.0;r1=a1->real;r2=a2->real;i1=a1->imag;i2=a2->imag;b->imag=r1*i2

5、+r2*i1;b->real=r1*r2-i1*i2;}//利用srand()、rand()随机生成一个输入并显示数据voidInput(double*data,intn){printf("输入信号为:");srand((int)time(0));for(inti=0;i

6、imag=-sin(x);b->real=cos(x);}//处理FFT的数据位置，输入倒位序，输出自然顺序（正序），用递归结构实现intreverse(double*a,intn){if(n==1)return0;double*temp=(double*)malloc(sizeof(double)*n);for(inti=0;i

7、rse(a,n/2);reverse(a+n/2,n/2);return1;}//定义FFT函数voidFFT(double*a,comp*b,intn){reverse(a,n);//对输入信号进行倒位序处理intk=n;intm=0;while(k/=2){//记录需要蝶形运算的级数m++;}k=m;comp*a_comp=(comp*)malloc(sizeof(comp)*n);for(inti=0;i

8、}for(inti=0;i