分裂基FFT算法教學(xué)課件

第4章快速傅里葉變換(FFT)

4.1引言4.2基2FFT算法4.3進(jìn)一步減少運(yùn)算量的措施4.4其他快速算法簡(jiǎn)介4.1引言

DFT是數(shù)字信號(hào)分析與處理中的一種重要變換。但直接計(jì)算DFT，當(dāng)N較大時(shí)，計(jì)算量太大，所以在快速傅里葉變換FFT(FastFourierTransform)出現(xiàn)以前，直接用DFT算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。直到1965年提出DFT的一種快速算法以后，情況才發(fā)生了根本的變化。

自從1965年庫(kù)利和圖基在《計(jì)算數(shù)學(xué)》雜志上發(fā)表了著名的《機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法》論文后，桑德—圖基等快速算法相繼出現(xiàn)，又經(jīng)人們進(jìn)行改進(jìn)，很快形成一套高效計(jì)算方法，這就是現(xiàn)在的快速傅里葉變換（FFT）。

這種算法使DFT的運(yùn)算效率提高了1~2個(gè)數(shù)量級(jí)，為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了條件，大大推動(dòng)了數(shù)字信號(hào)處理技術(shù)的發(fā)展。

人類的求知欲和科學(xué)的發(fā)展是永無(wú)止境的。多年來(lái)，人們繼續(xù)尋求更快、更靈活的好算法。1984年，法國(guó)的杜哈梅爾(P.Dohamel)和霍爾曼(H.Hollmann)提出的分裂基快速算法，使運(yùn)算效率進(jìn)一步提高。本章主要討論基2FFT算法。

4.2基2FFT算法4.2.1直接計(jì)算DFT的特點(diǎn)及減少運(yùn)算量的基本途徑有限長(zhǎng)序列x(n)的N點(diǎn)DFT為

考慮x(n)為復(fù)數(shù)序列的一般情況，對(duì)某一個(gè)k值，直接按(4.2.1)式計(jì)算X(k)的1個(gè)值需要N次復(fù)數(shù)乘法和(N－1)次復(fù)數(shù)加法。因此，計(jì)算X(k)的所有N個(gè)值，共需N2次復(fù)數(shù)乘法和N(N－1)次復(fù)數(shù)加法運(yùn)算。（4.2.1）

當(dāng)

時(shí)，N(N－1)≈N2。由上述可見，N點(diǎn)DFT的乘法和加法運(yùn)算次數(shù)均為N2。當(dāng)N較大時(shí)，運(yùn)算量相當(dāng)可觀。例如N=1024時(shí)，N2=1048576。這對(duì)于實(shí)時(shí)信號(hào)處理來(lái)說(shuō)，必將對(duì)處理設(shè)備的計(jì)算速度提出難以實(shí)現(xiàn)的要求。所以，必須減少其運(yùn)算量，才能使DFT在各種科學(xué)和工程計(jì)算中得到應(yīng)用。

如前所述，N點(diǎn)DFT的復(fù)乘法次數(shù)等于N2。顯然，把N點(diǎn)DFT分解為幾個(gè)較短的DFT，可使乘法次數(shù)大大減少。

FFT算法就是不斷地把長(zhǎng)序列的DFT分解成幾個(gè)短序列的DFT，并利用的周期性和對(duì)稱性來(lái)減少DFT的運(yùn)算次數(shù)。算法最簡(jiǎn)單最常用的是基2FFT。其對(duì)稱性表現(xiàn)為

(4.2.3a)

或者

(4.2.3b)

另外，旋轉(zhuǎn)因子具有明顯的周期性和對(duì)稱性。其周期性表現(xiàn)為4.2.2時(shí)域抽取法基2FFT基本原理

基2FFT算法分為兩類：時(shí)域抽取法FFT(Decimation

InTimeFFT，簡(jiǎn)稱DIT－FFT)；頻域抽取法FFT(DecimationInFrequencyFFT，簡(jiǎn)稱DIF－FFT)。本節(jié)介紹DIT－FFT算法。

設(shè)序列x(n)的長(zhǎng)度為N，且滿足N=2M，M為自然數(shù)。按n的奇偶把x(n)分解為兩個(gè)N/2點(diǎn)的子序列

則x(n)的DFT為因?yàn)樗云渲校?(k)和X2(k)分別為x1(r)和x2(r)的N/2點(diǎn)DFT,即由于X1(k)和X2(k)均以N/2為周期，且，因此X(k)又可表示為(4.2.5)

(4.2.6)

這樣，就將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT和(4.2.7)式以及(4.2.8)式的運(yùn)算。(4.2.7)和(4.2.8)式的運(yùn)算可用圖4.2.1所示的流圖符號(hào)表示，稱為蝶形運(yùn)算符號(hào)。采用這種圖示法，經(jīng)過(guò)一次奇偶抽取分解后，N點(diǎn)DFT運(yùn)算圖可以用圖4.2.2表示。圖中，N=23=8，X(0)~X(3)由(4.2.7)式給出，而X(4)~X(7)則由(4.2.8)式給出。(4.2.7)

(4.2.8)

圖4.2.1蝶形運(yùn)算符號(hào)偶數(shù)點(diǎn)的N/2DFT奇數(shù)點(diǎn)的N/2DFT序列DFT的N/2個(gè)點(diǎn)序列DFT的后N/2個(gè)點(diǎn)圖4.2.28點(diǎn)DFT一次時(shí)域抽取分解運(yùn)算流圖

由圖4.2.1可見，要完成一個(gè)蝶形運(yùn)算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法運(yùn)算。由圖4.2.2容易看出，經(jīng)過(guò)一次分解后，計(jì)算1個(gè)N點(diǎn)DFT共需要計(jì)算兩個(gè)N/2點(diǎn)DFT和N/2個(gè)蝶形運(yùn)算。而計(jì)算一個(gè)N/2點(diǎn)DFT需要(N/2)2次復(fù)數(shù)乘法和N/2(N/2－1)次復(fù)數(shù)加法。所以，按圖4.2.2計(jì)算N點(diǎn)DFT時(shí)，總共需要的復(fù)數(shù)乘法次數(shù)為復(fù)數(shù)加法次數(shù)為

由此可見，僅僅經(jīng)過(guò)一次分解，就使運(yùn)算量減少近一半。既然這樣分解對(duì)減少DFT的運(yùn)算量是有效的，且N=2M,N/2仍然是偶數(shù)，故可以對(duì)N/2點(diǎn)DFT再作進(jìn)一步分解。

與第一次分解相同，將x1(r)按奇偶分解成兩個(gè)N/4點(diǎn)的子序列x3(l)和x4(l)，即X1(k)又可表示為(4.2.9)式中

同理，由X3(k)和X4(k)的周期性和的對(duì)稱性最后得到：

(4.2.10)

用同樣的方法可計(jì)算出

(4.2.11)其中：

這樣，經(jīng)過(guò)第二次分解，又將N/2點(diǎn)DFT分解為2個(gè)N/4點(diǎn)DFT和(4.2.10)式或(4.2.11)式所示的N/4個(gè)蝶形運(yùn)算，如圖4.2.3所示。依次類推，經(jīng)過(guò)M次分解，最后將N點(diǎn)DFT分解成N個(gè)1點(diǎn)DFT和M級(jí)蝶形運(yùn)算，而1點(diǎn)DFT就是時(shí)域序列本身。一個(gè)完整的8點(diǎn)DIT－FFT運(yùn)算流圖如圖4.2.4所示。圖中用到關(guān)系式。圖中輸入序列不是順序排列，但后面會(huì)看到，其排列是有規(guī)律的。圖中的數(shù)組A用于存放輸入序列和每級(jí)運(yùn)算結(jié)果。圖4.2.38點(diǎn)DFT二次時(shí)域抽取分解運(yùn)算流圖圖4.2.48點(diǎn)DIT-FFT運(yùn)算流圖4.2.3DIT-FFT算法與直接計(jì)算DFT運(yùn)算量的比較

由DIT-FFT算法的分解過(guò)程及圖4.2.4可見，當(dāng)N=2M

時(shí)，其運(yùn)算流圖應(yīng)有M級(jí)蝶形，每一級(jí)都由N/2個(gè)蝶形運(yùn)算構(gòu)成。因此，每一級(jí)運(yùn)算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個(gè)蝶形需要兩次復(fù)數(shù)加法)。所以，M級(jí)運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為復(fù)數(shù)加次數(shù)為而直接計(jì)算DFT的復(fù)數(shù)乘為N2次，復(fù)數(shù)加為N(N－1)次。當(dāng)N>>1時(shí)，N2≥

(N/2)log2N，所以，DIT-FFT算法比直接計(jì)算DFT的運(yùn)算次數(shù)大大減少。例如，N=210=1024時(shí)，

這樣，就使運(yùn)算效率提高200多倍。圖4.2.5為FFT算法和直接計(jì)算DFT所需復(fù)數(shù)乘法次數(shù)CM與變換點(diǎn)數(shù)N的關(guān)系曲線。由此圖更加直觀地看出FFT算法的優(yōu)越性，顯然，N越大時(shí)，優(yōu)越性就越明顯。

圖4.2.5DIT-FFT算法與直接計(jì)算DFT所需復(fù)數(shù)乘法次數(shù)的比較曲線4.2.4DIT-FFT的運(yùn)算規(guī)律及蝶形畫法

1．原位計(jì)算由圖4.2.4可以看出，DIT-FFT的運(yùn)算過(guò)程很有規(guī)律。

N=2M點(diǎn)的FFT共進(jìn)行M級(jí)運(yùn)算，每級(jí)由N/2個(gè)蝶形運(yùn)算組成。同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)結(jié)點(diǎn)又同在一條水平線上，這就意味著計(jì)算完一個(gè)蝶形后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元(數(shù)組元素)。這樣，經(jīng)過(guò)M級(jí)運(yùn)算后，原來(lái)存放輸入序列數(shù)據(jù)的N個(gè)存儲(chǔ)單元(數(shù)組A)中便依次存放X(k)的N個(gè)值。8點(diǎn)DIT-FFT運(yùn)算流圖的畫法

2．旋轉(zhuǎn)因子的變化規(guī)律

如上所述，N點(diǎn)DIT-FFT運(yùn)算流圖中，每級(jí)都有N/2個(gè)蝶形。每個(gè)蝶形都要乘以因子，稱其為旋轉(zhuǎn)因子，p為旋轉(zhuǎn)因子的指數(shù)。但各級(jí)的旋轉(zhuǎn)因子都有所不同。為了畫出蝶形圖，應(yīng)先找出旋轉(zhuǎn)因子與運(yùn)算級(jí)數(shù)的關(guān)系。用L表示從左到右的運(yùn)算級(jí)數(shù)(L=1，2，…M)。觀察圖4.2.4不難發(fā)現(xiàn)，第L級(jí)共有2L－1個(gè)不同的旋轉(zhuǎn)因子。N=23=8時(shí)的各級(jí)旋轉(zhuǎn)因子表示如下：對(duì)N=2M的一般情況，第L級(jí)的旋轉(zhuǎn)因子為：因?yàn)?/p>

所以

（4.2.12）（4.2.13）這樣，就可按(4.2.12)和(4.2.13)式確定第L級(jí)運(yùn)算的旋轉(zhuǎn)因子。

3．序列的倒序DIT-FFT算法的輸入序列的排序看起來(lái)似乎很亂，但仔細(xì)分析就會(huì)發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于N=2M，因此順序數(shù)可用M位二進(jìn)制數(shù)(nM－1

nM－2…n1n0)表示。表4.2.1列出了N=8時(shí)以二進(jìn)制數(shù)表示的順序數(shù)和倒序數(shù)，由表顯而易見，只要將順序數(shù)(n2n1n0)的二進(jìn)制位倒置，則得對(duì)應(yīng)的二進(jìn)制倒序值(n0n1n2)表4.2.1順序和倒序二進(jìn)制數(shù)對(duì)照表4.2.5頻域抽取法FFT(DIF-FFT)

在基2FFT算法中，頻域抽取法FFT也是一種常用的快速算法，簡(jiǎn)稱DTF-FFT。

設(shè)序列x(n)長(zhǎng)度為N=2M，首先將x(n)前后對(duì)半分開，得到兩個(gè)子序列，其DFT可表示為如下形式：式中

將X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)(k=2m,m=0,1,…,N/2－1)時(shí)

（4.2.14）當(dāng)k取奇數(shù)(k=2m+1,m=0,1,…,N/2－1)時(shí)，令(4.2.15)

將x1(n)和x2(n)分別代入(4.2.14)和(4.2.15)式，可得

(4.2.16)式表明，X(k)按奇偶k值分為兩組，其偶數(shù)組是x1(n)的N/2點(diǎn)DFT，奇數(shù)組則是x2(n)的N/2點(diǎn)DFT。x1(n)、x2(n)和x(n)之間的關(guān)系也可用圖4.2.10所示的蝶形運(yùn)算流圖符號(hào)表示。圖4.2.11表示N=8時(shí)第一次分解的運(yùn)算流圖。（4.2.16）圖4.2.10DTF－FFT蝶形運(yùn)算流圖符號(hào)序列的前半部分序列的后半部分圖4.2.11DIF-FFT第一次分解運(yùn)算流圖（N=8）由于N=2M，N/2仍然是偶數(shù)，繼續(xù)將N/2點(diǎn)DFT分成偶數(shù)組和奇數(shù)組，這樣每個(gè)N/2點(diǎn)DFT又可由兩個(gè)N/4

點(diǎn)DFT形成，其輸入序列分別是x1(n)和x2(n)按上下對(duì)半分開形成的四個(gè)子序列。圖4.2.12示出了N=8時(shí)第二次分解運(yùn)算流圖。以這種方式分解下去，經(jīng)過(guò)M－1次分解，最后分解為2M－1個(gè)兩點(diǎn)DFT，兩點(diǎn)DFT就是一個(gè)基本蝶形運(yùn)算流圖。當(dāng)N=8，經(jīng)兩次分解，便分解為四個(gè)兩點(diǎn)DFT。N=8

的完整DIF-FFT運(yùn)算流圖如圖4.2.13所示。

圖4.2.12DIF-FFT第二次分解運(yùn)算流圖（N=8）圖4.2.13DIF-FFT運(yùn)算流圖（N=8）這種算法是對(duì)X(k)進(jìn)行奇偶抽取分解的結(jié)果，所以稱之為頻域抽取法FFT。觀察圖4.2.13可知，DIF-FFT算法與DIT-TTF算法類似，共有M級(jí)運(yùn)算，每級(jí)共有N/2個(gè)蝶形運(yùn)算，所以兩種算法的運(yùn)算次數(shù)亦相同。不同的是DIF-FFT算法輸入序列為自然順序，而輸出為倒序排列。因此，M級(jí)運(yùn)算完后，要對(duì)輸出數(shù)據(jù)進(jìn)行排序才能得到自然順序的X(k)。另外，蝶形運(yùn)算略有不同，DIT-FFT蝶形先乘后加(減)，而DIF-FFT蝶形先加(減)后相乘。

4.2.6IDFT的高效算法

上述FFT算法流圖也可以用于計(jì)算IDFT。比較DFT和IDFT的運(yùn)算公式：

只要將DFT運(yùn)算式中的系數(shù)

改為，最后乘以

1/N，就是IDFT運(yùn)算公式。所以，只要將上述的DIT-FFT與DIF-FFT算法中的旋轉(zhuǎn)因子改為，最后的輸出再乘以1/N就可以用來(lái)計(jì)算IDFT。只是現(xiàn)在流圖的輸入是X(k)，輸出就是x(n)。因此，原來(lái)的DIT-FFT改為IFFT后，稱為DIF-IFFT

更合適；DIF-FFT改為IFFT后,應(yīng)稱為DIT-IFFT。

如果希望直接調(diào)用FFT子程序計(jì)算IFFT，則可用下面的方法：由于

所以，可以先將X(k)取復(fù)共軛，然后直接調(diào)用FFT子程序，最后取復(fù)共軛并乘以1/N得到序列x(n)。這種方法雖然用了兩次取共軛運(yùn)算，但可以與FFT共用同一子程序，因而用起來(lái)很方便。圖4.2.48點(diǎn)DIT-FFT運(yùn)算流圖L=1L=2L=34.3進(jìn)一步減少運(yùn)算量的措施4.3.1多類蝶形單元運(yùn)算

由DIT-FFT運(yùn)算流圖已得出結(jié)論，N=2M點(diǎn)FFT共需要MN/2次復(fù)數(shù)乘法。由(4.2.12)式，當(dāng)L=1時(shí)，只有一種旋轉(zhuǎn)因子所以，第一級(jí)不需要乘法運(yùn)算。當(dāng)L=2時(shí)，共有兩個(gè)旋轉(zhuǎn)因子：和，因此，第二級(jí)也不需要乘法運(yùn)算。在DFT中，又稱其值為±1和±j的旋轉(zhuǎn)因子為無(wú)關(guān)緊要的旋轉(zhuǎn)因子如，，等。

綜上所述，先除去第一、二兩級(jí)后，所需復(fù)數(shù)乘法次數(shù)應(yīng)是

進(jìn)一步考慮各級(jí)中的無(wú)關(guān)緊要旋轉(zhuǎn)因子。當(dāng)L=3時(shí)，有兩個(gè)無(wú)關(guān)緊要的旋轉(zhuǎn)因子和，因?yàn)橥恍D(zhuǎn)因子對(duì)應(yīng)著2M－L=N/2L個(gè)碟形運(yùn)算，所以第三級(jí)共有2·N/23=N/4個(gè)碟形不需要復(fù)數(shù)乘法運(yùn)算。依此類推，當(dāng)L≥3時(shí)，第L級(jí)的2個(gè)無(wú)關(guān)緊要的旋轉(zhuǎn)因子減少?gòu)?fù)數(shù)乘法的次數(shù)為2·N/2L=N/2L－1。這樣，從L=3至L=M共減少?gòu)?fù)數(shù)乘法次數(shù)為(4.3.1)因此，DIT-FFT的復(fù)乘次數(shù)降至

下面再討論FFT中特殊的復(fù)數(shù)運(yùn)算，以便進(jìn)一步減少?gòu)?fù)數(shù)乘法次數(shù)。一般實(shí)現(xiàn)一次復(fù)數(shù)乘法運(yùn)算需要四次實(shí)數(shù)乘，兩次實(shí)數(shù)加。但對(duì)這一特殊復(fù)數(shù)，任一復(fù)數(shù)(x+jy)與其相乘時(shí)，(4.3.2)（4.3.3）只需要兩次實(shí)數(shù)加和兩次實(shí)數(shù)乘就可實(shí)現(xiàn)。這樣，對(duì)應(yīng)的每個(gè)蝶形節(jié)省兩次實(shí)數(shù)乘。

在DIT-FFT運(yùn)算流圖中，從L=3至L=M級(jí)，每級(jí)都包含旋轉(zhuǎn)因子，第L級(jí)中，對(duì)應(yīng)N/2L個(gè)蝶形運(yùn)算。因此從第三級(jí)至最后一級(jí)，旋轉(zhuǎn)因子節(jié)省的實(shí)數(shù)乘次數(shù)與(4.3.2)式相同。所以從實(shí)數(shù)乘運(yùn)算考慮，計(jì)算N=2M點(diǎn)DIT-FFT所需實(shí)數(shù)乘法次數(shù)為(4.3.4)

在基2FFT程序中，若包含了所有旋轉(zhuǎn)因子，則稱該算法為一類碟形單元運(yùn)算；若去掉的旋轉(zhuǎn)因子，則稱之為二類碟形單元運(yùn)算；若再去掉的旋轉(zhuǎn)因子，則稱為三類碟形單元運(yùn)算；若再判斷處理，則稱之為四類碟形運(yùn)算。我們將后三種運(yùn)算稱為多類碟形單元運(yùn)算。顯然，碟形單元類型越多，編程就越復(fù)雜，但當(dāng)N較大時(shí)，乘法運(yùn)算的減少量是相當(dāng)可觀的。例如，N=4096時(shí)，三類碟形單元運(yùn)算的乘法次數(shù)為一類碟形單元運(yùn)算的75%。4.3.2旋轉(zhuǎn)因子的生成

在FFT運(yùn)算中，旋轉(zhuǎn)因子，求正弦和余弦函數(shù)值的計(jì)算量是很大的。所以編程時(shí)，產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運(yùn)算速度。一種方法是在每級(jí)運(yùn)算中直接產(chǎn)生；另一種方法是在FFT程序開始前預(yù)先計(jì)算出，m=0，1，…，N/2－1，存放在數(shù)組中，作為旋轉(zhuǎn)因子表，在程序執(zhí)行過(guò)程中直接查表得到所需旋轉(zhuǎn)因子值，不再計(jì)算。這樣使運(yùn)算速度大大提高，其不足之處是占用內(nèi)存較多。4.3.3實(shí)序列的FFT算法

在實(shí)際工作中，數(shù)據(jù)x(n)常常是實(shí)數(shù)序列。如果直接按FFT運(yùn)算流圖計(jì)算，就是把x(n)看成一個(gè)虛部為零的復(fù)序列進(jìn)行計(jì)算，這就增加了存儲(chǔ)量和運(yùn)算時(shí)間。處理該問(wèn)題的方法有兩種。早期提出的方法是用一個(gè)N點(diǎn)FFT計(jì)算兩個(gè)N點(diǎn)實(shí)序列的FFT，一個(gè)實(shí)序列作為x(n)的實(shí)部，另一個(gè)作為虛部，計(jì)算完FFT后，根據(jù)DFT的共軛對(duì)稱性，由輸出X(k)分別得到兩個(gè)實(shí)序列的N點(diǎn)DFT（例題3.2.2）。第二種方法是用N/2點(diǎn)FFT計(jì)算一個(gè)N點(diǎn)實(shí)序列的DFT。下面簡(jiǎn)要介紹第二種方法。

設(shè)x(n)為N點(diǎn)實(shí)序列，取x(n)的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分別作為新構(gòu)造序列y(n)的實(shí)部和虛部，即

對(duì)y(n)進(jìn)行N/2點(diǎn)FFT，輸出Y(k)，則

根據(jù)DIT-FFT的思想及式(4.2.7)和(4.2.8)，可得到X(k)的前個(gè)值：

式中，。由于x(n)為實(shí)序列，因此X(k)具有共軛對(duì)稱性，X(k)的后N/2點(diǎn)的值為（4.3.5）

計(jì)算N/2點(diǎn)FFT的復(fù)乘次數(shù)為N(M-1)/4，計(jì)算式(4.3.5)的復(fù)乘次數(shù)為N/2，所以用這種算法,計(jì)算X(k)所需復(fù)數(shù)乘法次數(shù)為。相對(duì)一般的N點(diǎn)FFT算法，上述算法的運(yùn)算效率為

當(dāng)N=2M=210時(shí)，η=20/11，運(yùn)算速度提高近1倍。4.4其他快速算法簡(jiǎn)介

快速傅里葉變換算法是信號(hào)處理領(lǐng)域重要的研究課題。本章僅介紹算法最簡(jiǎn)單、編程最容易的基2FFT算法原理及其編程思想，使讀者建立快速傅里葉變換的基本概念，了解研究FFT算法的主要途徑和編程思路。例如，分裂基FFT算法、離散哈特萊變換(DHT)、基4FFT、基8FFT、基rFFT、混合基FFT，以及進(jìn)一步減少運(yùn)算量的途徑等內(nèi)容，對(duì)研究新的快速算法都是很有用的。本節(jié)簡(jiǎn)要介紹其他幾種快速算法的運(yùn)算量及其主要特點(diǎn)，以便讀者選擇快速算法時(shí)參考。

從理論上講，不同基數(shù)的FFT算法的運(yùn)算效率不同，實(shí)際中最常用的是基2FFT、基4FFT、分裂基FFT和DHT。為