一、完全了解傅里葉變換
快速傅里葉變換(Fast )是離散傅里葉變換的一種快速算法，簡稱FFT，經過FFT能夠將一個信號從時域變換到頻域。
模擬信號經過A/D轉化變為數字信號的進程稱為采樣。為確保采樣后信號的頻譜形狀不失真，采樣頻率有必要大于信號中最高頻率成分的2倍，這稱之為采樣定理。
假定采樣頻率為fs，采樣點數為N傅里葉變換代碼實現，那么FFT成果便是一個N點的復數，每一個點就對應著一個頻率點，某一點n(n從1開端)表明的頻率為：fn=(n-1)*fs/N。
舉例闡明：用1kHz的采樣頻率采樣128點，則FFT成果的128個數據即對應的頻率點分別是0，1k/128，2k/128，3k/128，…，127k/128 Hz。
這個頻率點的幅值為：該點復數的模值除以N/2(n=1時是直流重量，其幅值是該點的模值除以N)。
二、傅里葉變換的C言語編程
1、關于快速傅里葉變換FFT，第一個要處理的問題便是碼位倒序。
假定一個N點的輸入序列，那么它的序號二進制數位數便是t=log2N.
碼位倒序要處理兩個問題：①將t位二進制數倒序;②將倒序后的兩個存儲單元進行交流。
假如輸入序列的天然順序號i用二進制數表明，例如若最大序號為15，即用4位就可表明，則其倒序后j對應的二進制數便是，那么怎樣才能完結倒序呢?使用C言語的移位功用!
程序如下，我不多說，看不懂者智商一定在180以下!
復數類型界說及其運算
# N 64 //64點
# log2N 6 //log2N=6
/*復數類型*/
{
float real;
float img;
};
xdata x[N]; //輸入序列
/*復數加法*/
add( a, b)
{
c;
c.real=a.real+b.real;
c.img=a.img+b.img;
c;
}
/*復數減法*/
sub( a, b)
{
c;
c.real=a.real-b.real;
c.img=a.img-b.img;
c;
}
/*復數乘法*/
mul( a, b)
{
c;
c.real=a.real*b.real - a.img*b.img;
c.img=a.real*b.img + a.img*b.real;
c;
}
/***碼位倒序函數***/
void (void)
{
int i,j,k;
int t;
temp;//暫時交流變量
for(i=0;iN;i++)//從第0個序號到第N-1個序號
{
k=i;//當時第i個序號
j=0;//存儲倒序后的序號，先初始化為0
for(t=0;;t++)//共移位t次，其間log2N是事前宏界說算好的
{
j=1;
j|=(k1);//j左移一位然后加上k的最低位
k>>=1;//k右移一位，次低位變為最低位
}
if(j>i)//假如倒序后大于原序數，就將兩個存儲單元進行交流(判別j>i是為了避免重復交流)
{
temp=x;
x=x[j];
x[j]=temp;
}
}
}
2、第二個要處理的問題便是蝶形運算
620)this.width=620;" />
①第1級(第1列)每個蝶形的兩節點“間隔”為1，第2級每個蝶形的兩節點“間隔”為2，第3級每個蝶形的兩節點“間隔”為4，第4級每個蝶形的兩節點“間隔”為8。由此推得，
第m級蝶形運算，每個蝶形的兩節點“間隔”L=2m-1。
②關于16點的FFT，第1級有16組蝶形，每組有1個蝶形;第2級有4組蝶形，每組有2個蝶形;第3級有2組蝶形，每組有4個蝶形;第4級有1組蝶形，每組有8個蝶形。由此可推出傅里葉變換代碼實現，
關于N點的FFT，第m級有N/2L組蝶形，每組有L=2m-1個蝶形。
③旋轉因子
620)this.width=620;" />的確認
以16點FFT為例，第m級第k個旋轉因子為
620)this.width=620;" />，其間k=0～2m-1-1，即第m級共有2m-1個旋轉因子，依據旋轉因子的可約性，
620)this.width=620;" />，所以第m級第k個旋轉因子為
620)this.width=620;" />，其間k=0～2m-1-1。
為進步FFT的運算速度，咱們能夠事前樹立一個旋轉因子數組，然后經過查表法來完結。
code WN[N]=//旋轉因子數組
{ //為節約CPU核算時刻，旋轉因子選用查表處理
//★依據實踐FFT的點數N，該表數據需自行修正
//以下成果經過Excel主動生成
// WN[k].real=cos(2*PI/N*k);
// WN[k].img=-sin(2*PI/N*k);
{1.00000,0.00000},{0.99518,-0.09802},{0.98079,-0.19509},{0.95694,-0.29028},
{0.92388,-0.38268},{0.88192,-0.47140},{0.83147,-0.55557},{0.77301,-0.63439},
{0.70711,-0.70711},{0.63439,-0.77301},{0.55557,-0.83147},{0.47140,-0.88192},
{0.38268,-0.92388},{0.29028,-0.95694},{0.19509,-0.98079},{0.09802,-0.99518},
{0.00000,-1.00000},{-0.09802,-0.99518},{-0.19509,-0.98079},{-0.29028,-0.95694},
{-0.38268,-0.92388},{-0.47140,-0.88192},{-0.55557,-0.83147},{-0.63439,-0.77301},
{-0.70711,-0.70711},{-0.77301,-0.63439},{-0.83147,-0.55557},{-0.88192,-0.47140},
{-0.92388,-0.38268},{-0.95694,-0.29028},{-0.98079,-0.19509},{-0.99518,-0.09802},
{-1.00000,0.00000},{-0.99518,0.09802},{-0.98079,0.19509},{-0.95694,0.29028},
{-0.92388,0.38268},{-0.88192,0.47140},{-0.83147,0.55557},{-0.77301,0.63439},
{-0.70711,0.70711},{-0.63439,0.77301},{-0.55557,0.83147},{-0.47140,0.88192},
{-0.38268,0.92388},{-0.29028,0.95694},{-0.19509,0.98079},{-0.09802,0.99518},
{0.00000,1.00000},{0.09802,0.99518},{0.19509,0.98079},{0.29028,0.95694},
{0.38268,0.92388},{0.47140,0.88192},{0.55557,0.83147},{0.63439,0.77301},
{0.70711,0.70711},{0.77301,0.63439},{0.83147,0.55557},{0.88192,0.47140},
{0.92388,0.38268},{0.95694,0.29028},{0.98079,0.19509},{0.99518,0.09802}
};
3、算法完結
咱們現已知道，N點FFT從左到右共有log2N級蝶形，每級有N/2L組，每組有L個。所以FFT的C言語編程只需用3層循環即可完結：最外層循環完結每一級的蝶形運算(整個FFT共log2N級)，中間層循環完結每一組的蝶形運算(每一級有N/2L組)，最內層循環完結獨自1個蝶形運算(每一組有L個)。
/***【快速傅里葉變換】***/
void FFT(void)
{
int i,j,k,l;
top,,xW;
(); //碼位倒序
for(i=0;;i++) /*共log2N級*/
{ //一級蝶形運算
l=1i;//l等于2的i次方
for(j=0;jN;j+=2*l) /*每L個蝶形是一組，每級有N/2L組*/
{ //一組蝶形運算
for(k=0;kl;k++) /*每組有L個*/
{ //一個蝶形運算
xW=mul(x[j+k+l],WN[N/(2*l)*k]); //碟距離為l
top=add(x[j+k],xW); //每組的第k個蝶形
=sub(x[j+k],xW);
x[j+k]=top;
x[j+k+l]=;
}
}
}
}
三、FFT核算成果驗證
隨意輸入一個64點序列，例如
x[N]={{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0},{8,0},{4,0},{1,0},{3,0},{2,0},{5,0}};
在Keil中Debug檢查數組變量x的FFT核算成果并與核算成果進行比對，能夠發現十分精確，闡明程序編寫正確！
