第四章快速傅氏變換課件2

第四章快速傅氏變換第四章快速傅氏變換

引言：離散傅里葉變換在實際應(yīng)用中是非常重要的，利用它可以計算信號的頻譜、功率譜和線性卷積等。但是，如果使用定義式來直接計算DFT，當N很大時，即使使用高速計算機，所花的時間也太多。因此，如何提高計算DFT的速度，便成了重要的研究課題。1965年庫利(Cooley)和圖基(Tukey)在前人的研究成果的基礎(chǔ)上提出了快速計算DFT的算法，之后，又出現(xiàn)了各種各樣快速計算DFT的方法，這些方法統(tǒng)稱為快速傅里葉變換(Fast

FourierTransform)，簡稱為FFT。引言：離散傅里葉變換在實際應(yīng)用中是非常重要的快速傅里葉變換(FFT)是離散傅里葉變換(DFT)的快速算法它是DSP領(lǐng)域中的一項重大突破，它考慮了計算機和數(shù)字硬件實現(xiàn)的約束條件、研究了有利于機器操作的運算結(jié)構(gòu)，使DFT的計算時間縮短了1~2個數(shù)量級，還有效地減少了計算所需的存儲容量。FFT技術(shù)的應(yīng)用極大地推動了DSP的理論和技術(shù)的發(fā)展，成為數(shù)字信號處理強有力的工具。快速傅里葉變換(FFT)是離散傅里葉變換(DFT)的快速算法其中在導(dǎo)出FFT算法之前，先估計一下直接計算DFT所需計算量。DFT的定義其中在導(dǎo)出FFT算法之前，先估計一下直接計算DFT所需計算量將方程組寫成矩陣形式將DFT定義式展開成方程組將方程組寫成矩陣形式將DFT定義式展開成方程組同理用復(fù)數(shù)表示：用向量表示：同理用復(fù)數(shù)表示：用向量表示：從矩陣形式表示可以看出每計算一個X(k)值需要N次復(fù)乘法和(N-1)次復(fù)數(shù)加法，因而計算N個X(k)值，共需N2次復(fù)乘法和N(N-1)次復(fù)加法。每次復(fù)乘法包括4次實數(shù)乘法和2次實數(shù)加法，每次復(fù)加法包括2次實數(shù)加法，因此計算N點的DFT共需要4N2次實數(shù)乘法和(2N2+2N·(N-1))次實數(shù)加法。當N很大時，這是一個非常大的計算量。例如當N=1024，N2=1048576。在實際中，N往往是比較大的，因此有必要對DFT的計算予以改進。從矩陣形式表示可以看出每計算一個X(k)值需要N次復(fù)乘法和((1)對稱性或(2)周期性(3)可約性或(4)其它首先考察WNnk的一些特殊性質(zhì)：(1)對稱性或(2)周期性(3)可約性或(4)其它首先考察W§4.1

基2時間抽選法（庫里—圖基算法）一、基本原理：利用旋轉(zhuǎn)因子WNnk的對稱性和周期性，將一個長序列x(n)的DFT計算，在時域上按奇偶抽選分解成短序列的DFT來計算。設(shè)N＝2M，M為正整數(shù)。為推導(dǎo)方便，取N＝23＝8，即離散時間信號為x(n)={x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7)}將序列x(n)分為奇偶兩組，一組序號為偶數(shù)，另一組序號為奇數(shù)，即{x(0),x(2),x(4),x(6)|x(1),x(3),x(5),x(7)}分別表示為： g(r)=x(2r)——偶數(shù)項 h(r)=x(2r+1)——奇數(shù)項r=0,1,…,N/2-1§4.1

基2時間抽選法（庫里—圖基算法）一、基本原理：利因為WN2=WN/21，所以上式變?yōu)樯鲜街械腉(k)和H(k)都是N/2點的DFT。根據(jù)DFT的定義k=0,1,…,N/2-1(4.1)因為WN2=WN/21，所以上式變?yōu)樯鲜街械腉(k)和H(要用G(k)和H(k)來表達全部的X(k)值還必須考慮后半部分項數(shù)（k+N/2）。利用系數(shù)周期性，因為所以X(k)是N點序列，式4.1計算得到的只是前一半項數(shù)的結(jié)果k=0,1,…,N/2-1(4.2)將式4.1中的k用k+N/2代入，可得到要用G(k)和H(k)來表達全部的X(k)值還必須考慮后半部2點的DFT流程圖ab-1a-bWNka+bWNkWNk這樣就把一個N點的DFT分解成了兩個N/2點的DFT，只是最后求和的符號不同。式4.1與4.2的運算可用蝶形信號流圖來表示2點的DFT流程圖ab-1a-bWNka+bWNkW圖1N點的DFT分解成兩個N/2點DFT的的時間抽選流程圖N=8按照式4.1和式4.2可畫出下圖所示的信號流程圖。

N/2點DFTN/2點DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)G(1)G(2)G(3)H(1)H(2)H(9)X(1)=G(1)+WN1H(1)X(2)=G(2)+WN2H(2)X(3)=G(3)+WN3H(3)WN1WN2WN3-1-1-1X(5)=G(1)-WN1H(1)X(6)=G(2)-WN2H(2)X(7)=G(3)-WN3H(3)G(0)H(0)WN0-1X(0)=G(0)+WN0H(0)X(4)=G(0)-WN0H(0)圖1N點的DFT分解成兩個N/2點DFT的的時間抽選流程式4.1和式4.2把原N點DFT計算分解成兩個N/2點DFT計算。照此可進一步把每個N/2點DFT的計算再各分解成兩個N/4點DFT的計算。具體說來，是把{x(0)，x(2)，x(4)，x(6)}和{x(1)，x(3)，x(5)，x(7)}分為{x(0)，x(4)|x(2)，x(6)}和{x(1)，x(5)|x(3)，x(7)}。G(k)和H(k)分別計算如下:k=0,1,…,N/4-1(4.3)式4.1和式4.2把原N點DFT計算分解成兩個N/2點DFTk=0,1,…,N/4-1(4.4)k=0,1,…,N/4-1(4.5)k=0,1,…,N/4-1(4.6)k=0,1,…,N/4-1(4M(0)M(1)N(0)N(1)G(0)G(1)G(2)G(3)WN0WN2-1-1N/4點DFTx(0)x(4)x(2)x(6)N/4點DFT圖2N/2點的DFT分解成兩個N/4點DFT的的時間抽選流程圖N=8這樣，用式(4.3)～(4.6)就可計算圖1中的兩組N/2點DFT。圖2所示的是其中一組G(k)的計算。M(0)G(0)WN0-1N/4點x(0)N/4點圖2Nx(0)x(4)x(2)x(6)WN0WN2-1-1N/4點DFTN/4點DFTx(1)x(5)x(3)x(7)N/4點DFTN/4點DFTWN0WN2-1-1將圖1與圖2合并，便得到圖3所示的信號流程圖。X(0)X(1)X(2)X(3)WN0WN1WN2WN3-1-1-1-1X(4)X(5)X(6)X(7)G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)x(0)WN0-1N/4點N/4點x(1)N/4點N/4點W將2點DFT的信號流程圖移入圖3，得到圖4所示的8點時間抽選的完整的FFT流程圖。2點的DFT流程圖x(0)-1x(0)+x(4)WN0WN0x(4)x(0)-x(4)WN0N=8，圖3中N/4點的DFT就是2點的DFT。將2點DFT的信號流程圖移入圖3，得到圖4所示的8點時間抽選圖4基2時間抽選法8點FFT流程圖X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN0WN1WN2WN3-1-1-1-1WN0WN2-1-1WN0WN2-1-1x(1)x(5)x(3)x(7)x(0)x(4)x(2)x(6)WN0-1WN0-1WN0-1WN0-1圖4基2時間抽選法8點FFT流程圖X(0)WN0-1Wab-1a-bWNka+bWNkWNk從圖4中可看出幾個特點：(1)流程圖的每一級的基本計算單元都是一個蝶形；

(2)輸入x(n)不按自然順序排列，稱為“混序”排列，而輸出X(k)按自然順序排列，稱為“正序”排列，因而要對輸入進行“變址”；(3)由于流程圖的基本運算單元為蝶形，所以可以進行“同址”或“原位”計算。ab-1a-bWNka+bWNkWNk從圖4中可看出M=log2N由圖可看出完成一個蝶形計算需一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法二、運算量的減少（蝶形計算）任何一個N為2的整數(shù)冪（即N=2M）的DFT，都可以通過M次分解，最后成為2點的DFT來計算。M次分解構(gòu)成了從x(n)到X(k)的M級迭代計算，每級由N/2個蝶形組成。ab-1a-bWNka+bWNkWNk下圖表示了蝶形的一般形式表示。其輸入和輸出之間滿足下列關(guān)系：M=log2N由圖可看出完成一個蝶形計算需一次復(fù)數(shù)乘法和兩次大多數(shù)情況下復(fù)數(shù)乘法所花的時間最多，因此下面僅以復(fù)數(shù)乘法的計算次數(shù)為例來與直接計算進行比較。直接計算DFT需要的乘法次數(shù)為aD=N2，于是有即直接計算DFT所需復(fù)數(shù)乘法次數(shù)約為FFT的205倍。顯然，N越大，F(xiàn)FT的速度優(yōu)勢越大。復(fù)數(shù)乘法次數(shù)：例：當N=1024時，因此，完成N點的時間抽選FFT計算的總運算量為復(fù)數(shù)加法次數(shù)：大多數(shù)情況下復(fù)數(shù)乘法所花的時間最多，因此下面僅以復(fù)數(shù)乘法的計N所需復(fù)數(shù)乘法次數(shù)aD/aF直接計算DFT用FFT計算DFT24816326412825651210242048416642561024409616384655362621441048576419430414123280192448102423045120112644.04.05.48.012.821.436.664.0113.8204.8372.4不同N值所對應(yīng)的兩種計算方法的復(fù)數(shù)乘法次數(shù)和它們的比值N所需復(fù)數(shù)乘法次數(shù)aD/aF直接計算DFT用FFT計算DFTab-1a-bWNka+bWNkWNk三、同址(原位)計算圖4包含M級迭代運算，每級由N/2個蝶形計算構(gòu)成。蝶形計算的優(yōu)點是可進行所謂同址(原位)計算。首先每一個蝶形運算都需要兩個輸入數(shù)據(jù)，計算結(jié)果也是兩個數(shù)據(jù)，與其它結(jié)點的數(shù)據(jù)無關(guān)，其它蝶形運算也與這兩結(jié)點的數(shù)據(jù)無關(guān)。因此，一個蝶形運算一旦計算完畢，原輸入數(shù)據(jù)便失效了。這就意味著輸出數(shù)據(jù)可以立即使用原輸入數(shù)據(jù)結(jié)點所占用的內(nèi)存。原來的數(shù)據(jù)也就消失了。這樣輸出、輸入數(shù)據(jù)利用同一內(nèi)存單元的這種蝶形計算稱為同址計算。ab-1a-bWNka+bWNkWNk三、同址(原位-1WN0x(0)x(4)x(0)+x(4)WN0x(0)-x(4)WN0M(0)M(1)M(0)M(1)類似地，M(2)和M(3)中的x(2)和x(6)進入運算器進行蝶形運算后的結(jié)果也被送回到M(2)和M(3)保存，等等?，F(xiàn)在來考察第一級的計算規(guī)律設(shè)將輸入x(0)，x(4)，x(2)，x(6)，x(1)，x(5)，x(3)，x(7)分別存入計算機的存儲單元M(0),M(1),M(2),…，M(6)和M(7)中。首先，存儲單元M(0)和M(1)中的數(shù)據(jù)x(0)和x(4)進入運算器并進行蝶形運算，運算后的結(jié)果便可送到M(0)和M(1)存儲起來。-1WN0x(0)x(4)x(0)+x(4)WN0x(0第二級運算與第一級類似M(0)和M(2)存儲單元中的數(shù)據(jù)進行蝶形運算后的結(jié)果被送回M(0)和M(2)保存，M(1)和M(3)中的數(shù)據(jù)進行蝶形運算后送回M(1)和M(3)保存，等等。這樣一直到最后一級的最后一個蝶形運算完成?？梢钥闯觯恳患壍牡蔚妮斎肱c輸出在運算前后可以存儲在同一地址(原來位置上)的存儲單元中，這種同址運算的優(yōu)點是可以節(jié)省存儲單元，從而降低對計算機存儲量的要求或降低硬件實現(xiàn)的成本。第二級運算與第一級類似M(0)和M(2)存儲單元中的數(shù)據(jù)進M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)如圖所示的N點FFT計算，只需N個存儲存儲單元X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)WN0WN1WN2WN3-1-1-1-1WN0-1WN0-1WN0-1WN0-1WN0-1WN0-1WN2WN2-1-1M(0)M(0)M(0)M(0)如圖所示的N點FFT計算，只四、變址計算（倒序重排）從圖4所示的流程圖看出，同址計算要求輸入x(n)是“混序”排列的。所謂輸入為“混序”，并不是說輸入是雜亂無章的，實際上它是有規(guī)律的。如果輸入x(n)的序號用二進制碼來表示，就可以發(fā)現(xiàn)輸入的順序恰好是正序輸入的“碼位倒置”。下表2列出了這種規(guī)律。四、變址計算（倒序重排）從圖4所示的流程圖看出，同址計算要自然序列二進制表示碼位倒置混序x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(000)x(001)x(010)x(011)x(100)x(101)x(110)x(111)表2x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)x(000)x(100)x(010)x(110)x(001)x(101)x(011)x(111)自然序列二進制表示碼位倒置混序x(0)x(000)表2x(0存儲單元M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)自然順序x(n)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)碼位倒置順序x(l)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)變址圖5碼位倒置的變址處理在實際運算中，按碼位倒置順序輸入數(shù)據(jù)x(n)，特別當N較大時，是很不方便的。因此，數(shù)據(jù)總是按自然順序輸入存儲，然后通過“變址”運算將自然順序轉(zhuǎn)換成碼位倒置順序存儲。實現(xiàn)這種轉(zhuǎn)換的程序可用圖5來說明。存儲單元M(0)M(1)圖中用n表示自然順序的標號，用l表示碼位倒置的標號當l＝n時，x(n)和x(l)不必互相調(diào)換。當l≠n時，必須將x(l)和x(n)互相調(diào)換，但只能調(diào)換一次，為此必須規(guī)定每當l>n時，要將x(l)和x(n)相互調(diào)換，即把原來存放x(n)的存儲單元中的數(shù)據(jù)調(diào)入存儲x(l)的存儲單元中，而把原來存儲x(l)的存儲單元中的數(shù)據(jù)調(diào)入到存儲x(n)的存儲單元中。這樣，按自然序輸入的數(shù)據(jù)x(n)經(jīng)過變址計算后變成了碼位倒置的排列順序，便可進入第一級的蝶形運算。

圖中用n表示自然順序的標號，用l表示碼位倒置的標號當l＝n時另外一些形式的時間抽選FFT算法流程圖對于任何流程圖，只要保持各節(jié)點所連支路及其傳輸系數(shù)不變，則不論節(jié)點位置怎樣排列，所得到的流程圖總是等效的，因而都能得到DFT的正確結(jié)果，只是數(shù)據(jù)的提取和存儲次序不同而已。把圖4中與x(4)水平相鄰的所有節(jié)點和與x(1)水平相鄰的所有節(jié)點交換，把與x(6)水平相鄰的所有節(jié)點和與x(3)水平相鄰的所有節(jié)點交換，而與x(0)、x(2)、x(5)和x(7)水平相鄰各節(jié)點位置不變，就可以從圖4得到圖6。圖6與圖4的區(qū)別只是節(jié)點的排列不同，而支路傳輸比，即WN的各次冪保持不變。顯然圖6所示流程圖的輸入是正序（自然順序）排列的，輸出是碼位倒置排列的，所以輸出要進行變址計算。另外一些形式的時間抽選FFT算法流程圖對于任何流程圖，只要保圖4基2時間抽選法8點FFT流程圖X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN0WN1WN2WN3-1-1-1-1WN0WN2-1-1x(1)x(5)x(3)x(7)WN0WN2-1-1x(0)x(4)x(2)x(6)WN0-1WN0-1WN0-1WN0-1圖4基2時間抽選法8點FFT流程圖X(0)WN0-1W圖6基2時間抽選法8點FFT流程圖（輸入正序）X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)WN0WN0WN0WN0-1-1-1-1WN0WN0-1-1x(4)x(5)x(6)x(7)WN2WN2-1-1x(0)x(1)x(2)x(3)WN0-1WN1-1WN2-1WN3-1圖6基2時間抽選法8點FFT流程圖（輸入正序）X(0)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN0WN0WN0WN0-1-1-1-1WN0WN0x(4)x(5)x(6)x(7)WN2WN2x(0)x(1)x(2)x(3)WN0WN1WN2WN3-1-1-1-1-1-1-1-1另一種形式的流程圖是將節(jié)點排列成輸入和輸出兩者都是正序排列，但這類流程圖不能進行同址計算，因而需要兩列長度為N的復(fù)數(shù)存儲器。X(0)WN0-1WN0x(4)WN2x(0)WN0WN1W其中r=0,1,…,N/2-1§4.2基2頻率抽選法（桑德—圖基算法）基2頻率抽選法是在頻域內(nèi)將X(k)逐次分解成奇偶序列，再進行DFT計算設(shè)N＝2M，M為正整數(shù)。為推導(dǎo)方便，取N=23＝8。將頻率偶奇分， 即X(k)={X(0),X(2),X(4),X(6),|X(1),X(3),X(5),X(7)}用X(2r)和X(2r+1)分別表示頻率的偶數(shù)項和奇數(shù)項， 則有其中r=0,1,…,N/2-1§4.2基2頻率抽其中g(shù)(n)=x(n)+x(n+N/2)n=0,1,…,N/2-1同理其中h(n)=x(n)-x(n+N/2)n=0,1,…,N/2-1(4.7)(4.8)上面兩式所表示的是N/2的DFT。在實際計算中，首先形成序列g(shù)(n)和h(n)，然后計算h(n)WNn，最后分別計算g(n)和h(n)WNn的N/2點DFT，便得到偶數(shù)輸出點和奇數(shù)輸出點的DFT。計算流程圖如圖7所示。其中g(shù)(n)=x(n)+x(n+N/2)nN/2點DFTN/2點DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)WN0WN1WN2WN3-1-1-1-1圖7N點的DFT分解成兩個N/2點DFT的的頻率抽選流程圖N=8N/2點N/2點x(0)X(0)WN0-1圖7N點的DFab-1a-bWNka+bWNkWNkaa+bb-1(a–b)WNkWNk時間抽選蝶形單元頻率抽選蝶形單元與時間抽選的FFT算法一樣，圖7所示的流程圖的基本運算也是蝶形運算，但是頻率抽選與時間抽選中的蝶形單元有所不同。N是2的整數(shù)冪，所以N/2仍然是偶數(shù)。這樣可以將N/2點DFT的輸出再分為偶數(shù)組和奇數(shù)組，即將N/2點的DFT計算進一步分解為兩個N/4點的DFT計算，以此類推直到不能分解。如圖8ab-1a-bWNka+bWNkWNkaa+bb圖8基2頻率抽選法8點FFT流程圖X(0)X(4)X(2)X(6)WN0WN1WN2WN3-1-1-1-1WN0WN2-1-1x(4)x(5)x(6)x(7)WN0WN2-1-1x(0)x(1)x(2)x(3)WN0-1WN0-1WN0-1WN0-1X(1)X(5)X(3)X(7)圖8基2頻率抽選法8點FFT流程圖X(0)WN0-1W頻率抽選與時間抽選的異同點：比較圖4與圖8可知，頻率抽選FFT算法的計算量與時間抽選FFT算法的計算量相同。與時間抽選算法一樣，頻率抽選FFT算法也具有同址（原位）計算的優(yōu)點。但是，與時間抽選不同的是，頻率抽選FFT算法的信號輸入為正序排列，輸出為碼位倒置排列，因此輸出要進行變址計算。頻率抽選與時間抽選的異同點：比較圖4與圖8可知，頻率抽選FFk=0,1,…,N/2-1在時間抽選FFT法中，第一次分解得到G(k)、H(k)分別為輸入序列偶數(shù)點和奇數(shù)點的N/2點DFT(4.1)(4.2)§4.3

IFFT的計算方法（快速傅里葉反變換）一、IFFT算法k=0,1,…,N/2-1在時間抽選FFT法中，第一次k=0,1,…,N/2-1根據(jù)上式可畫出蝶形圖G(k)X(k)H(k)-1X(k+N/2)以此類推可求出x(n)的各點，反變換流程如圖9根據(jù)式4.1與4.2可得到k=0,1,…,N/2-1根據(jù)上式可畫出蝶形圖G(k)圖98點IFFT流程圖1/21/21/21/2X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1x(1)x(5)x(3)x(7)-1-1x(0)x(4)x(2)x(6)-1-1-1-11/21/21/21/21/21/21/21/2圖98點IFFT流程圖1/2X(0)-1-1x(1)比較上面兩式，可以看出，只要把DFT公式中的系數(shù)WNkn改為WN-kn

，并乘以系數(shù)1/N，將X(k)作為輸入序列，將x(n)作為輸出序列，就可用FFT算法來計算IDFT，這就得到了IFFT的算法。（例圖10）在IFFT計算中經(jīng)常把常量1/N分解成M個1/2連乘，即1/N＝(1/2)M，并且在M級的迭代運算中，每級的運算都分別乘上一個1/2因子。二、利用FFT求IFFTFFT算法同樣可以應(yīng)用于IDFT的計算。已知DFT和IDFT公式為比較上面兩式，可以看出，只要把DFT公式中的系數(shù)WNkn改x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)WN0WN-1WN-2WN-3-1-1-1-1WN0WN-2-1-1X(4)X(5)X(6)X(7)WN0WN-2-1-1WN0-1WN0-1WN0-1WN0-11/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/2圖108點IFFT流程圖（例：利用頻率抽取FFT—圖8）x(0)X(0)WN0-1WN0-1X(4)WN0-1WN0IFFT算法分類當把時間抽選FFT算法用于IFFT計算時，由于原來輸入的時間序列x(n)現(xiàn)在變?yōu)轭l率序列X(k)，原來是將x(n)偶奇分的，而現(xiàn)在變成對X(k)進行偶奇分了，因此這種算法改稱為頻率抽選IFFT算法。類似地，當把頻率抽選FFT算法用于計算IFFT時，應(yīng)該稱為時間抽選IFFT算法。（圖10為時間抽選8點IFFT算法）IFFT算法分類當把時間抽選FFT算法用于IFFT計算時，與DFT比較，只需將X*(k)作為輸入序列就可直接利用FFT流程具體步驟如下：1、求X(k)的共軛X*(k)，取共軛只需將虛部乘以(-1)2、以X*(k)作為輸入序列，直接調(diào)用FFT程序，計算得到Nx*(n)3、對計算結(jié)果取共軛并乘以1/N即得到x(n)取共軛法：對DFT的反變換取共軛與DFT比較，只需將X*(k)作為輸入序列就可直接利用FFT§4.4

基4FFT算法（略）基4FFT與基2FFT相比，復(fù)數(shù)乘法減少了約1/4，但復(fù)數(shù)加法卻增加了。無論是軟件還是硬件方法，復(fù)數(shù)乘法計算時間是復(fù)數(shù)加法的幾十倍乃至上百倍，所以基4算法產(chǎn)生的主要目的是為了減少復(fù)數(shù)乘法。近年來，在一些高速數(shù)字信號處理器中，實現(xiàn)一次乘法運算與一次加法運算的時間完全一樣，所以應(yīng)用基4算法時就不一定合算了。§4.4

基4FFT算法（略）基4FFT與基2FFT相比，§4.5

線性調(diào)頻Z變換算法（CZT）在某些情況下，我們所需要的頻率取樣點并不均勻的分布在單位圓上；有時只在單位圓的某一部分；有時要求某一部分取樣點密集（例如窄帶信號）；有時甚至取樣點不在單位圓上。（例如語音信號處理）§4.5

線性調(diào)頻Z變換算法（CZT）在某些情況下，我們所沿Z平面上的一段螺線作等分角抽樣Zk=AW-k

k=0,1,…,M-1且M≤N式中

如圖：一、算法基本原理已知x(n)長度為N，則W0、A0為正實數(shù)Im(z)z平面Re(z)1A0φ0

θ0

Z0ZM-10沿Z平面上的一段螺線作等分角抽樣如圖：一、算法基本原理已知xIm(z)z平面Re(z)1A0φ0

θ0

Z0ZM-10由圖可知：1、A0表示起始抽樣點Z0的矢量半徑長度，通常A0≤1，否則Z0將在單位圓之外；2、q0表示起始抽樣點Z0相角，可正可負;3、f0表示兩相鄰抽樣點間角度差，f0為正時，表示路徑逆時針，f0為負時表示路徑順時針。4、W0表示螺線的伸展率，W0＞1表示隨k增大螺線內(nèi)縮，W0＜1表示隨k增大螺線外伸。W0=1表示半徑為A0的一段圓弧，又如果A0=1,則圓弧是單位圓一部分。Im(z)z平面Re(z)1A0φ0θ0Z0ZM-10由與直接計算DFT相似，當N、M很大時，運算量很大；于是可采用布魯斯坦（Bluestein）等式，將其轉(zhuǎn)換為卷積和形式，從而可采用FFT算法。Bluestein等式令可得：0≤k≤M-1將Zk代入X(z)，有0≤k≤M-1與直接計算DFT相似，當N、M很大時，運算量很大；Blues計算過程如圖：x(n)h(n)y(n)g(n)令則或 可想象為頻率隨時間n成線性增長的復(fù)指數(shù)序列，在雷達系統(tǒng)中，這種信號稱為線性調(diào)頻信號(Chirpsignal)，因此在這里稱為線性調(diào)頻Z變換算法。序列0≤k≤M-10≤k≤M-10≤k≤M-10≤k≤M-1計算過程如圖：x(n)h(n)y(n)g(n)令則或 可由可知h(n)的長度為n=-(N-1)～M-1點數(shù)為L=N+M-1，y(n)的長度為N，要利用L點循環(huán)卷積來計算，y(n)需補M-1個零。二、實現(xiàn)步驟考慮h(n)的長度： 無限長由可知h(n)的長度為n=-(N-1)～M-1點數(shù)為L=N然后計算h(n)與y(n)的L點循環(huán)卷積其中g(shù)(0)到g(M-1)這M個值正與所需要的線性卷積值相等，后N-1個值不需要。當L=M+N-1=2m時，可利用基2FFT算法。n0h(n)M-1-(N-1)……n0h(n)M-1L-1而h(n)選取值如圖：然后計算h(n)與y(n)的L點循環(huán)卷積n0h(n)M-1-n0h(n)M-1L-12、將3、形成L點h(n)，并利用FFT法求H(k)0≤n≤M-1M≤n≤L-NL-N+1≤n≤L-1CZT運算步驟：1、選擇L值使L≥M+N-1，且L=2m補零，變?yōu)長點序列。并利用FFT法求Y(k)n0h(n)M-1L-12、將3、形成L點h(n)，并利用F（其中前M個值有用）0≤n≤M-1三、運算量估計（略）4、將H(k)與Y(k)相乘得到G(k)5、用FFT法求G(k)的L點IDFT6、最后求（其中前M個值有用）0≤n≤M-1三、運算量估計（略）4、將1、CZT算法靈活，輸入序列點數(shù)N與輸出序列點數(shù)M可不等；2、N與M為任意數(shù)，不需要為2的整數(shù)冪；3、Zk點間的角度分隔φ0可任意，因此可調(diào)整分辨率；4、Zk點所沿周線不必須是弧線；5、起始點Z0任意選點，即可以從任意頻率上開始對輸入數(shù)據(jù)進行頻譜分析；6、當A＝1、M＝N、W=e-j2p/N時，即為DFT，因此利用CZT也可快速計算DFT，且不要求N為2的整數(shù)冪。四、CZT與FFT比較1、CZT算法靈活，輸入序列點數(shù)N與輸出序列點數(shù)M可不等；四§4.6實序列的FFT高效算法在實際中，所需處理的實序列居多，實序列是虛部為0的復(fù)序列。一、兩個長度相等的實序列兩個長度相等的實序列，F(xiàn)FT可同時進行。因為DFT所變換的序列一般是復(fù)序列，故可將兩個實序列組合成一個復(fù)序列來進行FFT計算，從而完成這兩個FFT計算，節(jié)約了計算量。§4.6實序列的FFT高效算法在實際中，所需處理的實序列設(shè)h(n)與g(n)是長度均為N的實序列，組合y(n)=h(n)+jg(n)且DFT[y(n)]=Y(k)DFT[h(n)]=H(k)DFT[g(n)]=G(k)則有Y(k)=H(k)+jG(k)h(n)=Re[y(n)]H(k)=DFT{Re[y(n)]}＝Y(jié)ep(k)=1/2[Y(k)+Y*(N-k)]g(n)=Im[y(n)]G(k)=DFT{Im[y(n)]}＝Y(jié)op(k)=1/2j[Y(k)-Y*(N-k)]因此，做一次N點復(fù)序列FFT計算，可得到兩個實序列DFT。設(shè)h(n)與g(n)是長度均為N的實序列，組合y(n)=將一個2N點的實序列x(n)按奇偶分為兩組

h(n)=x(2n)

與g(n)=x(2n+1)n=0,1,…,N-1則有h(n)與g(n)按兩個長度相等的實序列計算（如上）k=0,1,…,N-1二、一個2N點的實序列將一個2N點的實序列x(n)按奇偶分為兩組h(n)與g(n)第四章快速傅氏變換第四章快速傅氏變換

引言：離散傅里葉變換在實際應(yīng)用中是非常重要的，利用它可以計算信號的頻譜、功率譜和線性卷積等。但是，如果使用定義式來直接計算DFT，當N很大時，即使使用高速計算機，所花的時間也太多。因此，如何提高計算DFT的速度，便成了重要的研究課題。1965年庫利(Cooley)和圖基(Tukey)在前人的研究成果的基礎(chǔ)上提出了快速計算DFT的算法，之后，又出現(xiàn)了各種各樣快速計算DFT的方法，這些方法統(tǒng)稱為快速傅里葉變換(Fast

FourierTransform)，簡稱為FFT。引言：離散傅里葉變換在實際應(yīng)用中是非常重要的快速傅里葉變換(FFT)是離散傅里葉變換(DFT)的快速算法它是DSP領(lǐng)域中的一項重大突破，它考慮了計算機和數(shù)字硬件實現(xiàn)的約束條件、研究了有利于機器操作的運算結(jié)構(gòu)，使DFT的計算時間縮短了1~2個數(shù)量級，還有效地減少了計算所需的存儲容量。FFT技術(shù)的應(yīng)用極大地推動了DSP的理論和技術(shù)的發(fā)展，成為數(shù)字信號處理強有力的工具。快速傅里葉變換(FFT)是離散傅里葉變換(DFT)的快速算法其中在導(dǎo)出FFT算法之前，先估計一下直接計算DFT所需計算量。DFT的定義其中在導(dǎo)出FFT算法之前，先估計一下直接計算DFT所需計算量將方程組寫成矩陣形式將DFT定義式展開成方程組將方程組寫成矩陣形式將DFT定義式展開成方程組同理用復(fù)數(shù)表示：用向量表示：同理用復(fù)數(shù)表示：用向量表示：從矩陣形式表示可以看出每計算一個X(k)值需要N次復(fù)乘法和(N-1)次復(fù)數(shù)加法，因而計算N個X(k)值，共需N2次復(fù)乘法和N(N-1)次復(fù)加法。每次復(fù)乘法包括4次實數(shù)乘法和2次實數(shù)加法，每次復(fù)加法包括2次實數(shù)加法，因此計算N點的DFT共需要4N2次實數(shù)乘法和(2N2+2N·(N-1))次實數(shù)加法。當N很大時，這是一個非常大的計算量。例如當N=1024，N2=1048576。在實際中，N往往是比較大的，因此有必要對DFT的計算予以改進。從矩陣形式表示可以看出每計算一個X(k)值需要N次復(fù)乘法和((1)對稱性或(2)周期性(3)可約性或(4)其它首先考察WNnk的一些特殊性質(zhì)：(1)對稱性或(2)周期性(3)可約性或(4)其它首先考察W§4.1

基2時間抽選法（庫里—圖基算法）一、基本原理：利用旋轉(zhuǎn)因子WNnk的對稱性和周期性，將一個長序列x(n)的DFT計算，在時域上按奇偶抽選分解成短序列的DFT來計算。設(shè)N＝2M，M為正整數(shù)。為推導(dǎo)方便，取N＝23＝8，即離散時間信號為x(n)={x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7)}將序列x(n)分為奇偶兩組，一組序號為偶數(shù)，另一組序號為奇數(shù)，即{x(0),x(2),x(4),x(6)|x(1),x(3),x(5),x(7)}分別表示為： g(r)=x(2r)——偶數(shù)項 h(r)=x(2r+1)——奇數(shù)項r=0,1,…,N/2-1§4.1

基2時間抽選法（庫里—圖基算法）一、基本原理：利因為WN2=WN/21，所以上式變?yōu)樯鲜街械腉(k)和H(k)都是N/2點的DFT。根據(jù)DFT的定義k=0,1,…,N/2-1(4.1)因為WN2=WN/21，所以上式變?yōu)樯鲜街械腉(k)和H(要用G(k)和H(k)來表達全部的X(k)值還必須考慮后半部分項數(shù)（k+N/2）。利用系數(shù)周期性，因為所以X(k)是N點序列，式4.1計算得到的只是前一半項數(shù)的結(jié)果k=0,1,…,N/2-1(4.2)將式4.1中的k用k+N/2代入，可得到要用G(k)和H(k)來表達全部的X(k)值還必須考慮后半部2點的DFT流程圖ab-1a-bWNka+bWNkWNk這樣就把一個N點的DFT分解成了兩個N/2點的DFT，只是最后求和的符號不同。式4.1與4.2的運算可用蝶形信號流圖來表示2點的DFT流程圖ab-1a-bWNka+bWNkW圖1N點的DFT分解成兩個N/2點DFT的的時間抽選流程圖N=8按照式4.1和式4.2可畫出下圖所示的信號流程圖。

N/2點DFTN/2點DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)G(1)G(2)G(3)H(1)H(2)H(9)X(1)=G(1)+WN1H(1)X(2)=G(2)+WN2H(2)X(3)=G(3)+WN3H(3)WN1WN2WN3-1-1-1X(5)=G(1)-WN1H(1)X(6)=G(2)-WN2H(2)X(7)=G(3)-WN3H(3)G(0)H(0)WN0-1X(0)=G(0)+WN0H(0)X(4)=G(0)-WN0H(0)圖1N點的DFT分解成兩個N/2點DFT的的時間抽選流程式4.1和式4.2把原N點DFT計算分解成兩個N/2點DFT計算。照此可進一步把每個N/2點DFT的計算再各分解成兩個N/4點DFT的計算。具體說來，是把{x(0)，x(2)，x(4)，x(6)}和{x(1)，x(3)，x(5)，x(7)}分為{x(0)，x(4)|x(2)，x(6)}和{x(1)，x(5)|x(3)，x(7)}。G(k)和H(k)分別計算如下:k=0,1,…,N/4-1(4.3)式4.1和式4.2把原N點DFT計算分解成兩個N/2點DFTk=0,1,…,N/4-1(4.4)k=0,1,…,N/4-1(4.5)k=0,1,…,N/4-1(4.6)k=0,1,…,N/4-1(4M(0)M(1)N(0)N(1)G(0)G(1)G(2)G(3)WN0WN2-1-1N/4點DFTx(0)x(4)x(2)x(6)N/4點DFT圖2N/2點的DFT分解成兩個N/4點DFT的的時間抽選流程圖N=8這樣，用式(4.3)～(4.6)就可計算圖1中的兩組N/2點DFT。圖2所示的是其中一組G(k)的計算。M(0)G(0)WN0-1N/4點x(0)N/4點圖2Nx(0)x(4)x(2)x(6)WN0WN2-1-1N/4點DFTN/4點DFTx(1)x(5)x(3)x(7)N/4點DFTN/4點DFTWN0WN2-1-1將圖1與圖2合并，便得到圖3所示的信號流程圖。X(0)X(1)X(2)X(3)WN0WN1WN2WN3-1-1-1-1X(4)X(5)X(6)X(7)G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)x(0)WN0-1N/4點N/4點x(1)N/4點N/4點W將2點DFT的信號流程圖移入圖3，得到圖4所示的8點時間抽選的完整的FFT流程圖。2點的DFT流程圖x(0)-1x(0)+x(4)WN0WN0x(4)x(0)-x(4)WN0N=8，圖3中N/4點的DFT就是2點的DFT。將2點DFT的信號流程圖移入圖3，得到圖4所示的8點時間抽選圖4基2時間抽選法8點FFT流程圖X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN0WN1WN2WN3-1-1-1-1WN0WN2-1-1WN0WN2-1-1x(1)x(5)x(3)x(7)x(0)x(4)x(2)x(6)WN0-1WN0-1WN0-1WN0-1圖4基2時間抽選法8點FFT流程圖X(0)WN0-1Wab-1a-bWNka+bWNkWNk從圖4中可看出幾個特點：(1)流程圖的每一級的基本計算單元都是一個蝶形；

(2)輸入x(n)不按自然順序排列，稱為“混序”排列，而輸出X(k)按自然順序排列，稱為“正序”排列，因而要對輸入進行“變址”；(3)由于流程圖的基本運算單元為蝶形，所以可以進行“同址”或“原位”計算。ab-1a-bWNka+bWNkWNk從圖4中可看出M=log2N由圖可看出完成一個蝶形計算需一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法二、運算量的減少（蝶形計算）任何一個N為2的整數(shù)冪（即N=2M）的DFT，都可以通過M次分解，最后成為2點的DFT來計算。M次分解構(gòu)成了從x(n)到X(k)的M級迭代計算，每級由N/2個蝶形組成。ab-1a-bWNka+bWNkWNk下圖表示了蝶形的一般形式表示。其輸入和輸出之間滿足下列關(guān)系：M=log2N由圖可看出完成一個蝶形計算需一次復(fù)數(shù)乘法和兩次大多數(shù)情況下復(fù)數(shù)乘法所花的時間最多，因此下面僅以復(fù)數(shù)乘法的計算次數(shù)為例來與直接計算進行比較。直接計算DFT需要的乘法次數(shù)為aD=N2，于是有即直接計算DFT所需復(fù)數(shù)乘法次數(shù)約為FFT的205倍。顯然，N越大，F(xiàn)FT的速度優(yōu)勢越大。復(fù)數(shù)乘法次數(shù)：例：當N=1024時，因此，完成N點的時間抽選FFT計算的總運算量為復(fù)數(shù)加法次數(shù)：大多數(shù)情況下復(fù)數(shù)乘法所花的時間最多，因此下面僅以復(fù)數(shù)乘法的計N所需復(fù)數(shù)乘法次數(shù)aD/aF直接計算DFT用FFT計算DFT24816326412825651210242048416642561024409616384655362621441048576419430414123280192448102423045120112644.04.05.48.012.821.436.664.0113.8204.8372.4不同N值所對應(yīng)的兩種計算方法的復(fù)數(shù)乘法次數(shù)和它們的比值N所需復(fù)數(shù)乘法次數(shù)aD/aF直接計算DFT用FFT計算DFTab-1a-bWNka+bWNkWNk三、同址(原位)計算圖4包含M級迭代運算，每級由N/2個蝶形計算構(gòu)成。蝶形計算的優(yōu)點是可進行所謂同址(原位)計算。首先每一個蝶形運算都需要兩個輸入數(shù)據(jù)，計算結(jié)果也是兩個數(shù)據(jù)，與其它結(jié)點的數(shù)據(jù)無關(guān)，其它蝶形運算也與這兩結(jié)點的數(shù)據(jù)無關(guān)。因此，一個蝶形運算一旦計算完畢，原輸入數(shù)據(jù)便失效了。這就意味著輸出數(shù)據(jù)可以立即使用原輸入數(shù)據(jù)結(jié)點所占用的內(nèi)存。原來的數(shù)據(jù)也就消失了。這樣輸出、輸入數(shù)據(jù)利用同一內(nèi)存單元的這種蝶形計算稱為同址計算。ab-1a-bWNka+bWNkWNk三、同址(原位-1WN0x(0)x(4)x(0)+x(4)WN0x(0)-x(4)WN0M(0)M(1)M(0)M(1)類似地，M(2)和M(3)中的x(2)和x(6)進入運算器進行蝶形運算后的結(jié)果也被送回到M(2)和M(3)保存，等等?，F(xiàn)在來考察第一級的計算規(guī)律設(shè)將輸入x(0)，x(4)，x(2)，x(6)，x(1)，x(5)，x(3)，x(7)分別存入計算機的存儲單元M(0),M(1),M(2),…，M(6)和M(7)中。首先，存儲單元M(0)和M(1)中的數(shù)據(jù)x(0)和x(4)進入運算器并進行蝶形運算，運算后的結(jié)果便可送到M(0)和M(1)存儲起來。-1WN0x(0)x(4)x(0)+x(4)WN0x(0第二級運算與第一級類似M(0)和M(2)存儲單元中的數(shù)據(jù)進行蝶形運算后的結(jié)果被送回M(0)和M(2)保存，M(1)和M(3)中的數(shù)據(jù)進行蝶形運算后送回M(1)和M(3)保存，等等。這樣一直到最后一級的最后一個蝶形運算完成?？梢钥闯?，每一級的蝶形的輸入與輸出在運算前后可以存儲在同一地址(原來位置上)的存儲單元中，這種同址運算的優(yōu)點是可以節(jié)省存儲單元，從而降低對計算機存儲量的要求或降低硬件實現(xiàn)的成本。第二級運算與第一級類似M(0)和M(2)存儲單元中的數(shù)據(jù)進M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)如圖所示的N點FFT計算，只需N個存儲存儲單元X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)WN0WN1WN2WN3-1-1-1-1WN0-1WN0-1WN0-1WN0-1WN0-1WN0-1WN2WN2-1-1M(0)M(0)M(0)M(0)如圖所示的N點FFT計算，只四、變址計算（倒序重排）從圖4所示的流程圖看出，同址計算要求輸入x(n)是“混序”排列的。所謂輸入為“混序”，并不是說輸入是雜亂無章的，實際上它是有規(guī)律的。如果輸入x(n)的序號用二進制碼來表示，就可以發(fā)現(xiàn)輸入的順序恰好是正序輸入的“碼位倒置”。下表2列出了這種規(guī)律。四、變址計算（倒序重排）從圖4所示的流程圖看出，同址計算要自然序列二進制表示碼位倒置混序x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(000)x(001)x(010)x(011)x(100)x(101)x(110)x(111)表2x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)x(000)x(100)x(010)x(110)x(001)x(101)x(011)x(111)自然序列二進制表示碼位倒置混序x(0)x(000)表2x(0存儲單元M(0)M(1)M(2)M(3)M(4)M(5)M(6)M(7)自然順序x(n)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)碼位倒置順序x(l)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)變址圖5碼位倒置的變址處理在實際運算中，按碼位倒置順序輸入數(shù)據(jù)x(n)，特別當N較大時，是很不方便的。因此，數(shù)據(jù)總是按自然順序輸入存儲，然后通過“變址”運算將自然順序轉(zhuǎn)換成碼位倒置順序存儲。實現(xiàn)這種轉(zhuǎn)換的程序可用圖5來說明。存儲單元M(0)M(1)圖中用n表示自然順序的標號，用l表示碼位倒置的標號當l＝n時，x(n)和x(l)不必互相調(diào)換。當l≠n時，必須將x(l)和x(n)互相調(diào)換，但只能調(diào)換一次，為此必須規(guī)定每當l>n時，要將x(l)和x(n)相互調(diào)換，即把原來存放x(n)的存儲單元中的數(shù)據(jù)調(diào)入存儲x(l)的存儲單元中，而把原來存儲x(l)的存儲單元中的數(shù)據(jù)調(diào)入到存儲x(n)的存儲單元中。這樣，按自然序輸入的數(shù)據(jù)x(n)經(jīng)過變址計算后變成了碼位倒置的排列順序，便可進入第一級的蝶形運算。

圖中用n表示自然順序的標號，用l表示碼位倒置的標號當l＝n時另外一些形式的時間抽選FFT算法流程圖對于任何流程圖，只要保持各節(jié)點所連支路及其傳輸系數(shù)不變，則不論節(jié)點位置怎樣排列，所得到的流程圖總是等效的，因而都能得到DFT的正確結(jié)果，只是數(shù)據(jù)的提取和存儲次序不同而已。把圖4中與x(4)水平相鄰的所有節(jié)點和與x(1)水平相鄰的所有節(jié)點交換，把與x(6)水平相鄰的所有節(jié)點和與x(3)水平相鄰的所有節(jié)點交換，而與x(0)、x(2)、x(5)和x(7)水平相鄰各節(jié)點位置不變，就可以從圖4得到圖6。圖6與圖4的區(qū)別只是節(jié)點的排列不同，而支路傳輸比，即WN的各次冪保持不變。顯然圖6所示流程圖的輸入是正序（自然順序）排列的，輸出是碼位倒置排列的，所以輸出要進行變址計算。另外一些形式的時間抽選FFT算法流程圖對于任何流程圖，只要保圖4基2時間抽選法8點FFT流程圖X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN0WN1WN2WN3-1-1-1-1WN0WN2-1-1x(1)x(5)x(3)x(7)WN0WN2-1-1x(0)x(4)x(2)x(6)WN0-1WN0-1WN0-1WN0-1圖4基2時間抽選法8點FFT流程圖X(0)WN0-1W圖6基2時間抽選法8點FFT流程圖（輸入正序）X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)WN0WN0WN0WN0-1-1-1-1WN0WN0-1-1x(4)x(5)x(6)x(7)WN2WN2-1-1x(0)x(1)x(2)x(3)WN0-1WN1-1WN2-1WN3-1圖6基2時間抽選法8點FFT流程圖（輸入正序）X(0)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN0WN0WN0WN0-1-1-1-1WN0WN0x(4)x(5)x(6)x(7)WN2WN2x(0)x(1)x(2)x(3)WN0WN1WN2WN3-1-1-1-1-1-1-1-1另一種形式的流程圖是將節(jié)點排列成輸入和輸出兩者都是正序排列，但這類流程圖不能進行同址計算，因而需要兩列長度為N的復(fù)數(shù)存儲器。X(0)WN0-1WN0x(4)WN2x(0)WN0WN1W其中r=0,1,…,N/2-1§4.2基2頻率抽選法（桑德—圖基算法）基2頻率抽選法是在頻域內(nèi)將X(k)逐次分解成奇偶序列，再進行DFT計算設(shè)N＝2M，M為正整數(shù)。為推導(dǎo)方便，取N=23＝8。將頻率偶奇分， 即X(k)={X(0),X(2),X(4),X(6),|X(1),X(3),X(5),X(7)}用X(2r)和X(2r+1)分別表示頻率的偶數(shù)項和奇數(shù)項， 則有其中r=0,1,…,N/2-1§4.2基2頻率抽其中g(shù)(n)=x(n)+x(n+N/2)n=0,1,…,N/2-1同理其中h(n)=x(n)-x(n+N/2)n=0,1,…,N/2-1(4.7)(4.8)上面兩式所表示的是N/2的DFT。在實際計算中，首先形成序列g(shù)(n)和h(n)，然后計算h(n)WNn，最后分別計算g(n)和h(n)WNn的N/2點DFT，便得到偶數(shù)輸出點和奇數(shù)輸出點的DFT。計算流程圖如圖7所示。其中g(shù)(n)=x(n)+x(n+N/2)nN/2點DFTN/2點DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)WN0WN1WN2WN3-1-1-1-1圖7N點的DFT分解成兩個N/2點DFT的的頻率抽選流程圖N=8N/2點N/2點x(0)X(0)WN0-1圖7N點的DFab-1a-bWNka+bWNkWNkaa+bb-1(a–b)WNkWNk時間抽選蝶形單元頻率抽選蝶形單元與時間抽選的FFT算法一樣，圖7所示的流程圖的基本運算也是蝶形運算，但是頻率抽選與時間抽選中的蝶形單元有所不同。N是2的整數(shù)冪，所以N/2仍然是偶數(shù)。這樣可以將N/2點DFT的輸出再分為偶數(shù)組和奇數(shù)組，即將N/2點的DFT計算進一步分解為兩個N/4點的DFT計算，以此類推直到不能分解。如圖8ab-1a-bWNka+bWNkWNkaa+bb圖8基2頻率抽選法8點FFT流程圖X(0)X(4)X(2)X(6)WN0WN1WN2WN3-1-1-1-1WN0WN2-1-1x(4)x(5)x(6)x(7)WN0WN2-1-1x(0)x(1)x(2)x(3)WN0-1WN0-1WN0-1WN0-1X(1)X(5)X(3)X(7)圖8基2頻率抽選法8點FFT流程圖X(0)WN0-1W頻率抽選與時間抽選的異同點：比較圖4與圖8可知，頻率抽選FFT算法的計算量與時間抽選FFT算法的計算量相同。與時間抽選算法一樣，頻率抽選FFT算法也具有同址（原位）計算的優(yōu)點。但是，與時間抽選不同的是，頻率抽選FFT算法的信號輸入為正序排列，輸出為碼位倒置排列，因此輸出要進行變址計算。頻率抽選與時間抽選的異同點：比較圖4與圖8可知，頻率抽選FFk=0,1,…,N/2-1在時間抽選FFT法中，第一次分解得到G(k)、H(k)分別為輸入序列偶數(shù)點和奇數(shù)點的N/2點DFT(4.1)(4.2)§4.3

IFFT的計算方法（快速傅里葉反變換）一、IFFT算法k=0,1,…,N/2-1在時間抽選FFT法中，第一次k=0,1,…,N/2-1根據(jù)上式可畫出蝶形圖G(k)X(k)H(k)-1X(k+N/2)以此類推可求出x(n)的各點，反變換流程如圖9根據(jù)式4.1與4.2可得到k=0,1,…,N/2-1根據(jù)上式可畫出蝶形圖G(k)圖98點IFFT流程圖1/21/21/21/2X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1x(1)x(5)x(3)x(7)-1-1x(0)x(4)x(2)x(6)-1-1-1-11/21/21/21/21/21/21/21/2圖98點IFFT流程圖1/2X(0)-1-1x(1)比較上面兩式，可以看出，只要把DFT公式中的系數(shù)WNkn改為WN-kn

，并乘以系數(shù)1/N，將X(k)作為輸入序列，將x(n)作為輸出序列，就可用FFT算法來計算IDFT，這就得到了IFFT的算法。（例圖10）在IFFT計算中經(jīng)常把常量1/N分解成M個1/2連乘，即1/N＝(1/2)M，并且在M級的迭代運算中，每級的運算都分別乘上一個1/2因子。二、利用FFT求IFFTFFT算法同樣可以應(yīng)用于IDFT的計算。已知DFT和IDFT公式為比較上面兩式，可以看出，只要把DFT公式中的系數(shù)WNkn改x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)WN0WN-1WN-2WN-3-1-1-1-1WN0WN-2-1-1X(4)X(5)X(6)X(7)WN0WN-2-1-1WN0-1WN0-1WN0-1WN0-11/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/2圖108點IFFT流程圖（例：利用頻率抽取FFT—圖8）x(0)X(0)WN0-1WN0-1X(4)WN0-1WN0IFFT算法分類當把時間抽選FFT算法用于IFFT計算時，由于原來輸入的時間序列x(n)現(xiàn)在變?yōu)轭l率序列X(k)，原來是將x(n)偶奇分的，而現(xiàn)在變成對X(k)進行偶奇分了，因此這種算法改稱為頻率抽選IFFT算法。類似地，當把頻率抽選FFT算法用于計算IFFT時，應(yīng)該稱為時間抽選IFFT算法。（圖10為時間抽選8點IFFT算法）IFFT算法分類當把時間抽選FFT算法用于IFFT計算時，與DFT比較，只需將X*(k)作為輸入序列就可直接利用FFT流程具體步驟如下：1、求X(k)的共軛X*(k)，取共軛只需將虛部乘以(-1)2、以X*(k)作為輸入序列，直接調(diào)用FFT程序，計算得到Nx*(n)3、對計算結(jié)果取共軛并乘以1/N即得到x(n)取共軛法：對DFT