注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

千鸟

本blog所有日志均系原创 转载请注明出处

 
 
 

日志

 
 

java版快速傅立叶变换(基-2FFT)  

2007-04-21 16:06:40|  分类: Arithmetic |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    其实,既然是写算法.就该画出图来.不过基-2FFT蝶形图实在麻烦,众看客自己翻<数字信号处理>去吧.为什么用java实现基-2FFT?对java的热情而已,绝对不会相信java会输给c++. 也用c++试验过,c++要代码的留下e-mail来

    用matlab试验过,计算结果相同.下面代码的根据我们学校刘益成教授的书改编成了java.  他的屋子其实就离我们工作室直线距离10米.他的研究生介绍说他目前的项目如果基-2FFT计算下来是40秒,而他现在的搞算法已经到了6秒,而要求却是2秒.  java版快速傅立叶变换(基-2FFT) - souljava - 千鸟高山仰止. 离散信号的快速傅立叶变换,在算离散卷积,离散信号相关性大大节约了时间. 特别是在处理图片的时候,用FFT计算卷积那是相当必要的.不知道photoshop的卷积用的是哪种算法

/*

author by soulnew@gmail.com

*/

package com.soulnew.Math;

public class MyFft{
 
 public MyFft(){
  
 }
 /*
  *实现倒码
  **/
 public static complex[] changedLow(complex[] a,int length){
     int mr=0;   
         
           for(int m=1;m<length;++m){
            int l=length/2;
            while(mr+l>=length){
             l=l>>1;    //右移相当于,l除以2
            }
            mr=mr%l+l;
            if(mr>m){
             complex t=new complex();
             t=a[m];
             a[m]=a[mr];
             a[mr]=t;
            }
           }

  return a;
 }
 /*
  *乘积因子
  **/
 public complex complex_exp(complex z){
  complex r=new complex();
  double expx=Math.exp(z.r);
  r.r=expx*Math.cos(z.i);
  r.i=expx*Math.sin(z.i);
  return r;
 }

 /*
  *基-2 fft蝶形变换
  *fft_tepy=1正变换, -1反变换
  **/
 public complex[] fft_2(complex[] a,int length,int fft_tepy){
  
     double pisign=fft_tepy*Math.PI;
   //  System.out.print(" pisign:"+pisign+"\n");
     complex t=new complex();
  int l=1;
  
  while(l<length){
   for(int m=0;m<l;++m){
    int temp_int=l*2; //左移相当于,l乘以2
    for(int i=m;temp_int<0?i>=(length-1):i<length;i+=temp_int){
     complex temp=new complex(0.0,m*pisign/l);

     complex temp_exp=complex_exp(temp);     
     t.r=a[i+l].r*temp_exp.r-a[i+l].i*temp_exp.i;
     t.i=a[i+l].r*temp_exp.i+a[i+l].i*temp_exp.r;
     
     a[i+l].r=a[i].r-t.r;
     a[i+l].i=a[i].i-t.i;
     a[i].r=a[i].r+t.r;
     a[i].i=a[i].i+t.i;
     
    } // end for i
   
   }  // end for m
   System.out.print("\n now is the loop and l="+l+"\n");
  for(int c=0;c<length;c++){         
         System.out.print(a[c].r+"+j"+a[c].i+"\n");
        }
   
   l=l*2;
  }//end while
    //左移相当于,l乘以2
  return a;
 }


 complex b[];
 /*
  *
  *main
  *
  *
  **/
 public static void main(String arg[]){
  MyFft mf=new MyFft();
  final int n=16;
  
  int dd[]=new int[n];
  mf.b= new complex[n];
  for(int c=0;c<n;c++){  //轮流赋值    
    mf.b[c]=new complex(c,0);        
         // System.out.print(mf.b[c].r+"+j"+mf.b[c].i+"\n");
        }
        System.out.print("\n\n");
       
        mf.b=mf.changedLow(mf.b,n);
        mf.b=mf.fft_2(mf.b,n,-1);
        //输出
        for(int c=0;c<n;c++){         
         System.out.print(mf.b[c].r+"+j"+mf.b[c].i+"\n");
        }
        
  
 }

}
 /*
  *复数类
  **/
class complex{
 double  r,i;
  public complex(){
   
  }
  public complex(double r,double i){
   this.r=r; //实部
   this.i=i;  //虚部
  }
  
}

  评论这张
 
阅读(1308)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017