FFT與DFT關係：
快速傅里葉變換(Fast Fourier Transform)是離散傅里葉（DFT）變換的一種快速算法，簡稱FFT，通過FFT可以將一個信號從時域變換到頻域；FFT（快速傅里葉變換）其本質就是DFT，只不過可以快速的計算出DFT結果，它只是傅立葉變換算法實現過程的一種改進。
要弄懂FFT，必須先弄懂DFT，DFT(DiscreteFourier Transform) 離散傅里葉變換的縮寫，咱們先來簡單討論一下DFT。DFT(FFT)的作用:可以將信號從時域變換到頻域，而且時域和頻域都是離散的，通俗的說，可以求出一個信號由哪些正弦波疊加而成，求出的結果就是這些正弦波的幅度和相位。
DFT的公式：
其中X(k)表示DFT變換後的數據，x(n)為採樣的模擬信號,公式中的x(n)可以為覆信號，實際當中x(n)都是實信號，即虛部為0,此時公式可以展開為：
那麼，對於一個 的序列進行不斷分解，就可以得出如下所謂的蝶形圖：
FFT處理蝶形運算
蝶形運算的規律：同一級中所有蝶形的輸入點在同一豎直線上，意味著我們可以按級來運算，對於M級的蝶形，編個M次循環就好了；所有數據點在運算後不會竄位，即計算後可以將結果存入原來的地址空間。
每級N/2個蝶都需要用到係數WN，這裡稱它為旋轉因子。我們來觀察旋轉因子WN的規律。以8點的蝶形圖為例：
可見，第L級的旋轉因子為：
可以看到，每個蝶的兩個輸入點下標跨度是不一樣的。比如第一級中是相鄰兩個數據作蝶運算，第二級中是兩個輸入點隔開一個點，而第三級隔開三個點。不難找到規律：第L級中，第二個輸入點的座標是第一個點的座標+space，space=Math.Pow(2, L)=num。
FFT的算法是寫一個三重循環：
第一重循環對每一級運算（每級含num=Math.Pow(2, L)個蝶形）；
第二重對每一個旋轉因子對應的蝶運算， 那麼有幾個蝶呢？很簡單，每級都應該有N/2個蝶，而每個因子對應N/2 / num個蝶；
第三重循環對每個蝶進行計算，需要注意的一是循環下標起始點的位置，二是每次計算需要申明臨時變量來保存輸入數據點。
實現代碼：
FFT算法的原理是通過許多小的更加容易進行的變換去實現大規模的變換，降低了運算要求，提高了與運算速度。FFT不是DFT的近似運算，它們完全是等效的。
傅里葉變換的C語言編程
對於快速傅里葉變換FFT，第一個要解決的問題就是碼位倒序。假設一個N點的輸入序列，那麼它的序號二進制數位數就是t=log2N。碼位倒序要解決兩個問題：
將t位二進制數倒序;
將倒序後的兩個存儲單元進行交換。如果輸入序列的自然順序號i用二進制數表示，例如若最大序號為15，即用4位就可表示n3n2n1n0，則其倒序後j對應的二進制數就是n0n1n2n3。
代碼如下：
複數類型定義及其運算
#define N 64 //64點
#define log2N 6 //log2N=6
/*複數類型*/
typedef struct
{
float real;
float img;
}complex;
complex xdata x[N]; //輸入序列
/*複數加法*/
complex add(complex a,complex b)
{
complex c;
c.real=a.real+b.real;
c.img=a.img+b.img;
return c;
}
/*複數減法*/
complex sub(complex a,complex b)
{
complex c;
c.real=a.real-b.real;
c.img=a.img-b.img;
return c;
}
/*複數乘法*/
complex mul(complex a,complex b)
{
complex c;
c.real=a.real*b.real - a.img*b.img;
c.img=a.real*b.img + a.img*b.real;
return c;
}
/***碼位倒序函數***/
void Reverse(void)
{
unsigned int i,j,k;
unsigned int t;
complex temp;//臨時交換變量
for(i=0;i { k=i;//當前第i個序號 j=0;//存儲倒序後的序號，先初始化為0 for(t=0;t<log2n> { j<<=1; j|=(k&1);//j左移一位然後加上k的最低位 k>>=1;//k右移一位，次低位變為最低位 } if(j>i)//如果倒序後大於原序數，就將兩個存儲單元進行交換(判斷j>i是為了防止重複交換) { temp=x; x=x[j]; x[j]=temp; } } } 
總結：
FFT是離散傅立葉變換的快速算法，可以將一個信號變換到頻域。有些信號在時域上是很難看出什麼特徵的，但是如果變換到頻域之後，就很容易看出特徵了。這就是很多信號分析採用FFT變換的原因。另外，FFT可以將一個信號的頻譜提取出來，這在頻譜分析方面也是經常用的。
/<log2n>閱讀更多 咱小二 的文章
