快速傅里葉變換C程序-方便移植

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

2、xTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/定義圓周率值/定義福利葉/定義一個復數(shù)結構/FFT輸入和輸#include#definePI3.1415926535897932384626433832795028841971#defineFFT_N128變換的點數(shù)structcompxfloatreal,imag;structcompxsFFT_N;出：從Sl開始存放，根據(jù)大小自己定義函數(shù)原型：structcompxEE(structcompxbl,structcompxb2)函數(shù)功能：對兩個復數(shù)進行乘法運算輸入?yún)?shù)：兩個以聯(lián)合體定義

3、的復數(shù)a,b輸出參數(shù)：a和b的乘積，以聯(lián)合體的形式輸出/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/structcompxEE(structcompxa,structcompxb)structcompxc;c.real=a.real*b.real-a.imag*b.imag;c.imag=a.real*b.imag+a.imag*b.real;return(c);函數(shù)原型

4、：voidFFT(structcompx*xin,intN)函數(shù)功能：對輸入的復數(shù)組進行快速傅里葉變換(FFT)輸入?yún)?shù)：*xin復數(shù)結構體組的首地址指針，struct型/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/voidFFT(structcompx*xin)intf,m,nv2,nm1,i,k,l,j=1;structcompxu,w,t;nv2=FFT_N/2;法nm1=

5、FFT_N-1;for(i=0;inm1;i+)if(ij)t=xinj;xinj=xini;xini=t;k=nv2;while(k=j)j=j-k;k=k/2;j=j+k;/變址運算，即把自然順序變成倒位序，采用雷德算如果ij,即進行變址/求j的下一個倒位序如果kv=j,表示j的最高位為1/把最高位變成0/k/2,比較次高位，依次類推，逐個比較，直到某個位為0/把0改為1intle,lei,ip;f=FFT_N;for(l=1;(f=f/2)!=1;l+)for(m=1;m=l;m+)l=log(2)Nle=2(m-1);相距l(xiāng)e點lei=le/2;u.real=1.0;u.imag=0.

6、0;w.real=cos(PI/lei);w.imag=-sin(PI/lei);for(j=0;j=lei-1;j+)蝶形結for(i=j;i=FFT_N-1;i=i+le)/FFT運算核，使用蝶形運算完成FFT運算/計算l的值，即計算蝶形級數(shù)/控制蝶形結級數(shù)/m表示第m級蝶形，l為蝶形級總數(shù)/le蝶形結距離，即第m級蝶形的蝶形結/同一蝶形結中參加運算的兩點的距離/u為蝶形結運算系數(shù)，初始值為1/w為系數(shù)商，即當前系數(shù)與前一個系數(shù)的商/控制計算不同種蝶形結，即計算系數(shù)不同的/控制同一蝶形結運算，即計算系數(shù)相同蝶形/i，ip分別表示參加蝶形運算的兩個節(jié)點/蝶形運算，詳見公式ip=i+lei;t

7、=EE(xinip,u);xinip.real=xini.real-t.real;xinip.imag=xini.imag-t.imag;xini.real=xini.real+t.real;xini.imag=xini.imag+t.imag;/改變系數(shù)，進行下一個蝶形運算u=EE(u,w);函數(shù)原型：voidmain()函數(shù)功能：測試FFT變換，演示函數(shù)使用方法輸入?yún)?shù)：無輸出參數(shù)：無/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/voidmain()inti;for(i=0;iFFT_N;i+)/給結構體賦值si.real=sin(2*3.141592653589793*i/FFT_N);/實部為正弦波FFT_N點采樣，賦值為1si.imag=