快速傅利葉轉換(Fast
Fourier Transform; FFT)
快速傅利葉轉換(Fast
Fourier Transform; FFT)
在本章第一節我們曾提及離散傅利葉轉換在計算上可以有取巧的地方，也就是所謂的快速傅利葉轉換
( FFT：Fast
Fouier Transform)，事實上我們在介紹
MATALB 軟體時，就已經使用快速傅利葉轉換了，MATALB
快速傅利葉轉換指令為 FFT
，在計算上大家可以感受到它的快速便利。早期的傅利葉轉換大都利用手算來完成，因此傅利葉轉換標本個數都很小，儘管早在
1865 年 Gauss
就曾提出有關於如何更快的計算傅利葉轉換的演算技巧，但快速傅利葉轉換的演算法真正開始受到重視是在
1965 年 Cooley
及 Tukey 發表一系列快速傅利葉轉換的論文，由於計算機能力的加強，傅利葉轉換標本個數增大了，大家開始關心如何使用更快的計算方式來節省計算機的時間，因此快速傅利葉轉換才有它的價值。當我們以傳統的計算方式進行
DFT 運算時，對一個
點的序列而言，
DFT 運算需要 
計算量，但是如果使用快速傳氏轉換
(FFT) 時，我們則只需要
個計算量，當
N 很大時，這樣節省下來的計算時間是相當可觀的。例如當序列樣本個數為
=1024 個，快速傅利葉轉換可減少
100 倍的運算量，如樣本個數為
=1048576
個，快速傅利葉轉換即可減少 10000
倍的運算量。由於有各種新的快速傅利葉轉換的計算方式被開發出來，目前快速傅利葉轉換樣本個數已不限只是
個點了，在
MATLAB 中，其快速傅利葉轉換的計算方式是先將序列樣本個數最接近的
個點之快速傅利葉轉換求出，其它的轉換值則再套入其它的快速傅利葉轉換的計算方式分別求出再予合併，然而如果您提供的快速傅利葉轉換樣本個數是
個點的話，所花費的計算時間將會比樣本個數不是
個點要節省
8 倍以上。
由於離散傅利葉轉換其定義為：
其中
，
，在此運算子
，由於
，亦即
為常數
1，乘入而不影響結果但可簡化整個式子。另外
也具有共軛複數對稱性：
，例如
。
此外， 
也具有週期性：
，
DFT 中一次複數之運算（乘法）就相當於四次實數乘法，亦即
一般而言，
。
我們可以發現在離散傅氏轉換 DFT 之複數運算中，有不少是一再重複的項次，因此我們可以將重複的項次重新編組，利用一種網狀的流程圖來運算，這也就是所謂的蝴蝶圖 (butterfly) 了。
對於一個有四個元素的一維信號，其快速傳氏轉換之蝴蝶圖如下(圖 A )：
讓我們驗算看看：由於
因此
X[0]=x[0]
+x[1]
+x[2]
+x[3]
=x[0]+x[1]+x[2]+x[3]
=(x[0]+x[2])+(x[1]+x[3])
=元素a+元素c
X[1]=x[0]
+x[1]
+x[2]
+x[3]
=(x[0]
+x[2]
)+(x[1]
+x[3]
)
=元素b+
元素d
X[2]=x[0]
+x[1]
+x[2]
+x[3]
=(x[0]+ x[2])+(x[1]+x[3]
)
=元素a+元素c
X[3]=x[0]
+x[1]
+x[2]
+x[3]
=(x[0]+x[2])+(x[1]
+x[3])
=元素b+元素d
驗證了它最後輸出的結果是正確的。
大家可能一時還很難接受這樣的快速傳氏轉換的方式（當然它不是唯一的快速傳氏轉換的方式），但是我們已經驗證了它最後輸出的結果是正確的，並且它的計算量也較少(由於傅利葉轉換標本個數很少，因此減少的計算量很少），於是我們就可以將這個架構繼續推展，如果有八個元素的一維信號，我們就可以先把它分成四個四個在一起，再將它們合併起來，因此對於一個有八個元素的一維信號，其快速傳氏轉換之蝴蝶圖如下(圖 B )：
我們可以觀察到上面的蝴蝶圖輸入值 x[n] 順序是交錯的，但是輸出值X[k]則是按順序排列的，我們也可以蝴蝶圖改成輸出值 X[k] 順序是交錯的，但是輸入值 x[n] 則是按順序排列的，或者是輸出值 X[k] 與輸入值 x[n] 都是按順序排列的蝴蝶圖，但這樣一來，蝴蝶圖中間的運算順序卻很混亂，並不適合進行快速傅利葉轉換程式的撰寫。
【練習一】
【練習二】
【練習三】
【練習四】
1.離散時間.... 2.離散系統之.... 3.信號取樣.... 4.離散傅氏.... 5.快速傅利葉轉換 回首頁 回文字版首頁