《快速傅里叶算法c语言完整实现》由会员分享，可在线阅读，更多相关《快速傅里叶算法c语言完整实现（8页珍藏版）》请在金锄头文库上搜索。
1、快速傅里叶算法快速傅里叶算法 C C 语言完整实现语言完整实现#include#include#define uint unsigned int#define uchar unsigned chartypedef struct Complex/复数结构体double Re;double Im;Complex;Complex Mul(Complex a,Complex b)/复数相乘Complex c;c.Re=a.Re*b.Re-a.Im*b.Im;c.Im=a.Re*b.Im+a.Im*b.Re;return c;Complex Plus(Complex a,Complex b)/复数相加C
2、omplex c;c.Re=a.Re+b.Re;c.Im=a.Im+b.Im;return c;Complex Sub(Complex a,Complex b)/复数相减Complex c;c.Re=a.Re-b.Re;c.Im=a.Im-b.Im;return c;/*函数说明：倒序运算参数说明：N 点数，等于 2 的 M 次方，*x 序列的首地址返回值：无*/void Invert_order(uint N,Complex *x,uchar M)uint power,i,j,m,tempp;/m 是 i 的倒位序数Complex temp;/是临时变量for(i=0;i=(M-1-j);i
3、f(tempppower=power*2;if(iIm;temp.Re=(x+i)-Re;(x+i)-Re=(x+m)-Re;(x+i)-Im=(x+m)-Im;(x+m)-Im=temp.Im;(x+m)-Re=temp.Re;/*Invert_order 函数结束：*/*函数说明：指数运算参数说明：BaseNumber 底数,IndexNumber 指数返回值：无符号整数*/uint Pow(uchar BaseNumber,uint IndexNumber)uint m=1;/指数函数值uchar i;for(i=0;iIndexNumber;i+)m=BaseNumber*m;retu
4、rn m;/*Pow 函数结束：*/*函数说明：对数运算参数说明：BaseNumber 底数,AntiNumber 真数返回值：无符号整数*/uint Log(uchar BaseNumber,uint AntiNumber)uint m=0;/对数函数值while(1)AntiNumber=AntiNumber/BaseNumber;if(AntiNumber)m+;else break;return m;/*log 函数结束：*/*函数说明：按时间抽取基二快速傅里叶算法参数说明：N 点数，等于 2 的 M 次方，*x 序列的首地址返回值：无*/void Dit2Fft(uint N,Com
5、plex *x)int clk=0;Complex temp;/临时复数变量uint L,M=Log(2,N);/M 级蝶形图uint k,j;uint StepLength;/k 值步长uint Bank ;/两点间的距离const double pai=3.1415926;double ps;uint r;/旋转因子的幂 Complex W;/旋转因子printf(“M de zhi shi :M=%un“,M);for(L=1;L=M;L+)StepLength=Pow(2,L);Bank=StepLength/2;printf(“L=%utStep=%utBank=%un“,L,Ste
6、pLength,Bank);for(j=0;j=Bank-1;j+)Complex W_temp;W_temp.Im=-1.0;W_temp.Re=1.0;r=Pow(2,M-L)*j ;ps=2*pai/N*r ;W.Re=cos(ps);W.Im=-sin(ps);/ W.Re=ps;/ W.Im=10.0*ps;for(k=j;k=N-1;k=k+StepLength)Complex x_temp;printf(“%un“,r);x_temp=Mul(W,xk+Bank);temp=Plus(xk,x_temp);xk+Bank=Sub(xk,x_temp);xk.Re=temp.Re;
7、xk.Im=temp.Im;/printf(“zhu yi le:clk=%dn“,clk);/*Dit2Fft 函数结束：*/#if 1 #define DATA_LEN 16void main()uint N,M;int i;Complex xDATA_LEN;N=DATA_LEN;M=Log(2,N);printf(“chu shi xu lie:n“);for( i=0;iDATA_LEN;i+)/序列初始化xi.Im=0;xi.Re=i;printf(“n“);Invert_order(N,x,M);printf(“dao xu hou xu lie:n“);for(i=0;iDAT
8、A_LEN;i+)/倒序后再次输出printf(“%lf %lf “,xi.Re,xi.Im);if(i%2=0)printf(“n“);printf(“n“);Dit2Fft(N,x);printf(“FFT yun suan hou xu lie:n“);for(i=0;iDATA_LEN;i+)/FFT 后再次输出/ printf(“%lf+%lfitt“,xi.Re,xi.Im);/printf(“%lft“,xi.Im);/ if(i%2=0)printf(“n“);/ printf(“n“);printf(“After.nRealttImagn“); for(i=0;iDATA_LEN;i+)/FFT 后再次输出printf(“%ft%ftn“,xi.Re,xi.Im);/ printf(“%fn“,sqrt(xi.Re*xi.Re+xi.Im*xi.Im);/ printf(“n“);#endif
