啥是傅立葉級(jí)數(shù)？

在數(shù)學(xué)中，傅里葉級(jí)數(shù)（Fourier series）是把類似波的函數(shù)表示成簡(jiǎn)單正弦波的方式。更正式地說(shuō)法是，它能將任何周期性函數(shù)或周期信號(hào)分解成一個(gè)（可能由無(wú)窮個(gè)元素組成的）簡(jiǎn)單振蕩函數(shù)的集合，即正弦函數(shù)和余弦函數(shù)（或者，等價(jià)地使用復(fù)指數(shù)），從數(shù)學(xué)的定義來(lái)看，是這樣地：

設(shè)x(t)是一周期信號(hào),其周期為T。若x(t)在一個(gè)周期的能量是有限的，有即

則，可以將x(t)展開(kāi)為傅立葉級(jí)數(shù)。公式中的k表示第k次諧波，這是個(gè)什么概念呢？不容易理解，看下對(duì)于一個(gè)方波的前4次諧波合成動(dòng)圖就比較好理解了。這里的合成的概念是時(shí)域上的疊加的概念，圖片來(lái)源wikipedia

啥是傅里葉變換？

在數(shù)學(xué)中，傅里葉變換(Fourier transform FT )是一種數(shù)學(xué)變換，它將一個(gè)函數(shù)(通常是一個(gè)時(shí)間的函數(shù)，或一個(gè)信號(hào))分解成它的組成頻率，例如用組成音符的音量和頻率表示一個(gè)音樂(lè)和弦。傅里葉變換指的是頻域表示和將頻域表示與時(shí)間函數(shù)相關(guān)聯(lián)的數(shù)學(xué)運(yùn)算。其本質(zhì)是一種線性積分變換，用于信號(hào)在時(shí)域（或空域）和頻域之間的變換，在物理學(xué)和工程學(xué)中有許多應(yīng)用。因其基本思想首先由法國(guó)學(xué)者約瑟夫·傅里葉系統(tǒng)地提出，所以以其名字來(lái)命名以示紀(jì)念。實(shí)際上傅里葉變換就像化學(xué)分析，確定物質(zhì)的基本成分；信號(hào)來(lái)自自然界，也可對(duì)其進(jìn)行分析，確定其基本頻率成分。其數(shù)學(xué)定義為：

對(duì)于連續(xù)時(shí)間信號(hào)x(t)，若x(t)在時(shí)間維度上可積分，（實(shí)際上并不一定是時(shí)間t維度，這里可以是任意維度，只需在對(duì)應(yīng)維度空間可積分即可），即：

那么，x(t)的傅立葉變換存在。在度量空間可積可以理解成其在度量空間能量有限，也即對(duì)其自變量積分（相當(dāng)于求面積)是一個(gè)確定值，那么這樣的函數(shù)或者信號(hào)就可以進(jìn)行傅立葉變換展開(kāi)，展開(kāi)得到的 就變成是頻域的函數(shù)了，如果對(duì)頻率 將函數(shù)值繪制出曲線就是我們所說(shuō)的頻譜圖，而其反變換就比較好理解了，如果我們知道一個(gè)信號(hào)或者函數(shù)譜密度函數(shù) ，就可以對(duì)應(yīng)還原出其時(shí)域的函數(shù)，也能繪制出時(shí)域的波形圖。

當(dāng)然，本文限定討論時(shí)域信號(hào)是因?yàn)槲覀冸娮酉到y(tǒng)中的應(yīng)用最為普遍的就是一個(gè)時(shí)域信號(hào)，當(dāng)然推而廣之，其他的多維度信號(hào)也能利用上面定義進(jìn)行推廣，同樣在多維空間信號(hào)也非常有應(yīng)用價(jià)值，比如2維圖像處理等等。

上面兩個(gè)概念是一個(gè)東東么？

• 傅立葉級(jí)數(shù)對(duì)應(yīng)的是周期信號(hào)，而傅立葉變換則對(duì)應(yīng)的是一個(gè)時(shí)間連續(xù)可積信號(hào)（不一定是周期信號(hào)）
• 傅立葉級(jí)數(shù)要求信號(hào)在一個(gè)周期內(nèi)能量有限，而后者則要求在整個(gè)區(qū)間能量有限
• 傅立葉級(jí)數(shù)的對(duì)應(yīng) 是離散的，而傅立葉變換則對(duì)應(yīng) 是連續(xù)的。

故而，兩者的物理含義不同，且其量綱也是不同的， 代表周期信號(hào)的第k次諧波幅度的大小，而 則是頻譜密度的概念。所以答案是這兩者從本質(zhì)上不是一個(gè)概念，傅立葉級(jí)數(shù)是周期信號(hào)的另一種時(shí)域的表達(dá)方式,也就是正交級(jí)數(shù),它是不同的頻率的波形的時(shí)域疊加。而傅立葉變換則是完全的頻域分析，傅里葉級(jí)數(shù)適用于對(duì)周期性現(xiàn)象做數(shù)學(xué)上的分析，傅里葉變換可以看作傅里葉級(jí)數(shù)的極限形式，也可以看作是對(duì)周期現(xiàn)象進(jìn)行數(shù)學(xué)上的分析，同時(shí)也適用于非周期性現(xiàn)象的分析。傅里葉級(jí)數(shù)適用于對(duì)周期性現(xiàn)象做數(shù)學(xué)上的分析，傅里葉變換可以看作傅里葉級(jí)數(shù)的極限形式，也可以看作是對(duì)周期現(xiàn)象進(jìn)行數(shù)學(xué)上的分析，同時(shí)也適用于非周期性現(xiàn)象的分析。

啥是離散傅立葉變換？

離散傅里葉變換（Discrete Fourier Transform，縮寫為DFT），是傅里葉變換在時(shí)域和頻域上都呈離散的形式，將信號(hào)的時(shí)域采樣變換為其DTFT的頻域采樣。

在形式上，變換兩端（時(shí)域和頻域上）的序列是有限長(zhǎng)的，而實(shí)際上這兩組序列都應(yīng)當(dāng)被認(rèn)為是離散周期信號(hào)的主值序列。即使對(duì)有限長(zhǎng)的離散信號(hào)作DFT，也應(yīng)當(dāng)將其看作其周期延拓的變換。在實(shí)際應(yīng)用中通常采用快速傅里葉變換計(jì)算DFT。

啥是快速傅立葉變換？

快速傅立葉變換（Fast Fourier Transform：FFT）是一種計(jì)算數(shù)字信號(hào)序列的離散傅立葉變換（Discrete Fourier Transform：DFT）或其逆變換（IDFT）的算法。傅里葉分析將信號(hào)從其原始域(通常是時(shí)間或空間)轉(zhuǎn)換為頻域的表示，反之亦然。DFT是通過(guò)將一系列值分解成不同頻率的分量來(lái)獲得的。這個(gè)操作在很多領(lǐng)域中都很有用，但是直接從定義中計(jì)算它通常太慢而不實(shí)際。FFT通過(guò)將DFT矩陣分解成稀疏(大部分為零)因子的乘積來(lái)快速計(jì)算這種轉(zhuǎn)換。所以其本質(zhì)是實(shí)現(xiàn)離散傅立葉變換的一種優(yōu)化算法，將時(shí)間復(fù)雜度從 降低為 ,其中N為待計(jì)算序列的長(zhǎng)度。當(dāng)N非常大時(shí)，這種優(yōu)化在時(shí)間維度上提升是非常顯著的。尤其在嵌入式應(yīng)用領(lǐng)域，由于受限于采用的芯片算力往往不強(qiáng)，所以FFT算法較之于DFT的效果是非常有應(yīng)用價(jià)值的。

1994年，Gilbert Strang將FFT描述為“我們一生中最重要的數(shù)值算法”，并被IEEE雜志《計(jì)算科學(xué)與工程》列入20世紀(jì)十大算法之一，它深遠(yuǎn)的影響了我們世界與日常生活。說(shuō)這個(gè)算法改變了世界也不為過(guò)。在我們?nèi)粘Ｉ钪泻芏嘣O(shè)備里面都有它的影子，比如手機(jī)、比如photoshop，比如數(shù)字音響等等。

快速傅立葉算法的最核心思想就是計(jì)算機(jī)科學(xué)里面常見(jiàn)的分治思想，即把一個(gè)復(fù)雜的問(wèn)題，分解為一個(gè)小的類似問(wèn)題進(jìn)行求解。

FFT基本上可分為兩類，時(shí)間抽取法和頻率抽取法，而一般的時(shí)間抽取法和頻率抽取法只能處理長(zhǎng)度N=2M的情況，另外還有組合數(shù)基四FFT來(lái)處理一般長(zhǎng)度的FFT。所謂抽取，就是把長(zhǎng)序列分為短序列的過(guò)程，可在時(shí)域也可在頻域進(jìn)行。最常用的時(shí)域抽選方法是按奇偶將長(zhǎng)序列不斷地變?yōu)槎绦蛄校Y(jié)果使輸入序列為倒序，輸出序列為順序排列，這就是Coolly—Tukey算法。

假定待變換離散時(shí)間序列信號(hào)長(zhǎng)度為 ，將x(n)按照奇偶分組。其中，k取0，1，...，N/2-1。

由于A(k),B(k)都是 點(diǎn)的DFT，X(k)為N點(diǎn)的DFT。那么這一分治思想還可以進(jìn)一步做下去，這里就不贅述了。

下圖就是一個(gè)時(shí)間抽取的基2FFT算法的示意圖：

對(duì)于頻率抽取基2的示意圖其原理類似，這里放個(gè)圖：

不同點(diǎn)：

• DIT2 FFT是在時(shí)域先進(jìn)行奇歐倒序，頻域輸出為正序
• DIF2 FFT其輸入序列在時(shí)域是正序，而頻域輸出為奇偶分開(kāi)的倒序。

代碼實(shí)踐

好了，前面碼了這么多字，還是不夠直觀，為了更好說(shuō)明前面的分治思想，這里放了個(gè)遞歸實(shí)現(xiàn)代碼測(cè)一下看看療效：

#include  #include  #include  #include  #define q 8 /* 2^q 點(diǎn)，256 */ #define N (1</* N點(diǎn) FFT, iFFT */ typedef float real; typedef struct{ real Re; 
  real Im;
} complex; #ifndef PI # define PI 3.14159265358979323846264338327950288 #endif /*為了更好說(shuō)明分治思想，這里采用遞歸實(shí)現(xiàn)，結(jié)束條件為N<=1*/ void fft( complex *v, int n, complex *tmp ) { if(n>1) { /* N如小于1，直接返回*/ int k,m; complex z, w, *vo, *ve;
    ve = tmp; vo = tmp+n/2; for(k=0; k2; k++) {
      ve[k] = v[2*k];
      vo[k] = v[2*k+1];
    }
    fft( ve, n/2, v ); /* FFT 偶數(shù)序列 v[] */ fft( vo, n/2, v ); /* FFT 偶數(shù)序列 v[] */ for(m=0; m2; m++) {
      w.Re = cos(2*PI*m/(double)n);
      w.Im = -sin(2*PI*m/(double)n);
      z.Re = w.Re*vo[m].Re - w.Im*vo[m].Im; /* Re(w*vo[m]) */ z.Im = w.Re*vo[m].Im + w.Im*vo[m].Re; /* Im(w*vo[m]) */ v[  m  ].Re = ve[m].Re + z.Re;
      v[  m  ].Im = ve[m].Im + z.Im;
      v[m+n/2].Re = ve[m].Re - z.Re;
      v[m+n/2].Im = ve[m].Im - z.Im;
    }
  } return;
} /*為了更好說(shuō)明分治思想，這里采用遞歸實(shí)現(xiàn)，結(jié)束條件為N<=1*/ void ifft( complex *v, int n, complex *tmp ) { if(n>1) { int k,m; complex z, w, *vo, *ve;
    ve = tmp; vo = tmp+n/2; for(k=0; k2; k++) {
      ve[k] = v[2*k];
      vo[k] = v[2*k+1];
    }
    ifft( ve, n/2, v ); /* FFT 偶數(shù)序列 v[] */ ifft( vo, n/2, v ); /* FFT 奇數(shù)序列 v[] */ for(m=0; m2; m++) {
      w.Re = cos(2*PI*m/(double)n);
      w.Im = sin(2*PI*m/(double)n);
      z.Re = w.Re*vo[m].Re - w.Im*vo[m].Im; /* Re(w*vo[m]) */ z.Im = w.Re*vo[m].Im + w.Im*vo[m].Re; /* Im(w*vo[m]) */ v[  m  ].Re = ve[m].Re + z.Re;
      v[  m  ].Im = ve[m].Im + z.Im;
      v[m+n/2].Re = ve[m].Re - z.Re;
      v[m+n/2].Im = ve[m].Im - z.Im;
    }
  } return;
} #define SAMPLE_RATE (10000.0f) int main(void) { complex v[N], scratch[N]; float amp[N]; int k; /*模擬一個(gè)采樣系統(tǒng)，采樣率為10KHz，有兩個(gè)信號(hào)：500Hz/2kHz*/ for(k=0; k1*sin(2*PI*500*k/SAMPLE_RATE)+0.5*sin(2*PI*2000*k/SAMPLE_RATE);
    v[k].Im = 0;//實(shí)際信號(hào)處理時(shí)，虛部常為0 } /*輸出模擬信號(hào)*/ for(int i=0;iprintf("%f,",v[i].Re);      
  } printf("\n");  
  fft( v, N, scratch ); for( int i=0;iprintf("%f,",sqrt(v[i].Re*v[i].Re+v[i].Im*v[i].Im));
  } printf("\n"); while(1);
}

代碼來(lái)源：https://www.math.wustl.edu/~victor/mfmm/fourier/fft.c

為華盛頓大學(xué)的教學(xué)代碼，上面代碼僅測(cè)試了正變換，對(duì)于逆變換有興趣的可以試試。

總結(jié)一下

本文目的為了方便理解快速傅立葉的算法思想，如果需要將算法實(shí)際應(yīng)用到單片機(jī)或者DSP中，還需要做進(jìn)一步的優(yōu)化，實(shí)際使用時(shí)，一般會(huì)將蝶形算子做成一個(gè)表，另外也會(huì)做定點(diǎn)優(yōu)化。對(duì)于ARM芯片而言，其CMSIS庫(kù)有現(xiàn)成的實(shí)現(xiàn)例子可以直接使用，對(duì)于TI系列DSP而言，也內(nèi)置了FFT代碼庫(kù)，可直接使用。