《《快速傅立葉變換》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《快速傅立葉變換》PPT課件.ppt（96頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第5章快速傅里葉變換,5.1引言.直接計(jì)算DFT的問(wèn)題及改進(jìn)的途徑5.2按時(shí)間抽?。―IT）的基2-FFT算法5.3按頻率抽取（DIF）的基2-FFT算法5.4離散傅立葉反變換(IDFT)的快速算法FFT5.5其他FFT快速算法5.6基于MATALAB的FFT快速算法,5.1.1引言在上一章中，我們引入了離散傅立葉變換(FFT)這個(gè)概念。通過(guò)這個(gè)變換我們可知，有限長(zhǎng)序列在頻域中也同樣可以離散化成一個(gè)有限長(zhǎng)序列。那么信號(hào)在時(shí)域和頻域中，都變成了數(shù)字信號(hào)，則對(duì)信號(hào)的分析與處理帶來(lái)很大的方便。所以說(shuō)在數(shù)字信號(hào)處理中起著極其重要的作用，如：信號(hào)頻譜分析，系統(tǒng)的分析設(shè)計(jì)與實(shí)現(xiàn)都會(huì)用到。但是直接用進(jìn)行頻譜分析與信號(hào)的實(shí)時(shí)處理計(jì)算量太大而不切實(shí)際，這也是很長(zhǎng)一段時(shí)間內(nèi)沒(méi)有廣泛應(yīng)用的原因。1965年J.W.Cooley與J.W.Turkey提出了一種計(jì)算的快速算法，即現(xiàn)在所說(shuō)的庫(kù)利—圖基算法，后來(lái)又有桑德—圖基等算法的出現(xiàn)，加上當(dāng)時(shí)電子數(shù)字計(jì)算機(jī)技術(shù)的發(fā)展，很快就發(fā)展與完善了一套高效的快速算法，也就是現(xiàn)在普遍稱(chēng)之為FFT（FastFourierTransform）的算法。,5.1引言.直接計(jì)算DFT的問(wèn)題及改進(jìn)的途徑,,,,本章的主要內(nèi)容則是若干計(jì)算離散傅立葉變換的快速算法，包括：基—2（包括按時(shí)間抽選及按頻率抽選）算法，快速算法，分裂基算法、混合基算法、線性調(diào)頻變換算法及相關(guān)的MATLAB仿真。,5.1.2直接計(jì)算的問(wèn)題及改進(jìn)的途徑一、直接計(jì)算的問(wèn)題長(zhǎng)度為N的有限長(zhǎng)序列的N點(diǎn)離散傅立葉變換對(duì)為：,k=0,1,…,N-1,（5-1-1）,反變換（IDFT）為,n=0,1,…,N-1,（5-1-2）,,由上面的表達(dá)式可以看出二者的差別只在于WN的指數(shù)符號(hào)不同，以及差一個(gè)常數(shù)乘因子1/N，所以所以我們只需討論其中一個(gè)式子的運(yùn)算量即可，下面我們選擇（5-1-1）式。下面我們只討論DFT的運(yùn)算量。一般情況下，時(shí)間序列x(n)及其頻譜序列X(k)都為復(fù)序列，我們現(xiàn)在就討論最一般的情況。由（5-1-1）式可以看出每計(jì)算一個(gè)X(k)值，需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法。因?yàn)閺?fù)數(shù)運(yùn)算實(shí)際上是由實(shí)數(shù)運(yùn)算來(lái)完成的，1次復(fù)乘包含4次實(shí)乘，2次實(shí)加；一次復(fù)加包含2次實(shí)加。計(jì)算X(k)的一個(gè)值計(jì)算量為：4N次實(shí)乘，4N-2次實(shí)加。那么計(jì)算出N點(diǎn)X(k)序列需要的計(jì)算量為：4N2次實(shí)乘，4N2-2N次實(shí)加。,從上面的統(tǒng)計(jì)可以看到，直接計(jì)算DFT，乘法次數(shù)和加法次數(shù)都是和N2成正比的，當(dāng)然，這不是十分精確的關(guān)系，如系數(shù)W0N=1，WNＮ／２=-1，WNN/4=-j等就不需乘法。當(dāng)很N大時(shí)，這些特例所占的比例基本可以忽略?？梢?jiàn)，當(dāng)N很大時(shí)運(yùn)算量會(huì)急劇增加，所以我們要想在實(shí)際中應(yīng)用，則需要在計(jì)算方法上加以改進(jìn)。,二、改進(jìn)途徑首先，因?yàn)檫\(yùn)算量與N2成正比，如果把較大數(shù)N點(diǎn)的DFT轉(zhuǎn)換成小點(diǎn)的DFT，則可以使運(yùn)算量相應(yīng)的減少。另外我們?cè)俅斡^察一下DFT的運(yùn)算會(huì)發(fā)現(xiàn)因子有明顯的周期性與對(duì)稱(chēng)性及可約性。表現(xiàn)為：,,,,,快速傅里葉變換算法（FFT）算法就是基于這些思想，同時(shí)利用因子的特征發(fā)展起來(lái)的。,,,,,,5.2按時(shí)間抽?。―IT）的基-2FFT算法,5.2.1算法原理按時(shí)間抽取（DIT）的基-2FFT算法，又稱(chēng)之為庫(kù)利—圖基算法，是很多離散傅立葉變換快速算法之一。設(shè)序列x(n)長(zhǎng)度為N，且滿足N=2L，L為正整數(shù)(若不滿足該條件，則在序列后面加上若干零值已達(dá)到這個(gè)條件)。按n的奇偶,x(n)分解為兩個(gè)N/2點(diǎn)的子序列（即大點(diǎn)數(shù)DFT化成小點(diǎn)數(shù)DFT,通過(guò)求子序列的DFT而實(shí)現(xiàn)計(jì)算整個(gè)序列的DFT）：則序列x(n)的N點(diǎn)DFT,,由于，故上式可表示成,（5-2-1）,式中，X1(k)與X2(k)分別是x1(r)及x2(r)的N/2點(diǎn)DFT：,需要注意的是：X1(k)與X2(k)分別是x1(r)及x2(r)的N/2點(diǎn)DFT,以N/2為周期。所以由（5-2-1）式僅可以得到N點(diǎn)序列X(k)的前N/2點(diǎn)，則X(k)的后N/2點(diǎn)為：,由,的周期性及,得：,（5-2-2）,綜合上面的結(jié)果，x(n)的N點(diǎn)DFT可以由x(n)奇偶子序列,、,的N/2點(diǎn)的DFT表示：,（5-2-3）,至此，也完成了N點(diǎn)DFT到N/2點(diǎn)DFT的轉(zhuǎn)換。（5-2-3）式的運(yùn)算關(guān)系可以用下面的一個(gè)流程圖來(lái)描述：,圖5-1按時(shí)間抽取算法基本蝶形運(yùn)算流圖,因?yàn)榱鞒虉D的外形像一只蝴蝶，所以稱(chēng)之為蝶形圖，由圖可見(jiàn)，一個(gè)蝶形圖包含1次復(fù)乘，2次復(fù)加?，F(xiàn)在來(lái)看一下，經(jīng)過(guò)第一次轉(zhuǎn)換以后計(jì)算量是否減少了，又減少了多少？由（5-2-3）式可以看出，計(jì)算一個(gè)N點(diǎn)的DFT，首先需要計(jì)算2個(gè)N/2點(diǎn)的DFT。一個(gè)N/2點(diǎn)的DFT需要N2/4次復(fù)乘，N/2(N/2-1)次復(fù)加，兩個(gè)N/2點(diǎn)DFT共需2(N/2)2=N2/2次復(fù)數(shù)乘法和N(N/2-1)次復(fù)數(shù)加法。將2個(gè)N/2點(diǎn)的DFT轉(zhuǎn)換成一個(gè)N點(diǎn)的DFT還需要N/2個(gè)蝶形運(yùn)算（即N/2次復(fù)乘，N次復(fù)加）。綜合以上，可見(jiàn)現(xiàn)在所需要的計(jì)算量為：(N2/2)+(N/2)=N(N+1)/2次復(fù)數(shù)乘法和N(N/2-1)+N=N2/2次復(fù)數(shù)加法。,當(dāng)N很大時(shí)(N2/2)+(N/2)≈N2/2?？梢?jiàn)，通過(guò)這樣分解后計(jì)算一個(gè)N點(diǎn)的DFT則需要N2/2次復(fù)加與N2/2次復(fù)乘。與直接計(jì)算N點(diǎn)的DFT計(jì)算量相比幾乎節(jié)省了一半的計(jì)算量，特別是當(dāng)N較大時(shí)，這種分解帶來(lái)的效益是相當(dāng)可觀的。所以可以對(duì)N/2點(diǎn)的子序列進(jìn)一步分解，直至不能分解為止。下面我們以N=8為例，完整的介紹這種快速算法及相應(yīng)的流程圖。當(dāng)N=8時(shí)第一次分解后，,相應(yīng)的：,第一次分解后的流程圖如下：,圖5-2按時(shí)間抽取將一個(gè)N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT（N=8）,第二次按照的奇偶得將每個(gè)N/2=4點(diǎn)序列分解成兩個(gè)N/4=2點(diǎn)的序列，設(shè)：,則：,其中：,同理,由和的周期性和的對(duì)稱(chēng)性可得到：,總結(jié)以上可得：,（5-2-4）,其中：,把N/2點(diǎn)序列分解成2個(gè)N/4點(diǎn)的DFT的過(guò)程如下面的流程圖所示：,圖5-3N/2點(diǎn)DFT分解為兩個(gè)N/4點(diǎn)DFT,與都是2點(diǎn)的DFT不能再繼續(xù)分解，直接計(jì)算可知：,同理可以得出：,（5-2-5）,其中：,計(jì)算得出：,當(dāng)N=8時(shí)，一個(gè)完整的DIT—FFT運(yùn)算流圖如下：,圖5-4N=8按時(shí)間抽取的FFT運(yùn)算流圖,5.2.2運(yùn)算量的比較觀察上面的運(yùn)算流圖可知：當(dāng)N=2L時(shí)，其運(yùn)算流圖有L級(jí)蝶形圖構(gòu)成，每一級(jí)均有N/2個(gè)蝶形運(yùn)算，一個(gè)蝶形運(yùn)算需要1次復(fù)乘，2次復(fù)加。則L級(jí)的蝶形圖共需復(fù)乘：次；復(fù)加：次。直接計(jì)算DFT所需運(yùn)算：復(fù)乘，次；復(fù)加：由于計(jì)算機(jī)上乘法運(yùn)算所需的時(shí)間比加法運(yùn)算所需的時(shí)間多得多，故以乘法為例，直接DFT復(fù)數(shù)乘法次數(shù)是,FFT復(fù)數(shù)乘法次數(shù),直接計(jì)算DFT與FFT算法的計(jì)算量之比為：,,,,,,,,例5-1用FFT算法處理一幅NN點(diǎn)的二維圖像，如用每秒可做10萬(wàn)次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問(wèn)需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？解當(dāng)N=1024點(diǎn)時(shí)，F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘法約為次，僅為直接計(jì)算DFT所需時(shí)間的10萬(wàn)分之一。即原需要3000小時(shí)，現(xiàn)在只需要2分鐘。,5.2.3時(shí)間抽取算法FFT（DIT—FFT）的運(yùn)算特點(diǎn)：一、原位運(yùn)算（同址運(yùn)算）當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，每一級(jí)運(yùn)算的結(jié)果仍然儲(chǔ)存在同一組存儲(chǔ)器中，直到最后輸出，中間無(wú)需其它存儲(chǔ)器，這叫原位計(jì)算。從圖5-4可以看出這種運(yùn)算是很有規(guī)律的，其每級(jí)（每列）計(jì)算都是由N/2個(gè)蝶形運(yùn)算構(gòu)成的，每一個(gè)蝶形結(jié)構(gòu)完成下述基本迭代運(yùn)算：,,（5-2-6）,式中，m表示第m列迭代，i,j則分別為該蝶形單元兩個(gè)輸入數(shù)據(jù)所在行數(shù)。式（5-2-6）的蝶形運(yùn)算如圖5-6所示。,,圖5-6按時(shí)間抽取算法基本蝶形運(yùn)算單元,由上面完整的運(yùn)算流程圖5-4可以看出，第m級(jí)蝶形運(yùn)算的輸出數(shù)據(jù)僅與該級(jí)蝶形運(yùn)算的輸入數(shù)據(jù)有關(guān)，與前m-1級(jí)蝶形的輸入數(shù)據(jù)無(wú)關(guān)，且第m-1級(jí)蝶形運(yùn)算的輸出數(shù)據(jù)為第m級(jí)蝶形運(yùn)算的輸入數(shù)據(jù)。某任何一個(gè)蝶形運(yùn)算的兩個(gè)輸入節(jié)點(diǎn)i和j的節(jié)點(diǎn)變量進(jìn)行蝶形運(yùn)算后，得到結(jié)果為該蝶形運(yùn)算兩個(gè)輸出節(jié)點(diǎn)，i,j兩節(jié)點(diǎn)的節(jié)點(diǎn)變量，而和其他節(jié)點(diǎn)變量無(wú)關(guān)，因而可以采用原位運(yùn)算。,例如，N=8的FFT運(yùn)算，輸入x(0)，x(4)，x(2)，x(6)…，x(7)可分別存入A(1)，A(2)，…，A(8)這8個(gè)存儲(chǔ)單元中，在第一級(jí)運(yùn)算中，首先是存儲(chǔ)單元A(1)，A(2)中x(0)，x(4)進(jìn)入蝶形運(yùn)算，x(0)，x(4)輸入運(yùn)算器后，其數(shù)值不再需要保存，因此蝶形運(yùn)算的結(jié)果可仍然送回存儲(chǔ)單元A(1)，A(2)中保存，然后A(3)，A(4)中x(2)，x(6)再進(jìn)入蝶形運(yùn)算，其結(jié)果再送回A(3)，A(4)，一直到算完A(7)，A(8)，則完成了第一級(jí)運(yùn)算過(guò)程。第二級(jí)運(yùn)算仍可采用這種原位的方式，但是進(jìn)入蝶形結(jié)的組合關(guān)系不同，首先進(jìn)入蝶形結(jié)的是A(1)、A(3)存儲(chǔ)單元中的數(shù)據(jù)，,運(yùn)算結(jié)果仍可送回A(1)、A(3)保存，然后進(jìn)入蝶形結(jié)的是A(2)、A(4)…，依此類(lèi)推，每一級(jí)運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)算結(jié)構(gòu)可節(jié)省存儲(chǔ)單元，降低設(shè)備成本，還可節(jié)省找地址的時(shí)間。那么進(jìn)行N點(diǎn)的FFT運(yùn)算，只需要N個(gè)寄存器存儲(chǔ)節(jié)點(diǎn)變量及N/2個(gè)寄存器存儲(chǔ)N/2系數(shù)，共N+N/2個(gè)存儲(chǔ)單元即可。,二、輸入、輸出序列的倒位序規(guī)律由流程圖可以看出，當(dāng)進(jìn)行原位運(yùn)算時(shí)，發(fā)現(xiàn)當(dāng)運(yùn)算完成后，F(xiàn)FT的輸出X(k)按自然順序排列在存儲(chǔ)單元中，即按X(0)，X(1)，…，X(7)的順序排列，但是這時(shí)輸入x(n)卻不是按自然順序存儲(chǔ)的，而是按x(0)，x(4)，…，x(7)的順序存入存儲(chǔ)單元，看起來(lái)好像是“混亂無(wú)序”的，實(shí)際上是有規(guī)律的，我們稱(chēng)之為倒位序。當(dāng)用二進(jìn)制表示這個(gè)順序時(shí)，它正好是“碼位倒置”的順序。例如，原來(lái)的自然順序應(yīng)是x(1)的地方，現(xiàn)在放著x(4)，用二進(jìn)制碼表示這一規(guī)律時(shí)，則是在x(001)處放著x(100),x(011)處,放著x(110)。即將自然順序的二進(jìn)制碼位倒置過(guò)來(lái)，第一位碼變成最末位碼，這樣倒置以后的順序正是輸入所需要的順序。下表列出N=8時(shí)按碼位倒置規(guī)律所得的順序，其結(jié)果與按時(shí)間抽取FFT流圖中的輸入順序是一致的。需要注意的是當(dāng)進(jìn)行原位運(yùn)算時(shí)，輸入輸出序列為倒位序的關(guān)系，若不為原位運(yùn)算，則這種關(guān)系不一定成立。在實(shí)際運(yùn)算中，一般直接將輸入數(shù)據(jù)x（n）按碼位倒置的順序排好輸入很不方便，總是先按自然順序輸入存儲(chǔ)單元，然后再通過(guò)變址運(yùn)算將自然順序的存儲(chǔ)轉(zhuǎn)換成碼位倒置順序的存儲(chǔ)，然后進(jìn)行FFT的原位計(jì)算。目前有許多通用DSP芯片支持這種碼位倒置的尋址功能。,表5-1N=8時(shí)的自然順序二進(jìn)制數(shù)和相應(yīng)的倒位序二進(jìn)制數(shù),三、蝶距,設(shè)N=2L則整個(gè)運(yùn)算流圖中包含L級(jí)蝶形運(yùn)算，每一級(jí)則有N/2個(gè)蝶形單元。蝶距即每個(gè)蝶形單元兩個(gè)輸入（出）節(jié)點(diǎn)的序號(hào)差。以N=8為例，共包含3級(jí)蝶形運(yùn)算，每一級(jí)蝶形單元的蝶距如下：蝶距：第一級(jí)，1，21-1=20第二級(jí)，2，22-1=21第三級(jí)，4，23-1=22可以觀察得出：第m級(jí)蝶形單元的蝶距為：2m-1,四、旋轉(zhuǎn)因子,由算法原理過(guò)程可知，若N=2L則共有L級(jí)蝶形運(yùn)算，各級(jí)蝶形運(yùn)算中旋轉(zhuǎn)因子分別如下：,,第L級(jí)：,第L-1級(jí)：,第L-2級(jí)：,???第1級(jí)：可見(jiàn)，第m級(jí)蝶形運(yùn)算中旋轉(zhuǎn)因子為：,即：,5.2.4按時(shí)間抽取的FFT算法的其他形式流圖顯然，對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連的支路及傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效的，所得最后結(jié)果都是x(n)的DFT的正確結(jié)果，只是數(shù)據(jù)的提取和存放的次序不同而已。這樣就可得到按時(shí)間抽取的FFT算法的若干其他形式流圖。將圖5-4中和x(4)水平相連的所有節(jié)點(diǎn)和x(1)水平相連的所有節(jié)點(diǎn)位置對(duì)調(diào)，再將和x(6)水平相連的所有節(jié)點(diǎn)與和x(3)水平相連的所有節(jié)點(diǎn)對(duì)調(diào)，其余諸節(jié)點(diǎn)保持不變，可得圖5-7的流圖。圖5-7與圖5-4的蝶形相同，運(yùn)算量也一樣，不同點(diǎn)是：,①數(shù)據(jù)存放的方式不同，圖5-4是輸入倒位序、輸出自然順序，圖5-8是輸入自然順序、輸出倒位序；②取用系數(shù)的順序不同，圖5-4的最后一列是按的順序取用系數(shù)，且其前一列所用系數(shù)是后一列所用系數(shù)中具有偶數(shù)冪的那些系數(shù)（例如）；圖5-7最后一列是按的順序取用系數(shù)，且其前一列所用系數(shù)是后一列所用系數(shù)的前一半，這種流圖是最初由庫(kù)利和圖基給出的時(shí)間抽取法。經(jīng)過(guò)簡(jiǎn)單變換，也可得輸入與輸出都是按自然順序排列的流圖以及其他各種形式的流圖。,圖5-7按時(shí)間抽取、輸入自然順序、輸出倒位序的FFT流圖,前面的圖5-4、5-7進(jìn)行各列計(jì)算時(shí)，因?yàn)楦鞔鎯?chǔ)器的取數(shù)與存數(shù)順序不同，所以都需要隨機(jī)存儲(chǔ)器。當(dāng)沒(méi)有隨機(jī)存儲(chǔ)器時(shí)，圖5-8、5-9就特別有用，因?yàn)楦骷?jí)的幾何形狀完全一樣，僅僅是級(jí)與級(jí)之間所乘的系數(shù)不同，這就可以按順序存取數(shù)據(jù)。,圖5-8按時(shí)間抽取，各級(jí)具有相同幾何形狀，輸入自然順序、輸出倒位序的FFT流圖,圖5-9按時(shí)間抽取，各級(jí)具有相同幾何形狀，輸入倒位序、輸出自然順序的FFT流圖,5.3按頻率抽?。―FT）的基-2FFT算法,前一節(jié)提到的是在時(shí)域內(nèi)將序列按照n的奇偶把大N點(diǎn)的DFT轉(zhuǎn)換成小點(diǎn)DFT的快速算法。與之相對(duì)應(yīng)的，基—2算法中還有一種FFT算法，就是在頻域中將按照k的奇偶劃分成小點(diǎn)子序列的快速算法。這一算法是1966年桑德提出的，又稱(chēng)之為桑德—圖基算法。,5.3.1算法原理設(shè)N=2L，L為正整數(shù)(若不滿足該條件，則在序列后面加上若干零值已達(dá)到這個(gè)條件)。則的偶數(shù)項(xiàng)與奇數(shù)項(xiàng)分別為：,因?yàn)椋?,,，,,則上式可以改寫(xiě)為,令(2)中,則：,,,,,（5-3-1）,同理：,令（2）中,有：,則：,（5-3-2）,由以上過(guò)程，將,第一次按k的奇偶分解后:,,（5-3-3）,若令：,則：,（5-3-4）,（5-3-4）式的運(yùn)算可由下圖的蝶形運(yùn)算圖來(lái)描述：,圖5-10按頻率抽選的基本蝶形運(yùn)算圖,至此我們就把N點(diǎn)的DFT分解成兩個(gè)N/2點(diǎn)的DFT運(yùn)算，下圖以N=8為例描述出了第一步的分解過(guò)程。,圖5-11按頻率抽選第一步分解的蝶形圖,與DIT—FFT的算法過(guò)程類(lèi)似，我們?cè)龠M(jìn)一步將兩個(gè)N/2點(diǎn)的DFT轉(zhuǎn)換為四個(gè)N/4點(diǎn)的DFT。按照,的奇偶得將,，,分解成兩個(gè)N/4=2點(diǎn)的序列，,設(shè)：,則：,同理：,經(jīng)過(guò)變量代換有,令,可見(jiàn)：,同樣可得：,（5-3-5）,,令：,（5-3-6）,可見(jiàn)：,,至此我們就完成了第二步的分解，當(dāng)N=8時(shí)，整個(gè)的分解過(guò)程所對(duì)應(yīng)的蝶形流程圖如下圖所示。,圖5-12按頻率抽選的完整的蝶形圖,5.3.2與DIT—FFT算法比較一、計(jì)算量由流程圖可以看出N=2L的FFT運(yùn)算需要L級(jí)蝶形運(yùn)算，每一個(gè)蝶形有N/2個(gè)蝶形單元，每個(gè)蝶形單元需要2次復(fù)加，1次復(fù)乘，所以N=2L點(diǎn)FFT運(yùn)算共需要復(fù)乘：,復(fù)加：,與DIT—FFT算法運(yùn)算量相同,二、基本蝶形圖按頻率抽取算法基本蝶形運(yùn)算流圖如下：,圖5-13按頻率抽取算法基本蝶形運(yùn)算流圖,與前面一節(jié)中所講的按時(shí)間抽取算法基本蝶形運(yùn)算流圖相比可以看到：二者所需的運(yùn)算量相同，且所主要講得兩種快速算法的蝶形流程圖都具有原位運(yùn)算的特點(diǎn)，所以所需的寄存器的個(gè)數(shù)都為：N+N/2個(gè)。不同點(diǎn)在于：DIT—FFT的基本蝶形運(yùn)算為先復(fù)乘后復(fù)加，DIF—FFT的基本蝶形運(yùn)算為先復(fù)加后復(fù)乘。,三、倒位序規(guī)律觀察整個(gè)的蝶形運(yùn)算流圖會(huì)發(fā)現(xiàn)當(dāng)DIF—FFT算法是原位運(yùn)算時(shí)，輸入為自然順序，輸出為倒位序，原因則是多次按k的奇偶將X(k)分成子序列的結(jié)果。,四、旋轉(zhuǎn)因子,由算法原理過(guò)程可知，若N=2L則共有L級(jí)蝶形運(yùn)算，各級(jí)蝶形運(yùn)算中旋轉(zhuǎn)因子,第1級(jí)：,第2級(jí)：,第3級(jí)：,分別如下：,???第L級(jí)：,可見(jiàn)，第m級(jí)蝶形運(yùn)算中旋轉(zhuǎn)因子,為：,,五、轉(zhuǎn)置定理觀察DIT—FFT、DIF—FFT的完整蝶形圖及基本蝶形圖我們會(huì)發(fā)現(xiàn)：如果把DIF—FFT的流程圖翻一個(gè)面，并倒轉(zhuǎn)信號(hào)的流向和變換一下輸入輸出，就可以得到DIT—FFT的流圖，即二者的流圖是互為轉(zhuǎn)置的關(guān)系。一種DIT—FFT的流圖就對(duì)應(yīng)一種DIF—FFT流圖。,5.4離散傅立葉反變換（IDFT）的快速算法IFFT,前兩節(jié)內(nèi)容討論了DFT的快速算法，對(duì)于IDFT來(lái)說(shuō)這些快速算法是否也適用呢？首先對(duì)DFT的與IDFT在定義式上進(jìn)行比較。長(zhǎng)度為N的有限長(zhǎng)序列,的,點(diǎn)離散傅立葉變換對(duì)為：,：,,（5-4-1）,：,,（5-4-2）,由定義式可見(jiàn)，DFT與IDFT兩者非常相似，僅有以下三點(diǎn)差別：①I(mǎi)DFT比DFT多了一個(gè)常系數(shù)因子,②旋轉(zhuǎn)因子DFT為,，IDFT為,③DFT輸入變量為,，IDFT為,，相差一個(gè)負(fù)號(hào),從以上特點(diǎn)，要想由FFT算法得到IFFT算法，需要作以下改變：①將FFT算法中旋轉(zhuǎn)因子,改為,②在FFT的每級(jí)蝶形運(yùn)算中都分別乘以因子1/2③輸入變量的改變，對(duì)整體算法的實(shí)現(xiàn)影響不大，但算法名稱(chēng)有相應(yīng)變化。如：在FFT算法中本來(lái)是按時(shí)間抽選的，現(xiàn)在經(jīng)過(guò)上述改變以后對(duì)應(yīng)的則是按頻率抽選的IFFT算法。,上述IFFT算法雖然已經(jīng)很簡(jiǎn)單了，但是仍需要對(duì)FFT算法程序及參數(shù)進(jìn)行一些改動(dòng)，那么我們是否可以直接運(yùn)用FFT來(lái)實(shí)現(xiàn)IFFT呢？,下面我們對(duì)DFT的定義式做一些變換有：,由上面表達(dá)式可以看到，我們完全不需要改動(dòng)FFT程序，而是直接利用它作IFFT。分以下三個(gè)步驟：,①將X（k）取共軛（虛部乘以-1）②然后直接作FFT③最后再對(duì)FFT的運(yùn)算結(jié)果取共軛并乘以1/N，得x（n）下面我們僅畫(huà)出其中一種IFFT算法流圖：,圖5-14按時(shí)間抽取算法IFFT蝶形運(yùn)算流圖(N=8),5.5其他FFT快速算法,在前幾節(jié)中我們討論的均為序列長(zhǎng)為N=2L的情況，但在實(shí)際中序列的點(diǎn)長(zhǎng)N則不一定是2的整數(shù)次冪，可能為一些可分解的復(fù)合數(shù)，甚至為一些素?cái)?shù)。對(duì)于這種情況，可以有以下的解決方法。1）直接將序列后補(bǔ)零值，使N成為2的整數(shù)次冪，由前面所講知識(shí)我們可知在序列后補(bǔ)零不會(huì)影響序列的頻譜。,只是頻譜的采樣點(diǎn)數(shù),增加了，當(dāng)然，采樣點(diǎn)的位置也,有相應(yīng)的變化。,但是，仍然存在一些問(wèn)題。如果N=56，不是2的整數(shù)次冪，可以在其后加8個(gè)零值點(diǎn)就可以使N成為26，所加的零值點(diǎn)比較少。如果N=9000，那么就需要在后面再補(bǔ)上7389個(gè)零值點(diǎn)才能使N成為2的整數(shù)次冪。首先這樣補(bǔ)很多個(gè)零值點(diǎn)很不經(jīng)濟(jì)，當(dāng)N變得很大時(shí)，計(jì)算量也隨之驟增。其次，上例中由56點(diǎn)增加到64點(diǎn)，采樣點(diǎn)則由2π/56的整數(shù)倍變?yōu)?π/64的整數(shù)倍，對(duì)應(yīng)的絕對(duì)頻率也由fs/56的整數(shù)倍變?yōu)閒s/64的整數(shù)倍。在許多場(chǎng)合這種處理是可接受的，但不適應(yīng)對(duì)某些特殊頻率點(diǎn)有特別要求的場(chǎng)合。所以需要另辟途徑。,2）當(dāng)N≠2L時(shí)，且為復(fù)合數(shù)，則可以用一種叫做混合基的FFT算法。3）當(dāng)N為素?cái)?shù)時(shí)，則可以用以后所提到的線性調(diào)頻Z變換FFT算法。5.5.1混合基算法一、算法原理若N是一個(gè)復(fù)合數(shù)，即它可以分解成一些因子的乘積，則可以用FFT的一般算法，即混合基FFT算法，如庫(kù)利-圖基（CooleyTukey）算法，而基—2算法只是這種一般算法的特例。,不管采用什么方法，計(jì)算DFT的高效算法是把計(jì)算長(zhǎng)度為N的序列的DFT逐次分解成計(jì)算長(zhǎng)度較短序列的DFT。這是很多高效算法的標(biāo)準(zhǔn)方法和基本原理。,設(shè)序列x(n)的長(zhǎng)度為,,(,)。則,示為,（,）也就是說(shuō)把原來(lái),標(biāo)示為矩陣的形式，,為列序號(hào)，,為行序號(hào)。,為列的數(shù)目，,為行的數(shù)目。,可以表,序列的序號(hào),設(shè)：N=15=,,=35，,=3，,=5，按照上述方法，則可以將,寫(xiě)成5行3列的矩陣。,,（,）,如下表所示：,=,表5-2,若將N=15=,,=53寫(xiě)成這樣的形式，則,=5，,=3，,=,（,）,表5.5.2,,例：一個(gè)長(zhǎng)度為N=15的序列，有兩種分解形式。1）當(dāng)N=15=,,=35，則,可以分解為5個(gè)長(zhǎng)為3的序列，,寫(xiě)成以下形式的二維矩陣,,2）當(dāng)N=15=,,=53，則,可以分解為3個(gè)長(zhǎng)為5的序列，,寫(xiě)成以下形式的二維矩陣,,,同理，我們定義輸出頻譜序列的k值也可以用矩陣排列的形式表達(dá)為：,（,）。,當(dāng)N=15=,,=35時(shí)，,，這里,為行序號(hào)，,為列序號(hào)。對(duì)應(yīng)序列,的N=,,點(diǎn)DFT運(yùn)算為：,因?yàn)槠渲蠳=,,，則有,=1，,=,，,=,則,令,（5-5-2）,（5-5-1）,可見(jiàn),為將,作為常量時(shí)，對(duì),點(diǎn)序列,做,點(diǎn)的DFT。因?yàn)?可以取,點(diǎn)個(gè)值，所以,共有,,點(diǎn)序列值。也就是對(duì)二維矩陣,每一列做,點(diǎn)DFT形成一,（,為行，,為列）。,新的陣列,令,表示為,乘以旋轉(zhuǎn)因子,所組成的N個(gè)新序列值。則有：,（5-5-3）,含義則是將,作為常量時(shí)，對(duì)序列,作,點(diǎn)DFT。若用矩陣,行，,列的矩陣,的第,行作,點(diǎn)的DFT。結(jié)果,。注意：從（5-5-3）式得出的為按照,，,排列的，需要通過(guò),進(jìn)行譯序得到,。,來(lái)描述則為對(duì),形成一個(gè)新的矩陣,二、運(yùn)算步驟由上面的原理可以總結(jié)出當(dāng)N=,,時(shí)的混合基算法步驟。,1）先將序列,分解為,個(gè),點(diǎn)長(zhǎng)的序列，形成一個(gè)二維陣列，,其中每個(gè)元素為：,,=,=,，,）,，,(,2）對(duì)上述所構(gòu)成的二維陣列的每一列做,點(diǎn)的DFT即：,構(gòu)成一個(gè)新的,,二維陣列,。,3)將第二步中二維矩陣的每個(gè)元素對(duì)應(yīng)乘以旋轉(zhuǎn)因子,形成一個(gè)新的陣列,4）對(duì),,的新二維陣列,的每一行分別作,點(diǎn)的DFT，,次即：,共需作,5）譯序，由,從,得,繼而得到,上面我們僅僅討論了當(dāng)N=,,況，若N為多個(gè)素?cái)?shù)組合的情況，則仍可依照上述的分解,時(shí)，分解為兩個(gè)素?cái)?shù)的情,方法將DFT分解為小點(diǎn)的DFT。,三、基數(shù)在前面我們也提到了基數(shù)這個(gè)概念，如前面所講的基—2FFT算法，這個(gè)概念用來(lái)描述的特定分解的。設(shè)N=﹒﹒﹒，當(dāng)==…=都是相同的素?cái)?shù)因子時(shí)，則可通過(guò)L級(jí)的r點(diǎn)DFT實(shí)現(xiàn)FFT.若，…為不同的素?cái)?shù)因子，則可將其分解為不同小點(diǎn)數(shù)的DFT來(lái)實(shí)現(xiàn)FFT算法。如：N=253，則可進(jìn)行5，2，3點(diǎn)DFT來(lái)實(shí)現(xiàn)快速算法。,四、N為復(fù)合數(shù)運(yùn)算量估計(jì)由上述所作的運(yùn)算步驟可知，主要所需計(jì)算在第2），3），4）步驟處。個(gè)點(diǎn)的DFT：復(fù)乘，.；復(fù)加，（-1）個(gè)點(diǎn)的DFT：復(fù)乘，.；復(fù)加，（-1）N=個(gè)元素乘旋轉(zhuǎn)因子：復(fù)乘，N次，所以共需復(fù)乘：（++1）；復(fù)加：（++2）。直接計(jì)算：復(fù)乘，；復(fù)加，,整個(gè)過(guò)程的運(yùn)算流圖如下：,圖5-15N=35=15時(shí)的FFT運(yùn)算流圖,5.5.2分裂基FFT算法在分裂基FFT算法中對(duì)數(shù)列的偶序號(hào)采用基—2算法，奇序號(hào)采用基—4算法。是一種將基—4，基—2算法糅合在一起的快速算法。不僅具有最少的乘法次數(shù)，并且具有基—2算法同址運(yùn)算的特點(diǎn)。與基—2類(lèi)似，也存在有按時(shí)間與按頻率抽取這兩種情況，下面就介紹這兩方面的內(nèi)容。在介紹分裂基算法之前，我們先簡(jiǎn)單介紹基—4算法。,一、按頻率抽選。對(duì)于N=2L點(diǎn)的DFT，序列,可以分為三個(gè)子序列：,對(duì)式子,對(duì)k的偶序號(hào)輸出項(xiàng)用基二算法有：,對(duì)k的奇序號(hào)項(xiàng)有：,經(jīng)過(guò)變量代換：,同理：,綜合上面結(jié)論可見(jiàn)可以由下面（5-5-4）式子計(jì)算：,（5-5-4）,可見(jiàn)，一個(gè)N點(diǎn)的的DFT可以分解為計(jì)算一個(gè)N/2點(diǎn)DFT，兩個(gè)N/4點(diǎn)的DFT。（5-5-4）式構(gòu)成的分裂基的L型算法結(jié)構(gòu)如下圖所示。,圖5-16分裂基FFT算法示意圖,