/*********************************************************************

快速福利葉變換C程序包

函數簡介：此程序包是通用的快速傅里葉變換C語言函數，移植性強，以下部分不依

賴硬件。此程序包采用聯合體的形式表示一個復數，輸入為自然順序的復

數(輸入實數是可令復數虛部為0)，輸出為經過FFT變換的自然順序的

復數.此程序包可在初始化時調用create_sin_tab()函數創建正弦函數表，

以后的可采用查表法計算耗時較多的sin和cos運算，加快可計算速度.與

Ver1.1版相比較，Ver1.2版在創建正弦表時只建立了1/4個正弦波的采樣值，

相比之下節省了FFT_N/4個存儲空間

使用說明：使用此函數只需更改宏定義FFT_N的值即可實現點數的改變，FFT_N的

應該為2的N次方，不滿足此條件時應在后面補0。若使用查表法計算sin值和

cos值，應在調用FFT函數前調用create_sin_tab()函數創建正弦表

函數調用：FFT(s);

作? ? 者：吉帥虎

時? ? 間：2010-2-20

版? ? 本：Ver1.2

參考文獻：

**********************************************************************/

#include

#include "fft_fp.h"

//#define FFT_N 64? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?//定義福利葉變換的點數

//#define PI 3.1415926535897932384626433832795028841971? ?? ?? ?? ?? ?//定義圓周率值

//

//struct compx {float real,imag;};? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?//定義一個復數結構

struct compx s[FFT_N];? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ? //FFT輸入和輸出：從S[0]開始存放，根據大小自己定義

float SIN_TAB[FFT_N/4+1];? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?//定義正弦表的存放空間

/*******************************************************************

函數原型：struct compx EE(struct compx b1,struct compx b2)

函數功能：對兩個復數進行乘法運算

輸入參數：兩個以聯合體定義的復數a,b

輸出參數：a和b的乘積，以聯合體的形式輸出

*******************************************************************/

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);

}

/******************************************************************

函數原型：void create_sin_tab(float *sin_t)

函數功能：創建一個正弦采樣表，采樣點數與福利葉變換點數相同

輸入參數：*sin_t存放正弦表的數組指針

輸出參數：無

******************************************************************/

void create_sin_tab(float *sin_t)

{

int i;

for(i=0;i<=FFT_N/4;i++)

sin_t[ i]=sin(2*PI*i/FFT_N);

}

/******************************************************************

函數原型：void sin_tab(float pi)

函數功能：采用查表的方法計算一個數的正弦值

輸入參數：pi 所要計算正弦值弧度值，范圍0--2*PI，不滿足時需要轉換

輸出參數：輸入值pi的正弦值

******************************************************************/

float sin_tab(float pi)

{

int n;

float a=0;

n=(int)(pi*FFT_N/2/PI);

if(n>=0&&n<=FFT_N/4)

a=SIN_TAB[n];

else if(n>FFT_N/4&&n

{

n-=FFT_N/4;

a=SIN_TAB[FFT_N/4-n];

}

else if(n>=FFT_N/2&&n<3*FFT_N/4)

{

n-=FFT_N/2;

a=-SIN_TAB[n];

}

else if(n>=3*FFT_N/4&&n<3*FFT_N)

{

n=FFT_N-n;

a=-SIN_TAB[n];

}

return a;

}

/******************************************************************

函數原型：void cos_tab(float pi)

函數功能：采用查表的方法計算一個數的余弦值

輸入參數：pi 所要計算余弦值弧度值，范圍0--2*PI，不滿足時需要轉換

輸出參數：輸入值pi的余弦值

******************************************************************/

float cos_tab(float pi)

{

float a,pi2;

pi2=pi+PI/2;

if(pi2>2*PI)

pi2-=2*PI;

a=sin_tab(pi2);

return a;

}

/*****************************************************************

函數原型：void FFT(struct compx *xin,int N)

函數功能：對輸入的復數組進行快速傅里葉變換(FFT)

輸入參數：*xin復數結構體組的首地址指針，struct型

輸出參數：無

*****************************************************************/

void FFT(struct compx *xin)

{

register int f,m,nv2,nm1,i,k,l,j=0;

struct compx u,w,t;

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 le,lei,ip;? ?? ?? ?? ?? ?? ?? ?? ?? ? //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<

lei=le/2;? ?? ?? ?? ?? ?? ?? ?? ?? ?? ? //同一蝶形結中參加運算的兩點的距離

u.real=1.0;? ?? ?? ?? ?? ?? ?? ?? ?? ???//u為蝶形結運算系數，初始值為1

u.imag=0.0;

//w.real=cos(PI/lei);? ?? ?? ?? ?? ?? ?//不適用查表法計算sin值和cos值

// w.imag=-sin(PI/lei);

w.real=cos_tab(PI/lei);? ?? ?? ?? ?? ? //w為系數商，即當前系數與前一個系數的商

w.imag=-sin_tab(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=EE(xin[ip],u);? ?? ?? ?? ?? ?? ? //蝶形運算，詳見公式

xin[ip].real=xin[ i].real-t.real;

xin[ip].imag=xin[ i].imag-t.imag;

xin[ i].real=xin[ i].real+t.real;

xin[ i].imag=xin[ i].imag+t.imag;

}

u=EE(u,w);? ?? ?? ?? ?? ?? ?? ?? ???//改變系數，進行下一個蝶形運算

}

}

}

}

/************************************************************

函數原型：void main()

函數功能：測試FFT變換，演示函數使用方法

輸入參數：無

輸出參數：無

************************************************************/

總結

以上是生活随笔為你收集整理的c语言 fft程序,FFT算法的使用说明与C语言版实现源码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。