#include??“msp430x24x.h“
#include?“math.h“

/*********************************************************************
?????????????????????????快速福利葉變換C函數(shù)
函數(shù)簡介：此函數(shù)是通用的快速傅里葉變換C語言函數(shù)，移植性強(qiáng)，以下部分不依
??????????賴硬件。此函數(shù)采用聯(lián)合體的形式表示一個(gè)復(fù)數(shù)，輸入為自然順序的復(fù)
??????????數(shù)（輸入實(shí)數(shù)是可令復(fù)數(shù)虛部為0），輸出為經(jīng)過FFT變換的自然順序的
??????????復(fù)數(shù)
使用說明：使用此函數(shù)只需更改宏定義FFT_N的值即可實(shí)現(xiàn)點(diǎn)數(shù)的改變，F(xiàn)FT_N的
??????????應(yīng)該為2的N次方，不滿足此條件時(shí)應(yīng)在后面補(bǔ)0
函數(shù)調(diào)用：FFT（s）;
時(shí)????間：2010-2-20
版????本：Ver1.0
參考文獻(xiàn)：????
??????
**********************************************************************/
#include

#define?PI?3.1415926535897932384626433832795028841971???????????????//定義圓周率值
#define?FFT_N?128???????????????????????????????????????????????????//定義福利葉變換的點(diǎn)數(shù)

struct?compx?{float?realimag;};????????????????????????????????????//定義一個(gè)復(fù)數(shù)結(jié)構(gòu)
struct?compx?s[FFT_N];??????????????????????????????????????????????//FFT輸入和輸出：從S[1]開始存放，根據(jù)大小自己定義


/*******************************************************************
函數(shù)原型：struct?compx?EE（struct?compx?b1struct?compx?b2）??
函數(shù)功能：對兩個(gè)復(fù)數(shù)進(jìn)行乘法運(yùn)算
輸入?yún)?shù)：兩個(gè)以聯(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;??????????????????//變址運(yùn)算，即把自然順序變成倒位序，采用雷德算法
???nm1=FFT_N-1;??
???for（i=0;i???{
????if（i?????{
??????t=xin[j];???????????
??????xin[j]=xin[i];
??????xin[i]=t;
?????}
????k=nv2;????????????????????//求j的下一個(gè)倒位序
????while（k<=j）???????????????//如果k<=j表示j的最高位為1???
?????{???????????
??????j=j-k;?????????????????//把最高位變成0
??????k=k/2;?????????????????//k/2，比較次高位，依次類推，逐個(gè)比較，直到某個(gè)位為0
?????}
???j=j+k;???????????????????//把0改為1
??}
?????????????????????????
??{
???int?leleiip;????????????????????????????//FFT運(yùn)算核，使用蝶形運(yùn)算完成FFT運(yùn)算
????f=FFT_N;
???for（l=1;（f=f/2）!=1;l++）??????????????????//計(jì)算l的值，即計(jì)算蝶形級數(shù)
???????????;
??for（m=1;m<=l;m++）?????????????????????????//?控制蝶形結(jié)級數(shù)
???{????????????????????????????????????????//m表示第m級蝶形，l為蝶形級總數(shù)l=log（2）N
????le=2<<（m-1）;????????????????????????????//le蝶形結(jié)距離，即第m級蝶形的蝶形結(jié)相距l(xiāng)e點(diǎn)
????lei=le/2;???????????????????????????????//同一蝶形結(jié)中參加運(yùn)算的兩點(diǎn)的距離
????u.real=1.0;?????????????????????????????//u為蝶形結(jié)運(yùn)算系數(shù)，初始值為1
????u.imag=0.0;
????w.real=cos（PI/lei）;?????????????????????//w為系數(shù)商，即當(dāng)前系數(shù)與前一個(gè)系數(shù)的商
????w.imag=-sin（PI/lei）;
????for（j=0;j<=lei-1;j++）???????????????????//控制計(jì)算不同種蝶形結(jié)，即計(jì)算系數(shù)不同的蝶形結(jié)
?????{
??????for（i=j;i<=FFT_N-1;i=i+le）????????????//控制同一蝶形結(jié)運(yùn)算，即計(jì)算系數(shù)相同蝶形結(jié)
???????{
????????ip=i+lei;???????????????????????????//i，ip分別表示參加蝶形運(yùn)算的兩個(gè)節(jié)點(diǎn)
????????t=E

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件??????46786??2013-02-27?18:00??fft\Backup?of?fft.ewp

?????文件??????28596??2013-02-28?16:27??fft\Debug\Exe\fft.d43

?????文件????????116??2013-02-28?20:03??fft\Debug\Obj\fft.pbd

?????文件??????25107??2013-02-28?16:27??fft\Debug\Obj\main.r43

?????文件????????157??2013-02-27?17:58??fft\fff.eww

?????文件???????2602??2013-02-28?21:28??fft\fft.dep

?????文件??????13372??2013-02-27?19:43??fft\fft.ewd

?????文件??????44625??2013-02-27?19:45??fft\fft.ewp

?????文件????????157??2013-02-27?17:41??fft\fft.eww

?????文件???????5924??2013-02-27?19:47??fft\FFT1.h

?????文件???????4709??2013-02-28?16:27??fft\main.c

?????文件???????3356??2013-02-28?21:28??fft\settings\fff.wsdt

?????文件???????2268??2013-02-28?20:03??fft\settings\fft.cspy.bat

?????文件???????5000??2013-02-28?21:28??fft\settings\fft.dbgdt

?????文件????????591??2013-02-28?21:28??fft\settings\fft.dni

?????文件???????2237??2013-02-27?19:43??fft\settings\fft.wsdt

?????目錄??????????0??2013-02-28?16:27??fft\Debug\Exe

?????目錄??????????0??2013-02-28?16:00??fft\Debug\List

?????目錄??????????0??2013-02-28?16:34??fft\Debug\Obj

?????目錄??????????0??2013-02-28?16:00??fft\Debug

?????目錄??????????0??2013-02-28?16:00??fft\settings

?????目錄??????????0??2013-03-05?11:09??fft

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

???????????????185603????????????????????22