《快速傅立葉變換》PPT課件.ppt

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

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