實(shí)數(shù)DFT，復(fù)數(shù)DFT，F(xiàn)FT

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)信號(hào)轉(zhuǎn)換成2個(gè)(N/2+1)點(diǎn)的頻域信號(hào)，其中1個(gè)(N/2+1)點(diǎn)的信號(hào)稱之為實(shí)部，另一個(gè)(N/2+1)點(diǎn)的信號(hào)稱之為虛部，實(shí)部和虛部分別是正弦和余弦信號(hào)的幅度。

相比較而言，復(fù)數(shù)DFT將2個(gè)N點(diǎn)的時(shí)域信號(hào)轉(zhuǎn)換為2個(gè)N點(diǎn)的頻域信號(hào)。時(shí)域和頻域中，1個(gè)N點(diǎn)信號(hào)是實(shí)部，另1個(gè)N點(diǎn)信號(hào)是虛部。如果要計(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ù)信號(hào)的DFT得到2個(gè)N點(diǎn)的頻域信號(hào)，1個(gè)N點(diǎn)是實(shí)部另1個(gè)N點(diǎn)是虛部，在這兩個(gè)N點(diǎn)的信號(hào)中，從0到N/2個(gè)點(diǎn)就是須計(jì)算的N點(diǎn)實(shí)數(shù)的DFT頻域。對(duì)于實(shí)數(shù)DFT來(lái)說(shuō)，就像前幾章講的那樣，它的頻域也是離散周期信號(hào)，其周期為N點(diǎn)，從0到N/2點(diǎn)和1-N到-1點(diǎn)具有對(duì)稱性，這個(gè)你可以從下面一張圖看出。圖中坐標(biāo)不是用N表示是用采樣頻率的分?jǐn)?shù)表示，如果你看不懂，請(qǐng)看前面幾章。

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

FFT如何工作

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

可以看出它是按照比特反轉(zhuǎn)順序來(lái)分解的。第二步是計(jì)算每個(gè)點(diǎn)的頻譜：這一步很簡(jiǎn)單，因?yàn)橐粋€(gè)時(shí)域的點(diǎn)的頻譜的數(shù)值就是它自己，所以這一步什么也不需做，但需明白這時(shí)候N個(gè)點(diǎn)不是時(shí)域信號(hào)了，而是頻域信號(hào)。第三步是將這N個(gè)頻域信號(hào)結(jié)合起來(lái)這一步是最麻煩的一步。就是和前面時(shí)域分解的順序相反，將2個(gè)1點(diǎn)的頻域信號(hào)變成1個(gè)2點(diǎn)的頻域信號(hào)，再將2個(gè)2點(diǎn)的頻域信號(hào)變成1個(gè)4點(diǎn)的頻域信號(hào)，一直到結(jié)束。這里看下如何將2個(gè)4點(diǎn)的頻域信號(hào)變成1個(gè)8點(diǎn)的頻域信號(hào)。

首先對(duì)1個(gè)4點(diǎn)的頻域信號(hào)進(jìn)行復(fù)制，這樣能稀釋時(shí)域信號(hào)，也對(duì)另1個(gè)4點(diǎn)的頻域信號(hào)進(jìn)行復(fù)制不過(guò)復(fù)制之前需要乘上正弦函數(shù)，這樣得到的稀釋時(shí)域信號(hào)時(shí)經(jīng)過(guò)了平移的，然后將這兩個(gè)頻域信號(hào)加起來(lái)，如下圖所示。之所以這么做的目的是在時(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的速度還能更快

比如使用基4或者基8，這樣不是2點(diǎn)一計(jì)算，而是4點(diǎn)或者8點(diǎn)一計(jì)算，可以提高速度。

FFT對(duì)DSP來(lái)說(shuō)就像是晶體管對(duì)電子學(xué)來(lái)說(shuō)，都是領(lǐng)域的基礎(chǔ)，每個(gè)人都知道怎么使用它們，但是只有很少一部分真正了解它們的原理。事實(shí)就是這樣，你只要知道怎么用就可以了。