#include?
#include?
#include?
#include?“fft12_ifft12.h“


/*快速付里哀變換
TD為時域值FD為頻域值power為2的冪數*/
void?FFT（COMPLEX?*?TD?COMPLEX?*?FD?int?power）
{
	int?count;
	int?ijkbfsizep;
	double?angle;
	COMPLEX?*W*X1*X2*X;

	/*計算付里哀變換點數*/
	count=1<	/*分配運算所需存儲器*/
	W=（COMPLEX?*）malloc（sizeof（COMPLEX）*count/2）;
	X1=（COMPLEX?*）malloc（sizeof（COMPLEX）*count）;
	X2=（COMPLEX?*）malloc（sizeof（COMPLEX）*count）;
	/*計算加權系數*/
	for（i=0;i	{
		angle=-i*pi*2/count;
		W[i].re=cos（angle）;
		W[i].im=sin（angle）;
	}
	/*將時域點寫入存儲器*/
	memcpy（X1TDsizeof（COMPLEX）*count）;
	/*蝶形運算*/
	for（k=0;k	{
		for（j=0;j<1<		{
			bfsize=1<<（power-k）;
			for（i=0;i			{
				p=j*bfsize;
				X2[i+p]=Add（X1[i+p]X1[i+p+bfsize/2]）;
				X2[i+p+bfsize/2]=Mul（Sub（X1[i+p]X1[i+p+bfsize/2]）W[i*（1<			}
		}
		X=X1;
		X1=X2;
		X2=X;
	}
	/*重新排序*/
	for（j=0;j	{
		p=0;
		for（i=0;i		{
			if?（j&（1<		}
		FD[j]=X1[p];
	}
	/*釋放存儲器*/
	free（W）;
	free（X1）;
	free（X2）;
}

/*快速付里哀反變換利用快速付里哀變換
FD為頻域值TD為時域值power為2的冪數*/
void?IFFT（COMPLEX?*FD?COMPLEX?*TD?int?power）
{
	int?icount;
	COMPLEX?*x;

	/*計算付里哀反變換點數*/
	count=1<	/*分配運算所需存儲器*/
	x=（COMPLEX?*）malloc（sizeof（COMPLEX）*count）;
	/*將頻域點寫入存儲器*/
	memcpy（xFDsizeof（COMPLEX）*count）;
	/*求頻域點的共軛*/
	for（i=0;i	{
		x[i].im=-x[i].im;
	}
	/*調用快速付里哀變換*/
	FFT（xTDpower）;
	/*求時域點的共軛*/
	for（i=0;i	{
		TD[i].re/=count;
		TD[i].im=-TD[i].im/count;
	}
	/*釋放存儲器*/
	free（x）;
}



/*************************************************************************
?*
?*?函數名稱：
?*???Fourier（）
?*
?*?參數:
?*???COMPLEX*?TD		-?輸入的時域序列
?*	?long?lWidth		-?圖象寬度
?*	?long?lHeight		-?圖象高度
?*	?COMPLEX*?FD		-?輸出的頻域序列
?*
?*?返回值:
?*???BOOL???????????????-?成功返回TRUE，否則返回FALSE。
?*
?*?說明:
?*???該函數進行二維快速付立葉變換。
?*
?************************************************************************/

void?FFT2（COMPLEX?*?TD?long?lWidth?long?lHeight?COMPLEX??*?FD）
{	COMPLEX?*TempT?*TempF;
	//?循環變量
	long	i;
	long	j;
	long????k;


	//?進行付立葉變換的寬度和高度（2的整數次方）
	long?w?=?1;
	long?h?=?1;
	int?wp?=?0;
	int?hp?=?0;
	
	//?計算進行付立葉變換的寬度和高度（2的整數次方）
	while?（w?	{
		w?*=?2;
		wp++;
	}
	?????????
	while?（h?	{
		h?*=?2;
		hp++;
	}
		
	//?分配內存


	TempT?=?（COMPLEX?*）malloc（sizeof（COMPLEX）*h）;
	TempF?=?（COMPLEX?*）malloc（sizeof（COMPLEX）*h）;
	
	//?對y方向進行快速付立葉變換
	//rgb
	/*for?（i?=?0;?i?	{
		//?抽取數據
		for?（j?=?0;?j?			TempT[j]?=?TD[j?*?w?*?3?+?i];//rgb
		
		//?一維快速傅立葉變換
		FFT（TempT?TempF?hp）;

		//?保存變換結果
		for?（j?=?0;?j?			TD[j?*?w?*?3?+?i]?=?TempF[j];
	}
	*/
	//灰度
	for?（i?=?0;?i?	{
		//?抽取數據
		for?（j?=?0;?j?		{	TempT[j]?=?TD[j?*?w??+?i];}//rgb
		
		//?一維快速傅立葉變換
		FFT（TempT?TempF?hp）;

		//?保存變換結果
		for?（j?=?0;?j?		{	TD[j?*?w??+?i

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2009-04-17?19:53??快速傅里葉變換_C語言代碼\
?????文件?????????664??2009-04-17?17:38??快速傅里葉變換_C語言代碼\complex_oper.h
?????目錄???????????0??2009-04-17?19:50??快速傅里葉變換_C語言代碼\Debug\
?????文件????????9810??2009-04-17?19:11??快速傅里葉變換_C語言代碼\Debug\fft12_ifft12.obj
?????文件??????208959??2009-04-17?19:50??快速傅里葉變換_C語言代碼\Debug\fft2_ifft2.exe
?????文件??????209332??2009-04-17?19:50??快速傅里葉變換_C語言代碼\Debug\fft2_ifft2.ilk
?????文件??????204828??2009-04-17?19:11??快速傅里葉變換_C語言代碼\Debug\fft2_ifft2.pch
?????文件??????459776??2009-04-17?19:50??快速傅里葉變換_C語言代碼\Debug\fft2_ifft2.pdb
?????文件????????3092??2009-04-17?19:50??快速傅里葉變換_C語言代碼\Debug\main.obj
?????文件???????41984??2009-04-17?19:50??快速傅里葉變換_C語言代碼\Debug\vc60.idb
?????文件???????53248??2009-04-17?19:50??快速傅里葉變換_C語言代碼\Debug\vc60.pdb
?????文件????????6786??2009-04-17?19:11??快速傅里葉變換_C語言代碼\fft12_ifft12.cpp
?????文件?????????831??2009-04-17?18:30??快速傅里葉變換_C語言代碼\fft12_ifft12.h
?????文件????????4456??2009-04-17?19:52??快速傅里葉變換_C語言代碼\fft2_ifft2.dsp
?????文件?????????528??2009-04-17?17:25??快速傅里葉變換_C語言代碼\fft2_ifft2.dsw
?????文件???????41984??2009-04-17?19:53??快速傅里葉變換_C語言代碼\fft2_ifft2.ncb
?????文件???????54784??2009-04-17?19:53??快速傅里葉變換_C語言代碼\fft2_ifft2.opt
?????文件????????1314??2009-04-17?19:50??快速傅里葉變換_C語言代碼\fft2_ifft2.plg
?????文件?????????361??2009-04-17?19:51??快速傅里葉變換_C語言代碼\main.cpp