.,第四章快速傅立葉變換(FFT),一、直接用DFT計算的運算量與用FFT計算的運算量比較，減少運算量的途徑,.,二、FFT算法中一些概念,按時間抽取法解過程的規(guī)律。1.原位運算（in-place)2.碼位倒讀規(guī)則，亂序輸入，順序輸出（1）“級”概念將N點DFT先分成兩個N/2點DFT，再是四個N/4點DFT直至N/2個兩點DFT.每分一次稱為“一”級運算。因為N=2M所以N點DFT可分成M級依次m=0,m=1.M-1共M級,.,（2）“組”概念,每一級都有N/2個蝶形單元，例如：N=8,則每級都有4個蝶形單元。每一級的N/2個蝶形單元可以分成若干組，每一組具有相同的結構，相同的因子分布，第m級的組數為：,例：N=8=23，分3級。m=0級,分成四組,每組系數為m=1級,分成二組,每組系數為m=2級,分成一組,每組系數為,.,(3)因子的分布,結論：每由后向前（m由M-1-0級）推進一級，則此系數為后級系數中偶數序號的那一半。,.,三、一個完整N=8的按DIT時間抽取FFT的運算流圖,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=0,m=1,m=2,.,一個完整N=8的按DIF頻率抽取FFT的運算流圖,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=0,m=1,m=2,.,2.直接利用FFT流圖方法的推導,可知：只須將頻域成份一個求共軛變換，即（1）將X(k)的虛部乘以-1，即先取X(k)的共軛，得X*(k)。(2)將X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再對運算結果取一次共軛變換，并乘以常數1/N，即可以求出IFFT變換的x(n)的值。,此為DFT可用FFT程序,.,3.用CZT求解DFT的流圖,.,6、說明1,（1）A為起始樣點位置,.,6、說明2,（2）zk是z平面一段螺線上的等分角上某一采樣點。,.,6、說明3,.,6、說明4,.,10、CZT運算量與直接運算量比較,當M、N足夠小時，直接算法運算量少。但M、N值比較大時（大于50），CZT算法比直接算法的運算量少得多。例M=50，N=50，N*M=2500次而CZT1600次。,.,重疊相加法,（1）x(n)為分段，每段長為p點，p選擇與M數量組相同。用xi(n)表示x(n)的第i段.,.,重疊保留法,.,.,第三章離散傅立葉變換（DFT）,一、四種不同的傅立葉變換對傅里葉級數(FS)：連續(xù)時間,離散頻率的傅里葉變換。連續(xù)傅里葉變換(FT)：連續(xù)時間,連續(xù)頻率的傅里葉變換。序列的傅里葉變換(DTFT):離散時間,連續(xù)頻率的傅里葉變換.離散傅里葉變換(DFT):離散時間,離散頻率的傅里葉變換,.,四種付里葉變換形式的歸納,.,二、DFS定義,設為周期為N的周期序列,則其離散傅里葉級數(DFS)變換對為:正變換反變換其中:,.,三、DFT,1、定義正變換反變換X(k)、x(n)為有限長序列的離散付里葉變換對，已知其中一個序列就能確定另一個序列。,.,2、DFT性質,時移特性已知DFTx(n)=X(k)則DFTx(n+m)NRN(n)=WN-mkX(k)頻移特性設頻域N點，有限長序列X(k)則,.,3、圓周卷積與線性卷積的性質對比,.,.,4、奇偶虛實關系表,.,四、頻域抽樣理論,長度為M的有限長序列,頻域抽樣不失真的條件：頻域抽樣點數N要大于或等于序列長度M,即滿足NM.此時可得到表明長度為N(或小于N)的有限長序列可用它的z變換在單位圓上的N個均分點上的抽樣值精確地表示.,.,五、DFT做傅里葉變換(級數)的逼近時所產生的問題,混疊現象:頻譜泄漏柵欄效應,.,1、混疊現象,利用DFT逼近連續(xù)時間信號的傅里葉變換,為避免混疊失真,要求滿足抽樣定理，即奈奎斯特準則：fs2fh其中fs為抽樣頻率,fh為信號最高頻率.但此條件只規(guī)定出fs的下限為fh,其上限要受抽樣間隔F的約束.抽樣間隔F即頻率分辨力,它是記錄長度的倒數,即Tp=1/F若抽樣點數為N,則抽樣間隔與fs的關系為F=fs/N2fh/N,.,混疊現象的結論,由F=fs/N2fh/N看出：在N給定時,為避免混疊失真而一味提高抽樣頻率fs,必然導致F增加,即頻率分辨力下降;反之,若要提高頻率分辨力即減小F,則導致減小fs,最終必須減小信號的高頻容量.以上兩點結論都是在記錄長度內抽樣點數N給定的條件下得到的.所以在高頻容量fh與頻率分辨力F參數中,保持其中一個不變而使另一個性能得以提高的唯一辦法,就是增加記錄長度內的點數N,即fh和F都給定時,則N必須滿足N2fh/F這是未采用任何特殊數據處理（例如加窗）情況下，為實現基本DFT算法所必須滿足條件。,.,2、頻譜泄漏注意點,由于我們無法取無數個點，所以在DFT時，時域的截斷是必然的，因而泄漏也是必然存在的。為了減少頻率泄漏可采用：（1）適當加大窗口寬度，增加M值；（2）采用適當形狀的窗函數截斷指出：泄漏是不能與混疊完全分開的。,.,3、減小柵欄效應方法,減小柵欄效應的一個方法是在所取數據的末端加一些零值點,使一個周期內點數增加,但是不改變原有的記錄數據.這種方法等效于加長了周期Tp.因公式F=1/Tp(F是抽樣間隔).Tp增加,抽樣間隔變小,從而能保持原來頻譜形式不變的情況下使譜線變密,也就使頻譜抽樣點數增加.這樣,原來看不到的頻譜分量就有可能看到了.,.,序列的傅立葉變換和性質（教材78頁，表2-3）,