#include <math.h>
const float 2PI= 2.0*3.14159265f; // 常數(shù)2PI定義 
const int MAX_N = 256; // 最大DFT點數(shù) 
N=256;
M=9;
//*----*----*----*----*----*----*----*----*----*----*----*----* 
FFT算法模塊接口定義 
*----*----*----*----*----*----*----*----*----*----*----*----*// 

/////////////////////////////////////////// 
// Function name : BitReverse 
// Description : 二進制倒序操作 
// Return type : int 
// Argument : int src 待倒讀的數(shù) 
// Argument : int size 二進制位數(shù) 
int BitReverse(int src, int size)          //奇偶分解
{ 
int tmp = src; 
int des = 0; 
for (int i=size-1; i>=0; i--)  
{ 
des = ((tmp & 0x1) << i) | des; 
tmp = tmp >> 1; 
} 
return des; 
} 

////////////////////////////////////////////////// 
// Function name : Reorder 
// Description : 數(shù)據(jù)二進制整序 
// Return type : void 
// Argument : ADC[MAX_N] 待整序數(shù)組 
// Argument : int N FFT點數(shù) 
// Argument : int M 點數(shù)的2的冪次 
void Reorder(ADC[MAX_N], int N, int M) 
{ 
new_ADC[MAX_N]; 
for (int i=0; i<N; i++) 
{new_ADC[i] = ADC[BitReverse(i, M)];      // 重新存入原數(shù)據(jù)中(已經(jīng)是二進制整序過了的數(shù)據(jù)) 
X[i] = new_ADC[i]; }
} 

////////////////////////////////////////////////// 
// Function name : CalcW 
// Description : 計算旋轉因子 
// Return type : void  
// Argument : int N FFT的點數(shù) 
// Argument : int flag 正逆變換標記 
void CalcW(double *re, double *im,int N) 
{ 
for (int i=0; i<N/2; i++) 
{ 
bcarg = -2PI*i/N;
aw = cos(bcarg); 
re[i]=aw;
bw = sin(bcarg); 
im[i]=bw;  
} 
} 

///////////////////////////////////////////////// 
// Function name : FFT_1D_Kernel 
// Description : FFT算法核心 
// Return type : void 
// Argument : Comp* x 數(shù)據(jù) 
// Argument : int M 冪次 
// Argument : int flag 正逆變換標記  

void FFT_1D(double *ADC[MAX_N], int M, int flag) 
{ 
X[N];
Reorder(N, M);    //整序 
CalcW(N,M);        // 旋轉因子計算 
Y[256];
 

// 級內群數(shù) 
int GroupNum = N/2;   // 第一級的群數(shù)為N/2 

// 群內蝶形單元數(shù) 
int CellNum = 1;     // 第一級的群內蝶形單元數(shù)為1 

// 處理各級 
for (int i=0; i<M; i++) 
{ 
// 處理各群 
for (int j=0; j<GroupNum; j++) 
{ 
// 處理各蝶形單元 
for (int k=0; k<CellNum; k++) 
{ 
// (1) 計算出當前蝶形單元所含元素在數(shù)據(jù)數(shù)組中的位置 

// 第一元素位置 
int Pos1 = CellNum * j * 2 + k ; // 已經(jīng)處理了前 j 群，每群有 CellNum 個單元， 每單元有 2 個元素 
// 第二元素位置 
int Pos2 = Pos1 + CellNum; 

// (2) 計算旋轉因子與單元的第二元素的復數(shù)乘積 
atemp = re[k*GroupNum] * X[Pos2] - im[k*GroupNum] * Y[Pos2];
btemp = re[k*GroupNum] * Y[Pos2] + im[k*GroupNum] * X[Pos2];
// (3) 計算最終結果, 并存入到數(shù)組的原先位置
X[Pos2] = X[Pos1] - atemp;
Y[Pos2] = Y[Pos1] - btemp;
X[Pos1] = X[Pos1] + atemp;
Y[Pos1] = Y[Pos1] + btemp;
} 
} 
GroupNum >>= 1;  // 級別增加, 則相應的群數(shù)減少一半 
CellNum <<= 1;   // 級別增加, 則相應的群內單元數(shù)增加一倍 
} 
}