快速傅里叶变换_C语言代码

使用VC++6.0进行编写的C语言快速傅里叶变换和逆变换（FFT和IFFT）

#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 < lWidth）
	{
		w *= 2;
		wp++;
	}
	         
	while （h < lHeight）
	{
		h *= 2;
		hp++;
	}
		
	// 分配内存


	TempT = （COMPLEX *）malloc（sizeof（COMPLEX）*h）;
	TempF = （COMPLEX *）malloc（sizeof（COMPLEX）*h）;
	
	// 对y方向进行快速付立叶变换
	//rgb
	/*for （i = 0; i < w * 3; i++）
	{
		// 抽取数据
		for （j = 0; j < h; j++）
			TempT[j] = TD[j * w * 3 + i];//rgb
		
		// 一维快速傅立叶变换
		FFT（TempT TempF hp）;

		// 保存变换结果
		for （j = 0; j < h; j++）
			TD[j * w * 3 + i] = TempF[j];
	}
	*/
	//灰度
	for （i = 0; i < w ; i++）
	{
		// 抽取数据
		for （j = 0; j < h; j++）
		{	TempT[j] = TD[j * w  + i];}//rgb
		
		// 一维快速傅立叶变换
		FFT（TempT TempF hp）;

		// 保存变换结果
		for （j = 0; j < h; 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