几个快速傅立叶变换算法_第1页
几个快速傅立叶变换算法_第2页
几个快速傅立叶变换算法_第3页
几个快速傅立叶变换算法_第4页
几个快速傅立叶变换算法_第5页
已阅读5页,还剩15页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、几个快速傅立叶变换算法离散傅里叶变换(DFT)DFT的的正变换和反变换分别为(1)和(2)式。假设有N个数据,则计算一个频率点需要N次复数乘法和N-1次复数加法,整个DFT需要N*N次复数乘法和N(N-1)次复数加法;由于一次的复数乘法需要进行4次的实数乘法和2次的复数加法,一次的复数加法需要两次的实数加法,因此整个DFT需要4*N*N次的实数乘法和2*N(N-1)+2*N*N4*N*N次的复数加法。当N比较大时,所需的计算工作量相当大,例如N=1024时大约需要400万次乘法运算,对于实时信号处理来说,将对计算设备提出非常苛刻的要求,于是就提出如何能够减少计算DFT的运算量的问题。1965年

2、,库力和图基在计算数学杂志上发表机器计算傅立叶级数的一种算法,此文是最早提出FFT算法的。此后关于DFT的快速算法称为人们研究的热点课题,也正是FFT算法的出现,才使得数字信号处理能够应用于实时场合并进一步推动数字信号处理的发展和应用。大多数的FFT算法都是利用(3)式的周期性、共轭对称性、可压缩和扩展性的特点来压缩计算量。 1)、根据DFT定义进行计算的代码直接利用DFT的定义进行计算的算法计算量非常大。/Data为输入数据指针,Log2N=log2(length),flag=-1时为正变换,flag=1时为反变换,变换结果由指针Data指向的原空间返回void dft(compl

3、ex<double>*Data,int Log2N,int flag)    int i,j,length;    complex<double> wn;    length=1<<Log2N;    complex<double>*temp=new complex<double>length;   

4、; for(i=0;i<length;i+)          tempi=0;      for(j=0;j<length;j+)              wn=complex<double>(cos(2.0*pi/length*i*j),sin(flag*2.

5、0*pi/length*i*j);        tempi+=Dataj*wn;                             if(flag=1)     for(i

6、=0;i<length;i+)       Datai=tempi/length;    delete temp;   2)、倒位序重排 基2、基4和分裂基的DIT、DIF都需要进行倒位序重排。DIT输入为倒位序,输出为正常顺序,DIT输入为正常顺序,输出为倒位序。因此使用DIT要对输入先进行倒位序重排,DIT要对输出进行倒位序重排,才能得到正常顺序的结果。倒序序重排的实现主要是利用加1是从高位开始加,并且进位是向低位进的特点,这刚好和正位序相反,因此可以得到

7、正位序相应的倒位序。还有一种方法,就是得到各个位上的数码,然后倒转再计入权值,就得到倒位序。(1)、基2的倒位序重排程序void reverse2(complex<double> *data,int Log2N) int i,j; int RevNum; int MaxPos,CurPos,MaxValue; complex<double> temp; MaxValue=(1<<Log2N)-1; MaxPos=1<<(Log2N-1); RevNum=0; for(

8、i=1;i<MaxValue;i+)   CurPos=MaxPos;  while(CurPos&RevNum)!=0)     RevNum=RevNum&(CurPos);   CurPos=CurPos>>1;    RevNum=RevNum|CurPos;  if (RevNum<i)     temp=dataRevNum;   dataRevNum=datai; 

9、0; datai=temp;   (2)、基4的倒位序重排程序/data为数据指针,Log4N=log4(length)。void reverse4(complex<double> *Data,int Log4N) int i,MaxValue,length,MaxPos,CurPos,RevNum; complex<double> temp; length=1<<(2*Log4N); MaxPos=length/4; MaxValue=length-1; RevNum=0;&#

10、160;for(i=1;i<MaxValue;i+)   CurPos=MaxPos;  while(3*CurPos<(RevNum+1)     RevNum=RevNum-3*CurPos;   CurPos=CurPos/4;    RevNum=RevNum+CurPos;  if(RevNum<i)     temp=Datai;   Datai=DataRevNum;   DataRe

11、vNum=temp;   3)、基2时间抽选FFT(DIT2)把时域的数字信号序列按照奇偶进行分组计算,可以进行如下的变换:从变换结果可以知道,一个长度为N的DFT可以变换成长度为N/2的两个子序列的组合。依次类推,可以直到转为N/2个2点的傅立叶变换的组合。由于经过多次的奇偶抽选,输入数据要按照基2倒序的原则进行重排,输出数据为正常顺序。下面首先用递归的形式进行算法的描述,由于递归方法没有充分利用DIT2算法的优点-原位计算,因此递归形式只是为了描述的清晰,并不是使用的程序。void dit2rec(complex<double>*InData,co

12、mplex<double>*OutData,int length,int flag)   complex<double>*EvenData=new complex<double>(length/2);/偶序列组成一个子序列   complex<double>*OddData  =new complex<double>(length/2);/奇序列组成一个子序列   complex<

13、double>*EvenResult=new complex<double>(length/2);/偶序列的变换结果   complex<double>*OddResult=new complex<double>(length/2);/奇序列的变换结果   int i,j;   if(length=1)/单个数的变换,不变,也是递归结束的条件        

14、; if (flag=1)         OutData0=InData0/length;      return;     for(i=0;i<length/2;i+)/形成奇序列和偶序列      EvenDatai=InData2*i;    OddDatai=InData2*i+1; 

15、;   dit2rec(EvenData,EvenResult,length/2,sign);/对奇偶序列分别进行变换  dit2rec(OddData,EvenResult,length/2,sign);  for(i=0;i<length/2;i+)/由奇偶序列的变换进行组合      OutDatai=EvenData+OddData*complex<double>(cos(2*pi*i/length),sin(flag*2*pi*i/len

16、gth);    OutDatai+length/2=EvenData- OddData*complex<double>(cos(2*pi*i/length),sin(flag*2*pi*i/length);    delete EvenData,OddData,EvenResult,OddResult;  return;非递归实现如下(现不考虑输入的倒序数问题):/data为数据指针,返回值相同,Log2N=log2(length),flag=-1时为正变换,f

17、lag=1时为逆变换。 complex<double>* dit2(complex<double>*Data,int Log2N,int flag) int i,j,k; int length=1<<Log2N; complex<double> wn,temp; int step; int index0,index1; for(i=1;i<=Log2N;i+)   step=1<<i;   for(j=0;j<step/2;

18、j+)       wn=complex<double>(cos(2*pi/step*j),sin(flag*2*pi/step*j);    for(k=0;k<length/step;k+)         index0=k*step+j;     index1=k*step+step/2+j;     temp=Dataindex0; 

19、;    Dataindex0=temp+wn*Dataindex1;     Dataindex1=temp-wn*Dataindex1;         if(flag=1)/如果为反变换,要除以序列的长度  for(int i=0;i<length;i+)   Datai/=length; return Data;当i=1时,也就是第一次循环并没有必要进行复数运算,因为j只能取1,wn为实数,这个时间可以

20、节省。因此可以改进为:void dit2(complex<double>*Data,int Log2N,int flag)   int i,j,k,step,length;   complex<double> wn,temp,deltawn;  length=1<<Log2N;   for(i=0;i<length;i+=2)      

21、;   temp=Datai;      Datai=Datai+Datai+1;      Datai+1=temp-Datai+1;      for(i=2;i<=Log2N;i+)         wn=1;step=1<<i;deltawn=complex<doub

22、le>(cos(2.0*pi/step),sin(flag*2.0*pi/step);;      for(j=0;j<step/2;j+)                      for(i=0;i<length/step;i+)     

23、0;             temp=Datai*step+step/2+j*wn;           Datai*step+step/2+j=Datai*step+j-temp;           Datai*step+j=Datai*ste

24、p+j+temp;                  wn=wn*deltawn;            if(flag=1)   for(i=0;i<length;i+)     Datai/=length;4)

25、、基2频率抽选FFT(DIF2)/DIF2的递归版本实现:void dif2rec(complex<double>*InData,complex<double>*OutData,int length,int flag)   complex<double>* LData=new complex<double>(length/2);   complex<double>* LResult=new complex&

26、lt;double>(length/2);   complex<double>* RData=new complex<double>(length/2);   complex<double>* RResult=new complex<double>(length/2);   complex<double> temp;   int i; 

27、60; if(length=1)          if(flag=1)          OutData0=InData0/length;       return;      for(i=0;i<length/2;i+)      

28、;  LDatai=InDatai;     RDatai=InDatai+length/2;        for(i=0;i<length/2;i+)        temp=LDatai;     LDatai=LDatai+RDatai;     RDatai=(temp-RDatai)* complex<double

29、>(cos(2*pi*i/length),sin(flag*2*pi*i/length)        dit2rec(LData,LResult,length/2,sign);     dit2rec(RData,RResult,length/2,sign);   for(i=0;i<length/2;i+)         OutData2*i=LResulti

30、;      OutData2*i+1=RResulti;        return; 非递归实现如下(现不考虑输入的倒序数问题):/data为数据指针,返回值相同,r=log2(length),flag=-1时为正变换,flag=1时为逆变换。complex<double>*dif2(complex<double>*Data,int Log2N,int flag) int i,j,k,step,length; int

31、index0,index1; complex<double> wn,temp; length=1<<Log2N; for(i=1;i<=Log2N;i+)   step=1<<(Log2N-i+1);  for(j=0;j<step/2;j+)     wn=complex<double>(cos(2*pi/step*j),sin(2*pi/step*j*flag);   for(k=0;k<length/st

32、ep;k+)       index0=k*step+j;    index1=k*step+step/2+j;    temp=Dataindex0;    Dataindex0=temp+Dataindex1;    Dataindex1=(temp-Dataindex1)*wn;       if(flag=1)  for(i=0;i<length;i+)

33、   Datai/=length; return Data;和DIT一样,最外层的最后一个循环可以另外独立出来,因为最后一个循环没有必要进行复数运算,这样可以减少复数运算的次数。5)、基4时间抽选FFT(DIT4) 基四时间抽选快速傅立叶算法  DIT4源程序:data为数据指针,返回值相同,Log4N=log4(length),flag=-1时为正变换,flag=1时为逆变换。 complex<double>*dit4(complex<double>*Data,int Log4N,int flag) int

34、i,j,k,length,step,index0,index1,index2,index3; complex<double> wn1,wn2,wn3,img,temp0,temp1,temp2,temp3; length=1<<(2*Log4N); img=complex<double>(0,1); / for(i=1;i<=Log4N;i+)   step=1<<(2*i);  for(j=0;j<step/4;j+)    

35、;    wn1=complex<double>(cos(2*pi/step*j),sin(flag*2*pi/step*j);   wn2=complex<double>(cos(4*pi/step*j),sin(flag*4*pi/step*j);   wn3=complex<double>(cos(6*pi/step*j),sin(flag*6*pi/step*j);   for(k=0;k<length/step;k+)    

36、0;  index0=k*step+j;index1=k*step+step/4+j;index2=k*step+step/2+j;index3=k*step+3*step/4+j;    temp0=Dataindex0+Dataindex1*wn1+Dataindex2*wn2+Dataindex3*wn3;    temp1=Dataindex0-Dataindex1*wn1*img-Dataindex2*wn2+Dataindex3*wn3*img;    temp2=Dataindex

37、0-Dataindex1*wn1+Dataindex2*wn2-Dataindex3*wn3;    temp3=Dataindex0+Dataindex1*wn1*img-Dataindex2*wn2-Dataindex3*wn3*img;    Dataindex0=temp0;    Dataindex1=temp1;    Dataindex2=temp2;    Dataindex3=temp3;    

38、  if(flag=1)   for(i=0;i<length;i+)     Datai/=length;    return Data;6)、基4频率抽选FFT(DIF4)DIF4源程序:data为数据指针,返回值相同,Log4N=log4(length),flag=-1时为正变换,flag=1时为逆变换。complex<double>* dif4(complex<double>*Data,int Log4N,int flag) int i,j,k,s

39、tep,length,index0,index1,index2,index3; complex<double> wn1,wn2,wn3,img,temp0,temp1,temp2,temp3; length=1<<(2*Log4N); img=complex<double>(0,1);  for(i=1;i<=Log4N;i+)   step=1<<2*(Log4N-i+1);  for(j=0;j<step/4;j+)    

40、; complex<double> wn1=complex<double>(cos(2*pi/step*j),sin(flag*2*pi/step*j);   complex<double> wn2=complex<double>(cos(2*pi/step*2*j),sin(flag*2*pi/step*2*j);   complex<double> wn3=complex<double>(cos(2*pi/step*3*j),sin(flag*2*pi/step*3*j);

41、60;  for(k=0;k<length/step;k+)       index0=k*step+j,index1=k*step+step/4+j;index2=k*step+step/2+j;index3=k*step+step*3/4+j;    temp0=Dataindex0+Dataindex1+Dataindex2+Dataindex3;    temp1=(Dataindex0-Dataindex1*img-Dataindex2+Dataindex3*

42、img)*wn1;    temp2=(Dataindex0-Dataindex1+Dataindex2-Dataindex3)*wn2;    temp3=(Dataindex0+Dataindex1*img-Dataindex2-Dataindex3*img)*wn3;    Dataindex0=temp0;    Dataindex1=temp1;    Dataindex2=temp2;    Datain

43、dex3=temp3;      if(flag=1) for(i=0;i<length;i+)  Datai/=length; return Data;  7)、时间抽选分裂基FFT(srfftdit)基4FFT运算量比基2FFT运算量少,但如果不满足N=4m就无法用基4FFT进行运算,又由于基2算法中偶序号部分FFT运算所需乘法次数比技术序号部分乘法次数少,因而对偶序数部分用基2FFT算法,而奇序数部分用基4算法,则运算量可以得到降低。1984年,法国的P.Dohamel和H.Hollmann把基2分解和

44、基4分解融合在一起,提出“分裂基”FFT算法(split-radix FFT或SRFFT),这种算法在目前已知的N=2m点FFT算法中乘、加法次数最少,已经非常接近理论上所需乘法次数的最小值,而且它的运算结构与基2FFT相似,没有更多的取指或存储数据的花销,特别适宜用ASIC实现。分裂基算法与混合基算法的不同之处在于,分裂基算法同一级内既有基2部分又有基4部分,而不像组合数FFT中同一级内只用同一种基运算,它们的相似之处在于可以有时间抽取算法,也可以有频率抽取算法。将输入数据分成三个子序列:做DFT运算有又有上式k范围的限制,还应该补充下列式子才能完整计算N个频率点接着对N/2点DFT和N/4

45、点DFT按以上方法分解成三部分,如此进行到最后不能分解位置。     8)、频率抽选分裂基FFT(srfftdif)  void srfftdif(complex<double>*Data,int Log2N,int sign) int i,j,k,len,step2,step4,ix,id,i0,i1,i2,i3; complex<double> temp0,temp1,temp2,temp3; complex<double> wn1,wn3,img=complex<double&

46、gt;(0,1); len=1<<Log2N; for(i=1;i<Log2N;i+)   step2=1<<(Log2N-i+1);  step4=step2/4;  for(j=0;j<step4;j+)     wn1=complex<double>(cos(2.0*pi/step2*j),sin(sign*2.0*pi/step2*j);   wn3=wn1*wn1*wn

47、1;   ix=j;   id=2*step2;   do       for(k=ix;k<len-1;k+=id)         i0=k;     i1=k+step4;     i2=k+2*step4;  

48、60;  i3=k+3*step4;     temp0=Datai0+Datai2;     temp1=Datai1+Datai3;     temp2=(Datai0-Datai2)-img*(Datai1-Datai3)*wn1;     temp3=(Datai0-Datai2)+img*(Datai1-Datai3)*wn3;   &#

49、160; Datai0=temp0;Datai1=temp1;Datai2=temp2;Datai3=temp3;        ix=2*id-step2+j;    id=4*id;    while(ix<(len-1);    ix=0; id=4; do   for(i=ix;i<len-1;i+=id)  

50、;   i0=i;   i1=i+1;   temp0=Datai0+Datai1;   temp1=Datai0-Datai1;   Datai0=temp0;   Datai1=temp1;    ix=2*id-2;  id=4*id;  while(ix<(len-1); 9)、高基FFT10)、混合基FFT11)、素因子FFT12)、线性调频Z变换(chirp-z变换)算法data为数据指针,Log2N=log2(length

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论