#include
//#include?
#include?
/*********************************************************************
快速福利葉變換C函數(shù)
函數(shù)簡介：此函數(shù)是通用的快速傅里葉變換C
語言函數(shù)，移植性強，以下部分不依賴硬件。此函數(shù)采用聯(lián)合體的形式表示一個復(fù)數(shù)，輸入為自然順序的復(fù)數(shù)（輸入實數(shù)是可令復(fù)數(shù)虛部為0），輸出為經(jīng)過FFT變換的自然順序的復(fù)數(shù)
使用說明：使用此函數(shù)只需更改宏定義FFT_N的值即可實現(xiàn)點數(shù)的改變，F(xiàn)FT_N的?應(yīng)該為2的N次方，不滿足此條件時應(yīng)在后面補0
函數(shù)調(diào)用：FFT（s）;
時間：2010-2-20
版本：Ver1.0?參考文獻(xiàn)：
**********************************************************************/
#include
#define?PI?3.1415926535897932384626433832795028841971?	//定義圓周率值
#define??FFT_N??512?									//定義福利葉變換的點數(shù)
struct?compx?{float?realimag;};?						//定義一個復(fù)數(shù)結(jié)構(gòu)struct?compx?s[FFT_N];
struct?compx?s[FFT_N];?			?	?	?	?	?	?	//FFT輸入和輸出：從S[1]開始存放，根據(jù)大小自己定義
float?result[FFT_N];
/*******************************************************************
函數(shù)原型：
struct?compx?EE（struct?compx?b1struct?compx?b2）
函數(shù)功能：對兩個復(fù)數(shù)進(jìn)行乘法運算
輸入?yún)?shù)：兩個以聯(lián)合體定義的復(fù)數(shù)ab
輸出參數(shù)：a和b的乘積，以聯(lián)合體的形式輸出
*******************************************************************/
struct?compx?EE（struct?compx?astruct?compx?b）
{
	struct?compx?c;
	c.real=a.real*b.real-a.imag*b.imag;
	c.imag=a.real*b.imag+a.imag*b.real;
return（c）;
}
/*****************************************************************
函數(shù)原型：void?FFT（struct?compx?*xinint?N）
函數(shù)功能：對輸入的復(fù)數(shù)組進(jìn)行快速傅里葉變換（FFT）
輸入?yún)?shù)：*xin復(fù)數(shù)結(jié)構(gòu)體組的首地址指針，struct型
*****************************************************************/
void?FFT（struct?compx?*xin）
{
	int?fmnv2nm1iklj=0;
	struct?compx?uwt;
	nv2=FFT_N/2;
	//變址運算，即把自然順序變成倒位序，采用雷德算法
	nm1=FFT_N-1;
	for（i=0;i	{
		if（i		{
			t=xin[j];
			xin