#include
#include


#define?PI?3.1415926535897932384626
#define?FFT_N??32?
#define?Change?32768
#define?Q??????15??

?????????????????????????????????????????????
//定點FFT
struct?compx_fp?{long?realimag;};?????????????????????????????????
struct?compx_fp?s_fp[FFT_N];

int?multiply_i（int?aint?b）??????????????????????
{
	int?ci=0;
	while（a<-Change||a>Change-1）
	{
		i+=1;
		a>>=1;
	}
	while（b<-Change||b>Change-1）
	{
		i+=1;
		b>>=1;
	}
	c=（（a*b）>>（Q-i））;
	return?c;

}


struct?compx_fp?multiply_fp（struct?compx_fp?astruct?compx_fp?b）?????????????????????
{
	struct?compx_fp?c;
	c.real=（multiply_i（a.realb.real）-multiply_i（a.imagb.imag））;
	c.imag=（multiply_i（a.realb.imag）+multiply_i（a.imagb.real））;
	return（c）;
}



void?FFT_fp（struct?compx_fp?*xin）
{
	int?fmnv2nm1iklj=0;
	struct?compx_fp?uwt;


	nv2=FFT_N/2;??????????????????
	nm1=FFT_N-1;??
	for（i=0;i	{
		if（i		{
			t=xin[j];???????????
			xin[j]=xin[i];
			xin[i]=t;
		}
		k=nv2;????????????????????
		while（k<=j）??????????????????
		{???????????
			j=j-k;?????????????????
			k=k/2;????????????????
		}
		j=j+k;???????????????????
	}
	
	
	int?leleiip;????????????????????????????
	f=FFT_N;
	for（l=1;（f=f/2）!=1;l++）?;?????????????????
	for（m=1;m<=l;m++）?????????????????????????
	{????????????????????????????????????????
		le=2<<（m-1）;????????????????????????????
		
		lei=le/2;??????????????????????????????
		u.real=（long）（1.0*Change）;?????????????????????????????
		u.imag=（long）（0.0*Change）;
		w.real=（long）（cos（PI/lei）*Change）;?????????????????????
		w.imag=（long）（-sin（PI/lei）*Change）;
		for（j=0;j<=lei-1;j++）???????????????????
		{
			for（i=j;i<=FFT_N-1;i=i+le）???????????
			{
				ip=i+lei;???????????????????????????
				t=multiply_fp（xin[ip]u）;????????????????????
				xin[ip].real=xin[i].real-t.real;
				xin[ip].imag=xin[i].imag-t.imag;
				xin[i].real=xin[i].real+t.real;
				xin[i].imag=xin[i].imag+t.imag;
			}
			u=multiply_fp（uw）;?
						
		}		
	}

	
}
//定點FFT


//浮點FFT
struct?compx_fl?{float?realimag;};???????????????????????????????????
struct?compx_fl?s_fl[FFT_N];?

struct?compx_fl?multiply_fl（struct?compx_fl?astruct?compx_fl?b）?????????????????????
{
	struct?compx_fl?c;
	c.real=a.real*b.real-a.imag*b.imag;
	c.imag=a.real*b.imag+a.imag*b.real;
	return（c）;
}

void?FFT_fl（struct?compx_fl?*xin）
{
	int?fmnv2nm1iklj=0;
	struct?compx_fl?uwt;
	
	nv2=FFT_N/2;??????????????????
	nm1=FFT_N-1;??
	for（i=0;i	{
		if（i		{
			t=xin[j];???????????
			xin[j]=xin[i];
			xin[i]=t;
		}
		k=nv2;????????????????????
		while（k<=j）???????????????
		{???????????
			j=j-k;?????????????????
			k=k/2;?????????????????
		}
		j=j+k;??????????????????
	}
	
	
	int?leleiip;????????????????????????????
	f=FFT_N;
	for（l=1;（f=f/2）!=1;l++）?;
	
	for（m=1;m<=l;m++）?????

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????225343??2015-05-20?09:29??fft_final\Debug\fft_final.exe

?????文件?????227280??2015-05-20?09:29??fft_final\Debug\fft_final.ilk

?????文件?????221564??2015-05-19?21:27??fft_final\Debug\fft_final.pch

?????文件?????508928??2015-05-20?09:29??fft_final\Debug\fft_final.pdb

?????文件??????16617??2015-05-20?09:29??fft_final\Debug\main.obj

?????文件??????33792??2015-05-20?18:24??fft_final\Debug\vc60.idb

?????文件??????53248??2015-05-20?09:29??fft_final\Debug\vc60.pdb

?????文件???????4315??2015-05-19?21:49??fft_final\fft_final.dsp

?????文件????????526??2015-05-19?21:26??fft_final\fft_final.dsw

?????文件??????41984??2015-06-05?00:26??fft_final\fft_final.ncb

?????文件??????48640??2015-06-05?00:26??fft_final\fft_final.opt

?????文件????????252??2015-05-20?18:24??fft_final\fft_final.plg

?????文件?????????96??2015-05-19?20:51??fft_final\input_i.txt

?????文件????????192??2015-05-19?20:42??fft_final\input_r.txt

?????文件???????7666??2015-05-20?09:29??fft_final\main.cpp

?????文件????????743??2015-05-20?18:24??fft_final\output_dl.txt

?????文件????????295??2015-05-20?18:24??fft_final\output_dp.txt

?????文件????????743??2015-05-20?18:24??fft_final\output_fl.txt

?????文件????????295??2015-05-20?18:24??fft_final\output_fp.txt

?????目錄??????????0??2019-03-31?12:19??fft_final\Debug

?????目錄??????????0??2019-03-31?12:19??fft_final

-----------?---------??----------?-----??----

??????????????1392519????????????????????21