怎么在Java中实现一个傅里叶变化算法

怎么在Java中实现一个傅里叶变化算法？相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

FFT.class 傅里叶变化功能实现代码

packagefft.test;
publicclassFFT{
//computetheFFTofx[],assumingitslengthisapowerof2
publicstaticComplex[]fft(Complex[]x){
intN=x.length;
//basecase
if(N==1)
returnnewComplex[]{x[0]};
//radix2Cooley-TukeyFFT
if(N%2!=0){
thrownewRuntimeException("Nisnotapowerof2");
}
//fftofeventerms
Complex[]even=newComplex[N/2];
for(intk=0;k<N/2;k++){
even[k]=x[2*k];
}
Complex[]q=fft(even);
//fftofoddterms
Complex[]odd=even;//reusethearray
for(intk=0;k<N/2;k++){
odd[k]=x[2*k+1];
}
Complex[]r=fft(odd);
//combine
Complex[]y=newComplex[N];
for(intk=0;k<N/2;k++){
doublekth=-2*k*Math.PI/N;
Complexwk=newComplex(Math.cos(kth),Math.sin(kth));
y[k]=q[k].plus(wk.times(r[k]));
y[k+N/2]=q[k].minus(wk.times(r[k]));
}
returny;
}
//computetheinverseFFTofx[],assumingitslengthisapowerof2
publicstaticComplex[]ifft(Complex[]x){
intN=x.length;
Complex[]y=newComplex[N];
//takeconjugate
for(inti=0;i<N;i++){
y[i]=x[i].conjugate();
}
//computeforwardFFT
y=fft(y);
//takeconjugateagain
for(inti=0;i<N;i++){
y[i]=y[i].conjugate();
}
//dividebyN
for(inti=0;i<N;i++){
y[i]=y[i].scale(1.0/N);
}
returny;
}
//computethecircularconvolutionofxandy
publicstaticComplex[]cconvolve(Complex[]x,Complex[]y){
//shouldprobablypadxandywith0ssothattheyhavesamelength
//andarepowersof2
if(x.length!=y.length){
thrownewRuntimeException("Dimensionsdon'tagree");
}
intN=x.length;
//computeFFTofeachsequence，求值
Complex[]a=fft(x);
Complex[]b=fft(y);
//point-wisemultiply，点值乘法
Complex[]c=newComplex[N];
for(inti=0;i<N;i++){
c[i]=a[i].times(b[i]);
}
//computeinverseFFT，插值
returnifft(c);
}
//computethelinearconvolutionofxandy
publicstaticComplex[]convolve(Complex[]x,Complex[]y){
ComplexZERO=newComplex(0,0);
Complex[]a=newComplex[2*x.length];//2n次数界，高阶系数为0.
for(inti=0;i<x.length;i++)
a[i]=x[i];
for(inti=x.length;i<2*x.length;i++)
a[i]=ZERO;
Complex[]b=newComplex[2*y.length];
for(inti=0;i<y.length;i++)
b[i]=y[i];
for(inti=y.length;i<2*y.length;i++)
b[i]=ZERO;
returncconvolve(a,b);
}
//displayanarrayofComplexnumberstostandardoutput
publicstaticvoidshow(Complex[]x,Stringtitle){
System.out.println(title);
System.out.println("-------------------");
intcomplexLength=x.length;
for(inti=0;i<complexLength;i++){
//输出复数
//System.out.println(x[i]);
//输出幅值需要*2/length
System.out.println(x[i].abs()*2/complexLength);
}
System.out.println();
}
/**
*将数组数据重组成2的幂次方输出
*
*@paramdata
*@return
*/
publicstaticDouble[]pow2DoubleArr(Double[]data){
//创建新数组
Double[]newData=null;
intdataLength=data.length;
intsumNum=2;
while(sumNum<dataLength){
sumNum=sumNum*2;
}
intaddLength=sumNum-dataLength;
if(addLength!=0){
newData=newDouble[sumNum];
System.arraycopy(data,0,newData,0,dataLength);
for(inti=dataLength;i<sumNum;i++){
newData[i]=0d;
}
}else{
newData=data;
}
returnnewData;
}
/**
*去偏移量
*
*@paramoriginalArr
*原数组
*@return目标数组
*/
publicstaticDouble[]deskew(Double[]originalArr){
//过滤不正确的参数
if(originalArr==null||originalArr.length<=0){
returnnull;
}
//定义目标数组
Double[]resArr=newDouble[originalArr.length];
//求数组总和
Doublesum=0D;
for(inti=0;i<originalArr.length;i++){
sum+=originalArr[i];
}
//求数组平均值
Doubleaver=sum/originalArr.length;
//去除偏移值
for(inti=0;i<originalArr.length;i++){
resArr[i]=originalArr[i]-aver;
}
returnresArr;
}
publicstaticvoidmain(String[]args){
//intN=Integer.parseInt(args[0]);
Double[]data={-0.35668879080953375,-0.6118094913035987,0.8534269560320435,-0.6699697478438837,0.35425500561437717,
0.8910250650549392,-0.025718699518642918,0.07649691490732002};
//去除偏移量
data=deskew(data);
//个数为2的幂次方
data=pow2DoubleArr(data);
intN=data.length;
System.out.println(N+"数组N中数量....");
Complex[]x=newComplex[N];
//originaldata
for(inti=0;i<N;i++){
//x[i]=newComplex(i,0);
//x[i]=newComplex(-2*Math.random()+1,0);
x[i]=newComplex(data[i],0);
}
show(x,"x");
//FFToforiginaldata
Complex[]y=fft(x);
show(y,"y=fft(x)");
//takeinverseFFT
Complex[]z=ifft(y);
show(z,"z=ifft(y)");
//circularconvolutionofxwithitself
Complex[]c=cconvolve(x,x);
show(c,"c=cconvolve(x,x)");
//linearconvolutionofxwithitself
Complex[]d=convolve(x,x);
show(d,"d=convolve(x,x)");
}
}
/*********************************************************************
*%javaFFT8x--------------------0.35668879080953375-0.6118094913035987
*0.8534269560320435-0.66996974784388370.354255005614377170.8910250650549392
*-0.0257186995186429180.07649691490732002
*
*y=fft(x)-------------------0.5110172121330208-1.245776663065442+
*0.7113504894129803i-0.8301420417085572-0.8726884066879042i
*-0.17611092978238008+2.4696418005143532i1.1395317305034673
*-0.17611092978237974-2.4696418005143532i-0.8301420417085572+
*0.8726884066879042i-1.2457766630654419-0.7113504894129803i
*
*z=ifft(y)--------------------0.35668879080953375-0.6118094913035987+
*4.2151962932466006E-17i0.8534269560320435-2.691607282636124E-17i
*-0.6699697478438837+4.1114763914420734E-17i0.35425500561437717
*0.8910250650549392-6.887033953004965E-17i-0.025718699518642918+
*2.691607282636124E-17i0.07649691490732002-1.4396387316837096E-17i
*
*c=cconvolve(x,x)--------------------1.0786973139009466-
*2.636779683484747E-16i1.2327819138980782+2.2180047699856214E-17i
*0.4386976685553382-1.3815636262919812E-17i-0.5579612069781844+
*1.9986455722517509E-16i1.432390480003344+2.636779683484747E-16i
*-2.2165857430333684+2.2180047699856214E-17i-0.01255525669751989+
*1.3815636262919812E-17i1.0230680492494633-2.4422465262488753E-16i
*
*d=convolve(x,x)-------------------0.12722689348916738+
*3.469446951953614E-17i0.43645117531775324-2.78776395788635E-18i
*-0.2345048043334932-6.907818131459906E-18i-0.5663280251946803+
*5.829891518914417E-17i1.2954076913348198+1.518836016779236E-16i
*-2.212650940696159+1.1090023849928107E-17i-0.018407034687857718-
*1.1306778366296569E-17i1.023068049249463-9.435675069681485E-17i
*-1.205924207390114-2.983724378680108E-16i0.796330738580325+
*2.4967811657742562E-17i0.6732024728888314-6.907818131459906E-18i
*0.00836681821649593+1.4156564203603091E-16i0.1369827886685242+
*1.1179436667055108E-16i-0.00393480233720922+1.1090023849928107E-17i
*0.005851777990337828+2.512241462921638E-17i1.1102230246251565E-16-
*1.4986790192807268E-16i
*********************************************************************/

Complex.class 复数类

packagefft.test;
/******************************************************************************
*Compilation:javacComplex.java
*Execution:javaComplex
*
*Datatypeforcomplexnumbers.
*
*Thedatatypeis"immutable"soonceyoucreateandinitialize
*aComplexobject,youcannotchangeit.The"final"keyword
*whendeclaringreandimenforcesthisrule,makingita
*compile-timeerrortochangethe.reor.iminstancevariablesafter
*they'vebeeninitialized.
*
*%javaComplex
*a=5.0+6.0i
*b=-3.0+4.0i
*Re(a)=5.0
*Im(a)=6.0
*b+a=2.0+10.0i
*a-b=8.0+2.0i
*a*b=-39.0+2.0i
*b*a=-39.0+2.0i
*a/b=0.36-1.52i
*(a/b)*b=5.0+6.0i
*conj(a)=5.0-6.0i
*|a|=7.810249675906654
*tan(a)=-6.685231390246571E-6+1.0000103108981198i
*
******************************************************************************/
importjava.util.Objects;
publicclassComplex{
privatefinaldoublere;//therealpart
privatefinaldoubleim;//theimaginarypart
//createanewobjectwiththegivenrealandimaginaryparts
publicComplex(doublereal,doubleimag){
re=real;
im=imag;
}
//returnastringrepresentationoftheinvokingComplexobject
publicStringtoString(){
if(im==0)
returnre+"";
if(re==0)
returnim+"i";
if(im<0)
returnre+"-"+(-im)+"i";
returnre+"+"+im+"i";
}
//returnabs/modulus/magnitude
publicdoubleabs(){
returnMath.hypot(re,im);
}
//returnangle/phase/argument,normalizedtobebetween-piandpi
publicdoublephase(){
returnMath.atan2(im,re);
}
//returnanewComplexobjectwhosevalueis(this+b)
publicComplexplus(Complexb){
Complexa=this;//invokingobject
doublereal=a.re+b.re;
doubleimag=a.im+b.im;
returnnewComplex(real,imag);
}
//returnanewComplexobjectwhosevalueis(this-b)
publicComplexminus(Complexb){
Complexa=this;
doublereal=a.re-b.re;
doubleimag=a.im-b.im;
returnnewComplex(real,imag);
}
//returnanewComplexobjectwhosevalueis(this*b)
publicComplextimes(Complexb){
Complexa=this;
doublereal=a.re*b.re-a.im*b.im;
doubleimag=a.re*b.im+a.im*b.re;
returnnewComplex(real,imag);
}
//returnanewobjectwhosevalueis(this*alpha)
publicComplexscale(doublealpha){
returnnewComplex(alpha*re,alpha*im);
}
//returnanewComplexobjectwhosevalueistheconjugateofthis
publicComplexconjugate(){
returnnewComplex(re,-im);
}
//returnanewComplexobjectwhosevalueisthereciprocalofthis
publicComplexreciprocal(){
doublescale=re*re+im*im;
returnnewComplex(re/scale,-im/scale);
}
//returntherealorimaginarypart
publicdoublere(){
returnre;
}
publicdoubleim(){
returnim;
}
//returna/b
publicComplexdivides(Complexb){
Complexa=this;
returna.times(b.reciprocal());
}
//returnanewComplexobjectwhosevalueisthecomplexexponentialof
//this
publicComplexexp(){
returnnewComplex(Math.exp(re)*Math.cos(im),Math.exp(re)*Math.sin(im));
}
//returnanewComplexobjectwhosevalueisthecomplexsineofthis
publicComplexsin(){
returnnewComplex(Math.sin(re)*Math.cosh(im),Math.cos(re)*Math.sinh(im));
}
//returnanewComplexobjectwhosevalueisthecomplexcosineofthis
publicComplexcos(){
returnnewComplex(Math.cos(re)*Math.cosh(im),-Math.sin(re)*Math.sinh(im));
}
//returnanewComplexobjectwhosevalueisthecomplextangentofthis
publicComplextan(){
returnsin().divides(cos());
}
//astaticversionofplus
publicstaticComplexplus(Complexa,Complexb){
doublereal=a.re+b.re;
doubleimag=a.im+b.im;
Complexsum=newComplex(real,imag);
returnsum;
}
//SeeSection3.3.
publicbooleanequals(Objectx){
if(x==null)
returnfalse;
if(this.getClass()!=x.getClass())
returnfalse;
Complexthat=(Complex)x;
return(this.re==that.re)&&(this.im==that.im);
}
//SeeSection3.3.
publicinthashCode(){
returnObjects.hash(re,im);
}
//sampleclientfortesting
publicstaticvoidmain(String[]args){
Complexa=newComplex(3.0,4.0);
Complexb=newComplex(-3.0,4.0);
System.out.println("a="+a);
System.out.println("b="+b);
System.out.println("Re(a)="+a.re());
System.out.println("Im(a)="+a.im());
System.out.println("b+a="+b.plus(a));
System.out.println("a-b="+a.minus(b));
System.out.println("a*b="+a.times(b));
System.out.println("b*a="+b.times(a));
System.out.println("a/b="+a.divides(b));
System.out.println("(a/b)*b="+a.divides(b).times(b));
System.out.println("conj(a)="+a.conjugate());
System.out.println("|a|="+a.abs());
System.out.println("tan(a)="+a.tan());
}
}

看完上述内容，你们掌握怎么在Java中实现一个傅里叶变化算法的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注恰卡编程网行业资讯频道，感谢各位的阅读！