實(shí)驗(yàn)用的頭文件 MYFFT.H 
作用：為幫助小虎子做實(shí)驗(yàn)，這個(gè)頭文件提供了完整的一維與二維FFT算法，我想應(yīng)改是夠你折騰了吧！ 

#include <complex> // complex<float> 
using namespace std; 
typedef complex<float> Comp; // 復(fù)數(shù)類型定義 

const float _2PI_ = 2.0f * 3.14159265f; // 常數(shù)2PI定義 
const int MAX_N = 256; // 最大DFT點(diǎn)數(shù) 

/*----*----*----*----*----*----*----*----*----*----*----*----* 
FFT算法模塊接口定義 
*----*----*----*----*----*----*----*----*----*----*----*----*/ 

/////////////////////////////////////////// 
// Function name : BitReverse 
// Description : 二進(jìn)制倒序操作 
// Return type : int 
// Argument : int src 待倒讀的數(shù) 
// Argument : int size 二進(jìn)制位數(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ù)二進(jìn)制整序 
// Return type : void 
// Argument : Comp x[MAX_N] 待整序數(shù)組 
// Argument : int N FFT點(diǎn)數(shù) 
// Argument : int M 點(diǎn)數(shù)的2的冪次 
void Reorder(Comp x[MAX_N], int N, int M) 
{ 
Comp new_x[MAX_N]; 
for (int i=0; i<N; i++) 
new_x = x[BitReverse(i, M)]; 
// 重新存入原數(shù)據(jù)中(已經(jīng)是二進(jìn)制整序過了的數(shù)據(jù)) 
for (i=0; i<N; i++) 
x = new_x; 
} 

////////////////////////////////////////////////// 
// Function name : CalcW 
// Description : 計(jì)算旋轉(zhuǎn)因子 
// Return type : void 
// Argument : Comp W[MAX_N] 存放因子的數(shù)組 
// Argument : int N FFT的點(diǎn)數(shù) 
// Argument : int flag 正逆變換標(biāo)記 
void CalcW(Comp W[MAX_N], int N, int flag) 
{ 
for (int i=0; i<N/2; i++) 
{ 
if (flag == 1) 
W = exp(Comp(0, -_2PI_ * i / N)); // 正FFT變換 
else 
W = exp(Comp(0, _2PI_ * i / N)); // 逆FFT變換 
} 
} 

///////////////////////////////////////////////// 
// Function name : FFT_1D_Kernel 
// Description : FFT算法核心 
// Return type : void 
// Argument : Comp* x 數(shù)據(jù) 
// Argument : int M 冪次 
// Argument : int flag 正逆變換標(biāo)記 
以下本應(yīng)由自己完成。 

void FFT_1D(Comp* x, int M, int flag) 
{ 
int N = (1 << M); 

// 二進(jìn)制整序 
Reorder(x, N, M); 

// 旋轉(zhuǎn)因子計(jì)算 
Comp W[MAX_N]; 
CalcW(W, N, flag); 

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

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

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

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

// (2) 計(jì)算旋轉(zhuǎn)因子與單元的第二元素的復(fù)數(shù)乘積 
Comp TMP = x[Pos2] * W[k * GroupNum] ; 

// (3) 計(jì)算最終結(jié)果, 并存入到數(shù)組的原先位置 
x[Pos2] = x[Pos1] - TMP ; 
x[Pos1] = x[Pos1] + TMP ; 
} 
} 
GroupNum >>= 1; // 級別增加, 則相應(yīng)的群數(shù)減少一半 
CellNum <<= 1; // 級別增加, 則相應(yīng)的群內(nèi)單元數(shù)增加一倍 
} 

// 如果是IFFT，各元素還要再除以N 
if (flag != 1) 
{ 
for (i=0; i<N; i++) 
x /= N; 
} 
} 

////////////////////////////////////////////////////// 
// Function name : FFT_2D_Kernel 
// Description : 2D FFT核心算法 
// Return type : void 
// Argument : Comp x[MAX_N][MAX_N] 二維數(shù)據(jù) 
// Argument : int M 冪次 
// Argument : int flag 正逆變換標(biāo)記 


以下本應(yīng)由自己完成。 

void FFT_2D(Comp x[MAX_N][MAX_N], int M, int flag) 
{ 
int N = (1 << M); 

// 先逐行進(jìn)行 1D-FFT 
for (int i=0; i<N; i++) 
FFT_1D(x, M, flag); // <--- 計(jì)算結(jié)果再存入矩陣x中 

// 再逐列進(jìn)行 1D-FFT 
Comp col[MAX_N]; 
for (int j=0; j<N; j++) 
{ 
// 取得第j列的數(shù)據(jù) 
for (int i=0; i<N; i++) 
col = x[j]; 

// 對第j列數(shù)據(jù)進(jìn)行 1D-FFT 
FFT_1D(col, M, flag); // <--- 計(jì)算結(jié)果在數(shù)組col中 

// 將結(jié)果放回矩陣第j列中 
for (i=0; i<N; i++) 
x[j] = col; 
} 
} 
// <--- End of [FFT.H]