快速傅裡葉變換FFT的C語言算法徹底研究

        LED音樂頻譜顯示的核心算法就是快速傅裡葉變換，FFT的了解和程式設計還是比較難的， 特地撰寫此文分享一下 研究 成果。

一、徹底了解傅裡葉變換

快速傅裡葉變換（Fast Fourier Transform)是離散傅裡葉變換的一種快速算法，簡稱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位就可表示n3n2n1n0，則其倒序後j對應的二進制數就是n0n1n2n3，那麼怎樣才能實作倒序呢？利用C語言的移位功能！

程式如下，我不多說，看不懂者智商一定在180以下！

複數類型定義及其運算

#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 FFT(void)

  {

   unsigned int i,j,k,l;

   complex top,bottom,xW;

   Reverse(); //碼位倒序

   for(i=0;i<log2N;i++)   

   {    //一級蝶形運算

    l=1<<i;//l等于2的i次方

    for(j=0;j<N;j+=2*l)  

    {   //一組蝶形運算

     for(k=0;k<l;k++)   

     {  //一個蝶形運算

       xW=mul(x[j+k+l],WN[N/(2*l)*k]);//碟間距為l

       top=add(x[j+k],xW);//每組的第k個蝶形

       bottom=sub(x[j+k],xW);

       x[j+k]=top;

       x[j+k+l]=bottom;

     }

    }

   }

  }

三、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計算結果并與MATLAB計算結果進行比對，可以發現非常準确，說明程式編寫正确！

FFT驗證：C語言與MATLAB計算結果對比