快速傅里葉變換課件

第四章快速傅里葉變換第四章快速傅里葉變換11965年庫利--圖基《計(jì)算數(shù)學(xué)》(MathematicofComputation)“機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法”——揭開了FFT發(fā)展史上的第一頁1967年至1968年間FFT的數(shù)字硬件制成電子數(shù)字計(jì)算機(jī)——FFT算法迅速發(fā)展——DFT走向?qū)嵱?965年庫利--圖基《計(jì)算數(shù)學(xué)》(Mathematico2一、直接計(jì)算DFT算法——存在的問題及改進(jìn)途徑問題提出：設(shè)有限長序列x(n),非零值長度為N,計(jì)算對(duì)x(n)進(jìn)行一次DFT運(yùn)算，共需多大的運(yùn)算工作量?(一)存在的問題一、直接計(jì)算DFT算法——存在的問題及改進(jìn)途徑問題提出：設(shè)有31.比較DFT與IDFT之間的運(yùn)算量其中x(n)為復(fù)數(shù)，也為復(fù)數(shù)所以DFT與IDFT二者計(jì)算量相同。1.比較DFT與IDFT之間的運(yùn)算量其中x(n)為復(fù)數(shù)，42.DFT的復(fù)數(shù)運(yùn)算量計(jì)算一個(gè)X(k)(一個(gè)頻率成份)值，運(yùn)算量為例k=1則要進(jìn)行完成整個(gè)DFT運(yùn)算，其計(jì)算量為：N次復(fù)數(shù)乘法+(N-1)次復(fù)數(shù)加法N*N次復(fù)數(shù)相乘+N*(N-1)次復(fù)數(shù)加法2.DFT的復(fù)數(shù)運(yùn)算量計(jì)算一個(gè)X(k)(一個(gè)頻率成份)53.一次復(fù)數(shù)運(yùn)算量換算成實(shí)數(shù)運(yùn)算量4次復(fù)數(shù)乘法2次實(shí)數(shù)加法復(fù)數(shù)運(yùn)算要比實(shí)數(shù)運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間長。一個(gè)復(fù)數(shù)乘法包括4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)一個(gè)復(fù)數(shù)加法包括2次實(shí)數(shù)加法。(a+jb)+(c+jd)=(a+c)+j(b+d)2次實(shí)數(shù)加法3.一次復(fù)數(shù)運(yùn)算量換算成實(shí)數(shù)運(yùn)算量4次復(fù)數(shù)乘法2次實(shí)數(shù)加法復(fù)64.計(jì)算DFT需要的實(shí)數(shù)運(yùn)算量由此看出：直接計(jì)算DFT時(shí)，乘法次數(shù)與加法次數(shù)都是和N2成比例的。當(dāng)N很大時(shí)，所需工作量非?？捎^。4N2次實(shí)數(shù)相乘和2N(2N-1)次實(shí)數(shù)相加.整個(gè)DFT實(shí)數(shù)運(yùn)算量為：N*N次復(fù)數(shù)乘+N*(N-1)次復(fù)數(shù)加整個(gè)DFT的復(fù)數(shù)運(yùn)算量轉(zhuǎn)換為實(shí)數(shù)運(yùn)算量：2*N*N次實(shí)數(shù)加4*N*N次實(shí)數(shù)乘2*N*(N-1)次實(shí)數(shù)加2N(2N-1)次實(shí)數(shù)加4.計(jì)算DFT需要的實(shí)數(shù)運(yùn)算量由此看出：直接計(jì)算DFT時(shí)，乘7例子例1:當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算DFT需要：這對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理(如雷達(dá)信號(hào)處理——它對(duì)計(jì)算速度有十分苛刻的要求)來講，迫切需要改進(jìn)DFT的計(jì)算方法，以減少總的運(yùn)算次數(shù)。4*N2=4194304次實(shí)數(shù)乘2N(2N-1)=4192256次實(shí)數(shù)加例子例1:當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算DFT需要：這對(duì)實(shí)時(shí)性8(二)改善DFT運(yùn)算效率的基本途徑基本思路：利用DFT運(yùn)算的系數(shù)的固有對(duì)稱性和周期性，改善DFT的運(yùn)算效率。1.合并法：合并DFT運(yùn)算中的某些項(xiàng)。2.分解法：將長序列DFT利用對(duì)稱性和周期性，分解為短序列DFT。(二)改善DFT運(yùn)算效率的基本途徑基本思路：利用DFT運(yùn)91.利用DFT運(yùn)算的系數(shù)的固有對(duì)稱性和周期性，改善DFT的運(yùn)算效率的共軛對(duì)稱性：的周期性：1.利用DFT運(yùn)算的系數(shù)的固有對(duì)稱性和周102、將長序列DFT利用對(duì)稱性和周期性分解為短序列DFTDFT的運(yùn)算量與N2成正比大點(diǎn)數(shù)N的DFT小點(diǎn)數(shù)DFT的組合分解減少運(yùn)算工作量思路：2、將長序列DFT利用對(duì)稱性和周期性分解為短序列DFTDFT11把N點(diǎn)數(shù)據(jù)分成二半：其運(yùn)算量為：再分二半：+=+++=這樣一直分下去，剩下兩點(diǎn)的變換。方法把N點(diǎn)數(shù)據(jù)分成二半：其運(yùn)算量為：再分二半：+=+++=這樣一12結(jié)論快速付里葉變換(FFT)就是在此特性基礎(chǔ)上發(fā)展起來，并產(chǎn)生了多種FFT算法，其基本上可分成兩大類：按抽取方法分：時(shí)間抽取法(DIT);頻率抽取法(DIF)按“基數(shù)”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：線性調(diào)頻Z變換(CZT法)結(jié)論快速付里葉變換(FFT)就是在此特性基礎(chǔ)上發(fā)展起來，并產(chǎn)13二、基--2按時(shí)間抽取的FFT算法

(Coolkey-Tukey)（一）算法原理

設(shè)輸入序列長度為N=2M

(M為正整數(shù)），將該序列按時(shí)間順序的奇偶分解為越來越短的子序列，稱為基2按時(shí)間抽取的FFT算法。也稱為Coolkey-Tukey算法。特別注意：若不滿足這個(gè)條件，可以人為地加上若干零值（加零補(bǔ)長）使其達(dá)到N=2M序列長度N必須滿足N=2M，M為整數(shù).二、基--2按時(shí)間抽取的FFT算法

(Coolkey-Tuk14(二)算法步驟DFT變換：1.分組，變量置換先將x(n)按n的奇偶分為兩組，作變量置換:當(dāng)n=偶數(shù)時(shí)，令n=2r;當(dāng)n=奇數(shù)時(shí)，令n=2r+1;得到：x(2r)=x1(r);x(2r+1)=x2(r);r=0…N/2-1;(二)算法步驟DFT變換：1.分組，變量置換先將x(n15利用得2.分組序列的DFT中生成兩個(gè)子序列利用得2.分組序列的DFT中生成兩個(gè)子序列16X1(k):原序列偶數(shù)項(xiàng)的DFTX2(k):原序列奇數(shù)項(xiàng)的DFTX1(k):原序列偶數(shù)項(xiàng)的DFTX2(k):原序列奇173.結(jié)論1再應(yīng)用W系數(shù)的周期性，求出用X1(k),X2(k)表達(dá)的后半部的X(k+N/2)的值。一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X2(k)這兩個(gè)N/2點(diǎn)的DFT按照：3.結(jié)論1再應(yīng)用W系數(shù)的周期性，求出用X1(k),X2(k184.求出后半部的表示式看出：后半部的k值所對(duì)應(yīng)的X1(k),X2(k)則完全重復(fù)了前半部分的k值所對(duì)應(yīng)的X1(k),X2(k)的值。4.求出后半部的表示式看出：后半部的k值所對(duì)應(yīng)的X1(k),195.結(jié)論2頻域中的N個(gè)點(diǎn)頻率成分為：只要求出（0~N/2-1）區(qū)間內(nèi)的各個(gè)整數(shù)k值所對(duì)應(yīng)的X1(k),X2(k)值，即可以求出(0~N-1)整個(gè)區(qū)間內(nèi)全部X(k)值，這就是FFT能大量節(jié)省計(jì)算的關(guān)鍵。結(jié)論：5.結(jié)論2頻域中的N個(gè)點(diǎn)頻率成分為：只要求出（0~N/2-1206.結(jié)論3由于N=2M，因此N/2仍為偶數(shù)，可以依照上面方法進(jìn)一步把每個(gè)N/2點(diǎn)子序列，再按輸入n的奇偶分解為兩個(gè)N/4點(diǎn)的子序列，按這種方法不斷劃分下去，直到最后剩下的是2點(diǎn)DFT，兩點(diǎn)DFT實(shí)際上只是加減運(yùn)算。6.結(jié)論3由于N=2M，因此N/2仍為偶數(shù)，可以依照上面方法21（三）蝶形結(jié)即蝶式計(jì)算結(jié)構(gòu),或蝶式信號(hào)流圖。X1(k)X2(k)作圖要素：(1)左入右出(2)上加下減(3)系數(shù)標(biāo)箭頭上面頻域中前/后半部分表示式可以用蝶形信號(hào)流圖表示如下。（三）蝶形結(jié)即蝶式計(jì)算結(jié)構(gòu),或蝶式信號(hào)流圖。X1(k)X2(22例子先將N=8DFT分解成2個(gè)4點(diǎn)DFT：可知：時(shí)域上：x(0),x(2),x(4),x(6)為偶子序列x(1),x(3),x(5),x(7)為奇子序列

頻域上：X(0)~X(3)，由X(k)給出X(4)~X(7),由X(k+N/2)給出求N=23=8點(diǎn)FFT變換解：（1）先按N=8-->N/2=4，做4點(diǎn)的DFT：例子先將N=8DFT分解成2個(gè)4點(diǎn)DFT：求N=23=8點(diǎn)23將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號(hào)流圖4點(diǎn)DFTx(0)x(2)x(4)x(6)4點(diǎn)DFTx(1)x(3)x(5)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶數(shù)序列奇數(shù)序列X(4)~X(7)同學(xué)們自已寫x1(r)x2(r)將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號(hào)流圖4點(diǎn)x(0)4點(diǎn)24(2)N/2(4點(diǎn))-->N/4(2點(diǎn))FFT因?yàn)?點(diǎn)DFT還是比較麻煩，所以再繼續(xù)分解。若將N/2(4點(diǎn))子序列按奇/偶分解成兩個(gè)N/4點(diǎn)（2點(diǎn)）子序列。即將x1(r)和x2(r)分解成奇、偶兩個(gè)N/4點(diǎn)（2點(diǎn)）點(diǎn)的子序列。(2)N/2(4點(diǎn))-->N/4(2點(diǎn))FFT25一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(0)x(2)26另一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)另一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(1)x(327(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT最后剩下兩點(diǎn)DFT,它可分解成兩個(gè)一點(diǎn)DFT，但一點(diǎn)DFT就等于輸入信號(hào)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x(0)、x(4)為例。(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT282個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx(0)1點(diǎn)DFTx(4)X3(0)X3(1)進(jìn)一步簡化為蝶形流圖：X3(0)X3(1)x(0)x(4)2個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx(0)1點(diǎn)DFTx(429(4)一個(gè)完整N=8的按時(shí)間抽取FFT的運(yùn)算流圖x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2(4)一個(gè)完整N=8的按時(shí)間抽取FFT的運(yùn)算流圖x(0)X30三、基--2按頻率抽取的FFT算法(DIF)(Sander-Tukey)(一)算法原理

設(shè)輸入序列長度為N=2M(M為正整數(shù)，將該序列的頻域的輸出序列X(k)(也是M點(diǎn)序列)，按其頻域順序的奇偶分解為越來越短的子序列，稱為基2按頻率抽取的FFT算法。也稱為Sander-Tukey算法。三、基--2按頻率抽取的FFT算法(DIF)(Sande31基--2按時(shí)間抽取的FFT時(shí)域：按奇偶劃分頻域：按前后劃分基--2按頻率抽取的FFT時(shí)域：按前后劃分頻域：按奇偶劃分基--2按時(shí)間抽取的FFT時(shí)域：按奇偶劃分32例子頻域上：X(0),X(2),X(4),X(6)由x1(n)給出X(1),X(3),X(5),X(7),由x2(n)給出求N=23=8點(diǎn)DIF（1）先按N=8-->N/2=4，做4點(diǎn)的DIF：例子頻域上：X(0),X(2),X(4),X(6)由x1(n33將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DIF的信號(hào)流圖4點(diǎn)DFTx(0)x(1)x(2)x(3)4點(diǎn)DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列x1(n)x2(n)X2(k)將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DIF的信號(hào)流圖4點(diǎn)x(0)4點(diǎn)34(4)一個(gè)完整N=8的按頻率抽取FFT的運(yù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)m=0m=1m=2(4)一個(gè)完整N=8的按頻率抽取FFT的運(yùn)算流圖x(0)X35DIF與DIT比較相同之處：（1）DIF與DIT兩種算法均為原位運(yùn)算。（2）DIF與DIT運(yùn)算量相同。它們都需要DIF與DIT比較相同之處：36不同之處：（1）DIF與DIT兩種算法結(jié)構(gòu)倒過來。DIF為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行“二進(jìn)制倒讀”程序。DIT為輸入亂序，輸出順序。先運(yùn)行“二進(jìn)制倒讀”程序，再進(jìn)行求DFT。（2）DIF與DIT根本區(qū)別：在于蝶形結(jié)不同。DIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。DIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。不同之處：37第四章快速傅里葉變換第四章快速傅里葉變換381965年庫利--圖基《計(jì)算數(shù)學(xué)》(MathematicofComputation)“機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法”——揭開了FFT發(fā)展史上的第一頁1967年至1968年間FFT的數(shù)字硬件制成電子數(shù)字計(jì)算機(jī)——FFT算法迅速發(fā)展——DFT走向?qū)嵱?965年庫利--圖基《計(jì)算數(shù)學(xué)》(Mathematico39一、直接計(jì)算DFT算法——存在的問題及改進(jìn)途徑問題提出：設(shè)有限長序列x(n),非零值長度為N,計(jì)算對(duì)x(n)進(jìn)行一次DFT運(yùn)算，共需多大的運(yùn)算工作量?(一)存在的問題一、直接計(jì)算DFT算法——存在的問題及改進(jìn)途徑問題提出：設(shè)有401.比較DFT與IDFT之間的運(yùn)算量其中x(n)為復(fù)數(shù)，也為復(fù)數(shù)所以DFT與IDFT二者計(jì)算量相同。1.比較DFT與IDFT之間的運(yùn)算量其中x(n)為復(fù)數(shù)，412.DFT的復(fù)數(shù)運(yùn)算量計(jì)算一個(gè)X(k)(一個(gè)頻率成份)值，運(yùn)算量為例k=1則要進(jìn)行完成整個(gè)DFT運(yùn)算，其計(jì)算量為：N次復(fù)數(shù)乘法+(N-1)次復(fù)數(shù)加法N*N次復(fù)數(shù)相乘+N*(N-1)次復(fù)數(shù)加法2.DFT的復(fù)數(shù)運(yùn)算量計(jì)算一個(gè)X(k)(一個(gè)頻率成份)423.一次復(fù)數(shù)運(yùn)算量換算成實(shí)數(shù)運(yùn)算量4次復(fù)數(shù)乘法2次實(shí)數(shù)加法復(fù)數(shù)運(yùn)算要比實(shí)數(shù)運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間長。一個(gè)復(fù)數(shù)乘法包括4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)一個(gè)復(fù)數(shù)加法包括2次實(shí)數(shù)加法。(a+jb)+(c+jd)=(a+c)+j(b+d)2次實(shí)數(shù)加法3.一次復(fù)數(shù)運(yùn)算量換算成實(shí)數(shù)運(yùn)算量4次復(fù)數(shù)乘法2次實(shí)數(shù)加法復(fù)434.計(jì)算DFT需要的實(shí)數(shù)運(yùn)算量由此看出：直接計(jì)算DFT時(shí)，乘法次數(shù)與加法次數(shù)都是和N2成比例的。當(dāng)N很大時(shí)，所需工作量非常可觀。4N2次實(shí)數(shù)相乘和2N(2N-1)次實(shí)數(shù)相加.整個(gè)DFT實(shí)數(shù)運(yùn)算量為：N*N次復(fù)數(shù)乘+N*(N-1)次復(fù)數(shù)加整個(gè)DFT的復(fù)數(shù)運(yùn)算量轉(zhuǎn)換為實(shí)數(shù)運(yùn)算量：2*N*N次實(shí)數(shù)加4*N*N次實(shí)數(shù)乘2*N*(N-1)次實(shí)數(shù)加2N(2N-1)次實(shí)數(shù)加4.計(jì)算DFT需要的實(shí)數(shù)運(yùn)算量由此看出：直接計(jì)算DFT時(shí)，乘44例子例1:當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算DFT需要：這對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理(如雷達(dá)信號(hào)處理——它對(duì)計(jì)算速度有十分苛刻的要求)來講，迫切需要改進(jìn)DFT的計(jì)算方法，以減少總的運(yùn)算次數(shù)。4*N2=4194304次實(shí)數(shù)乘2N(2N-1)=4192256次實(shí)數(shù)加例子例1:當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算DFT需要：這對(duì)實(shí)時(shí)性45(二)改善DFT運(yùn)算效率的基本途徑基本思路：利用DFT運(yùn)算的系數(shù)的固有對(duì)稱性和周期性，改善DFT的運(yùn)算效率。1.合并法：合并DFT運(yùn)算中的某些項(xiàng)。2.分解法：將長序列DFT利用對(duì)稱性和周期性，分解為短序列DFT。(二)改善DFT運(yùn)算效率的基本途徑基本思路：利用DFT運(yùn)461.利用DFT運(yùn)算的系數(shù)的固有對(duì)稱性和周期性，改善DFT的運(yùn)算效率的共軛對(duì)稱性：的周期性：1.利用DFT運(yùn)算的系數(shù)的固有對(duì)稱性和周472、將長序列DFT利用對(duì)稱性和周期性分解為短序列DFTDFT的運(yùn)算量與N2成正比大點(diǎn)數(shù)N的DFT小點(diǎn)數(shù)DFT的組合分解減少運(yùn)算工作量思路：2、將長序列DFT利用對(duì)稱性和周期性分解為短序列DFTDFT48把N點(diǎn)數(shù)據(jù)分成二半：其運(yùn)算量為：再分二半：+=+++=這樣一直分下去，剩下兩點(diǎn)的變換。方法把N點(diǎn)數(shù)據(jù)分成二半：其運(yùn)算量為：再分二半：+=+++=這樣一49結(jié)論快速付里葉變換(FFT)就是在此特性基礎(chǔ)上發(fā)展起來，并產(chǎn)生了多種FFT算法，其基本上可分成兩大類：按抽取方法分：時(shí)間抽取法(DIT);頻率抽取法(DIF)按“基數(shù)”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：線性調(diào)頻Z變換(CZT法)結(jié)論快速付里葉變換(FFT)就是在此特性基礎(chǔ)上發(fā)展起來，并產(chǎn)50二、基--2按時(shí)間抽取的FFT算法

(Coolkey-Tukey)（一）算法原理

設(shè)輸入序列長度為N=2M

(M為正整數(shù)），將該序列按時(shí)間順序的奇偶分解為越來越短的子序列，稱為基2按時(shí)間抽取的FFT算法。也稱為Coolkey-Tukey算法。特別注意：若不滿足這個(gè)條件，可以人為地加上若干零值（加零補(bǔ)長）使其達(dá)到N=2M序列長度N必須滿足N=2M，M為整數(shù).二、基--2按時(shí)間抽取的FFT算法

(Coolkey-Tuk51(二)算法步驟DFT變換：1.分組，變量置換先將x(n)按n的奇偶分為兩組，作變量置換:當(dāng)n=偶數(shù)時(shí)，令n=2r;當(dāng)n=奇數(shù)時(shí)，令n=2r+1;得到：x(2r)=x1(r);x(2r+1)=x2(r);r=0…N/2-1;(二)算法步驟DFT變換：1.分組，變量置換先將x(n52利用得2.分組序列的DFT中生成兩個(gè)子序列利用得2.分組序列的DFT中生成兩個(gè)子序列53X1(k):原序列偶數(shù)項(xiàng)的DFTX2(k):原序列奇數(shù)項(xiàng)的DFTX1(k):原序列偶數(shù)項(xiàng)的DFTX2(k):原序列奇543.結(jié)論1再應(yīng)用W系數(shù)的周期性，求出用X1(k),X2(k)表達(dá)的后半部的X(k+N/2)的值。一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X2(k)這兩個(gè)N/2點(diǎn)的DFT按照：3.結(jié)論1再應(yīng)用W系數(shù)的周期性，求出用X1(k),X2(k554.求出后半部的表示式看出：后半部的k值所對(duì)應(yīng)的X1(k),X2(k)則完全重復(fù)了前半部分的k值所對(duì)應(yīng)的X1(k),X2(k)的值。4.求出后半部的表示式看出：后半部的k值所對(duì)應(yīng)的X1(k),565.結(jié)論2頻域中的N個(gè)點(diǎn)頻率成分為：只要求出（0~N/2-1）區(qū)間內(nèi)的各個(gè)整數(shù)k值所對(duì)應(yīng)的X1(k),X2(k)值，即可以求出(0~N-1)整個(gè)區(qū)間內(nèi)全部X(k)值，這就是FFT能大量節(jié)省計(jì)算的關(guān)鍵。結(jié)論：5.結(jié)論2頻域中的N個(gè)點(diǎn)頻率成分為：只要求出（0~N/2-1576.結(jié)論3由于N=2M，因此N/2仍為偶數(shù)，可以依照上面方法進(jìn)一步把每個(gè)N/2點(diǎn)子序列，再按輸入n的奇偶分解為兩個(gè)N/4點(diǎn)的子序列，按這種方法不斷劃分下去，直到最后剩下的是2點(diǎn)DFT，兩點(diǎn)DFT實(shí)際上只是加減運(yùn)算。6.結(jié)論3由于N=2M，因此N/2仍為偶數(shù)，可以依照上面方法58（三）蝶形結(jié)即蝶式計(jì)算結(jié)構(gòu),或蝶式信號(hào)流圖。X1(k)X2(k)作圖要素：(1)左入右出(2)上加下減(3)系數(shù)標(biāo)箭頭上面頻域中前/后半部分表示式可以用蝶形信號(hào)流圖表示如下。（三）蝶形結(jié)即蝶式計(jì)算結(jié)構(gòu),或蝶式信號(hào)流圖。X1(k)X2(59例子先將N=8DFT分解成2個(gè)4點(diǎn)DFT：可知：時(shí)域上：x(0),x(2),x(4),x(6)為偶子序列x(1),x(3),x(5),x(7)為奇子序列

頻域上：X(0)~X(3)，由X(k)給出X(4)~X(7),由X(k+N/2)給出求N=23=8點(diǎn)FFT變換解：（1）先按N=8-->N/2=4，做4點(diǎn)的DFT：例子先將N=8DFT分解成2個(gè)4點(diǎn)DFT：求N=23=8點(diǎn)60將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號(hào)流圖4點(diǎn)DFTx(0)x(2)x(4)x(6)4點(diǎn)DFTx(1)x(3)x(5)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶數(shù)序列奇數(shù)序列X(4)~X(7)同學(xué)們自已寫x1(r)x2(r)將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號(hào)流圖4點(diǎn)x(0)4點(diǎn)61(2)N/2(4點(diǎn))-->N/4(2點(diǎn))FFT因?yàn)?點(diǎn)DFT還是比較麻煩，所以再繼續(xù)分解。若將N/2(4點(diǎn))子序列按奇/偶分解成兩個(gè)N/4點(diǎn)（2點(diǎn)）子序列。即將x1(r)和x2(r)分解成奇、偶兩個(gè)N/4點(diǎn)（2點(diǎn)）點(diǎn)的子序列。(2)N/2(4點(diǎn))-->N/4(2點(diǎn))FFT62一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(0)x(2)63另一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)另一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(1)x(364(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT最后剩下兩點(diǎn)DFT,它可分解成兩個(gè)一點(diǎn)DFT，但一點(diǎn)DFT就等于輸入信號(hào)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x(0)、x(4)為例。(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT652個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx(0)1點(diǎn)DFTx(4)X3(0)X3(1)進(jìn)一步簡化為蝶形流圖：X3(0)X3(1)x(0)x(4)2個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx(0)1點(diǎn)DFTx(466(4)一個(gè)完整N=8的按時(shí)間抽取FFT的運(yùn)算流圖x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=