快速傅里叶变换的基2fft算法的c 实现

《快速傅里叶变换的基2fft算法的c 实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、快速傅里叶变换的基2FFT算法的C实现快速傅里叶变换的基2FFT算法的C++实现2011-01-1905：26快速傅里叶变换的基本原理由于公式不好显示请读者参考其它文章或书籍，本文重点给出了时域抽取法FFT的C++实现。下面是算法的流程图倒序的流程图C++实现代码：1.FFT.h#pragmaonce#ifndefFFT_H#defineFFT_H#includecstring#includecmathusingnamespacestd；#definepi3.141592classFFT{private：voidchangeOrder(double*xr,d

2、ouble*xi,intn)；public：FFT(void)；voidFFT_1D(double*ctxr,double*ctxi,double*cfxr,double*cfxi,intlen)；voidrFFT_1D(double*ctxr,double*cfxr,double*cfxi,intlen)；voidIFFT_1D(double*cfxr,double*cfxi,double*ctxr,double*ctxi,intlen)；voidrIFFT_1D(double*cfxr,double*cfxi,double*ctxr,intlen)；~F

3、FT(void)；}；#endif2.FFT.cpp#include".fft.h"FFT：FFT(){}/////////////////////////////倒序实现//xr实部，xi虚部，n为2的幂///////////////////////////voidFFT：changeOrder(double*xr,double*xi,intn){doubletemp；intk；intlh=n/2；intj=lh；intn1=n-2；for(inti=1；i=n1；i++){if(ij){temp=xr[i]；xr[i]=xr[j]；xr[j]=temp

4、；temp=xi[i]；xi[i]=xi[j]；xi[j]=temp；}k=lh；while(j=k){j=j-k；k=(int)(k/2+0.5)；}j=j+k；}}////////////////////////////复数FFT//ctxr和ctxi的长度为len//cfxr和cfxi的长度为2的幂//////////////////////////voidFFT：FFT_1D(double*ctxr,double*ctxi,double*cfxr,double*cfxi,intlen){intm=ceil(log((double)len)/log(2

5、.0))；intl,b,j,p,k；doublerkb,ikb；intn=1m；double*rcos=newdouble[n/2]；double*isin=newdouble[n/2]；for(l=0；ln/2；l++){rcos[l]=cos(l*pi*2/n)；isin[l]=sin(l*pi*2/n)；}memcpy(cfxr,ctxr,sizeof(double)*len)；memcpy(cfxi,ctxi,sizeof(double)*len)；for(l=len；ln；l++){cfxr[l]=0；cfxi[l]=0；}changeOrder(

6、cfxr,cfxi,n)；//倒序for(l=1；l=m；l++){b=(int)(pow(2,l-1)+0.5)；for(j=0；jb；j++){p=j*(int)(pow(2,m-l)+0.5)；for(k=j；kn；k+=(int)(pow(2,l)+0.5)){rkb=cfxr[k+b]*rcos+cfxi[k+b]*isin；ikb=cfxi[k+b]*rcos-cfxr[k+b]*isin；cfxr[k+b]=cfxr[k]-rkb；cfxi[k+b]=cfxi[k]-ikb；cfxr[k]=cfxr[k]+rkb；cfxi[k]=cfxi[k]

7、+ikb；}}}deletercos；deleteisin；}///////////////////////////////实数FFT//ctxr的长度为len//cfxr和cfxi的长度为2的幂////////////////////////////voidFFT：rFFT_1D(double*ctxr,double*cfxr,double*cfxi,intlen){intm=ceil(log((double)len)/log(2.0))；intn=1m；double*rcos=newdouble[n/2]；double*isin=newdouble[n/

8、2]；for(intl=0；ln/2；l++){rc