FFT快速傅立葉變換的工作原理

FFT是計(jì)算DFT的快速算法，但是它是基于復(fù)數(shù)的，所以計(jì)算實(shí)數(shù)DFT的時(shí)候需要將其轉(zhuǎn)換為復(fù)數(shù)的格式，下圖展示了實(shí)數(shù)DFT和虛數(shù)DFT的情況，實(shí)數(shù)DFT將時(shí)域中N點(diǎn)信號轉(zhuǎn)換成2個(gè)(N/2+1)點(diǎn)的頻域信號，其中1個(gè)(N/2+1)點(diǎn)的信號稱之為實(shí)部，另一個(gè)(N/2+1)點(diǎn)的信號稱之為虛部，實(shí)部和虛部分別是正弦和余弦信號的幅度。

相比較而言，復(fù)數(shù)DFT將2個(gè)N點(diǎn)的時(shí)域信號轉(zhuǎn)換為2個(gè)N點(diǎn)的頻域信號。時(shí)域和頻域中，1個(gè)N點(diǎn)信號是實(shí)部，另1個(gè)N點(diǎn)信號是虛部。

如果要計(jì)算N點(diǎn)實(shí)數(shù)DFT，則將這個(gè)N個(gè)點(diǎn)作為時(shí)域中的實(shí)部，另取N個(gè)0點(diǎn)作為時(shí)域的虛部，用FFT計(jì)算這樣一個(gè)復(fù)數(shù)信號的DFT得到2個(gè)N點(diǎn)的頻域信號，1個(gè)N點(diǎn)是實(shí)部另1個(gè)N點(diǎn)是虛部，在這兩個(gè)N點(diǎn)的信號中，從0到N/2個(gè)點(diǎn)就是須計(jì)算的N點(diǎn)實(shí)數(shù)的DFT頻域。

對于實(shí)數(shù)DFT來說，它的頻域也是離散周期信號，其周期為N點(diǎn)，從0到N/2點(diǎn)和1-N到-1點(diǎn)具有對稱性，這個(gè)你可以從下面一張圖看出。圖中坐標(biāo)不是用N表示，是用采樣頻率的分?jǐn)?shù)表示。

所以你如果用FFT反變換計(jì)算的是實(shí)數(shù)時(shí)域，則要滿足上圖的對稱性。

FFT如何工作

◤

FFT的計(jì)算可以分為三步：首先將1個(gè)N點(diǎn)的時(shí)域信號分成N個(gè)1點(diǎn)的時(shí)域信號，然后計(jì)算這N個(gè)1點(diǎn)時(shí)域信號的頻域，得到N個(gè)頻域的點(diǎn)，然后將這個(gè)N個(gè)頻域的點(diǎn)按照一定的順序加起來，就得到了我們需要的頻譜。這里每個(gè)點(diǎn)的意思是復(fù)數(shù)，都有實(shí)部和虛部。

• 第一步的信號分解按照下面的規(guī)律執(zhí)行：

可以看出它是按照比特反轉(zhuǎn)順序來分解的。

• 第二步是計(jì)算每個(gè)點(diǎn)的頻譜：

這一步很簡單，因?yàn)橐粋€(gè)時(shí)域的點(diǎn)的頻譜的數(shù)值就是它自己，所以這一步什么也不需做，但需明白這時(shí)候N個(gè)點(diǎn)不是時(shí)域信號了，而是頻域信號。

• 第三步是將這N個(gè)頻域信號結(jié)合起來

這一步是最麻煩的一步。就是和前面時(shí)域分解的順序相反，將2個(gè)1點(diǎn)的頻域信號變成1個(gè)2點(diǎn)的頻域信號，再將2個(gè)2點(diǎn)的頻域信號變成1個(gè)4點(diǎn)的頻域信號，一直到結(jié)束。這里看下如何將2個(gè)4點(diǎn)的頻域信號變成1個(gè)8點(diǎn)的頻域信號。

首先對1個(gè)4點(diǎn)的頻域信號進(jìn)行復(fù)制，這樣能稀釋時(shí)域信號，也對另1個(gè)4點(diǎn)的頻域信號進(jìn)行復(fù)制，不過復(fù)制之前需要乘上正弦函數(shù)，這樣得到的稀釋時(shí)域信號時(shí)經(jīng)過了平移的，然后將這兩個(gè)頻域信號加起來，如下圖所示。之所以這么做的目的是在時(shí)域分解的時(shí)候就是用這種交織的分解方式的。

以下是基本的運(yùn)算，稱為蝶形運(yùn)算，它將2個(gè)1點(diǎn)的復(fù)數(shù)變成1個(gè)2點(diǎn)的復(fù)數(shù)。

FFT運(yùn)算的流程圖

運(yùn)算速度比較

• 如果用相關(guān)方法計(jì)算DFT：

• 如果用FFT方法計(jì)算DFT：

不過，F(xiàn)FT的速度還能更快。 比如使用基4或者基8，這樣不是2點(diǎn)一計(jì)算，而是4點(diǎn)或者8點(diǎn)一計(jì)算，可以提高速度。

FFT對DSP來說就像是晶體管對電子學(xué)來說，都是領(lǐng)域的基礎(chǔ)，每個(gè)人都知道怎么使用它們，但是只有很少一部分真正了解它們的原理。

事實(shí)就是這樣，你只要知道怎么用就可以了。