資源描述：
《第4章 快速付立葉變換(FFT)ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第四章FFT快速傅氏變換§4-5線性卷積的FFT算法§4-3DIF的FFT算法§4-4IFFT算法§4-2按時間抽取(DIT)的FFT算法§4-1引言目§4-1引言一.DFT的計算工作量兩者的差別僅在指數(shù)的符號和因子1/N.DFT與IDFT運算特點復(fù)數(shù)乘法復(fù)數(shù)加法一個X(k)NN–1N個X(k)(N點DFT)N2N(N–1)同理：IDFT運算量與DFT相同。實數(shù)乘法實數(shù)加法一次復(fù)乘42一次復(fù)加2一個X(k)4N2N+2(N–1)=2(2N–1)N個X(k)(N點DFT)4N22N(2N–1)通常x(n)和都是復(fù)數(shù),所以計
2、算一個X(k)的值需要N次復(fù)數(shù)乘法運算,和次復(fù)數(shù)加法運算.那么,所有的X(k)就要N2次復(fù)數(shù)乘法運算,N(N-1)次復(fù)數(shù)加法運算.當(dāng)N很大時,運算量將是驚人的,如N=1024,則要完成1048576次(一百多萬次)運算.這樣,難以做到實時處理.一個X(k)的值的工作量,如X(1)二.改進的途徑1.的對稱性和周期性得:對稱性:周期性:利用上述特性,可以將有些項合并,并將DFT分解為短序列,從而降低運算次數(shù),提高運算速度.1965年,庫利(cooley)和圖基(Tukey)首先提出FFT算法.對于N點DFT,僅需(N/2)l
3、og2N次復(fù)數(shù)乘法運算.例如N=1024=210時，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%,速度提高20倍FFT算法分類:時間抽選法DIT:Decimation-In-Time頻率抽選法DIF:Decimation-In-Frequency§4-2按時間抽取(DIT)的FFT算法 —庫利-圖基算法一.算法原理(基2FFT)(一)N/2點DFT1.先將按n的奇偶分為兩組作DFT,設(shè)N=2L,不足時,可補些零。這樣有:n為偶數(shù)時:n為奇數(shù)時:因此，由于:所以,上式可
4、表示為:(n為偶數(shù))(n為奇數(shù))其中,2.兩點結(jié)論:(1)X(k),X(k)均為N/2點的DFT。(2)X(k)=X(k)+WX(k)只能確定出X(k)的k=個；即前一半的結(jié)果。1212kN同理,這就是說,X1(k),X2(k)的后一半,分別等于其前一半的值。3.X(k)的后一半的確定由于（周期性）,所以:可見,X(k)的后一半，也完全由X1(k),X2(k)的前一半所確定。*N點的DFT可由兩個N/2點的DFT來計算。又由于,所以實現(xiàn)上式運算的流圖稱作蝶形運算前一半4.蝶形運算后一半（N/2個蝶形)(前一半)(后一半)
5、1111-1由X1(k)、X2(k)表示X(k)的運算是一種特殊的運算-碟形運算5.分解后的運算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個N/2點DFT(N/2)2N/2(N/2–1)兩個N/2點DFTN2/2N(N/2–1)一個蝶形12N/2個蝶形N/2N總計運算量減少了近一半例如N=8時的DFT,可以分解為兩個N/2=4點的DFT.具體方法如下:(1)n為偶數(shù)時,即分別記作:(2)n為奇數(shù)時,分別記作:x1(0)=x(0)x1(1)=x(2)N/2點x1(2)=x(4)DFTx1(3)=x(6)x2(0)=x(1)x2(1)=x(3)
6、N/2點x2(2)=x(5)DFTx2(3)=x(7)12~~X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN2WN1WN0WN3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)(3)對X(k)和X(k)進行蝶形運算,前半部為X(0)X(3),后半部分為X(4)X(7)整個過程如下圖所示:由于N=2L,所以N/2仍為偶數(shù),可以進一步把每個N/2點的序列再按其奇偶部分分解為兩個N/4的子序列。例如，n為偶數(shù)時的N/2點分解為:(二)N/4點DFT進行N/4
7、點的DFT,得到(偶中偶)(偶中奇)從而可得到前N/4的X1(k)后N/4的X1(k)為注意到(奇中偶)(奇中奇)同樣對n為奇數(shù)時，N/2點分為兩個N/4點的序列進行DFT，則有:例如,N=8時的DFT可分解為四個N/4的DFT,具體步驟如下:(1)將原序列x(n)的“偶中偶”部分:構(gòu)成N/4點DFT，從而得到X3(0),X3(1)。(2)將原序列x(n)的“偶中奇”部分:構(gòu)成N/4點DFT，從而得到X4(0),X4(1)。(3)將原序列x(n)的“奇中偶”部分:構(gòu)成N/4點DFT，從而得到X5(0),X5(1)。(4)
8、將原序列x(n)的“奇中奇”部分:構(gòu)成N/4點DFT，從而得到X6(0),X6(1)。（5）由X3(0),X3(1),X4(0),X4(1)進行碟形運算,得到X1(0),X1(1),X1(2),X1(3)。（6）由X5(0),X5(1),X6(0),X6(1)進行碟形運算,得到X2(0),X2(1),X2(2),X2
