摘要

0.1 FFT：
快速傅里葉變換是一種降低離散傅里葉變換計算復雜度的算法，且這種算法有很多種。本文基于Cooley&Tuckey的DIT(decimation in time)算法。

0.2 關鍵詞：
FFT（快速傅里葉變換），DFT（離散傅里葉變換）,DIT（Decimation In Time）,DIF(Decimation In Frequency)

0.3 注意：

DFT(離散傅里葉變換)與DTFT(離散時間傅里葉變換)是不一樣的，DTFT可以當做是有無限個采樣點，而DFT是對采樣信號取一部分（windowing）進行變換的。

對DFT的一種理解（interpretation）：
DFT指代將N個時域信號采樣點轉換為N個頻域信號采樣點。

DFT

1.1 DFT計算公式：

1.2 DFT的矩陣表示方法：

XN是一個N * 1矩陣，指示X[k], k = [0,N-1] （信號時域采樣點的DFT）
xN也是一個N * 1矩陣，指示x[n], n = [0,N-1] (信號的時域采樣點)
WN是一個N * N矩陣，離散傅里葉變換系數（見下式），k = [0,N-1] ，n = [0,N-1]。
Tip: 此處XN的N是下標，xN的N同樣也是下標。
具體表示出來大致如下：

1.3 DFT的計算時間復雜度：
N采樣點的DFT計算時間復雜度為O(N^2)
乘法計算次數為N^2
加法計算次數為N(N-1)

FFT

2.1 降低計算復雜度的方法：
為了降低計算復雜度，將x[n]分為n為奇數和n為偶數兩部分。

n為偶數時，可以用n = 2r, r = [0, (N/2)-1]。
n為奇數時，可以用n = 2r+1，r = [0, (N/2)-1]。
2.2 k取0到N/2-1
這樣展開后就成為下式：

此時我們可以注意到，r是從0到N/2-1的，這意味著我們算X[k]時，k只能取0到N/2-1。
當我們要計算k從N/2到N-1區間的X[k]時，可以計算X[k+N/2]。
2.3 k取N/2到N-1

可以發現，計算X[k]與計算X[k+(N/2)]只有一個符號的差別，這樣可以大大減少計算量。
2.4 總結起來如下：

這種形式的操作可以指示為’butterfly‘操作。

2.5 舉例
對于N=8，8個時域信號采樣點的DFT，可以表示為下式：

當然如果分塊后，N/2依然是偶數，我們還可以利用這種方式減少計算量，如下：

2.6 FFT計算復雜度：
O(NlogN) 此處log以2為底
乘法計算次數為(N/2)*log2(N)
加法計算次數為Nlog2(N)
可以看到，相比于DFT，FFT大大減少了計算量，讓DFT在計算機上的實現變得可能。

總結

以上是生活随笔為你收集整理的快速傅里叶变换FFT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。