庫利-圖基快速傅立葉變換算法(Cooley-Tukey算法)是最常見的快速傅立葉變換算法。這一方法以分治法為策略遞歸地將長度為N = N1N2的DFT分解為長度分別為N1和N2的兩個較短序列的DFT,以及與旋轉因子的複數乘法。
基本介紹
- 中文名:庫利-圖基快速傅立葉變換算法
- 外文名:Cooley-Tukey
簡介,複雜度,時域-頻域抽取法,時域抽取法,頻域抽取法,單一基底,2基底,4基底,8基底,混合基底,2-8基底,2-4-8基底,4基底,8基底,
簡介
這種方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作發表An algorithm for the machine calculation of complex Fourier series之後開始為人所知。但後來發現,實際上這兩位作者只是重新發明了高斯在1805年就已經提出的算法(此算法在歷史上數次以各種形式被再次提出)。
庫利-圖基快速傅立葉變換算法是將序列長為N的DFT分區為兩個長為N/2的子序列的DFT,因此這一套用只適用於序列長度為2的冪的DFT計算,即基2-FFT。實際上,如同高斯和庫利與圖基都指出的那樣,庫利-圖基算法也可以用於序列長度N為任意因數分解形式的DFT,即混合基FFT,而且還可以套用於其他諸如分裂基FFT等變種。儘管庫利-圖基算法的基本思路是採用遞歸的方法進行計算,大多數傳統的算法實現都將顯示的遞歸算法改寫為非遞歸的形式。另外,因為庫利-圖基算法是將DFT分解為較小長度的多個DFT,因此它可以同任一種其他的DFT算法聯合使用。
複雜度
時域-頻域抽取法
在FFT算法中,針對輸入做不同方式的分組會造成輸出順序上的不同。如果我們使用時域抽取(Decimation-in-time),那么輸入的順序將會是比特反轉排列(bit-reversed order),輸出將會依序排列。但若我們採取的是頻域抽取(Decimation-in-frequency),那么輸出與輸出順序的情況將會完全相反,變為依序排列的輸入與比特反轉排列的輸出。
![DIF FFT DIF FFT](/img/4/4be/nBnauY2YhljNzEGN5AjN3YWZ3MGN1kTZ1UGM4ITYwQ2NiJjYygTO1QzMjF2LtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
時域抽取法
我們可以將DFT公式中的項目在時域上重新分組,這樣就叫做時域抽取(Decimation-in-time),在這裡
將會被代換為旋轉因子(twiddle factor)
。
![](/img/4/c46/fae0f978a016d36f9e1970f0d2e3.jpg)
![](/img/3/4a8/fe2ffe49493097eea0c44dbba67b.jpg)
![](/img/0/e99/7cda72c03da7855233efcd07b37a.jpg)
![](/img/1/cf3/a48837c7121d8d512c2ef74697fe.jpg)
![](/img/a/8d1/57ccae746b5ff3770919f216054f.jpg)
![](/img/1/9b4/3c2e53edae2b179c10c4507b27d5.jpg)
![](/img/8/61a/6075d5859b89e57a408bed3e69c7.jpg)
![](/img/9/4d5/3af4c323ffa0424a47e776649551.jpg)
在這邊我們要注意的是,我們所替換的G[k]與H[k]具有周期性:
![](/img/b/aaa/beaa72667cdbd79311f8008cfe38.jpg)
上述的推導可以劃成下面的圖:
![推導圖 推導圖](/img/8/721/nBnauQmZ3AjZhJWNyAjM4AjZmdTYlJGMiBDOhNDNxQWN5gzYzMTOkdTYzQzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
劃紅框處所示的
點DFT架構如下圖所示:
![](/img/3/543/4e1cc8ee711e93309b024628dbab.jpg)
![DFT架構圖1 DFT架構圖1](/img/8/a7d/nBnaukDMjFGOmFWZ0QzN4MzMwATO5EjY3YmN5MjNiZTOwUmYmFjMmZDNiBzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
劃紅框處所示的
點DFT架構如下圖所示:
![](/img/8/242/7e838af4c77da5bc432680c8b0a9.jpg)
![DFT架構圖2 DFT架構圖2](/img/9/8d7/nBnauAzYkdTMzQmY1ITO5UmZjV2YwYjZzIDN5YWMwYWZlRTO0UzY4YGO1I2LtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
下圖是一個8點DIT FFT的完整架構圖。
![DIT FFT DIT FFT](/img/9/d60/nBnaukzM3kzNlRTNjVmY3UGM0ImNjFmZyADZhlTZxADMxQGO5Q2Y3M2YyE2LtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
頻域抽取法
我們可以將DFT公式中的項目在頻域上重新分組,這樣就叫做頻域抽取(Decimation-in-frequency)。
首先先觀察在頻域上偶數項的部分:
![](/img/a/ced/8c0ff34dd8004c4b98030145b553.jpg)
![](/img/e/20d/a05f09ed2fa7be68f319355409d3.jpg)
![](/img/4/05d/a3edc10906824dae794925dc673f.jpg)
![](/img/d/deb/9a02cf31538b982615d12622b0e3.jpg)
![](/img/a/56e/f39c02968c3a038eaa18d5a553a3.jpg)
![](/img/4/149/c1b8989f1bcf4a0dafbd0ec17d94.jpg)
再觀察在頻域上奇數項的部分:
![](/img/e/1ea/560ccc6cf8ab05205fd29265d5a7.jpg)
![](/img/4/67c/1897a8cab28cd303f77b13163f7b.jpg)
![](/img/1/f83/4667c65b80c18f84cc29d943e80b.jpg)
![](/img/6/949/efb7c6540052af90a9306a019e61.jpg)
![](/img/e/5d7/e1e892da5e099d04605886a33204.jpg)
![](/img/5/e93/62f08bb5aad6276025f67cda3d0f.jpg)
![](/img/e/78f/777405f624d482d46908d43d382f.jpg)
![](/img/f/810/31ece4fd07e3a4fc7210013c2b7c.jpg)
上述的推導可以畫成下面的圖:
![DIF-1 DIF-1](/img/2/6ad/nBnaukDO4M2YyYTNzQmMmlDZlZDOycDZ3EmM0gDMyAjY3EGM1kDZxYDMmZzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
更進一步的拆解
-point DFT的架構
![](/img/b/a7d/696621112c6e64cb3a98f416f148.jpg)
![DIF-2 DIF-2](/img/7/8cc/nBnauIjMjJDZmJzYlN2MjNmZ0MmYlRjNjZWY5IGOycTMxQ2YxEWYiBDMwQ2LtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
下圖為8點FFT下
-point DFT的架構
![](/img/4/706/e2da4bcbc3384c2e66305d472052.jpg)
![DIF-3 DIF-3](/img/f/621/nBnauYGZ5UGZ4IzNzAjNmBTO2QDOmdjNzEGZ5cTMlFzYmZ2Y2IjM4kTYyQzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
總結上述架構,完整的8點DIF FFT架構圖為
![DIF-4 DIF-4](/img/e/893/nBnauIzMiBTO4E2NkNmNlFmZ5MTZmlDM3QWM2gTMiFGNykDM2EDMkZjNzUzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
單一基底
利用庫利-圖基算法進行離散傅立葉拆解時,能夠依需求而以2, 4, 8…等2的冪次方為單位進行拆解,不同的拆解方法會產生不同層數快速傅立葉變換的架構,基底越大則層數越少,複數乘法器也越少,但是每級的蝴蝶形架構則會越複雜,因此常見的架構為2基底、4基底與8基底這三種設計。
2基底
2基底-快速傅立葉算法(Radix-2 FFT)是最廣為人知的一種庫利-圖基快速傅立葉算法分支。此方法不斷地將N點的FFT拆解成兩個'N/2'點的FFT,利用旋轉因子
的對稱性藉此來降低DFT的計算複雜度,達到加速的功效。
![](/img/2/02e/c720f9cf86f9e59bd869c64f7238.jpg)
而其實前述有關時域抽取或是頻域抽取的方法介紹,即為2基底的快速傅立葉轉換法。以下展示其他種2基底快速傅立葉算法的連線方法,此種不規則的連線方法可以讓輸出與輸入都為循序排列,但是連線的複雜度卻大大的增加。
4基底
4基底快速傅立葉變換算法則是承接2基底的概念,在此里用時域抽取的技巧,將原本的DFT公式拆解為四個一組的形式:
![](/img/1/c78/09542e04059a354cbaba0de66aed.jpg)
![](/img/3/e69/9879a2eed076472c89bbe2d020e4.jpg)
![](/img/2/0af/d33f2683b7bc0d5186f8f25d8a7e.jpg)
![](/img/8/8e9/5bfa447231195661327451e4f648.jpg)
![](/img/3/f08/b166567883ebaa154060a3875ef5.jpg)
![](/img/c/05c/48442baf6556776d8649d7a49ae1.jpg)
在這裡再利用
的特性來進行與2基數FFT類似的化減方法,以降低算法複雜度。
![](/img/0/99d/3d50b230e00c842a0970ac7c81d2.jpg)
8基底
在庫利-圖基算法裡,使用的基底(radix)越大,複數的乘法與存儲器的訪問就越少,所帶來的好處不言而喻。但是隨之而來的就是實數的乘法與實數的加法也會增加,尤其計算單元的設計也就越複雜,對於可套用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。要注意的是所有的輸出與輸入都是複數的形式,而輸出與輸入的排序也並非規律排列,此種排列方式是為了要達到接線的最最佳化。
![8基地-1 8基地-1](/img/7/4e3/nBnauUWNycjZkZWN4EGNzAjNwUDOjNWN1gTNzUmZwUWNmRmM5ITYzYWMxY2LtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
混合基底
2-8基底
在2/8基底的算法中,我們可以看到我們對於偶數項的輸出會使用2基底的分解法,對於奇數項的輸出採用8基底的分解法。這個做法充分利用了2基底與4基底擁有最少乘法數與加法數的特性。當使用了2基底的分解法後,偶數項的輸出如下所示。
![](/img/2/00b/b1a92cc9398890e60a61b5859dc5.jpg)
![](/img/7/426/5bbecef4ff34319a95dc93b17149.jpg)
![](/img/4/de3/d1aeb0e10f443fa4a09abb87dbdd.jpg)
![](/img/1/098/104c8450bff102125b125b456659.jpg)
![](/img/c/ddf/e67c9e7c84ebf103a180f80381e4.jpg)
以上式子就是2/8基底的FFT快速算法。在架構圖上可化為L型的蝴蝶運算架構,如下圖所示。
2-4-8基底
為了改進Radix 2/8在架構上的不規則性,我們在這裡做了一些修改,如下表.。此修改可讓架構更加規則,且所使用的加法器與乘法器數量更加減少,如下表所示。
N=8 | 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(Process Element),PE內部包含了2/8基底、2/4基底、2基底的運算,簡化過的信號處理流程與蝴蝶型架構圖可見下圖
![蝴蝶型架構圖 蝴蝶型架構圖](/img/b/616/nBnauMmMkdTMzQmY1ITO5UmZjV2YwY2Y3MGZ5YWMwYWZlRTO0UzY4YGO1I2LtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
4基底
基底的選擇越大會造成蝴蝶形架構更加複雜,控制電路也會複雜化。因此Shousheng He和Mats Torkelson在1996提出了一個2^2基底的FFT算法,利用旋轉因子的特性:
。而–j的乘法基本上只需要將被乘數的實部虛部對調,然後將虛部加上負號即可,這樣的負數乘法被定義為'簡單乘法',因此可以用很簡單的硬體架構來實現。利用上面的特性,22基底FFT能用串接的方式將旋轉因子以4為單位對DFT公式進行拆解,將蝴蝶形架構層數降到log4N,大幅減少複數乘法器的用量,而同時卻維持了2基底蝴蝶形架構的簡單性,在性能上獲得改進。2^2基底DIF FFT算法的拆解方法如下列公式所述:
![](/img/2/f52/647c81c7fba7ba9f89f278bcb000.jpg)
N點DFT公式:
![](/img/0/d6f/7abea4e0c5f5f319ebcb3603778e.jpg)
利用線性映射將n與k映射到三個維度上面
![](/img/1/f00/e60a6577e6cf5ca8ca5aca2b0ab5.jpg)
然後套用Common Factor Algorithm(CFA)
![](/img/a/e27/c6df04c704e89f6735d3a84089ac.jpg)
![](/img/1/aeb/2a96732e2fde0bb84f22cf00caf7.jpg)
而蝴蝶型架構會變成以下形式
![](/img/8/898/e40ba64178a96bb7d35d9860354d.jpg)
![](/img/8/b36/5013729b9af6999de6c75bc6acf6.jpg)
![](/img/6/1ff/ea9d1a66674ba393e61dcc3e0609.jpg)
![](/img/5/546/8fc5e652a8a47d59e01a877c2f72.jpg)
![](/img/e/aa9/d282d811acc261117d057837e21f.jpg)
![](/img/7/962/da94cc2df7d0f68fb27a8c1d683d.jpg)
如上述公式所示,原本的DFT公式會被拆解成多個
,而
又可分為BF2I與BF2II兩個層次結構,分別會對應到之後所介紹的兩種硬體架構。
![](/img/7/71d/09602889595381ee4e0d058b9e98.jpg)
![](/img/5/12a/f04b6d79639009d86de5f0341532.jpg)
一個16點的DFT公式經過一次上面所述之拆解之後可得下面的FFT架構
![16點FFT架構 16點FFT架構](/img/6/190/nBnauYTOxcTMiNGOmRWZ1gTY4MTO5gjY5YTNxUjM5kTZmBTZ1YGZykjMiNzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
可以看出上圖的架構保留了2基底的簡單架構,然而複數乘法卻降到每兩級才出現一次,也就是
次。而BF2I以及BF2II所對應的硬體架構下圖:
![](/img/5/0c5/4ae78289c1a51c31801e8ba1f715.jpg)
其中BF2II硬體單元中左下角的交叉電路就是用來處理-j的乘法。
一個256點的FFT架構可以由下面的硬體來實現:
![22-128 22-128](/img/1/e86/nBnauE2NwYTYmNmZ2EDZ5IWMyMmNxIDNyAjZlZWZwkTMxcTZkRWNlVzM0gzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
其中圖下方的為一7比特寬的計數器,而此架構的控制電路相當單純,只要將計數器的各個比特分別接上BF2I與BF2II單元即可。
下表將2基底、4基底與22基底算法做一比較,可以發現22基底算法所需要的乘法氣數量為2基底的一半,加法棄用量是4基底的一半,並維持一樣的存儲器用量和控制電路的簡單性。
乘法數 | 加法數 | 存儲器大小 | 控制電路 | |
---|---|---|---|---|
R2SDF | 2(log4N-1) | 4log4N | N-1 | 簡單 |
R4SDF | log4N -1 | 8log4N | N-1 | 中等 |
R2SDF | log4N -1 | 4log4N | N-1 | 簡單 |
8基底
如上所述,22算法是將旋轉因子
視為一個簡單乘法,進而由公式以及硬體上的化簡獲得硬體需求上的改進。而藉由相同的概念,Shousheng He和Mats Torkelson進一步將旋轉因子
的乘法化簡成一個簡單乘法,而化簡的方法將會在下面講解。
![](/img/7/85f/c622fa11fc116920d1950ddfb5b8.jpg)
![](/img/3/4ad/0a7cf904cddc76ac94d9b90ec4b4.jpg)
在2基數FFT算法中的基本概念是利用旋轉因子
的對稱性,4基數算法則是利用
的特性。但是我們會發在這些旋轉因子的對稱特性中出現。
![](/img/5/340/243b13fef24c27b93a2e7d0b69d4.jpg)
![](/img/e/0ed/7b16b932ed093b1594961070cfbf.jpg)
![](/img/c/48f/cfe1dee94687936c046dd791f1aa.jpg)
─並沒有被利用到。主要是因為
的乘法運算會讓整個FFT變得複雜,但是如果藉由近似的方法,我們便可以將此一運算化簡為12個加法。
![](/img/e/05c/9339916bf8cdc613babd53851774.jpg)
![](/img/5/467/e908d087a8b8ccc6a9db82851e44.jpg)
![](/img/d/0f3/a1d0653210595cb902c45b149575.jpg)
![](/img/5/bd3/d4f70e643d2af70636298dcff1fd.jpg)
![12adder_multi 12adder_multi](/img/7/e85/nBnauUjNxUDZzgzY5AzN2U2MzcTZlZmMxIDM2gzYxQWYjVTOmFTNyUGNxMzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
經由與
基底類似的推導,並用串接的方式將旋轉因子以8為單位對DFT公式進行拆解,
基底FFT算法進一步將複數乘法器的用量縮減到log8N,並同時維持硬體架構的簡單性。推導的方法與
基底相當類似。藉由這樣的方法,
基底能將乘法器的用量縮減到2基底的1/3,並同時維持一樣的存儲器用量以及控制電路的簡單性。
![](/img/e/0be/c0a020aa82c917c31612414fb188.jpg)
![](/img/e/0be/c0a020aa82c917c31612414fb188.jpg)
![](/img/e/0be/c0a020aa82c917c31612414fb188.jpg)
![](/img/e/0be/c0a020aa82c917c31612414fb188.jpg)