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

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