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

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

#define?PI?3.1415926535897932384626433832795028841971???????????????//定義圓周率值
#define?FFT_N?128???????????????????????????????????????????????????//定義福利葉變換的點數

struct?compx?{float?realimag;};????????????????????????????????????//定義一個復數結構
struct?compx?s[FFT_N];??????????????????????????????????????????????//FFT輸入和輸出：從S[1]開始存放，根據大小自己定義


/*******************************************************************
函數原型：struct?compx?EE（struct?compx?b1struct?compx?b2）??
函數功能：對兩個復數進行乘法運算
輸入參數：兩個以聯合體定義的復數ab
輸出參數：a和b的乘積，以聯合體的形式輸出
*******************************************************************/
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）;
}

/*****************************************************************
函數原型：void?FFT（struct?compx?*xinint?N）
函數功能：對輸入的復數組進行快速傅里葉變換（FFT）
輸入參數：*xin復數結構體組的首地址指針，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[j]=xin[i];
??????xin[i]=t;
?????}
????k=nv2;????????????????????//求j的下一個倒位序
????while（k<=j）???????????????//如果k<=j表示j的最高位為1???
?????{???????????
??????j=j-k;?????????????????//把最高位變成0
??????k=k/2;?????????????????//k/2，比較次高位，依次類推，逐個比較，直到某個位為0
?????}
???j=j+k;???????????????????//把0改為1
??}
?????????????????????????
??{
???int?leleiip;????????????????????????????//FFT運算核，使用蝶形運算完成FFT運算
????f=FFT_N;
???for（l=1;（f=f/2）!=1;l++）??????????????????//計算l的值，即計算蝶形級數
???????????;
??for（m=1;m<=l;m++）?????????????????????????//?控制蝶形結級數
???{????????????????????????????????????????//m表示第m級蝶形，l為蝶形級總數l=log（2）N
????le=2<<（m-1）;????????????????????????????//le蝶形結距離，即第m級蝶形的蝶形結相距le點
????lei=le/2;???????????????????????????????//同一蝶形結中參加運算的兩點的距離
????u.real=1.0;?????????????????????????????//u為蝶形結運算系數，初始值為1
????u.imag=0.0;
????w.real=cos（PI/lei）;?????????????????????//w為系數商，即當前系數與前一個系數的商
????w.imag=-sin（PI/lei）;
????for（j=0;j<=lei-1;j++）???????????????????//控制計算不同種蝶形結，即計算系數不同的蝶形結
?????{
??????for（i=j;i<=FFT_N-1;i=i+le）????????????//控制同一蝶形結運算，即計算系數相同蝶形結
???????{
????????ip=i+lei;???????????????????????????//i，ip分別表示參加蝶形運算的兩個節點
????????t=E

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

?????文件??????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