fft算法代码注释及流程框图

《fft算法代码注释及流程框图》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基2的DIT蝶形算法源代码及注释如下：/************FFT***********///整个程序输入和输出利用同一个空间x[N]，节约空间#include#include#include#defineN1000//定义输入或者输出空间的最大长度typedefstruct{doublereal;doubleimg;}complex;//定义复数型变量的结构体voidfft();//快速傅里叶变换函数声明voidinitW();//计算W(0)~W(size_x-1)的值函数声明voidchange();//码元位置倒置函数函数

2、声明voidadd(complex,complex,complex*);/*复数加法*/voidmul(complex,complex,complex*);/*复数乘法*/voidsub(complex,complex,complex*);/*复数减法*/voiddivi(complex,complex,complex*);/*复数除法*/voidoutput();/*输出结果*/complexx[N],*W;/*输出序列的值*/intsize_x=0;/*输入序列的长度，只限2的N次方*/doublePI;//pi的值intmain(){inti;system("cls");PI=at

3、an(1)*4;printf("Pleaseinputthesizeofx:");/*输入序列的长度*/scanf("%d",&size_x);printf("Pleaseinputthedatainx[N]:(suchas:56)");/*输入序列对应的值*/for(i=0;i

4、蝶形算法。这个算法的思路就是，先把计算过程分为log(size_x)/log(2)-1级（用i控制级数）；然后把每一级蝶形单元分组（用j控制组的第一个元素起始下标）；最后算出某一级某一组每一个蝶形单元（用k控制个数，共l个）。*/voidfft(){inti=0,j=0,k=0,l=0;complexup,down,product;change();//实现对码位的倒置for(i=0;i

5、2)）-1】{for(k=0;k

6、ex)*size_x);/*申请size_x个复数W的空间(这部申请的空间有点多，实际上只要申请size_x/2个即可)*/for(i=0;i<(size_x/2);i++)/*预先计算出size_x/2个W的值，存放,由于蝶形算法只需要前size_x/2个值即可*/{W[i].real=cos(2*PI/size_x*i);//计算W的实部W[i].img=-1*sin(2*PI/size_x*i);//计算W的虚部}}voidchange()//输入的码组码位倒置实现函数{complextemp;unsignedshorti=0,j=0,k=0;doublet;for(i=0;i

7、ize_x;i++){k=i;j=0;t=(log(size_x)/log(2));while((t--)>0){j=j<<1;j

8、=(k&1);k=k>>1;}if(j>i){temp=x[i];x[i]=x[j];x[j]=temp;}}}voidoutput()//输出结果实现函数{inti;printf("Theresultareasfollows");for(i=0;i