库利－图基快速傅里叶变换算法 - 维基百科
文章推薦指數： 80 %
库利－图基算法最有名的應用，是將序列長為N的DFT分割為兩個長為N/2的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。
實際上，如同高斯和库利與 ...
庫利－圖基快速傅立葉變換演算法
語言
監視
編輯
庫利－圖基快速傅立葉變換演算法（Cooley-Tukey演算法）[1]是最常見的快速傅里葉變換演算法。
這一方法以分治法為策略遞迴地將長度為N=N1N2的DFT分解為長度分別為N1和N2的兩個較短序列的DFT，以及與旋轉因子的複數乘法。
這種方法以及FFT的基本思路在1965年J.W.Cooley和J.W.Tukey合作發表AnalgorithmforthemachinecalculationofcomplexFourierseries之後開始為人所知。
但後來發現，實際上這兩位作者只是重新發明了高斯在1805年就已經提出的演算法（此演算法在歷史上數次以各種形式被再次提出）。
庫利－圖基演算法最有名的應用，是將序列長為N的DFT分割為兩個長為N/2的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。
實際上，如同高斯和庫利與圖基都指出的那樣，庫利－圖基演算法也可以用於序列長度N為任意因數分解形式的DFT，即混合基FFT，而且還可以應用於其他諸如分裂基FFT等變種。
儘管庫利－圖基演算法的基本思路是採用遞迴的方法進行計算，大多數傳統的演算法實現都將顯示的遞迴演算法改寫為非遞迴的形式。
另外，因為庫利－圖基演算法是將DFT分解為較小長度的多個DFT，因此它可以同任一種其他的DFT演算法聯合使用。
目次
1複雜度
2時域/頻域抽取法
2.1時域抽取法
2.2頻域抽取法
3單一基底
3.12基底
3.24基底
3.38基底
4混合基底
4.12/8基底
4.22/4/8基底
4.322基底
4.423基底
4.4.1'"`UNIQ--postMath-00000041-QINU`"'乘法化簡
5一般性分解[2]
5.1'"`UNIQ--postMath-0000004F-QINU`"'非互質
5.2'"`UNIQ--postMath-000000A8-QINU`"'互質
6參考資料
複雜度編輯
離散傅立葉變換的複雜度為
O
(
n
2
)
{\displaystyle{\mathcal{O}}(n^{2})}
（可參考大O符號）
快速傅立葉變換的複雜度為
O
(
N
log
N
)
{\displaystyle{\mathcal{O}}(N\logN)}
，分析可見下方架構圖部分，級數為
log
N
{\displaystyle\logN}
而每一級的複雜度為
N
{\displaystyleN}
，故複雜度為
O
(
N
log
N
)
{\displaystyle{\mathcal{O}}(N\logN)}
時域/頻域抽取法編輯
在FFT演算法中，針對輸入做不同方式的分組會造成輸出順序上的不同。
如果我們使用時域抽取（Decimation-in-time），那麼輸入的順序將會是位元反轉排列（bit-reversedorder），輸出將會依序排列。
但若我們採取的是頻域抽取（Decimation-in-frequency），那麼輸出與輸出順序的情況將會完全相反，變為依序排列的輸入與位元反轉排列的輸出。
時域抽取法編輯
我們可以將DFT公式中的項目在時域上重新分組，這樣就叫做時域抽取（Decimation-in-time），在這裡
e
−
j
(
2
π
n
k
N
)
{\displaystylee^{-j(2\pi{\frac{nk}{N}})}}
將會被代換為旋轉因子（twiddlefactor）
W
N
n
k
{\displaystyleW_{N}^{nk}}
。
X
[
k
]
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
j
(
2
π
n
k
N
)
k
=
0
,
1
,
…
,
N
−
1
{\displaystyleX[k]=\sum_{n=0}^{N-1}x[n]e^{-j(2\pi{\frac{nk}{N}})}\qquadk=0,1,\ldots,N-1}
=
∑
n
e
v
e
n
x
[
n
]
W
N
n
k
+
∑
n
o
d
d
x
[
n
]
W
N
n
k
{\displaystyle=\sum_{n\even}x[n]W_{N}^{nk}+\sum_{n\odd}x[n]W_{N}^{nk}}
=
∑
r
=
0
(
N
/
2
)
−
1
x
[
2
r
]
W
N
2
r
k
+
∑
r
=
0
(
N
/
2
)
−
1
x
[
2
r
+
1
]
W
N
(
2
r
+
1
)
k
{\displaystyle=\sum_{r=0}^{(N/2)-1}x[2r]W_{N}^{2rk}+\sum_{r=0}^{(N/2)-1}x[2r+1]W_{N}^{(2r+1)k}}
=
∑
r
=
0
(
N
/
2
)
−
1
x
[
2
r
]
W
N
2
r
k
+
W
N
k
∑
r
=
0
(
N
/
2
)
−
1
x
[
2
r
+
1
]
W
N
2
r
k
{\displaystyle=\sum_{r=0}^{(N/2)-1}x[2r]W_{N}^{2rk}+W_{N}^{k}\sum_{r=0}^{(N/2)-1}x[2r+1]W_{N}^{2rk}}
=
∑
r
=
0
(
N
/
2
)
−
1
x
[
2
r
]
W
N
/
2
r
k
+
W
N
k
∑
r
=
0
(
N
/
2
)
−
1
x
[
2
r
+
1
]
W
N
/
2
r
k
{\displaystyle=\sum_{r=0}^{(N/2)-1}x[2r]W_{N/2}^{rk}+W_{N}^{k}\sum_{r=0}^{(N/2)-1}x[2r+1]W_{N/2}^{rk}}
=
G
[
k
]
+
W
N
k
H
[
k
]
{\displaystyle=G[k]+W_{N}^{k}H[k]}
在這邊我們要注意的是，我們所替換的G[k]與H[k]具有週期性：
{
G
[
k
+
N
2
]
=
G
[
k
]
H
[
k
+
N
2
]
=
H
[
k
]
{\displaystyle{\begin{cases}G[k+{\frac{N}{2}}]=G[k]\\H[k+{\frac{N}{2}}]=H[k]\end{cases}}}
還注意到係數具有對稱性：
W
N
k
+
N
/
2
=
−
W
N
k
{\displaystyleW_{N}^{k+N/2}=-W_{N}^{k}}
上述的推導可以劃成下面的圖：
劃紅框處所示的
N
2
{\displaystyle{\frac{N}{2}}}
點DFT架構如下圖所示：
劃紅框處所示的
N
4
{\displaystyle{\frac{N}{4}}}
點DFT架構如下圖所示：
下圖是一個8點DITFFT的完整架構圖。
頻域抽取法編輯
我們可以將DFT公式中的項目在頻域上重新分組，這樣就叫做頻域抽取（Decimation-in-frequency）。
首先先觀察在頻域上偶數項的部分：
X
[
2
r
]
=
∑
n
=
0
N
−
1
x
[
n
]
W
N
n
(
2
r
)
r
=
0
,
1
,
⋯
,
N
2
−
1
{\displaystyleX[2r]=\sum_{n=0}^{N-1}x[n]W_{N}^{n(2r)}\r=0,1,\cdots,{\frac{N}{2}}-1}
=
∑
n
=
0
N
2
−
1
x
[
n
]
W
N
2
n
r
+
∑
n
=
N
2
N
−
1
x
[
n
]
W
N
2
n
r
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}x[n]W_{N}^{2nr}+\sum_{n={\frac{N}{2}}}^{N-1}x[n]W_{N}^{2nr}}
=
∑
n
=
0
N
2
−
1
x
[
n
]
W
N
2
n
r
+
∑
n
=
0
N
2
−
1
x
[
n
+
N
2
]
W
N
2
r
[
n
+
N
2
]
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}x[n]W_{N}^{2nr}+\sum_{n=0}^{{\frac{N}{2}}-1}x[n+{\frac{N}{2}}]W_{N}^{2r[n+{\frac{N}{2}}]}}
∵
W
N
2
r
[
n
+
N
2
]
=
W
N
2
r
n
W
N
r
N
=
W
N
2
r
n
{\displaystyle{\color{Gray}\becauseW_{N}^{2r[n+{\frac{N}{2}}]}=W_{N}^{2rn}W_{N}^{rN}=W_{N}^{2rn}}}
=
∑
n
=
0
N
2
−
1
x
[
n
]
W
N
2
r
n
+
∑
n
=
0
N
2
−
1
x
[
n
+
N
2
]
W
N
2
r
n
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}x[n]W_{N}^{2rn}+\sum_{n=0}^{{\frac{N}{2}}-1}x[n+{\frac{N}{2}}]W_{N}^{2rn}}
=
∑
n
=
0
N
2
−
1
(
x
[
n
]
+
x
[
n
+
N
2
]
)
W
N
2
r
n
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}(x[n]+x[n+{\frac{N}{2}}])W_{\frac{N}{2}}^{rn}}
=
∑
n
=
0
N
2
−
1
g
[
n
]
W
N
2
r
n
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}g[n]W_{\frac{N}{2}}^{rn}}
再觀察在頻域上奇數項的部分：
X
[
2
r
+
1
]
=
∑
n
=
0
N
−
1
x
[
n
]
W
N
n
(
2
r
+
1
)
r
=
0
,
1
,
⋯
,
N
2
−
1
{\displaystyleX[2r+1]=\sum_{n=0}^{N-1}x[n]W_{N}^{n(2r+1)}\r=0,1,\cdots,{\frac{N}{2}}-1}
=
∑
n
=
0
N
2
−
1
x
[
n
]
W
N
n
(
2
r
+
1
)
+
∑
n
=
N
2
N
−
1
x
[
n
]
W
N
n
(
2
r
+
1
)
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}x[n]W_{N}^{n(2r+1)}+\sum_{n={\frac{N}{2}}}^{N-1}x[n]W_{N}^{n(2r+1)}}
=
∑
n
=
0
N
2
−
1
x
[
n
]
W
N
n
(
2
r
+
1
)
+
∑
n
=
0
N
2
−
1
x
[
n
+
N
2
]
W
N
(
2
r
+
1
)
[
n
+
N
2
]
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}x[n]W_{N}^{n(2r+1)}+\sum_{n=0}^{{\frac{N}{2}}-1}x[n+{\frac{N}{2}}]W_{N}^{(2r+1)[n+{\frac{N}{2}}]}}
∵
W
N
(
2
r
+
1
)
[
n
+
N
2
]
=
W
N
(
2
r
+
1
)
n
W
N
(
2
r
+
1
)
N
2
=
−
W
N
(
2
r
+
1
)
n
{\displaystyle{\color{Gray}\becauseW_{N}^{(2r+1)[n+{\frac{N}{2}}]}=W_{N}^{(2r+1)n}W_{N}^{(2r+1){\frac{N}{2}}}=-W_{N}^{(2r+1)n}}}
=
∑
n
=
0
N
2
−
1
x
[
n
]
W
N
(
2
r
+
1
)
n
−
∑
n
=
0
N
2
−
1
x
[
n
+
N
2
]
W
N
(
2
r
+
1
)
n
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}x[n]W_{N}^{(2r+1)n}-\sum_{n=0}^{{\frac{N}{2}}-1}x[n+{\frac{N}{2}}]W_{N}^{(2r+1)n}}
=
∑
n
=
0
N
2
−
1
(
x
[
n
]
−
x
[
n
+
N
2
]
)
W
N
n
(
2
r
+
1
)
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}(x[n]-x[n+{\frac{N}{2}}])W_{N}^{n(2r+1)}}
=
∑
n
=
0
N
2
−
1
(
x
[
n
]
−
x
[
n
+
N
2
]
)
W
N
n
W
N
2
n
r
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}(x[n]-x[n+{\frac{N}{2}}])W_{N}^{n}W_{\frac{N}{2}}^{nr}}
=
∑
n
=
0
N
2
−
1
(
h
[
n
]
W
N
n
)
W
N
2
r
n
{\displaystyle=\sum_{n=0}^{{\frac{N}{2}}-1}(h[n]W_{N}^{n})W_{\frac{N}{2}}^{rn}}
上述的推導可以畫成下面的圖：
更進一步的拆解
N
2
{\displaystyle{\frac{N}{2}}}
-pointDFT的架構
下圖為8點FFT下
N
4
{\displaystyle{\frac{N}{4}}}
-pointDFT的架構
總結上述架構，完整的8點DIFFFT架構圖為
單一基底編輯
利用庫利－圖基演算法進行離散傅立葉拆解時，能夠依需求而以2,4,8…等2的冪次方為單位進行拆解，不同的拆解方法會產生不同層數快速傅里葉變換的架構，基底越大則層數越少，複數乘法器也越少，但是每級的蝴蝶形架構則會越複雜，因此常見的架構為2基底、4基底與8基底這三種設計。
2基底編輯
2基底-快速傅立葉演算法（Radix-2FFT）是最廣為人知的一種庫利－圖基快速傅立葉演算法分支。
此方法不斷地將N點的FFT拆解成兩個'N/2'點的FFT，利用旋轉因子
W
n
k
,
W
N
2
{\displaystyleW^{nk},W^{\frac{N}{2}}}
的對稱性藉此來降低DFT的計算複雜度，達到加速的功效。
而其實前述有關時域抽取或是頻域抽取的方法介紹，即為2基底的快速傅立葉轉換法。
以下展示其他種2基底快速傅立葉演算法的連線方法，此種不規則的連線方法可以讓輸出與輸入都為循序排列，但是連線的複雜度卻大大的增加。
4基底編輯
4基底快速傅立葉變換演算法則是承接2基底的概念，在此裡用時域抽取的技巧，將原本的DFT公式拆解為四個一組的形式：
X
[
k
]
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
j
(
2
π
n
k
N
)
k
=
0
,
1
,
…
,
N
−
1
{\displaystyleX[k]=\sum_{n=0}^{N-1}x[n]e^{-j(2\pi{\frac{nk}{N}})}\qquadk=0,1,\ldots,N-1}
=
∑
n
=
0
N
4
−
1
x
[
4
n
+
0
]
W
N
(
4
n
+
0
)
k
+
∑
n
=
0
N
4
−
1
x
[
4
n
+
1
]
W
N
(
4
n
+
1
)
k
{\displaystyle=\sum_{n=0}^{{\frac{N}{4}}-1}x[4n+0]W_{N}^{(4n+0)k}+\sum_{n=0}^{{\frac{N}{4}}-1}x[4n+1]W_{N}^{(4n+1)k}}
+
∑
n
=
0
N
4
−
1
x
[
4
n
+
2
]
W
N
(
4
n
+
2
)
k
+
∑
n
=
0
N
4
−
1
x
[
4
n
+
3
]
W
N
(
4
n
+
3
)
k
{\displaystyle+\sum_{n=0}^{{\frac{N}{4}}-1}x[4n+2]W_{N}^{(4n+2)k}+\sum_{n=0}^{{\frac{N}{4}}-1}x[4n+3]W_{N}^{(4n+3)k}}
=
W
N
0
∑
n
=
0
N
4
−
1
x
[
4
n
+
0
]
W
N
4
n
k
+
W
N
1
k
∑
n
=
0
N
4
−
1
x
[
4
n
+
1
]
W
N
4
n
k
{\displaystyle=W_{N}^{0}\sum_{n=0}^{{\frac{N}{4}}-1}x[4n+0]W_{\frac{N}{4}}^{nk}+W_{N}^{1k}\sum_{n=0}^{{\frac{N}{4}}-1}x[4n+1]W_{\frac{N}{4}}^{nk}}
+
W
N
2
k
∑
n
=
0
N
4
−
1
x
[
4
n
+
2
]
W
N
4
n
k
+
W
N
3
k
∑
n
=
0
N
4
−
1
x
[
4
n
+
3
]
W
N
4
n
k
{\displaystyle+W_{N}^{2k}\sum_{n=0}^{{\frac{N}{4}}-1}x[4n+2]W_{\frac{N}{4}}^{nk}+W_{N}^{3k}\sum_{n=0}^{{\frac{N}{4}}-1}x[4n+3]W_{\frac{N}{4}}^{nk}}
W
N
0
F
0
(
k
)
+
W
N
k
F
1
(
k
)
+
W
N
2
k
F
2
(
k
)
+
W
N
3
k
F
3
(
k
)
{\displaystyleW_{N}^{0}F_{0}(k)+W_{N}^{k}F_{1}(k)+W_{N}^{2k}F_{2}(k)+W_{N}^{3k}F_{3}(k)}
在這裡再利用
W
n
k
+
N
4
=
−
W
n
k
+
3
N
4
=
−
j
W
n
k
{\displaystyleW^{nk+{\frac{N}{4}}}=-W^{nk+{\frac{3N}{4}}}=-jW^{nk}}
的特性來進行與2基數FFT類似的化減方法，以降低演算法複雜度。
8基底編輯
在庫利－圖基演算法裡，使用的基底（radix）越大，複數的乘法與記憶體的存取就越少，所帶來的好處不言而喻。
但是隨之而來的就是實數的乘法與實數的加法也會增加，尤其計算單元的設計也就越複雜，對於可應用FFT之點數限制也就越嚴格。
在表中我們可以看到在不同基底下所需的計算成本。
使用4096點FFT在不同基底下的計算量
動作
2基底
4基底
8基底
複數乘法
22528
15360
10752
實數乘法
0
0
8192
複數加法
49152
49152
49152
實數加法
0
0
8192
記憶體存取
49152
24576
16384
在DFT的公式中，我們重新定義x=[x(0),x(1),…,x(N-1)]T,X=[X(0),X(1),…,X(N-1)]T，則DFT可重寫為X=FN‧x。
FN是一個N×N的DFT矩陣，其元素定義為[FN]ij=WNij(i,j∈[0,N-1])，當N=8時，我們可以得到以下的F8矩陣並且進一步將其拆解。
在拆解成三個矩陣相乘之後，我們可以將複數運算的數量從56個降至24個複數的加法。
底下是8基底的的SFG。
要注意的是所有的輸出與輸入都是複數的形式，而輸出與輸入的排序也並非規律排列，此種排列方式是為了要達到接線的最佳化。
混合基底編輯
2/8基底編輯
在2/8基底的演算法中，我們可以看到我們對於偶數項的輸出會使用2基底的分解法，對於奇數項的輸出採用8基底的分解法。
這個做法充分利用了2基底與4基底擁有最少乘法數與加法數的特性。
當使用了2基底的分解法後，偶數項的輸出如下所示。
C
2
k
=
∑
n
=
0
N
2
−
1
(
x
2
n
+
x
N
2
+
n
)
W
2
n
k
{\displaystyleC_{2k}=\sum_{n=0}^{{\frac{N}{2}}-1}(x_{2n}+x_{{\frac{N}{2}}+n})W^{2nk}}
奇數項的輸出則交由8基底分解來處理，如下四式所述。
C
8
k
+
1
=
∑
n
=
0
N
8
−
1
{
[
(
x
n
−
x
n
+
N
2
)
−
j
(
x
n
+
N
4
−
x
n
+
3
N
4
)
]
+
W
N
8
[
(
x
n
+
N
8
−
x
n
+
5
N
8
)
−
j
(
x
n
+
3
N
8
−
x
n
+
7
N
8
)
]
}
W
8
n
k
W
n
{\displaystyleC_{8k+1}=\sum_{n=0}^{{\frac{N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac{N}{2}}})-j(x_{n+{\frac{N}{4}}}-x_{n+{\frac{3N}{4}}})]+W^{\frac{N}{8}}[(x_{n+{\frac{N}{8}}}-x_{n+{\frac{5N}{8}}})-j(x_{n+{\frac{3N}{8}}}-x_{n+{\frac{7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{n}}
C
8
k
+
5
=
∑
n
=
0
N
8
−
1
{
[
(
x
n
−
x
n
+
N
2
)
−
j
(
x
n
+
N
4
−
x
n
+
3
N
4
)
]
−
W
N
8
[
(
x
n
+
N
8
−
x
n
+
5
N
8
)
−
j
(
x
n
+
3
N
8
−
x
n
+
7
N
8
)
]
}
W
8
n
k
W
5
n
{\displaystyleC_{8k+5}=\sum_{n=0}^{{\frac{N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac{N}{2}}})-j(x_{n+{\frac{N}{4}}}-x_{n+{\frac{3N}{4}}})]-W^{\frac{N}{8}}[(x_{n+{\frac{N}{8}}}-x_{n+{\frac{5N}{8}}})-j(x_{n+{\frac{3N}{8}}}-x_{n+{\frac{7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{5n}}
C
8
k
+
3
=
∑
n
=
0
N
8
−
1
{
[
(
x
n
−
x
n
+
N
2
)
+
j
(
x
n
+
N
4
−
x
n
+
3
N
4
)
]
+
W
3
N
8
[
(
x
n
+
N
8
−
x
n
+
5
N
8
)
+
j
(
x
n
+
3
N
8
−
x
n
+
7
N
8
)
]
}
W
8
n
k
W
3
n
{\displaystyleC_{8k+3}=\sum_{n=0}^{{\frac{N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac{N}{2}}})+j(x_{n+{\frac{N}{4}}}-x_{n+{\frac{3N}{4}}})]+W^{\frac{3N}{8}}[(x_{n+{\frac{N}{8}}}-x_{n+{\frac{5N}{8}}})+j(x_{n+{\frac{3N}{8}}}-x_{n+{\frac{7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{3n}}
C
8
k
+
7
=
∑
n
=
0
N
8
−
1
{
[
(
x
n
−
x
n
+
N
2
)
+
j
(
x
n
+
N
4
−
x
n
+
3
N
4
)
]
−
W
3
N
8
[
(
x
n
+
N
8
−
x
n
+
5
N
8
)
+
j
(
x
n
+
3
N
8
−
x
n
+
7
N
8
)
]
}
W
8
n
k
W
7
n
{\displaystyleC_{8k+7}=\sum_{n=0}^{{\frac{N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac{N}{2}}})+j(x_{n+{\frac{N}{4}}}-x_{n+{\frac{3N}{4}}})]-W^{\frac{3N}{8}}[(x_{n+{\frac{N}{8}}}-x_{n+{\frac{5N}{8}}})+j(x_{n+{\frac{3N}{8}}}-x_{n+{\frac{7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{7n}}
以上式子就是2/8基底的FFT快速演算法。
在架構圖上可化為L型的蝴蝶運算架構，如下圖所示。
而下圖表示的是一個64點的FFT使用2/8基底的架構圖。
雖然2/8基底的演算法縮減了
W
N
8
,
W
3
N
8
{\displaystyleW^{\frac{N}{8}},W^{\frac{3N}{8}}}
的乘法量，但是這種演算法最大的缺點是跟其他固定基底或是混合基底比較起來，他的架構較為不規則。
所以在硬體上比4基底或是2基底更難實現。
2/4/8基底編輯
為了改進Radix2/8在架構上的不規則性，我們在這裡做了一些修改，如下圖4.。
此修改可讓架構更加規則，且所使用的加法器與乘法器數量更加減少，如下表所示。
8n點FFT在不同演算法下所需複數乘法量
N=8n
2基底
4基底
2/4混合基底
2/4/8基底
8
2
-
2
0
64
98
76
72
48
512
1538
-
1082
824
4096
18434
13996
12774
10168
在這裡我們最小的運算單元稱為PE（ProcessElement）,PE內部包含了2/8基底、2/4基底、2基底的運算，簡化過的訊號處理流程與蝴蝶型架構圖可見下圖
22基底編輯
基底的選擇越大會造成蝴蝶形架構更加複雜，控制電路也會複雜化。
因此ShoushengHe和MatsTorkelson在1996提出了一個2^2基底的FFT演算法，利用旋轉因子的特性：
W
N
4
=
−
j
{\displaystyleW_{\frac{N}{4}}=-j}
。
而–j的乘法基本上只需要將被乘數的實部虛部對調，然後將虛部加上負號即可，這樣的負數乘法被定義為'簡單乘法'，因此可以用很簡單的硬體架構來實現。
利用上面的特性，22基底FFT能用串接的方式將旋轉因子以4為單位對DFT公式進行拆解，將蝴蝶形架構層數降到log4N，大幅減少複數乘法器的用量，而同時卻維持了2基底蝴蝶形架構的簡單性，在效能上獲得改進。
22基底DIFFFT演算法的拆解方法如下列公式所述：
N點DFT公式：
X
(
k
)
=
∑
n
=
0
N
−
1
x
(
n
)
W
N
n
k
,
0
≦
k
<
N
{\displaystyleX(k)=\sum_{n=0}^{N-1}x(n)W_{N}^{nk},0\leqqk
一個16點的DFT公式經過一次上面所述之拆解之後可得下面的FFT架構
可以看出上圖的架構保留了2基底的簡單架構，然而複數乘法卻降到每兩級才出現一次，也就是
l
o
g
4
N
{\displaystylelog_{4}N}
次。
而BF2I以及BF2II所對應的硬體架構下圖：
其中BF2II硬體單元中左下角的交叉電路就是用來處理-j的乘法。
一個256點的FFT架構可以由下面的硬體來實現：
其中圖下方的為一7位元寬的計數器，而此架構的控制電路相當單純，只要將計數器的各個位元分別接上BF2I與BF2II單元即可。
下表將2基底、4基底與22基底演算法做一比較，可以發現22基底演算法所需要的乘法氣數量為2基底的一半，加法棄用量是4基底的一半，並維持一樣的記憶體用量和控制電路的簡單性。
乘法器與加法器數量比較
乘法數
加法數
記憶體大小
控制電路
R2SDF
2(log4N-1)
4log4N
N-1
簡單
R4SDF
log4N-1
8log4N
N-1
中等
R22SDF
log4N-1
4log4N
N-1
簡單
23基底編輯
如上所述，22演算法是將旋轉因子
W
N
4
=
−
j
{\displaystyleW^{\frac{N}{4}}=-j}
視為一個簡單乘法，進而由公式以及硬體上的化簡獲得硬體需求上的改進。
而藉由相同的概念，ShoushengHe和MatsTorkelson進一步將旋轉因子
W
N
8
=
2
2
(
1
−
j
)
{\displaystyleW^{\frac{N}{8}}={\frac{\sqrt{2}}{2}}(1-j)}
的乘法化簡成一個簡單乘法，而化簡的方法將會在下面講解。
2
2
{\displaystyle{\frac{\sqrt{2}}{2}}}
乘法化簡編輯
在2基數FFT演算法中的基本概念是利用旋轉因子
W
n
k
,
W
N
2
{\displaystyleW^{nk},W^{\frac{N}{2}}}
的對稱性，4基數演算法則是利用
W
n
k
+
N
4
=
−
W
n
k
+
3
N
4
=
−
j
W
n
k
{\displaystyleW^{nk+{\frac{N}{4}}}=-W^{nk+{\frac{3N}{4}}}=-jW^{nk}}
的特性。
但是我們會發現在這些旋轉因子的對稱特性中─
W
N
8
=
−
W
5
N
8
=
2
2
(
1
−
j
)
,
W
3
N
8
=
−
W
7
N
8
=
−
2
2
(
1
+
j
)
{\displaystyleW^{\frac{N}{8}}=-W^{\frac{5N}{8}}={\frac{\sqrt{2}}{2}}(1-j),W^{\frac{3N}{8}}=-W^{\frac{7N}{8}}=-{\frac{\sqrt{2}}{2}}(1+j)}
─並沒有被利用到。
主要是因為
2
2
(
1
−
j
)
{\displaystyle{\frac{\sqrt{2}}{2}}(1-j)}
的乘法運算會讓整個FFT變得複雜，但是如果藉由近似的方法，我們便可以將此一運算化簡為12個加法。
2
2
=
0.70710678
=
2
−
1
+
2
−
3
+
2
−
4
+
2
−
6
+
2
−
8
+
2
−
9
{\displaystyle{\frac{\sqrt{2}}{2}}=0.70710678=2^{-1}+2^{-3}+2^{-4}+2^{-6}+2^{-8}+2^{-9}}
我們可以從上式注意到，
2
2
{\displaystyle{\frac{\sqrt{2}}{2}}}
可以被近似為五個加法的結果，所以
2
2
(
1
+
j
)
{\displaystyle{\frac{\sqrt{2}}{2}}(1+j)}
就可以被簡化為只有六個加法，再算入實部與虛部的計算，總共只需12個加法器就可以運用到此一簡化特性。
經由與22基底類似的推導，並用串接的方式將旋轉因子以8為單位對DFT公式進行拆解，23基底FFT演算法進一步將複數乘法器的用量縮減到log8N，並同時維持硬體架構的簡單性。
推導的方法與22基底相當類似。
藉由這樣的方法，23基底能將乘法器的用量縮減到2基底的1/3，並同時維持一樣的記憶體用量以及控制電路的簡單性。
一般性分解[2]編輯
除了常在應用中見到與
2
{\displaystyle2}
相關基底的拆解法，對於更加一般性的
N
=
N
1
N
2
{\displaystyleN=N_{1}N_{2}}
點離散傅立葉變換問題，
我們也有辦法在理論上進行拆解，將問題化為數個
N
1
{\displaystyleN_{1}}
與
N
2
{\displaystyleN_{2}}
點離散傅立葉變換問題，並可對計算量進行估計。
而特別的是，透過互質在數論上的特性，對於
N
1
{\displaystyleN_{1}}
與
N
2
{\displaystyleN_{2}}
互質的情況，可以進一步節省一些運算，
在下面會特別分開討論。
N
1
N
2
{\displaystyleN_{1}N_{2}}
非互質編輯
為了避免之後的符號混淆，我們先將
N
1
N
2
{\displaystyleN_{1}N_{2}}
置換為
P
1
P
2
{\displaystyleP_{1}P_{2}}
，也就是說接著要將
N
=
P
1
P
2
{\displaystyleN=P_{1}P_{2}}
點離散傅立葉變換，
想辦法拆解為數個
P
1
{\displaystyleP_{1}}
與
P
2
{\displaystyleP_{2}}
點離散傅立葉變換問題。
接著定義要拆分的問題，要拆分的問題為
N
{\displaystyleN}
點離散傅立葉變換，將
f
[
n
]
{\displaystylef[n]}
轉換至
F
[
m
]
{\displaystyleF[m]}
：
F
[
m
]
=
∑
n
=
0
N
−
1
e
−
i
2
π
N
m
n
f
[
n
]
m
,
n
=
0
,
1
,
…
,
N
−
1
{\displaystyleF[m]=\sum_{n=0}^{N-1}e^{-i{\frac{2\pi}{N}}mn}f[n]\qquadm,n=0,1,\ldots,N-1}
直觀地說，這個
N
{\displaystyleN}
點離散傅立葉變換，將由
n
{\displaystylen}
作為參數的函式
f
[
n
]
{\displaystylef[n]}
，轉換成由
m
{\displaystylem}
作為參數的函式
F
[
m
]
{\displaystyleF[m]}
，
並且
m
,
n
{\displaystylem,n}
都有
N
{\displaystyleN}
個可能的數值。
待定義好要拆分的問題，便可以開始討論如何進行拆分，基本概念是將有
N
{\displaystyleN}
個可能的數值的
m
,
n
{\displaystylem,n}
，
分別化為個使用兩個參數進行描述的函式
m
=
[
m
1
,
m
2
]
,
n
=
[
n
1
,
n
2
]
{\displaystylem=[m_{1},m_{2}],n=[n_{1},n_{2}]}
，並藉此將原問題化為二維度離散傅立葉變換，
便可使用數個較小的離散傅立葉變換問題描述整個過程。
而一種很直覺的轉換方式，便是透過將
m
,
n
{\displaystylem,n}
分別除以
P
2
,
P
1
{\displaystyleP_{2},P_{1}}
，
以商數與餘數來做為參數描述
m
,
n
{\displaystylem,n}
的值：
n
=
n
1
P
1
+
n
2
m
=
m
1
+
m
2
P
2
{\displaystylen=n_{1}P_{1}+n_{2}\qquadm=m_{1}+m_{2}P_{2}}
n
1
,
m
1
=
0
,
1
,
…
,
P
2
−
1
n
2
,
m
2
=
0
,
1
,
…
,
P
1
−
1
{\displaystylen_{1},m_{1}=0,1,\ldots,P_{2}-1\qquadn_{2},m_{2}=0,1,\ldots,P_{1}-1}
其中
n
1
{\displaystylen_{1}}
作為將
n
{\displaystylen}
除以
P
1
{\displaystyleP_{1}}
的商數，與作為
m
{\displaystylem}
除以
P
2
{\displaystyleP_{2}}
的餘數的
m
1
{\displaystylem_{1}}
相同，
具有
P
2
{\displaystyleP_{2}}
個可能數值，同理
n
2
{\displaystylen_{2}}
與
m
2
{\displaystylem_{2}}
有
P
1
{\displaystyleP_{1}}
個可能數值。
將上述的參數代換及
N
=
P
1
P
2
{\displaystyleN=P_{1}P_{2}}
帶入原式，可以得到：
F
[
m
1
+
m
2
P
2
]
=
∑
n
1
=
0
P
2
−
1
∑
n
2
=
0
P
1
−
1
e
−
i
2
π
P
1
P
2
(
m
1
+
m
2
P
2
)
(
n
1
P
1
+
n
2
)
f
[
n
1
P
1
+
n
2
]
{\displaystyleF[m_{1}+m_{2}P_{2}]=\sum_{n_{1}=0}^{P_{2}-1}\sum_{n_{2}=0}^{P_{1}-1}e^{-i{\frac{2\pi}{P_{1}P_{2}}}(m_{1}+m_{2}P_{2})(n_{1}P_{1}+n_{2})}f[n_{1}P_{1}+n_{2}]}
將右式的指數部分乘開並分項化簡可以得到：
F
[
m
1
+
m
2
P
2
]
=
∑
n
1
=
0
P
2
−
1
∑
n
2
=
0
P
1
−
1
f
[
n
1
P
1
+
n
2
]
e
−
i
2
π
P
2
m
1
n
1
e
−
i
2
π
P
1
m
2
n
2
e
−
i
2
π
P
1
P
2
m
1
n
2
e
−
i
2
π
m
2
n
1
{\displaystyleF[m_{1}+m_{2}P_{2}]=\sum_{n_{1}=0}^{P_{2}-1}\sum_{n_{2}=0}^{P_{1}-1}f[n_{1}P_{1}+n_{2}]e^{-i{\frac{2\pi}{P_{2}}}m_{1}n_{1}}e^{-i{\frac{2\pi}{P_{1}}}m_{2}n_{2}}e^{-i{\frac{2\pi}{P_{1}P_{2}}}m_{1}n_{2}}e^{-i2\pim_{2}n_{1}}}
最後透過
e
−
i
2
π
=
1
{\displaystylee^{-i2\pi}=1}
與
P
1
P
2
=
N
{\displaystyleP_{1}P_{2}=N}
，可以得到：
F
[
m
1
+
m
2
P
2
]
=
∑
n
2
=
0
P
1
−
1
∑
n
1
=
0
P
2
−
1
f
[
n
1
P
1
+
n
2
]
e
−
i
2
π
P
2
m
1
n
1
e
−
i
2
π
N
m
1
n
2
e
−
i
2
π
P
1
m
2
n
2
{\displaystyleF[m_{1}+m_{2}P_{2}]=\sum_{n_{2}=0}^{P_{1}-1}\sum_{n_{1}=0}^{P_{2}-1}f[n_{1}P_{1}+n_{2}]e^{-i{\frac{2\pi}{P_{2}}}m_{1}n_{1}}e^{-i{\frac{2\pi}{N}}m_{1}n_{2}}e^{-i{\frac{2\pi}{P_{1}}}m_{2}n_{2}}}
觀察上式，並加上括號輔助釐清運算順序我們可以得到：
F
[
m
1
+
m
2
P
2
]
=
∑
n
2
=
0
P
1
−
1
{
{
∑
n
1
=
0
P
2
−
1
f
[
n
1
P
1
+
n
2
]
e
−
i
2
π
P
2
m
1
n
1
}
e
−
i
2
π
N
m
1
n
2
}
e
−
i
2
π
P
1
m
2
n
2
{\displaystyleF[m_{1}+m_{2}P_{2}]=\sum_{n_{2}=0}^{P_{1}-1}\left\{\left\{\sum_{n_{1}=0}^{P_{2}-1}f[n_{1}P_{1}+n_{2}]e^{-i{\frac{2\pi}{P_{2}}}m_{1}n_{1}}\right\}e^{-i{\frac{2\pi}{N}}m_{1}n_{2}}\right\}e^{-i{\frac{2\pi}{P_{1}}}m_{2}n_{2}}}
最內層的運算可以視為將雙參數函式
f
[
n
1
,
n
2
]
{\displaystylef[n_{1},n_{2}]}
中的一個參數
n
1
{\displaystylen_{1}}
，透過離散傅立葉變換取代為由
m
1
{\displaystylem_{1}}
描述，
得到一個新函式
G
1
[
m
1
,
n
2
]
{\displaystyleG_{1}[m_{1},n_{2}]}
(這步因為對每個不同
n
2
{\displaystylen_{2}}
，都需要做一次將
n
1
{\displaystylen_{1}}
取代為
m
1
{\displaystylem_{1}}
的轉換，
共需要
P
1
{\displaystyleP_{1}}
個
P
2
{\displaystyleP_{2}}
點離散傅立葉變換)：
F
[
m
1
+
m
2
P
2
]
=
∑
n
2
=
0
P
1
−
1
{
G
1
[
m
1
,
n
2
]
e
−
i
2
π
N
m
1
n
2
}
e
−
i
2
π
P
1
m
2
n
2
{\displaystyleF[m_{1}+m_{2}P_{2}]=\sum_{n_{2}=0}^{P_{1}-1}\left\{G_{1}[m_{1},n_{2}]e^{-i{\frac{2\pi}{N}}m_{1}n_{2}}\right\}e^{-i{\frac{2\pi}{P_{1}}}m_{2}n_{2}}}
下一層的運算則可視為單純的乘法，將
G
1
[
m
1
,
n
2
]
{\displaystyleG_{1}[m_{1},n_{2}]}
與
e
−
i
2
π
N
m
1
n
2
{\displaystylee^{-i{\frac{2\pi}{N}}m_{1}n_{2}}}
相乘，得到
G
2
[
m
1
,
n
2
]
{\displaystyleG_{2}[m_{1},n_{2}]}
(這步需要的計算量視
m
1
n
2
N
{\displaystyle{\frac{m_{1}n_{2}}{N}}}
的特殊性而會有變化)：
F
[
m
1
+
m
2
P
2
]
=
∑
n
2
=
0
P
1
−
1
G
2
[
m
1
,
n
2
]
e
−
i
2
π
P
1
m
2
n
2
{\displaystyleF[m_{1}+m_{2}P_{2}]=\sum_{n_{2}=0}^{P_{1}-1}G_{2}[m_{1},n_{2}]e^{-i{\frac{2\pi}{P_{1}}}m_{2}n_{2}}}
最後的運算可以視為將函式
G
2
[
m
1
,
n
2
]
{\displaystyleG_{2}[m_{1},n_{2}]}
中
n
2
{\displaystylen_{2}}
，透過離散傅立葉變換取代為由
m
2
{\displaystylem_{2}}
描述，
得到一個新函式
G
3
[
m
1
,
m
2
]
{\displaystyleG_{3}[m_{1},m_{2}]}
(這步因為對每個不同
m
1
{\displaystylem_{1}}
，都需要做一次將
n
2
{\displaystylen_{2}}
取代為
m
2
{\displaystylem_{2}}
的轉換，
共需要
P
2
{\displaystyleP_{2}}
個
P
1
{\displaystyleP_{1}}
點離散傅立葉變換)：
F
[
m
(
=
m
1
+
m
2
P
2
)
]
=
G
3
[
m
1
,
m
2
]
{\displaystyleF[m(=m_{1}+m_{2}P_{2})]=G_{3}[m_{1},m_{2}]}
就成功僅使用
P
1
{\displaystyleP_{1}}
與
P
2
{\displaystyleP_{2}}
點離散傅立葉變換，描述了原先的
N
{\displaystyleN}
點離散傅立葉變換。
而在這樣的分解下，我們使用了
P
1
{\displaystyleP_{1}}
個
P
2
{\displaystyleP_{2}}
點離散傅立葉變換與
P
2
{\displaystyleP_{2}}
個
P
1
{\displaystyleP_{1}}
點離散傅立葉變換與一些額外的乘法，
並且這些額外使用的複數乘法
G
1
[
m
1
,
n
2
]
×
e
−
i
2
π
N
m
1
n
2
{\displaystyleG_{1}[m_{1},n_{2}]\timese^{-i{\frac{2\pi}{N}}m_{1}n_{2}}}
，
在電腦的運算架構中，如果
m
1
n
2
N
{\displaystyle{\frac{m_{1}n_{2}}{N}}}
是
1
4
{\displaystyle{\frac{1}{4}}}
的倍數則不需要使用乘法，
如果
m
1
n
2
N
{\displaystyle{\frac{m_{1}n_{2}}{N}}}
是
1
8
,
1
12
{\displaystyle{\frac{1}{8}},{\frac{1}{12}}}
的倍數則僅需兩個實數乘法，
其他則需三個實數乘法，所以總運算量可以如下方式表示：
P
2
B
1
+
P
1
B
2
+
3
D
3
+
2
D
2
{\displaystyleP_{2}B_{1}+P_{1}B_{2}+3D_{3}+2D_{2}}
其中
B
1
{\displaystyleB_{1}}
是
P
1
{\displaystyleP_{1}}
傅立葉所需乘法數，
B
2
{\displaystyleB_{2}}
是
P
2
{\displaystyleP_{2}}
傅立葉所需乘法數，
D
3
{\displaystyleD_{3}}
是需三個實數乘法
m
1
n
2
{\displaystylem_{1}n_{2}}
組合個數，
D
2
{\displaystyleD_{2}}
是需兩個實數乘法
m
1
n
2
{\displaystylem_{1}n_{2}}
組合個數。
而常見以
2
{\displaystyle2}
為基底的分解則是為了使離散傅立葉變換所需乘法數為零，這樣就僅需考慮上面提到的額外乘法，可以提高效率也有較簡單的結構。
N
1
N
2
{\displaystyleN_{1}N_{2}}
互質編輯
在
N
1
N
2
{\displaystyleN_{1}N_{2}}
互質的情況下，仍是採取和上面相近的思路來將問題進行拆分，首先，為了避免之後的符號混淆，我們同樣將
N
1
N
2
{\displaystyleN_{1}N_{2}}
置換為
P
1
P
2
{\displaystyleP_{1}P_{2}}
。
接著同樣定義要拆分的問題：
F
[
m
]
=
∑
n
=
0
N
−
1
e
−
i
2
π
N
m
n
f
[
n
]
m
,
n
=
0
,
1
,
…
,
N
−
1
{\displaystyleF[m]=\sum_{n=0}^{N-1}e^{-i{\frac{2\pi}{N}}mn}f[n]\qquadm,n=0,1,\ldots,N-1}
接著就是和上面的演算法有最大差異的部分，在將
m
,
n
{\displaystylem,n}
化為個使用兩個參數進行描述的函式
m
=
[
m
1
,
m
2
]
,
n
=
[
n
1
,
n
2
]
{\displaystylem=[m_{1},m_{2}],n=[n_{1},n_{2}]}
時，
最直覺的作法便是使用商數和餘數，但在
P
1
,
P
2
{\displaystyleP_{1},P_{2}}
互質的情況下，可以有一些其他更具技巧性的選擇。
當
P
1
,
P
2
{\displaystyleP_{1},P_{2}}
互質，對所有
n
=
0
,
1
,
…
,
N
−
1
{\displaystylen=0,1,\ldots,N-1}
我們可以找到唯一且不重複的一組
n
1
,
n
2
{\displaystylen_{1},n_{2}}
使得：
n
=
(
(
n
1
P
1
+
n
2
P
2
)
)
N
=
n
1
P
1
+
n
2
P
2
+
c
1
N
0
≤
n
1
<
P
2
0
≤
n
2
<
P
1
{\displaystylen=((n_{1}P_{1}+n_{2}P_{2}))_{N}=n_{1}P_{1}+n_{2}P_{2}+c_{1}N\qquad0\leqn_{1}
延伸文章資訊
- 1Split Vector-Radix-2/8 2-D Fast Fourier Transform
The split vector-radix-2/8. FFT algorithm saves 14% real multiplications and has much lower arith...
- 2Fast Fourier Transform (FFT) - CMLab, NTU
Radix-2 FFT Algorithms. Let us consider the computation of the N = 2v point DFT by the divide-and...
- 3Radix 2 FFT - CCRMA - Stanford University
DFT requires no multiplies. The overall result is called a radix 2 FFT. A different radix 2 FFT i...
- 4库利－图基快速傅里叶变换算法 - 维基百科
库利－图基算法最有名的應用，是將序列長為N的DFT分割為兩個長為N/2的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。實際上，如同高斯和库利與 ...
- 5Chapter3 快速傅立葉轉換之架構分類3-0 簡介
由圖可知，此架構是由三級radix-2 FFT 所構成，並且配置乘法器於. 適當的位置，再加上適當的乘法器來達成。所以可視為這二種組合的硬體. 是一樣的。 從架構可以清楚看到， ...
