(快速傅里葉變換)C語(yǔ)言程序.

1、#i nclude #in elude vintrin sics.h/*快速傅立葉變換 C 函數(shù)函數(shù)簡(jiǎn)介：此函數(shù)是通用的快速傅里葉變換C 語(yǔ)言函數(shù)，移植性強(qiáng)，以下部分不依賴硬件。此函數(shù)采用聯(lián)合體的形式表示一個(gè)復(fù)數(shù)，輸入為自然順序的復(fù) 數(shù)(輸入實(shí)數(shù)是可令復(fù)數(shù)虛部為0)，輸出為經(jīng)過(guò) FFT 變換的自然順序的復(fù)數(shù)使用說(shuō)明：使用此函數(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)：*#in clude#defi ne PI 3.141592653589793238

2、4626433832795028841971#define FFT_N 128變換的點(diǎn)數(shù)定義圓周率值/定義傅立葉struct compx float real,imag;struct compx sFFT_N;出：從 S1開(kāi)始存放，根據(jù)大小自己定義/定義一個(gè)復(fù)數(shù)結(jié)構(gòu)/FFT 輸入和輸/*函數(shù)原型： struct compx EE(struct compx b1,struct compx b2) 函數(shù)功能：對(duì)兩個(gè)復(fù)數(shù)進(jìn)行乘法運(yùn)算輸入?yún)?shù)：兩個(gè)以聯(lián)合體定義的復(fù)數(shù)a,b輸出參數(shù)：a 和 b 的乘積，以聯(lián)合體的形式輸出*/struct compx EE(struct compx a,struct co

3、mpx 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 *xi n,int N)函數(shù)功能：對(duì)輸入的復(fù)數(shù)組進(jìn)行快速傅里葉變換(FFT)輸入?yún)?shù)：*xin 復(fù)數(shù)結(jié)構(gòu)體組的首地址指針，struct 型*/ void FFT(struct compx *xi n)int f,m, nv2,n m1,i,k,l,j=O;struct compx u,w,t;/變址運(yùn)算，即把自然順序變成倒位序，采用雷德

4、算如果 ij,即進(jìn)行變址/求 j 的下一個(gè)倒位序如果 k=j,表示 j 的最高位為 1/把最高位變成 0/k/2，比較次高位，依次類推，逐個(gè)比較，直到某個(gè)位為0/把 0 改為 1/FFT 運(yùn)算核，使用蝶形運(yùn)算完成FFT 運(yùn)算/計(jì)算 I 的值，即計(jì)算蝶形級(jí)數(shù)/控制蝶形結(jié)級(jí)數(shù)/m 表示第 m 級(jí)蝶形，I 為蝶形級(jí)總數(shù)/le 蝶形結(jié)距離，即第 m 級(jí)蝶形的蝶形結(jié)/同一蝶形結(jié)中參加運(yùn)算的兩點(diǎn)的距離/u 為蝶形結(jié)運(yùn)算系數(shù)，初始值為1/w 為系數(shù)商，即當(dāng)前系數(shù)與前一個(gè)系數(shù)的商 /控制計(jì)算不同種蝶形結(jié)，即n v2=FFT_N/2;法n m 仁 FFT_N-1;for(i=0;i nm1;i+) if(ij)

5、t=xi nj;xi nj=xi n i;xin i=t;k=nv2;while(k=j)j=j-k;k=k/2;j=j+k;int le,lei,ip;f=FFT_N;for(l=1;(f=f/2)!=1;l+);for(m=1;m=l;m+)l=log ( 2)N le=2(m-1);相距 le 點(diǎn)lei=le/2;u.real=1.0;u.imag=0.0;w.real=cos(PI/lei);w.imag=-sin( PI/lei);for(j=0;j=lei-1;j+)計(jì)算系數(shù)不同的si.real=sqrt(si.real*si.real+si.imag*si.imag);while

6、(1);蝶形結(jié)for(i=j;i=FFT_N-1;i=i+le)控制同一蝶形結(jié)運(yùn)算，即計(jì)算系數(shù)相同蝶形ip=i+lei; t=EE(xi n ip,u);xi nip.real=xi n i.real-t.real;xin ip.imag=x ini.imag-t.imag; xi ni.real=xin i.real+t.real;xi ni.imag=xini.imag+t.imag; u=EE(u,w);/i，ip 分別表示參加蝶形運(yùn)算的兩個(gè)節(jié)點(diǎn) /蝶形運(yùn)算，詳見(jiàn)公式/改變系數(shù)，進(jìn)行下一個(gè)蝶形運(yùn)算/*函數(shù)原型 函數(shù)功能 輸入?yún)?shù) 輸出參數(shù)void mai n()測(cè)試 FFT 變換，演示函

7、數(shù)使用方法 無(wú)無(wú)*/void mai n()int i;for(i=0;iFFT_N;i+)si.real=si n(2*3.141592653589793*i/FFT_N); /si.imag=0;/給結(jié)構(gòu)體賦值實(shí)部為正弦波 FFT_N 點(diǎn)采樣，賦值為 1 虛部為 0FFT(s);/進(jìn)行快速傅立葉變換for(i=0;iFFT_N;i+)部部分/求變換后結(jié)果的模值，存入復(fù)數(shù)的實(shí)#i nclude #in elude vintrin sics.h/*快速傅立葉變換 C 程序包函數(shù)簡(jiǎn)介：此程序包是通用的快速傅里葉變換C 語(yǔ)言函數(shù)，移植性強(qiáng)，以下部分不依賴硬件。此程序包采用聯(lián)合體的形式表示一個(gè)復(fù)數(shù)，

8、輸入為自然順序的復(fù)數(shù)(輸入實(shí)數(shù)是可令復(fù)數(shù)虛部為0)，輸出為經(jīng)過(guò) FFT 變換的自然順序的復(fù)數(shù).此程序包可在初始化時(shí)調(diào)用create_sin_tab()函數(shù)創(chuàng)建正弦函數(shù)表，以后的可采用查表法計(jì)算耗時(shí)較多的sin 和 cos 運(yùn)算，加快可計(jì)算速度使用說(shuō)明：使用此函數(shù)只需更改宏定義FFT_N 的值即可實(shí)現(xiàn)點(diǎn)數(shù)的改變，F(xiàn)FT_N應(yīng)該為 2 的 N 次方，不滿足此條件時(shí)應(yīng)在后面補(bǔ)0。若使用查表法計(jì)算 sin 值和cos 值，應(yīng)在調(diào)用 FFT 函數(shù)前調(diào)用 create_sin_tab()函數(shù)創(chuàng)建正弦表函數(shù)調(diào)用：FFT(s);時(shí)間：2010-2-20版本：Ver1.1參考文獻(xiàn)：*/#in clude#def

9、ine FFT_N 128/ 定義傅立葉變換的點(diǎn)數(shù)#defi ne PI 3.1415926535897932384626433832795028841971/ 定義圓周率值struct compx float real,imag;/ 定義一個(gè)復(fù)數(shù)結(jié)構(gòu)struct compx sFFT_N;/FFT 輸入和輸出：從 S0開(kāi)始存放，根據(jù)大小自己定義float SIN_TABFFT_N/2;/定義正弦表的存放空間/*函數(shù)原型： struct compx EE(struct compx b1,struct compx b2)函數(shù)功能：對(duì)兩個(gè)復(fù)數(shù)進(jìn)行乘法運(yùn)算輸入?yún)?shù)：兩個(gè)以聯(lián)合體定義的復(fù)數(shù)a,b輸出參

10、數(shù)：a 和 b 的乘積，以聯(lián)合體的形式輸出*/struct compx EE(struct compx a,struct 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 create_sin_tab(float *sin_t)函數(shù)功能：創(chuàng)建一個(gè)正弦采樣表，采樣點(diǎn)數(shù)與傅立葉變換點(diǎn)數(shù)相同 輸入?yún)?shù)：*sin_t 存放正弦表的數(shù)組指針輸出參數(shù)：無(wú)*/void create_s in _tab(float *sin_t)i

11、nt i;for(i=0;i=0&n =FFT_ N/2&n 2*PI)pi2-=2*PI;a=s in _tab(pi2);return a;*函數(shù)原型：void FFT(struct compx *xi n,int N)函數(shù)功能：對(duì)輸入的復(fù)數(shù)組進(jìn)行快速傅里葉變換(FFT)輸入?yún)?shù)：*xin 復(fù)數(shù)結(jié)構(gòu)體組的首地址指針，struct 型輸出參數(shù)：無(wú)*/ void FFT(struct compx *xi n)int f,m, nv2,n m1,i,k,l,j=O;struct compx u,w,t;/變址運(yùn)算，即把自然順序變成倒位序，采用雷德算法/求 j 的下一個(gè)倒位序如果

12、k=j,表示 j 的最高位為 1/把最高位變成 0/k/2，比較次高位，依次類推，逐個(gè)比較，直到某個(gè)位為把 0 改為 1n v2=FFT_N/2; nm 仁 FFT_N-1;for(i=0;i nm1;i+) if(ij)t=xi nj;xi nj=xi n i;xin i=t;k=nv2;while(k=j)j=j-k;k=k/2;j=j+k;如果 ij,即進(jìn)行變址int le,lei,ip;f=FFT_N;for(l=1;(f=f/2)!=1;l+)Jfor(m=1;m=l;m+) le=2(m-1);lei=le/2;u.real=1.0;u.imag=0.0;w.real=cos(PI

13、/lei);/ w.imag=-si n( PI/lei);w.real=cos_tab(PI/lei);w.imag=-sin_tab(PI/lei);/FFT 運(yùn)算核，使用蝶形運(yùn)算完成FFT計(jì)算 I 的值，即計(jì)算蝶形級(jí)數(shù)/控制蝶形結(jié)級(jí)數(shù)/m 表示第 m 級(jí)蝶形，I 為蝶形級(jí)總數(shù) l=log/le 蝶形結(jié)距離，即第m 級(jí)蝶形的蝶形結(jié)相距同一蝶形結(jié)中參加運(yùn)算的兩點(diǎn)的距離/u 為蝶形結(jié)運(yùn)算系數(shù)，初始值為1不適用查表法計(jì)算 sin 值和 cos 值/w 為系數(shù)商，即當(dāng)前系數(shù)與前一個(gè)系數(shù)的商運(yùn)算(2) Nle 點(diǎn)for(j=0;j=lei_1;j+)for(i=j;i=FFT_N-1;i=i+le)

14、ip=i+lei;t=EE(xi n ip,u);xi nip.real=xi n i.real-t.real;xin ip.imag=x in i.imag-t.imag;xi ni.real=xi n i.real+t.real;xi ni.imag=xi ni.imag+t.imag;u=EE(u,w);/*函數(shù)原型：void mai n()函數(shù)功能：測(cè)試 FFT 變換，演示函數(shù)使用方法輸入?yún)?shù)：無(wú)輸出參數(shù)：無(wú)*/void mai n()int i;create_sin_tab(SIN_TAB);for(i=0;iFFT_N;i+)/ 給結(jié)構(gòu)體賦值si.real=sin(2*3.1415

15、92653589793*i/FFT_N); /實(shí)部為正弦波 FFT_N 點(diǎn)采樣，賦值為 1si.imag=0;/虛部為 0FFT(s);/進(jìn)行快速傅立葉變換for(i=0;iFFT_N;i+)求變換后結(jié)果的模值，存入復(fù)數(shù)的實(shí)部部分si.real=sqrt(si.real*si.real+si.imag*si.imag);while(1);/控制計(jì)算不同種蝶形結(jié)，即計(jì)算系數(shù)不同的蝶形結(jié)控制同一蝶形結(jié)運(yùn)算，即計(jì)算系數(shù)相同蝶形結(jié)i, ip 分別表示參加蝶形運(yùn)算的兩個(gè)節(jié)點(diǎn)/蝶形運(yùn)算，詳見(jiàn)公式/改變系數(shù)，進(jìn)行下一個(gè)蝶形運(yùn)算#i nclude #in elude vintrin sics.h/*快速傅立葉

16、變換 C 程序包函數(shù)簡(jiǎn)介：此程序包是通用的快速傅里葉變換C 語(yǔ)言函數(shù)，移植性強(qiáng)，以下部分不依賴硬件。此程序包采用聯(lián)合體的形式表示一個(gè)復(fù)數(shù)，輸入為自然順序的復(fù) 數(shù)(輸入實(shí)數(shù)是可令復(fù)數(shù)虛部為0)，輸出為經(jīng)過(guò) FFT 變換的自然順序的復(fù)數(shù).此程序包可在初始化時(shí)調(diào)用create_sin_tab()函數(shù)創(chuàng)建正弦函數(shù)表，以后的可采用查表法計(jì)算耗時(shí)較多的sin 和 cos 運(yùn)算，加快可計(jì)算速度.與Ver1.1 版相比較，Ver1.2 版在創(chuàng)建正弦表時(shí)只建立了1/4 個(gè)正弦波的采樣值，相比之下節(jié)省了FFT_N/4 個(gè)存儲(chǔ)空間使用說(shuō)明：使用此函數(shù)只需更改宏定義FFT_N 的值即可實(shí)現(xiàn)點(diǎn)數(shù)的改變，F(xiàn)FT_N 的應(yīng)

17、該為 2 的 N 次方，不滿足此條件時(shí)應(yīng)在后面補(bǔ)0。若使用查表法計(jì)算sin 值和cos 值，應(yīng)在調(diào)用 FFT 函數(shù)前調(diào)用 create_sin_tab()函數(shù)創(chuàng)建正弦表函數(shù)調(diào)用：FFT(s);時(shí)間：2010-2-20版本：Ver1.2參考文獻(xiàn)：*/#in clude#define FFT_N 128/ 定義傅立葉變換的點(diǎn)數(shù)#defi ne PI 3.1415926535897932384626433832795028841971/ 定義圓周率值struct compx float real,imag;/ 定義一個(gè)復(fù)數(shù)結(jié)構(gòu)struct compx sFFT_N;/FFT 輸入和輸出：從 S0開(kāi)始

18、存放，根據(jù)大小自己定義float SIN_TABFFT_N/4+1;/定義正弦表的存放空間/*函數(shù)原型： struct compx EE(struct compx b1,struct compx b2)函數(shù)功能：對(duì)兩個(gè)復(fù)數(shù)進(jìn)行乘法運(yùn)算輸入?yún)?shù)：兩個(gè)以聯(lián)合體定義的復(fù)數(shù)a,b輸出參數(shù)：a 和 b 的乘積，以聯(lián)合體的形式輸出*/struct compx EE(struct compx a,struct 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(

19、c);/*函數(shù)原型：void create_sin_tab(float *sin_t)函數(shù)功能：創(chuàng)建一個(gè)正弦采樣表，采樣點(diǎn)數(shù)與傅立葉變換點(diǎn)數(shù)相同輸入?yún)?shù)：*sin_t 存放正弦表的數(shù)組指針 輸出參數(shù)：無(wú)*/void create_s in _tab(float *sin_t)int i;for(i=0;i=0&nFFT_N/ 4&* FFT_N/2)n-=FFT_N/4;a=SIN_TABFFT_N/4-n;else if(n =FFT_N/2&n=3*FFT_N/4&n2*PI)pi2-=2*PI;a=s in _tab(pi2);return a;/*函數(shù)原

20、型：void FFT(struct compx *xi n,int N)函數(shù)功能：對(duì)輸入的復(fù)數(shù)組進(jìn)行快速傅里葉變換( FFT) 輸入?yún)?shù)：*xin 復(fù)數(shù)結(jié)構(gòu)體組的首地址指針，struct 型輸出參數(shù)：無(wú)*/void FFT(struct compx *xi n)int f,m, nv2,n m1,i,k,l,j=0;struct compx u,w,t;/變址運(yùn)算，即把自然順序變成倒位序，采用雷德算如果 ij,即進(jìn)行變址/求 j 的下一個(gè)倒位序如果 k=j,表示 j 的最高位為 1/把最高位變成 0/k/2，比較次高位，依次類推，逐個(gè)比較，直到某個(gè)位為 0n v2=FFT_N/2;法n m 仁

21、 FFT_N-1;for(i=0;i nm1;i+) if(ij)t=xi nj;xi nj=xi n i;xin i=t;k=nv2;while(k=j)j=j-k;k=k/2;j=j+k;/*把 0 改為 1/FFT 運(yùn)算核，使用蝶形運(yùn)算完成FFT 運(yùn)算/計(jì)算 I 的值，即計(jì)算蝶形級(jí)數(shù)/控制蝶形結(jié)級(jí)數(shù)/m 表示第 m 級(jí)蝶形，I 為蝶形級(jí)總數(shù)/le 蝶形結(jié)距離，即第m 級(jí)蝶形的蝶形結(jié)/同一蝶形結(jié)中參加運(yùn)算的兩點(diǎn)的距離/u 為蝶形結(jié)運(yùn)算系數(shù)，初始值為 1/不適用查表法計(jì)算 sin 值和 cos 值/w 為系數(shù)商，即當(dāng)前系數(shù)與前一個(gè)系數(shù)的商控制計(jì)算不同種蝶形結(jié)， 即計(jì)算系數(shù)不同的蝶控制同一蝶形結(jié)運(yùn)算，即計(jì)算系數(shù)相同蝶形/i，ip 分別表示參加蝶形運(yùn)算的兩個(gè)節(jié)點(diǎn)/蝶形運(yùn)算，詳見(jiàn)公式/改變系數(shù)，進(jìn)行下一個(gè)蝶形運(yùn)算 /*函數(shù)原型：void mai n()函