//
//?FFT.cpp
//

#include?“FFT.h“


//?標準?FFT，其中?Data.size（）?為2的冪次方
void?CFFT::FFT（VectorC&?Data）
{
	ReArrange（Data）;
	Perform（Data）;
}

//?擴展?FFT，其中?Output.size（）?為2的冪次方，Input.size（）?void?CFFT::FFT（VectorC&?Output?const?VectorC&?Input）
{
	ReArrange（Output?Input）;
	Perform（Output）;
}

//?標準?IFFT，其中?Data.size（）?為2的冪次方
void?CFFT::IFFT（VectorC&?Data）
{
	ReArrange（Data）;
	Perform（Data?true）;
	Scale（Data）;
}

?//?擴展?IFFT，其中?Output.size（）?為2的冪次方，Input.size（）?void?CFFT::IFFT（VectorC&?Output?const?VectorC&?Input）
{
	ReArrange（Output?Input）;
	Perform（Output?true）;
	Scale（Output）;
}

//?Matlab?中的?fftshift?函數
void?CFFT::FFTSHIFT（VectorC&?Data）
{
	int?N?=?Data.size（）;
	int?K?=?（N?+?1）?/?2;

	VectorC?Temp（N）;
	for?（int?i?=?0;?i?		Temp[i]?=?Data[（i?+?K）?%?N];

	for?（int?i?=?0;?i?		Data[i]?=?Temp[i];
}

//?FFT?的實現部分
void?CFFT::Perform（VectorC&?Data?const?bool?bIFFT?/*?=?false?*/）
{
	unsigned?int?N?=?Data.size（）;
	const?double?PI?=?3.14159265358979323846;

	for?（unsigned?int?Step?=?1;?Step?	{
		const?unsigned?int?Jump?=?Step?<		const?double?delta?=?（bIFFT???PI?:?-PI）?/?Step;
		const?double?Sine?=?sin（0.5*delta）;
		const?ComplexD?Multiplier（-2?*?Sine*Sine?sin（delta））;

		ComplexD?Factor（1?0）;
		for?（unsigned?int?Group?=?0;?Group?		{
			for?（unsigned?int?Pair?=?Group;?Pair?			{
				const?unsigned?int?Match?=?Pair?+?Step;
				const?ComplexD?Product?=?Factor*Data[Match];
				Data[Match]?=?Data[Pair]?-?Product;
				Data[Pair]?+=?Product;
			}
			Factor?=?Multiplier*Factor?+?Factor;
		}
	}
}

//?將?Data?的逆序結果放入?Data
void?CFFT::ReArrange（VectorC&?Data）
{
	unsigned?int?N?=?Data.size（）;

	unsigned?int?j?=?0;
	for?（unsigned?int?i?=?0;?i?	{
		if?（j?>?i）
		{
			const?ComplexD?Temp?=?Data[j];
			Data[j]?=?Data[i];
			Data[i]?=?Temp;
		}

		unsigned?int?mask?=?N;
		while?（j&（mask?>>=?1））
			j?&=?~mask;

		j?|=?mask;
	}
}

//?將?Input?的逆序結果放入?Output
void?CFFT::ReArrange（VectorC&?Output?const?VectorC&?Input）
{
	unsigned?int?Ni?=?Input.size（）;
	unsigned?int?No?=?Output.size（）;

	if?（No?
	VectorC?Temp;
	bool?flag?=?false;
	if?（Ni?	{
		Temp?=?VectorC（No）;
		for?（int?i?=?0;?i?			Temp[i]?=?Input[i];

		flag?=?!flag;
	}

	unsigned?int?j?=?0;
	for?（unsigned?int?i?=?0;?i?	{
		if?（flag）????Output[j]?=?Temp[i];
		else?????????Output[j]?=?Input[i];

		unsigned?int?mask?=?No;
		while?（j&（mask?>>=?1））
			j?&=?~mask;

		j?|=?mask;
	}
}

//?只針對IFFT，最后結果要除以?Data.size（）
void?CFFT::Scale（VectorC&?Data）
{
	unsigned?int?N?=?Data.size（）;

	const?double?Factor?=?1.0?/?N;
	for?（unsigned?int?i?=?0;?i?		Data[i]?*=?Factor;
}

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

?????文件?????527420??2017-03-25?16:47??bpCSAR3deg\1.bmp

?????文件?????753558??2017-03-25?16:48??bpCSAR3deg\2.bmp

?????文件???????7651??2017-01-04?15:17??bpCSAR3deg\bpCSAR3deg\bpCSAR3deg.vcxproj

?????文件???????1500??2017-01-04?15:17??bpCSAR3deg\bpCSAR3deg\bpCSAR3deg.vcxproj.filters

?????文件???????2914??2017-01-04?15:45??bpCSAR3deg\bpCSAR3deg\FFT.cpp

?????文件???????1167??2017-01-04?15:45??bpCSAR3deg\bpCSAR3deg\FFT.h

?????文件????????993??2017-01-04?10:20??bpCSAR3deg\bpCSAR3deg\Jet.cpp

?????文件????????174??2017-03-25?15:39??bpCSAR3deg\bpCSAR3deg\Jet.h

?????文件???????5643??2017-03-25?16:41??bpCSAR3deg\bpCSAR3deg\main.cpp

?????文件????????305??2016-12-31?16:01??bpCSAR3deg\bpCSAR3deg\Point3D.cpp

?????文件????????218??2017-03-25?15:39??bpCSAR3deg\bpCSAR3deg\Point3D.h

?????文件???????1330??2016-12-31?14:25??bpCSAR3deg\bpCSAR3deg.sln

????..A..H.?????38912??2017-03-25?16:44??bpCSAR3deg\bpCSAR3deg.v12.suo

?????文件??????32768??2017-03-25?16:41??bpCSAR3deg\x64\Release\bpCSAR3deg.exe

?????目錄??????????0??2017-03-25?16:49??bpCSAR3deg\x64\Release

?????目錄??????????0??2017-03-25?16:49??bpCSAR3deg\bpCSAR3deg

?????目錄??????????0??2017-03-25?15:29??bpCSAR3deg\x64

?????目錄??????????0??2017-03-25?16:49??bpCSAR3deg

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

??????????????1374553????????????????????18