fft.c

C语言版,机载SAR回波仿真程序

#include "FFT.h"

void FFT(comp *data,int FFTn,int inverse)
{
	comp      u,w,t;
	double     temp1,temp2;
	double     pi;
	int       i,j,k,l,ip;
	int       le,le1,m;

	pi=3.1415926f;
	m=0;
	while(FFTn != (0x0001<<m)) m++;
	for(i=0,j=0; i<FFTn-1; i++)
	{
		if(i<j)
		{
			t=data[j];
			data[j]=data[i];
			data[i]=t;
		}
		k=FFTn/2;
		while(k<=j)
		{
			j-=k;
			k/=2;
		}
		j+=k;
	}
	le=1;
	for(l=0; l<m; l++ )
	{
		le*=2;
		le1=le/2;
		u.re=(float)1.0;
		u.im=(float)0.0;
		w.re=(float)cos(pi/le1);
		w.im=(float)(inverse*sin(pi/le1));
		for(j=0; j<le1; j++)
		{
			for(i=j; i<FFTn; i+=le)
			{
				ip=i+le1;
				t.re=data[ip].re*u.re-data[ip].im*u.im;
				t.im=data[ip].re*u.im+data[ip].im*u.re;
				data[ip].re=data[i].re-t.re;
				data[ip].im=data[i].im-t.im;
				data[i].re+=t.re;
				data[i].im+=t.im;
			 }
			temp1=u.re;
			temp2=u.im;
			u.re=(float)(temp1*w.re-temp2*w.im);
			u.im=(float)(temp1*w.im+temp2*w.re);
		}
    }
	if(inverse>0) return;
	for(i=0; i<FFTn; i++)
	{
		data[i].re/=FFTn;
		data[i].im/=FFTn;
	}
	return;
}