庫利-圖基快速傅立葉變換演算法

庫利－圖基快速傅立葉變換演算法。庫利－圖基演算法最有名的應用，是將序列長為N的DFT分割為兩個長為N/2的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。實際上，如同高斯和庫利與圖基都指出的那樣，庫利－圖基演算法也可以用於序列長度N為任意因數分解形式的DFT，即混合基FFT，而且還可以應用於其他諸如分裂基FFT等變種。儘管庫利－圖基演算法的基本思路是採用遞迴的方法進行計算，大多數傳統的演算法實現都將顯示的遞迴演算法改寫為非遞迴的形式。另外，因為庫利－圖基演算法是將DFT分解為較小長度的多個DFT，因此它可以同任一種其他的DFT演算法聯合使用。複雜度.離散傅立葉變換的複雜度為formula_1快速傅立葉變換的複雜度為formula_2，分析可見下方架構圖部分，級數為formula_3而每一級的複雜度為formula_4，故複雜度為formula_2時域/頻域抽取法.在FFT演演算法中，針對輸入做不同方式的分組會造成輸出順序上的不同。如果我們使用時域抽取，那麼輸出與輸出順序的情況將會完全相反，變為依序排列的輸入與位元反轉排列的輸出。時域抽取法.我們可以將DFT公式中的專案在時域上重新分組，這樣就叫做時域抽取formula_7。formula_8formula_9formula_10formula_11formula_12formula_13在這邊我們要注意的是，我們所替換的G[k]與H[k]具有週期性：還注意到係數具有對稱性：上述的推導可以劃成下面的圖：劃紅框處所示的formula_16點DFT架構如下圖所示：劃紅框處所示的formula_17點DFT架構如下圖所示：下圖是一個8點DIT FFT的完整架構圖。頻域抽取法.我們可以將DFT公式中的專案在頻域上重新分組，這樣就叫做頻域抽取。首先先觀察在頻域上偶數項的部分：formula_18formula_19formula_20formula_21formula_22formula_23formula_24再觀察在頻域上奇數項的部分：formula_25formula_26formula_27formula_28formula_29formula_30formula_31formula_32上述的推導可以畫成下面的圖：更進一步的拆解formula_16-point DFT的架構下圖為8點FFT下formula_17-point DFT的架構總結上述架構，完整的8點DIF FFT架構圖為單一基底.利用庫利－圖基演演算法進行離散傅立葉拆解時，能夠依需求而以2, 4, 8…等2的冪次方為單位進行拆解，不同的拆解方法會產生不同層數快速傅裡葉變換的架構，基底越大則層數越少，複數乘法器也越少，但是每級的蝴蝶形架構則會越複雜，因此常見的架構為2基底、4基底與8基底這三種設計。2基底.2基底-快速傅立葉演演算法是最廣為人知的一種庫利－圖基快速傅立葉演演算法分支。此方法不斷地將N點的FFT拆解成兩個'N/2'點的FFT，利用旋轉因子formula_35的對稱性藉此來降低DFT的計算複雜度，達到加速的功效。而其實前述有關時域抽取或是頻域抽取的方法介紹，即為2基底的快速傅立葉轉換法。以下展示其他種2基底快速傅立葉演演算法的連線方法，此種不規則的連線方法可以讓輸出與輸入都為循序排列，但是連線的複雜度卻大大的增加。4基底.4基底快速傅立葉變換演演算法則是承接2基底的概念，在此裡用時域抽取的技巧，將原本的DFT公式拆解為四個一組的形式：formula_8formula_37formula_38formula_39formula_40formula_41在這裡再利用formula_42的特性來進行與2基數FFT類似的化減方法，以降低演演算法複雜度。8基底.在庫利－圖基演算法裡，使用的基底越大，複數的乘法與記憶體的存取就越少，所帶來的好處不言而喻。但是隨之而來的就是實數的乘法與實數的加法也會增加，尤其計算單元的設計也就越複雜，對於可應用FFT之點數限制也就越嚴格。在表中我們可以看到在不同基底下所需的計算成本。在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基底的分解法後，偶數項的輸出如下所示。formula_43奇數項的輸出則交由8基底分解來處理，如下四式所述。formula_44formula_45formula_46formula_47以上式子就是2/8基底的FFT快速演演算法。在架構圖上可化為L型的蝴蝶運算架構，如下圖所示。而下圖表示的是一個64點的FFT使用2/8基底的架構圖。雖然2/8基底的演演算法縮減了formula_48的乘法量，但是這種演演算法最大的缺點是跟其他固定基底或是混合基底比較起來，他的架構較為不規則。所以在硬體上比4基底或是2基底更難實現。2/4/8基底.為了改進Radix 2/8在架構上的不規則性，我們在這裡做了一些修改，如下圖4.。此修改可讓架構更加規則，且所使用的加法器與乘法器數量更加減少，如下表所示。在這裡我們最小的運算單元稱為PE,PE內部包含了2/8基底、2/4基底、2基底的運算，簡化過的訊號處理流程與蝴蝶型架構圖可見下圖22基底.基底的選擇越大會造成蝴蝶形架構更加複雜，控制電路也會複雜化。因此Shousheng He和Mats Torkelson在1996提出了一個2^2基底的FFT演演算法，利用旋轉因子的特性：formula_49。而–j的乘法基本上只需要將被乘數的實部虛部對調，然後將虛部加上負號即可，這樣的負數乘法被定義為'簡單乘法'，因此可以用很簡單的硬體架構來實現。利用上面的特性，22基底FFT能用串接的方式將旋轉因子以4為單位對DFT公式進行拆解，將蝴蝶形架構層數降到log4N，大幅減少複數乘法器的用量，而同時卻維持了2基底蝴蝶形架構的簡單性，在效能上獲得改進。22基底DIF FFT演演算法的拆解方法如下列公式所述：N點DFT公式：formula_50利用線性對映將n與k對映到三個維度上面formula_51然後套用Common Factor Algorithmformula_52formula_53而蝴蝶型架構會變成以下形式formula_54利用旋轉因子formula_49的特性，可以觀察出formula_56formula_57再將此公式帶入原式中可以得到formula_58formula_59如上述公式所示，原本的DFT公式會被拆解成多個formula_60，而formula_60又可分為BF2I與BF2II兩個階層，分別會對應到之後所介紹的兩種硬體架構。一個16點的DFT公式經過一次上面所述之拆解之後可得下面的FFT架構可以看出上圖的架構保留了2基底的簡單架構，然而複數乘法卻降到每兩級才出現一次，也就是formula_62次。而BF2I以及BF2II所對應的硬體架構下圖：其中BF2II硬體單元中左下角的交叉電路就是用來處理-j的乘法。一個256點的FFT架構可以由下面的硬體來實現：其中圖下方的為一7位元寬的計數器，而此架構的控制電路相當單純，只要將計數器的各個位元分別接上BF2I與BF2II單元即可。下表將2基底、4基底與22基底演演算法做一比較，可以發現22基底演演算法所需要的乘法氣數量為2基底的一半，加法棄用量是4基底的一半，並維持一樣的記憶體用量和控制電路的簡單性。23基底.如上所述，22演演算法是將旋轉因子formula_63視為一個簡單乘法，進而由公式以及硬體上的化簡獲得硬體需求上的改進。而藉由相同的概念，Shousheng He和Mats Torkelson進一步將旋轉因子formula_64的乘法化簡成一個簡單乘法，而化簡的方法將會在下面講解。formula_65乘法化簡.在2基數FFT演演算法中的基本概念是利用旋轉因子formula_35的對稱性，4基數演演算法則是利用formula_42的特性。但是我們會發現在這些旋轉因子的對稱特性中─formula_68─並沒有被利用到。主要是因為formula_69的乘法運算會讓整個FFT變得複雜，但是如果藉由近似的方法，我們便可以將此一運算化簡為12個加法。formula_70我們可以從上式注意到，formula_65可以被近似為五個加法的結果，所以formula_72就可以被簡化為只有六個加法，再算入實部與虛部的計算，總共只需12個加法器就可以運用到此一簡化特性。經由與22基底類似的推導，並用串接的方式將旋轉因子以8為單位對DFT公式進行拆解，23基底FFT演演算法進一步將複數乘法器的用量縮減到log8N，並同時維持硬體架構的簡單性。推導的方法與22基底相當類似。藉由這樣的方法，23基底能將乘法器的用量縮減到2基底的1/3，並同時維持一樣的記憶體用量以及控制電路的簡單性。一般性分解.除了常在應用中見到與formula_73相關基底的拆解法，對於更加一般性的formula_74點離散傅立葉變換問題，我們也有辦法在理論上進行拆解，將問題化為數個formula_75與formula_76點離散傅立葉變換問題，並可對計算量進行估計。而特別的是，透過互質在數論上的特性，對於formula_75與formula_76互質的情況，可以進一步節省一些運算，在下面會特別分開討論。formula_79非互質.為了避免之後的符號混淆，我們先將formula_79置換為formula_81，也就是說接著要將formula_82點離散傅立葉變換，想辦法拆解為數個formula_83與formula_84點離散傅立葉變換問題。接著定義要拆分的問題，要拆分的問題為formula_4點離散傅立葉變換，將formula_86轉換至formula_87：formula_88直觀地說，這個formula_4點離散傅立葉變換，將由formula_90作為引數的函式formula_86，轉換成由formula_92作為引數的函式formula_87，並且formula_94都有formula_4個可能的數值。待定義好要拆分的問題，便可以開始討論如何進行拆分，基本概念是將有formula_4個可能的數值的formula_94，分別化為個使用兩個引數進行描述的函式formula_98，並藉此將原問題化為二維度離散傅立葉變換，便可使用數個較小的離散傅立葉變換問題描述整個過程。而一種很直覺的轉換方式，便是透過將formula_94分別除以formula_100，以商數與餘數來做為引數描述formula_94的值：formula_102formula_103其中formula_104作為將formula_90除以formula_83的商數，與作為formula_92除以formula_84的餘數的formula_109相同，具有formula_84個可能數值，同理formula_111與formula_112有formula_83個可能數值。將上述的引數代換及formula_82帶入原式，可以得到：formula_115將右式的指數部分乘開並分項化簡可以得到：formula_116最後透過formula_117與formula_118，可以得到：formula_119觀察上式，並加上括號輔助釐清運算順序我們可以得到：formula_120最內層的運算可以視為將雙引數函式formula_121中的一個引數formula_104，透過離散傅立葉變換取代為由formula_109描述，得到一個新函式formula_124(這步因為對每個不同formula_111，都需要做一次將formula_104取代為formula_109的轉換，共需要formula_83個formula_84點離散傅立葉變換)：formula_130下一層的運算則可視為單純的乘法，將formula_124與formula_132相乘，得到formula_133(這步需要的計算量視formula_134的特殊性而會有變化)：formula_135最後的運算可以視為將函式formula_133中formula_111，透過離散傅立葉變換取代為由formula_112描述，得到一個新函式formula_139(這步因為對每個不同formula_109，都需要做一次將formula_111取代為formula_112的轉換，共需要formula_84個formula_83點離散傅立葉變換)：formula_145就成功僅使用formula_83與formula_84點離散傅立葉變換，描述了原先的formula_4點離散傅立葉變換。而在這樣的分解下，我們使用了formula_83個formula_84點離散傅立葉變換與formula_84個formula_83點離散傅立葉變換與一些額外的乘法，並且這些額外使用的複數乘法formula_153，在電腦的運算架構中，如果formula_134是formula_155的倍數則不需要使用乘法，如果formula_134是formula_157的倍數則僅需兩個實數乘法，其他則需三個實數乘法，所以總運算量可以如下方式表示：formula_158其中formula_159是formula_160傅立葉所需乘法數，formula_161是formula_162傅立葉所需乘法數，formula_163是需三個實數乘法formula_164組合個數，formula_165是需兩個實數乘法formula_164組合個數。而常見以formula_167為基底的分解則是為了使離散傅立葉變換所需乘法數為零，這樣就僅需考慮上面提到的額外乘法，可以提高效率也有較簡單的結構。formula_79互質.在formula_79互質的情況下，仍是採取和上面相近的思路來將問題進行拆分，首先，為了避免之後的符號混淆，我們同樣將formula_79置換為formula_81。接著同樣定義要拆分的問題：formula_88接著就是和上面的演算法有最大差異的部分，在將formula_94化為個使用兩個引數進行描述的函式formula_98時，最直覺的作法便是使用商數和餘數，但在formula_175互質的情況下，可以有一些其他更具技巧性的選擇。當formula_175互質，對所有formula_177我們可以找到唯一且不重複的一組formula_178使得：formula_179其中formula_180，代表取餘數的意思，formula_181是一個整數。例如假設formula_182，則formula_183對應到的formula_184就是formula_185，有formula_186。並且對所有formula_178的組合(有formula_188組)，都對應到一個特定不重複的formula_90。同理我們可以把formula_190表示為formula_191的雙引數函式：formula_192將上述的引數代換及formula_82帶入原式，可以得到：formula_194接著透過一次的展開化簡及應用formula_117可得：formula_196再將formula_82帶入並再透過一次的展開化簡及應用formula_117可得：formula_199觀察上式，並加上括號輔助釐清運算順序我們可以得到：formula_200內層的運算可以視為將雙引數函式formula_201中的一個引數formula_104，透過離散傅立葉變換取代為由一個與formula_109有關的變數formula_204描述，得到一個新函式formula_205(這步因為對每個不同formula_111，都需要做一次將formula_104取代為formula_208的轉換，共需要formula_83個formula_84點離散傅立葉變換)：formula_211外層的運算可以視為將函式formula_205中的引數formula_111，透過離散傅立葉變換取代為由一個與formula_112有關的變數formula_215描述，得到一個新函式formula_216(這步因為對每個不同formula_208，都需要做一次將formula_111取代為formula_219的轉換，共需要formula_84個formula_83點離散傅立葉變換)：formula_222最後透過formula_223與formula_224在不同formula_191時的點點數值對應關係，就成功僅使用formula_83與formula_84點離散傅立葉變換，描述了原先的formula_4點離散傅立葉變換。而這個方法透過聰明的選取表達formula_94的方式，使得拆解的過程中完全不需要多餘的乘法運算，總運算量可以簡單表示為：formula_158其中formula_159是formula_160傅立葉所需乘法數，formula_161是formula_162傅立葉所需乘法數。雖然這個方法可以較上面的方法節省運算量，但這個方法也牽涉較為複雜的formula_94與formula_236轉換，較為不直覺且不易理解，也會遇到許多需要取餘數的運算，可能會需要較大的空間建表進行查表法。最後關於實際上要如何求得formula_90與formula_178的轉換關係，可以先透過輾轉相除法取得一對特定的formula_239使得：formula_240然後我們可以知道對於任意整數formula_241有：formula_242然後就可以得到：formula_243滿足：formula_244