第五章快速傅里葉變換（FFT）5.1引言

5.2離散傅里葉變換直接計(jì)算的難點(diǎn)及其解決途徑

5.3按時(shí)間抽選的快速傅里葉變換算法

5.4按頻率抽選的快速傅里葉變換算法

5.5快速傅里葉反變換(IFFT)算法

5.1引言

通過(guò)一至三章的討論，我們知道，離散傅里葉變換（DFT）由于其在頻率域也已離散化成有限長(zhǎng)序列這一重要突破，使之不僅具有至關(guān)重要的理論意義，更具有了十分關(guān)鍵的實(shí)用價(jià)值。如在信號(hào)的頻譜分析中，我們即可直接用它完成有關(guān)任務(wù)，因?yàn)樾盘?hào)序列的離散傅里葉變換本身就是信號(hào)頻譜的實(shí)際樣本。尤其重要的是，在一系列系統(tǒng)分析、設(shè)計(jì)及相應(yīng)的工程實(shí)踐中，經(jīng)常借助離散傅里葉變換實(shí)現(xiàn)多方面的實(shí)際需求。但是，需要指出的是，盡管離散傅里葉變換實(shí)現(xiàn)了十分重要的離散化計(jì)算，可它仍然存在著實(shí)際計(jì)算量過(guò)大的固有缺陷，因而在相當(dāng)長(zhǎng)的時(shí)間里，雖然可以利用計(jì)算機(jī)等彌補(bǔ)許多不足，但還是阻礙了該變換的具體使用。

5.2離散傅里葉變換直接計(jì)算的難點(diǎn)及其解決途徑

快速傅里葉變換（FFT）并不是一種新的變換，它只是離散傅里葉變換的一種快速實(shí)現(xiàn)方法。在具體介紹此快速算法之前，有必要先討論一下直接計(jì)算離散傅里葉變換的情況。我們知道，離散傅里葉變換的表達(dá)式為k=0,1,…,N-1（5－1）

式中的WN=e-j(2π/N)。

離散傅里葉反變換（IDFT）為

n=0,1,…,N-1（5－2）

式（5－1）和式（5－2）中的x(n)和X(k)均可以是復(fù)數(shù)。兩式的差別除了WN的冪的符號(hào)不同之外，僅差一個(gè)比例因子1/N。因此只要對(duì)式（5－1）的計(jì)算過(guò)程稍作修正，將同樣適用于式（5－2）的具體計(jì)算。為了說(shuō)明高效計(jì)算方案的實(shí)際價(jià)值,這里先討論直接計(jì)算離散傅里葉變換的情況。考慮到x(n)可能是復(fù)數(shù),我們將式(5－1)寫(xiě)成更具一般意義的形式,即k=0,1,…,N-1(5－3)大多數(shù)提高離散傅里葉變換計(jì)算效率的方法都是基于的兩個(gè)特性：

(1)對(duì)稱(chēng)性

(2)周期性

由此可以得出

于是，利用上述特性，在離散傅里葉變換運(yùn)算中有些項(xiàng)就可以合并，特別是藉此還可以將較長(zhǎng)序列的離散傅里葉變換不斷分解成較短序列的離散傅里葉變換。我們知道，離散傅里葉變換的運(yùn)算量與N2成正比，N越小，顯然越有利?？焖俑道锶~變換本質(zhì)上就是連續(xù)將一個(gè)長(zhǎng)序列的離散傅里葉變換運(yùn)算分解為兩個(gè)短序列來(lái)計(jì)算，直到最后形成的短序列在計(jì)算其離散傅里葉變換時(shí)已不需要或幾乎不需要乘法運(yùn)算為止。

5.3按時(shí)間抽選的快速傅里葉變換算法

在時(shí)間域?qū)⑿蛄衳(n)分解成逐次變小的子序列的方法通常稱(chēng)為時(shí)間分解或時(shí)間抽選法。時(shí)間分解或時(shí)間抽選法用于N=2v（v為整數(shù)）的場(chǎng)合時(shí)，更便于用所謂基-2的形式具體實(shí)現(xiàn)。設(shè)N=2v,此時(shí)的N為偶數(shù)，可以將x(n)分解成兩個(gè)N/2點(diǎn)的序列來(lái)計(jì)算X(k)。其中一個(gè)序列由x(n)的偶數(shù)點(diǎn)組成，另一個(gè)則由x(n)的奇數(shù)點(diǎn)組成。由于k=0,1,…,N-1(5－4)

將x(n)分解成偶數(shù)點(diǎn)及奇數(shù)點(diǎn)后可得

此時(shí)作變量替換，當(dāng)n為偶數(shù)時(shí)令n=2r，n為奇數(shù)時(shí)令n=2r+1，

則

k=0,1,…,N-1(5－5)由于

，

因此式（5－5）可以改寫(xiě)成

(5－6)

式（5－6）中的每個(gè)求和式都可以看作是N/2點(diǎn)的離散傅里葉變換。其中第一個(gè)求和式為原序列的偶數(shù)點(diǎn)的N/2點(diǎn)的離散傅里葉變換，第二個(gè)求和式則為原序列奇數(shù)點(diǎn)的N/2點(diǎn)的離散傅里葉變換。雖然標(biāo)號(hào)k=0,1,…,N-1，但因G(k)與H(k)均是周期為N/2的周期序列，所以每個(gè)求和式實(shí)際僅需對(duì)間的k計(jì)算即可。在計(jì)算完與求和式對(duì)應(yīng)的兩個(gè)離散傅里葉變換之后，即可如式（5－6）那樣將它們合并成N點(diǎn)的離散傅里葉變換。圖5.1列出了N=8的信號(hào)序列按式（5－6）計(jì)算X(k)時(shí)的有關(guān)計(jì)算。圖中我們引用了第四章表示差分方程時(shí)所用的信號(hào)流圖規(guī)則，即一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)值等于進(jìn)入該節(jié)點(diǎn)的所有支路的輸出和。當(dāng)支路上未標(biāo)加權(quán)系數(shù)時(shí)，我們假設(shè)該支路的傳輸比為1，其他支路的傳輸比則為WN的冪次不同的指數(shù)值。圖5.1

N點(diǎn)的DFT分解成兩個(gè)點(diǎn)DFT計(jì)算的時(shí)間抽選流圖(N=8)

如前所述，利用直接算法，整個(gè)X(k)的計(jì)算需作N2次復(fù)數(shù)乘法及N(N-1)次復(fù)數(shù)加法。事實(shí)上，當(dāng)N較大時(shí)，復(fù)加次數(shù)通常也以N2表示。而按式（5－6）及圖5.1所示的流圖分成兩個(gè)N/2點(diǎn)的離散傅里葉變換計(jì)算時(shí)，一個(gè)N/2點(diǎn)的離散傅時(shí)葉變換要作（N/2）2次復(fù)數(shù)乘和接近2（N/2）2次復(fù)數(shù)加，兩個(gè)N/2點(diǎn)的離散傅里葉變換則需作2（N/2）2次復(fù)數(shù)乘及接近2（N/2）2次復(fù)數(shù)加，其后尚需將兩者合并，即還要作N次復(fù)數(shù)乘法之后再進(jìn)行N次復(fù)數(shù)加法,因而實(shí)際需作N＋2（N/2）2次也就是次復(fù)數(shù)乘法及幾乎同樣多次復(fù)數(shù)加法?？梢宰C明，當(dāng)N>2時(shí),顯然小于N2。如果N/2還是偶數(shù)（N是2的冪指數(shù)時(shí)通常都是這樣），我們還可以將式（5－6）中的兩個(gè)和式再分解成N/4點(diǎn)的離散傅里葉變換的形式，然后再將這兩個(gè)變換合并成N/2點(diǎn)的離散傅里葉變換。于是，

式（5－6）中的

可以表示成

(5－7)

用式（5－7）計(jì)算圖5.1所示的4點(diǎn)離散傅里葉變換時(shí)，顯然可以按圖5.2那樣具體進(jìn)行。另一半4點(diǎn)離散傅里葉變換H(k)的計(jì)算與此完全一樣，將它們一起畫(huà)入圖5.1，就可得到圖5.3所示的形式。需要說(shuō)明的是，這里也利用了的條件。

圖5.2以?xún)蓚€(gè)點(diǎn)的DFT來(lái)實(shí)現(xiàn)G(k)計(jì)算的流圖

圖5.3將圖5.2代入圖5.1的結(jié)果

討論至此，我們已經(jīng)把8點(diǎn)的離散傅里葉變換簡(jiǎn)化成僅需計(jì)算2點(diǎn)的離散傅里葉變換了。例如由X(0)與X(4)構(gòu)成的2點(diǎn)離散傅里葉變換可以由下式表示：

(5－8)圖5.4就是其具體流圖。將圖5.4的計(jì)算畫(huà)入圖5.3，就可得到圖5.5的計(jì)算8點(diǎn)離散傅里葉變換的完整流圖。

圖5.4

2點(diǎn)DFT的流圖

圖

5.5一個(gè)時(shí)間抽選的8點(diǎn)DFT計(jì)算流圖

對(duì)于N=2v且v大于3的情況，我們可以將式（5－7）中的N/4點(diǎn)變換再分解成N/8點(diǎn)變換，并繼續(xù)分解下去直到僅剩下2點(diǎn)的離散傅里葉變換為止。這時(shí)需作v級(jí)這樣的計(jì)算（N=8時(shí)則如圖5.5所示，需作3級(jí)計(jì)算），而v=lbN。前面我們已經(jīng)知道，將N點(diǎn)變換分解成兩個(gè)N/2點(diǎn)變換后，所需的復(fù)數(shù)乘法與加法次數(shù)同為N+2(N/2)2。在N/2點(diǎn)變換分解成N/4點(diǎn)變換時(shí)，因（N/2）2被替代，所以，此時(shí)整個(gè)計(jì)算需要次復(fù)數(shù)乘法和加法。如果N=2v，則最多可以分解v=lbN次。于是在全部分解之后，復(fù)數(shù)乘法和加法的次數(shù)等于NlbN。圖5.5也表明，在計(jì)算傳輸比為的支路數(shù)目時(shí)，每一級(jí)共有N次復(fù)數(shù)乘法和加法。由于總共有l(wèi)bN級(jí)，因此總的將有NlbN次復(fù)數(shù)乘法和加法。N較大時(shí)，NlbN<<N2,這就是能使計(jì)算量顯著減少的主要原因。例如N=32時(shí)，v=5，復(fù)數(shù)乘法與加法各為160次，而原先需作N2=1024次。接著可看到，利用的對(duì)稱(chēng)性及周期性，還可以使計(jì)算量進(jìn)一步減少。5.3.1原位計(jì)算在計(jì)算諸如圖5.5等流圖時(shí)，一般來(lái)說(shuō)，可以用兩列復(fù)數(shù)寄存器具體進(jìn)行，其中一列用以給計(jì)算提供數(shù)據(jù)，另一列則用以寄存計(jì)算結(jié)果。為了討論方便，我們?cè)O(shè)Xm(l)表示所計(jì)算的第m+1級(jí)的輸入復(fù)序列。這里的l=0,1,…,N-1，表示寄存器序號(hào)；m=0,1,…,v-1，表示第1,2,…,v級(jí)。于是，對(duì)于圖5.5中的第1級(jí)輸入復(fù)序列將為（5－9）

在圖5.5中，我們不難看出，其基本運(yùn)算實(shí)際上都是由圖5.6所示的網(wǎng)絡(luò)實(shí)現(xiàn)的。由于這種流圖狀如蝴蝶，因此又將其稱(chēng)作蝶形計(jì)算（ButterflyComputation）。由此可得第m+1級(jí)的輸出與其輸入的關(guān)系為

(5－10)上式的乘法次數(shù)實(shí)際還可減少一半，

這是因?yàn)?/p>

所以式（5－10）可以表示成

（5－11）

相應(yīng)地，

圖5.6也可改成圖5.7所示的形式。

圖5.6圖5.5中的基本蝶形計(jì)算流圖

圖5.7僅需一次復(fù)數(shù)乘法的簡(jiǎn)化蝶形計(jì)算流圖

由于每一級(jí)具有N/2個(gè)類(lèi)似于圖5.7所示的蝶形，現(xiàn)在共有l(wèi)bN級(jí)，因此總的乘法次數(shù)應(yīng)為(N/2)lbN次，而不再是圖5.5所示的NlbN次。用圖5.7的基本流圖替代圖5.6那樣的蝶形，可以將圖5.5改畫(huà)成圖5.8所示的形式。總的復(fù)數(shù)乘法次數(shù)同樣可從該圖中得到，而總的復(fù)數(shù)加法次數(shù)仍為NlbN次未變。從圖5.7和5.8中可以清楚地看到，第m列的Xm(p)和Xm(q)經(jīng)蝶形運(yùn)算后在第m+1列中的節(jié)點(diǎn)序號(hào)是不變的，即Xm+1(p)中的p與Xm+1(q)中的q仍是Xm(p)中的p值與Xm(q)中的q值。并且，蝶形運(yùn)算自成體系，即Xm+1(p)只與Xm(p)和Xm(q)有關(guān)，Xm+1(q)也僅與這兩者有關(guān)，而與別的節(jié)點(diǎn)值無(wú)關(guān)。與之同時(shí)，Xm(p)和Xm(q)也不再參與別的蝶形的運(yùn)算。于是，我們就有可能把計(jì)算所得的結(jié)果Xm+1(p)和Xm+1(q)重新置于計(jì)算之前的Xm(p)和Xm(q)所在的存儲(chǔ)單元之中，而不必另設(shè)新的寄存器和新的地址來(lái)存儲(chǔ)計(jì)算結(jié)果，這就是原位計(jì)算稱(chēng)謂的由來(lái)。原位計(jì)算所需的存儲(chǔ)單元僅等于給定數(shù)據(jù)所需的單元數(shù)，無(wú)需另設(shè)存放計(jì)算結(jié)果的單元。圖5.8利用圖5.7的蝶形構(gòu)成的8點(diǎn)DFT流圖

5.3.2位序的顛倒和規(guī)律在按奇、偶數(shù)抽選構(gòu)成的圖5.5和圖5.8的流圖中，輸入數(shù)據(jù)顯然已不再按序列的自然順序排列，而是需按倒置的次序寄存。我們還專(zhuān)門(mén)把此稱(chēng)為倒位序寄存器。不過(guò)這種因抽選奇、偶數(shù)造成的倒位序情況實(shí)際上是有一定規(guī)律可循的。為了說(shuō)明倒位序及其規(guī)律的含義，我們?nèi)钥捎靡恢痹谟懻摰?點(diǎn)流圖為例，此時(shí)如果將式（5－9）寫(xiě)成二進(jìn)制的形式，就可得

（5－12）

如果n2n1n0是序列x(n)的標(biāo)號(hào)的二進(jìn)制表示，則序列值x(n2n1n0)應(yīng)存放在數(shù)列X0(n0n1n2)的位置。這就是說(shuō)，確定x(n2n1n0)在輸入數(shù)列的位置時(shí)，我們必須將標(biāo)號(hào)的位序倒置。為了更直觀地看出原位計(jì)算需要倒置的原因，我們不妨回顧一下由圖5.1得到圖5.5的過(guò)程。序列x(n)首先分成偶數(shù)樣本和奇數(shù)樣本，偶數(shù)樣本出現(xiàn)在圖5.1的上半部分，而奇數(shù)樣本則出現(xiàn)在下半部分，從形式上考慮，這種數(shù)據(jù)劃分可以借助于觀察標(biāo)號(hào)n的最低位(n0)完成。具體講，就是最低位為0時(shí)，序列值相當(dāng)于偶數(shù)樣本，所以出現(xiàn)在X0(l)的上半部分。如果最低位為1，則序列值相當(dāng)于奇數(shù)樣本，因而出現(xiàn)在X0(l)的下半部分。接下來(lái)對(duì)于由此形成的每一個(gè)偶數(shù)和奇數(shù)子序列又分別按數(shù)據(jù)標(biāo)號(hào)的倒數(shù)第二位分成偶數(shù)和奇數(shù)部分。先看偶數(shù)子序列，如果倒數(shù)第二位為0，那么該序列值是這個(gè)子序列的偶數(shù)項(xiàng)，如果倒數(shù)第二位為1，則序列值在這個(gè)子序列中具有奇標(biāo)號(hào)。對(duì)奇數(shù)子序列也作同樣的處理。如此繼續(xù)劃分直至最終得到N個(gè)長(zhǎng)度為1(即不能再分)的子序列為止。圖5.9的樹(shù)狀結(jié)構(gòu)較為直觀地描述了這種不斷劃分偶數(shù)和奇數(shù)子序列,同時(shí)也是不斷將離散傅里葉變換計(jì)算分解成較小的離散傅里葉變換造成位序顛倒的過(guò)程。圖5.9形成倒位序的樹(shù)狀結(jié)構(gòu)表示在對(duì)倒位序進(jìn)行具體編排時(shí)，我們?nèi)砸詧D5.8為例。為了實(shí)現(xiàn)同址計(jì)算，此時(shí)輸入必須呈倒位序，而計(jì)算結(jié)果則成正常位序。一般情況下，輸入序列并不是倒位序的，所以實(shí)現(xiàn)圖5.8的第一步是先對(duì)輸入樣本序列作排列處理。當(dāng)N=8時(shí)，這種處理可用圖5.10表示。圖5.10

對(duì)N=8的位序倒置編排

從圖可以看到，將x(n)排列成倒位序可以按“原位”方式進(jìn)行。此時(shí)通常用一個(gè)按倒位序“計(jì)數(shù)”的標(biāo)號(hào)計(jì)數(shù)器實(shí)現(xiàn)（戈?duì)柕潞屠椎陆o出了這種倒位計(jì)數(shù)器的流圖從圖5.10可以看到，當(dāng)n=l時(shí)不必交換，而當(dāng)n≠l時(shí)，則必須交換x(n)與x(l),但是，我們還必須保證交換只進(jìn)行一次,為此，可將n與l作比較，只有當(dāng)l>n時(shí)才進(jìn)行交換。于是對(duì)于倒位編排的一個(gè)簡(jiǎn)單方法是：將序列x(n)的標(biāo)號(hào)n按正常位序從0到N-1數(shù)號(hào)，而l則按倒位序從0到N-1數(shù)號(hào)。每當(dāng)l>n時(shí)就交換x(n)與x(l)，否則就不作交換。一旦輸入變成倒位序之后，我們即可著手圖5.8中第一級(jí)的計(jì)算。此時(shí)該級(jí)需作乘法的加權(quán)系數(shù)全是WN0=1，而蝶形的輸入X0(·)為兩個(gè)相鄰節(jié)點(diǎn)的節(jié)點(diǎn)值。在第二級(jí)中，作乘法加權(quán)的系數(shù)全為WN0或，而蝶形的輸入相距2個(gè)間隔。在第m級(jí)中，有關(guān)支路所乘的系數(shù)將為的整數(shù)冪，而蝶形的輸入則相隔2m-1

個(gè)間隔。我們也可看到，如果蝶形計(jì)算從圖5.8的上端開(kāi)始的話，則要求WN的冪次成正常位序。上面的討論規(guī)定了有關(guān)數(shù)據(jù)在某一級(jí)的運(yùn)算中必須遵循的存取方式,它當(dāng)然與選用的具體流圖有關(guān)系。

5.3.3其他形式

圖5.11是另一種原位計(jì)算的形式。在圖5.11的流圖中，輸入序列是正常位序的，而其離散傅里葉變換的輸出則是位序倒置的。其實(shí)，將圖5.8中的x(4)水平相鄰的所有節(jié)點(diǎn)與x(1)水平相鄰的所有節(jié)點(diǎn)交換，同樣，將圖5.8中與x(6)水平相鄰的所有節(jié)點(diǎn)和x(3)水平相鄰的所有節(jié)點(diǎn)作交換，而與x(2)、x(5)和x(7)水平相鄰的諸節(jié)點(diǎn)不變，即可比較方便地得到圖5.11所示的結(jié)構(gòu)。事實(shí)上，圖5.11也就是最初由庫(kù)利和圖基給出的時(shí)間抽選算法的基本流圖形式。圖5.11輸入為正常位序，

輸出為倒位序的圖5.8的另一種排列

從圖5.8和5.11可以看到，它們之間的唯一差異就是節(jié)點(diǎn)的排列有別，而支路傳輸比（WN的各次冪）保持不變。顯然，還可以有多種不同的排列形式，但大多數(shù)方式從計(jì)算角度考慮并無(wú)更多實(shí)際意義。其中較為有用的一種是將輸入和輸出節(jié)點(diǎn)都排列成正常位序的形式,其流圖如圖5.12所示。不過(guò)此時(shí)的計(jì)算已不能再按原位方式完成，因而也就需要使用兩列長(zhǎng)度為N的復(fù)數(shù)存儲(chǔ)器。

圖5.12輸入和輸出均成正常位序的圖5.8的重新排列

在實(shí)現(xiàn)圖5.8、圖5.11及圖5.12的具體計(jì)算時(shí)，中間諸列的節(jié)點(diǎn)顯然不能按順序存取。為提高計(jì)算速度，復(fù)數(shù)數(shù)據(jù)需存放于隨機(jī)存取的存儲(chǔ)器中。如圖5.8所示，在輸入數(shù)據(jù)列之后的第一列中，作為每一蝶形計(jì)算的兩個(gè)輸入是相鄰的節(jié)點(diǎn)值，可以想像到它們是被存放在相鄰的存儲(chǔ)位置上。當(dāng)從第一列計(jì)算中間的第二列時(shí)，蝶形計(jì)算的兩個(gè)輸入相距了兩個(gè)存儲(chǔ)位置，而從第二列計(jì)算第三列時(shí)，蝶形計(jì)算的兩個(gè)輸入將有四個(gè)存儲(chǔ)間隔。若N大于8，則第四列計(jì)算的蝶形計(jì)算輸入之間的間隔為8，第五級(jí)為16，等等。最后的第v級(jí)的間隔應(yīng)為N/2。

圖5.11的情況與此相似，以輸入數(shù)據(jù)計(jì)算第一列時(shí)，我們?nèi)∑溟g隔為4，從第一列計(jì)算第二列時(shí)，它們的間隔為2，而計(jì)算最后一列時(shí)，則取相鄰數(shù)據(jù)。如圖5.12所示的計(jì)算不再符合原位形式，其結(jié)構(gòu)也要復(fù)雜不少。

圖5.13也是圖5.8的流圖的另一種排列，這種排列在沒(méi)有隨機(jī)存取存儲(chǔ)器時(shí)比較有用。圖中的輸入還是倒位序的，而輸出也仍是正常位序的。這個(gè)流圖的重要特征是各級(jí)的幾何形狀完全一樣，只是級(jí)與級(jí)之間的支路的傳輸比有相應(yīng)的變化。這種結(jié)構(gòu)帶來(lái)一個(gè)好處，即它可以按順序存取數(shù)據(jù)。

圖5.13圖5.8的重新排列(各級(jí)具有相同幾何形狀因此可以順序存取數(shù)據(jù))5.4按頻率抽選的快速傅里葉變換算法

按時(shí)間抽選的快速傅里葉變換算法是基于將輸入序列x(n)分解成越來(lái)越短的子序列的一種方法。此外，我們也可以將輸出序列X(k)按同樣的方法分成越來(lái)越短的子序列來(lái)進(jìn)行。根據(jù)這種處理方法建立起來(lái)的快速傅里葉變換算法通常稱(chēng)作頻率抽選或桑德—圖基算法。我們?nèi)栽O(shè)N=2v，而且先將輸入序列分成前一半與后一半的形式，于是其離散傅里葉變換可表示成

或

(5－13)應(yīng)該注意的是，雖然式（5－13）中所含的是兩個(gè)N/2點(diǎn)的求和式，但每個(gè)和式中出現(xiàn)的是,而非，所以每個(gè)和式都不是N/2點(diǎn)的離散傅里葉變換。不過(guò)，合并這兩個(gè)和式，并利用 ，則可得(5－14)下面我們把k為偶數(shù)和k為奇數(shù)的兩種情況分開(kāi)來(lái)討論，并以X(2r)和X(2r+1)分別代表偶數(shù)與奇數(shù)點(diǎn)的變換值，于是有(5－15)及

(5－16)這里的r=0,1,…,

。

考慮到

式（5－15）及式（5－16）可以寫(xiě)成

(5－17)(5－18)及

（5－18）

式中的

(5－19)

(5－20)

與式（5－13）不同，式（5－17）及式（5－18）可視為N/2點(diǎn)的離散傅里葉變換。式（5－17）為輸入序列前半部分與后半部分之和的N/2點(diǎn)的離散傅里葉變換，式（5－18）則為輸入序列前、后半部分之差并與WNn相乘以后的N/2點(diǎn)的離散傅里葉變換。它們的具體流圖則如圖5.14所示。與按時(shí)間抽選的算法類(lèi)似，考慮到N是2的冪指數(shù)，當(dāng)N/2仍為偶數(shù)時(shí)，依舊可以用計(jì)算其偶數(shù)和奇數(shù)輸出點(diǎn)的方法來(lái)計(jì)算這兩個(gè)N/2點(diǎn)的離散傅里葉變換。與上述分解式（5－15）和式（5－16）的情況相似，此時(shí)對(duì)于每一個(gè)N/2點(diǎn)的離散傅里葉變換，仍可將其前一半及后一半按類(lèi)似的方式進(jìn)行組合，然后計(jì)算N/4點(diǎn)的離散傅里葉變換。對(duì)于8點(diǎn)的例子，按這種方式得出的流圖則如圖5.15所示。

圖5.14按頻率抽選法把一個(gè)N點(diǎn)的DFT的計(jì)算分解成兩個(gè)N/2點(diǎn)的DFT的計(jì)算的流圖圖5.15把8點(diǎn)DFT按頻率抽選成四個(gè)2點(diǎn)DFT計(jì)算的流圖

由于所舉的是8點(diǎn)的例子，此時(shí)的流圖已被分解成計(jì)算2點(diǎn)離散傅里葉變換的情況，它顯然可以以?xún)蓚€(gè)輸入值的相加及相減來(lái)完成，即可用圖5.16所示的計(jì)算來(lái)完成。至于總的N=8的離散傅里葉變換的計(jì)算，

則可用圖5.17的流圖表示。

圖5.16按頻率抽選分解到最后一級(jí)時(shí)的2點(diǎn)DFT的流圖

圖5.17按頻率抽選的8點(diǎn)DFT的完整流圖

我們可以清點(diǎn)一下圖5.17中的算術(shù)運(yùn)算次數(shù)，并進(jìn)而推廣到N=2v的一般情況。從圖中不難看到，它要求次復(fù)數(shù)乘法和NlbN次復(fù)數(shù)加法時(shí)，即按頻率抽選的離散傅里葉變換的實(shí)際計(jì)算量與按時(shí)間抽選的情況是相同的。

與按時(shí)間抽選的快速離散傅里葉變換算法一樣，按頻率抽選的快速離散傅里葉變換算法也有類(lèi)似的具體問(wèn)題。

我們擇其一、

二略作解釋。

5.4.1原位計(jì)算從圖5.17所示的按頻率抽選的流圖中可以看到，它實(shí)際上也是以一系列典型的蝶形計(jì)算來(lái)實(shí)現(xiàn)的。跟以前討論過(guò)的情況一樣，如果我們將第m+1級(jí)的輸入復(fù)數(shù)序列表示為Xm(l)，這里的m=0,1,…,v-1，而l=0,1,…,N-1,于是，圖5.17所示的流圖中的所有蝶形將可用圖5.18的基本蝶形表示，而式（5－21）則代表了第m+1級(jí)的蝶形的具體運(yùn)算，即此時(shí)的根據(jù)蝶形計(jì)算性質(zhì)，

(5－21)圖5.17所示的流圖顯然可以視為離散傅里葉變換的另一種原位計(jì)算形式。

5.4.2轉(zhuǎn)置關(guān)系比較圖5.7和圖5.18，或?qū)Ρ仁剑?－11）和式（5－21），我們可以看到，兩種快速傅里葉變換算法的蝶形本身是有區(qū)別的。不過(guò)，我們不難注意到這樣的事實(shí)，即兩種基本蝶形計(jì)算之間以及圖5.7及圖5.18之間有著極其相似的地方。事實(shí)上，圖5.18就是圖5.7的轉(zhuǎn)置。圖5.17也可以通過(guò)顛倒圖5.8的信號(hào)流圖的方向以及將輸入輸出互換得到，只是在輸入輸出互換時(shí)，應(yīng)該注意被置換處原先按正常位序排列的，置換后該處仍按正常位序排列，而被置換處原先按顛倒位序排列的，置換后該處則依舊按顛倒位序排列。所以圖5.17實(shí)際上就是圖5.8的轉(zhuǎn)置。

根據(jù)轉(zhuǎn)置定理，

兩者的傳輸特性顯然是相同的。

圖5.18圖5.17要求的典型蝶形計(jì)算流圖

如果將轉(zhuǎn)置處理應(yīng)用于圖5.11，就可得到圖5.19的流圖。在這個(gè)流圖中，輸出按正常位序，而輸入