標籤：

如何理解和掌握快速傅里葉變換的計算和概念？

01-07

離散傅立葉變換（DFT）的定義：

Xleft[k ight]=sum_{n=0}^{N-1}{xleft[n ight]e^{-jfrac{2pi}{N}kn}} ,0le k leq N-1

為了表達簡潔，令W_N=e^{-jfrac{2pi}{N}}，則Xleft[k ight]=sum_{n=0}^{N-1}{xleft[n ight]W_N^{kn}} 。

FFT的種類很多，這裡以最簡單的基於2的FFT（信號長度N 是2的整數冪）為例：

FFT實際上一種分治演算法。FFT將長度為N 的信號分解成兩個長度為frac{N}{2}信號進行處理，這樣分解一直到最後，每一次的分解都會減少計算的次數。理解FFT分以下三個步驟進行：

步驟1：將信號xleft[n ight]分解成兩個子信號

偶數樣本點信號：xleft[2n ight]；

奇數樣本點信號：xleft[2n+1 ight]；N=0,1,cdots,frac{N}{2}-1

則：Xleft[k ight]=sum_{n=0}^{N-1}{xleft[n ight]W_N^{kn}} =sum_{n=0}^{frac{N}{2}-1}{xleft[2n ight]W_N^{kleft(2n ight)}}+sum_{n=0}^{frac{N}{2}-1}{xleft[2n+1 ight]W_N^{kleft(2n+1 ight)}}

步驟2：將兩個求和項理解成兩個長度為frac{N}{2}的DFT

Xleft[k ight]=sum_{n=0}^{N-1}{xleft[n ight]W_N^{kn}} =sum_{n=0}^{frac{N}{2}-1}{xleft[2n ight]W_N^{kleft(2n ight)}}+W_N^ksum_{n=0}^{frac{N}{2}-1}{xleft[2n+1 ight]W_N^{kleft(2n ight)}}

其中W_N^{kleft(2n ight)}=e^{-jfrac{2pi}{N}2n}=e^{-jfrac{2pi}{frac{N}{2}}n}=W_{frac{N}{2}}^{kn}，所以

Xleft[k ight]=Eleft[k ight]+W_N^kOleft[k ight],0le k leq N-1

其中，偶數樣本點信號的DFT：Eleft[k ight]=sum_{n=0}^{frac{N}{2}-1}{xleft[2n ight]}W_{frac{N}{2}}^{kn}

奇數樣本點信號的DFT：Oleft[k ight]=sum_{n=0}^{frac{N}{2}-1}{xleft[2n+1 ight]}W_{frac{N}{2}}^{kn}

步驟3：FFT的具體計算過程（通過蝶形圖可視化）

由於W_N^{kn}對k和n都具有周期性：W_N^{kn}=W_N^{kleft(n+N ight)}=W_N^{left(k+N ight)n}，所以，

Eleft[k ight]=Eleft[k+frac{N}{2} ight]，Oleft[k ight]=Oleft[k+frac{N}{2} ight]（周期性）

以N=8為例，信號的FFT計算過程如下：

第1次分解：

第2次分解：

第3次分解：

FFT與DFT的性能比較

根據DFT的定義，

對於任意k都要進行N次加法操作，所以DFT共有N^2次乘法操作。

對於任意k都要進行N-1次加法操作，所以DFT共有Nleft(N-1 ight)次加法操作。

從FFT的蝶形圖中可以看出，

共有Nleft(log_2N-1 ight)次乘法操作和Nlog_2N次加法操作。

十、從頭到尾徹底理解傅里葉變換演算法、上

靈魂級別詳解快速傅立葉變換

這篇博客里寫的非常好！可能每個人有每個人的理解，但是這編文章寫完讓我快速理解fft！

如果可以再詳細一點或者形象一點就更好了。對於蝶形演算法似懂非懂，希望還有高人指點。

推薦閱讀：

※信號的傅立葉變換後的虛數怎樣理解?
※學習複分析需要哪些基礎？
※怎樣高效閱讀一本英文數學教材？
※傅里葉變換的不足有哪些？有哪些改進的方法？
※如何獲取FFT序列中每個點的頻率值？

TAG:計算 | 傅里葉變換FourierTransform |