為什么需要FFT

　　第一個問題是為什么要創造FFT，簡單的說，為了速度。我們承認DFT很有用，但是我們發現他的速度不是很快，1D的DFT原始算法的時間復雜度是O（n^2），這個可以通過公式觀察出來，對于2D的DFT其時間復雜度是O（n^4），這個速度真的很難接受，也就是說，你計算一幅1024x768的圖像時，所以找到一種快速方法的方法計算FFT勢在必行。

　　以下為DFT公式

　　如何得到FFT

　　通過觀察DFT公式，我們發現DFT計算每一項X［u］的時候都遍歷了完整的x［n］所以，我們的想法就是能不能通過其他的X［u+m］（m為一個整數，可正可負）得到X［u］，也就是充分利用之間的計算結構來構建現在的結果，這種方法就很容易表現成迭代的形式。本文介紹基2的FFT，及離散信號x［n］的個數為2的k次方，即如果完整的離散信號中有N個信分量{x1，x2，x3.。。.xN}其中N=1《《k。

　　FFT的數學基礎其實就是

　　用C語言編寫FFT算法

　　用simulink建模的方法實現FFT的問題特別多，還不如手工編寫，也不是很復雜。

　　以下是512點的單邊譜FFT算法，在TMS320C6713的DSP開發板上調試通過。下面是C語言編寫FFT算法。

　　#include “math.h”

　　#define PI 3.1415926

　　#define SAMPLENUMBER 512

　　void InitForFFT（）;

　　void MakeWave（）;

　　void FFT（）;

　　int INPUT［SAMPLENUMBER］，DATA［SAMPLENUMBER］;

　　float fWaveR［SAMPLENUMBER］，fWaveI［SAMPLENUMBER］，w［SAMPLENUMBER］;

　　float sin_tab［SAMPLENUMBER］，cos_tab［SAMPLENUMBER］;

　　main（）

　　{

　　int i;

　　InitForFFT（）;

　　MakeWave（）;

　　for （ i=0;i

　　{

　　fWaveR［i］=INPUT［i］;

　　fWaveI［i］=0.0f;

　　w［i］=0.0f;

　　}

　　FFT（fWaveR，fWaveI）;

　　for （ i=0;i

　　{

　　DATA［i］=w［i］;

　　}

　　while （ 1 ）; // break point

　　}

　　void FFT（float dataR［SAMPLENUMBER］，float dataI［SAMPLENUMBER］）

　　{

　　int x0，x1，x2，x3，x4，x5，x6，x7，x8，xx;

　　int i，j，k，b，p，L;

　　float TR，TI，temp;

　　for （ i=0;i

　　{

　　x0=x1=x2=x3=x4=x5=x6=x7=x8=0;

　　x0=i&0x01; x1=（i/2）&0x01; x2=（i/4）&0x01; x3=（i/8）&0x01;x4=（i/16）&0x01; x5=（i/32）&0x01; x6=（i/64）&0x01;x7=（i/128）&0x01;x8=（i/256）&0x01;

　　xx=x0*256+x1*128+x2*64+x3*32+x4*16+x5*8+x6*4+x7*2+x8;

　　dataI［xx］=dataR［i］;

　　}

　　for （ i=0;i

　　{

　　dataR［i］=dataI［i］; dataI［i］=0;

　　}

　　for （ L=1;L《=9;L++ ）

　　{

　　b=1; i=L-1;

　　while （ i》0 ）

　　{

　　b=b*2; i--;

　　}

　　for （ j=0;j《=b-1;j++ ）

　　{

　　p=1; i=9-L;

　　while （ i》0 ）

　　{

　　p=p*2; i--;

　　}

　　p=p*j;

　　for （ k=j;k《512;k=k+2*b ）

　　{

　　TR=dataR［k］; TI=dataI［k］; temp=dataR［k+b］;

　　dataR［k］=dataR［k］+dataR［k+b］*cos_tab［p］+dataI［k+b］*sin_tab［p］;

　　dataI［k］=dataI［k］-dataR［k+b］*sin_tab［p］+dataI［k+b］*cos_tab［p］;

　　dataR［k+b］=TR-dataR［k+b］*cos_tab［p］-dataI［k+b］*sin_tab［p］;

　　dataI［k+b］=TI+temp*sin_tab［p］-dataI［k+b］*cos_tab［p］;

　　}

　　}

　　}

　　for （ i=0;i

　　{

　　w［i］=sqrt（dataR［i］*dataR［i］+dataI［i］*dataI［i］）;

　　}

　　}

　　void InitForFFT（）

　　{

　　int i;

　　for （ i=0;i

　　{

　　sin_tab［i］=sin（PI*2*i/SAMPLENUMBER）;

　　cos_tab［i］=cos（PI*2*i/SAMPLENUMBER）;

　　}

　　}

　　void MakeWave（）

　　{

　　int i;

　　for （ i=0;i

　　{

　　INPUT［i］=sin（PI*2*i/SAMPLENUMBER*30）*1024;

　　}