1、1,離散傅里葉變換(DFT) 利用DFT做連續(xù)信號(hào)的頻譜分析 快速傅里葉變換（FFT） 關(guān)于FFT應(yīng)用中的幾個(gè)問題,內(nèi)容提要,第二章 離散傅里葉變換及其快速算法,2,2.1 離散傅里葉變換DFT,FS Fourier Series,FT Fourier Transform,DTFT Discrete Time Fourier Transform,DFT Discrete Fourier Transform,3,Fourier變換的幾種可能形式,時(shí)間函數(shù) 頻率函數(shù),連續(xù)時(shí)間、連續(xù)頻率傅里葉變換(FT),連續(xù)時(shí)間、離散頻率傅里葉級(jí)數(shù)(FS),離散時(shí)間、連續(xù)頻率離散時(shí)間信號(hào)的傅里葉 變換(DTFT)

2、,離散時(shí)間、離散頻率離散傅里葉變換(DFT),4,連續(xù)時(shí)間的周期信號(hào)、離散頻率傅里葉級(jí)數(shù),時(shí)域連續(xù)函數(shù)造成頻域是非周期的譜，而頻域的離散對(duì)應(yīng)時(shí)域是周期函數(shù)。,5,連續(xù)時(shí)間的非周期信號(hào)、連續(xù)頻率傅里葉變換,時(shí)域連續(xù)函數(shù)造成頻域是非周期的譜， 而時(shí)域的非周期造成頻域是連續(xù)的譜密度函數(shù)。,6,離散時(shí)間的非周期信號(hào)、連續(xù)頻率離散時(shí)間信號(hào)的傅里葉變換,時(shí)域的離散化造成頻域的周期延拓，而時(shí)域的非周期對(duì)應(yīng)于頻域的連續(xù),7,離散時(shí)間、離散頻率離散傅里葉變換,一個(gè)域的離散造成另一個(gè)域的周期延拓，因此離散傅里葉變換的時(shí)域和頻域都是離散的和周期的,8,四種傅里葉變換形式的歸納,FT,FS,DTFT,DFS Disc

3、rete Fourier Series,9,FT,FS,DTFT,DFS,10,2.1.1 離散傅里葉級(jí)數(shù)(DFS),11,離散周期信號(hào)、離散周期頻譜的序列周期都為N。 對(duì)于周期序列實(shí)際計(jì)算只需要計(jì)算一個(gè)周期的值（0 N-1），其余值可以通過周期擴(kuò)展得到。所以可以定義一個(gè)有限序列（長度為周期）的傅氏變換便于計(jì)算。,DFS與IDFS,12,系數(shù)的性質(zhì),13,離散傅里葉級(jí)數(shù)(DFS)的性質(zhì),線性 序列的移位 共軛對(duì)稱性,14,離散傅里葉級(jí)數(shù)(DFS)的性質(zhì),周期卷積,15,周 期 卷 積,周期卷積演示,16,離散周期信號(hào)、離散周期頻譜的序列周期都為N。 對(duì)于周期序列實(shí)際計(jì)算只需要計(jì)算一個(gè)周期的值（

4、0 N-1），其余值可以通過周期擴(kuò)展得到。 離散周期序列實(shí)際上只在有限個(gè)序列值有意義，因此，其離散傅里葉級(jí)數(shù)的表示式適用于有限長序列,17,2.1.2 離散傅里葉變換(DFT),定義,隱含周期性,18,DFT的矩陣方程表示,19,離散傅里葉變換(DFT)的性質(zhì),線性 循環(huán)移位 循環(huán)卷積 共軛對(duì)稱性 選頻性 DFT與z變換 DFT形式下的Parseval定理,20,離散傅里葉變換(DFT)的性質(zhì),循環(huán)移位 概念 周期延拓序列 記作： 主值序列,21,離散傅里葉變換(DFT)的性質(zhì),循環(huán)移位,22,循環(huán)移位,有限長序列,周期延拓,周期序列移位,取主值空間,23,圓周移位,移位前,左移兩位后,周期序

5、列的圓周表示： 當(dāng)序列x(n)為周期序列時(shí)，可以將序列元素按反時(shí)針方向順序排列在N等分的圓周上。序列時(shí)移m，是將序列在圓周上順時(shí)針旋轉(zhuǎn)m個(gè)位置。,24,離散傅里葉變換(DFT)的性質(zhì),循環(huán)卷積(Circular Convolution),25,離散傅里葉變換(DFT)的性質(zhì),循環(huán)卷積(Circular Convolution),26,1）由有限長序列 x(n)、y(n) 構(gòu)造周期序列,循環(huán)卷積過程:,2）計(jì)算周期卷積,3）卷積 結(jié)果取主值,27,28,循環(huán)卷積與線性卷積的關(guān)系,DFT只能計(jì)算循環(huán)卷積，但實(shí)際使用中經(jīng)常要求的是兩個(gè)序列的線性卷積，所以有必要討論一下循環(huán)卷積與線性卷積的關(guān)系。,29

6、,循環(huán)卷積線性卷積的條件,若LN1N21，則L點(diǎn)循環(huán)卷積等于線性卷積而不產(chǎn)生混疊。,30,比較線性卷積與循環(huán)卷積,例: 設(shè)有兩個(gè)序列，x（n）為N=4矩形序列，y（n）為M=6矩形序列，觀察其線性卷積和圓周卷積。,a,b,c,d,e,f,g,h,當(dāng)L=N+M-1=9時(shí)，循環(huán)卷積等于線性卷積，不失真,31,離散傅里葉變換(DFT)的性質(zhì),共軛對(duì)稱性,32,離散傅里葉變換(DFT)的性質(zhì),共軛對(duì)稱性有限長序列的共軛對(duì)稱定義,33,離散傅里葉變換(DFT)的性質(zhì),共軛對(duì)稱性,任一個(gè)復(fù)數(shù)序列可以表示為實(shí)部序列和虛部序列（分別為實(shí)數(shù)序列）,任一個(gè)復(fù)數(shù)序列可以表示為共軛偶對(duì)稱和共軛奇對(duì)稱和的形式,34,離

7、散傅里葉變換(DFT)的性質(zhì),共軛對(duì)稱性,35,序列及其DFT的實(shí)、虛、偶、奇關(guān)系,36,共軛對(duì)稱性,任一個(gè)復(fù)數(shù)序列可以表示為四個(gè)實(shí)數(shù)序列,離散傅里葉變換(DFT)的性質(zhì),37,XIm(k)為實(shí)數(shù)序列,序列及其DFT的實(shí)、虛、偶、奇關(guān)系,38,離散傅里葉變換(DFT)的性質(zhì),選頻性,39,離散傅里葉變換(DFT)的性質(zhì),DFT與z變換,40,離散傅里葉變換(DFT)的性質(zhì),DFT與z變換,41,離散傅里葉變換(DFT)的性質(zhì),DFT與z變換,42,離散傅里葉變換(DFT)的性質(zhì),DFT形式下的Parseval定理,43,采樣定律告訴我們，一個(gè)頻帶有限的信號(hào)，可以對(duì)它進(jìn)行時(shí)域采樣而不丟失任何信息

8、； DFT變換進(jìn)一步告訴我們，對(duì)于時(shí)間有限的信號(hào)（有限長序列），也可以對(duì)其進(jìn)行頻域采樣，而不丟失任何信息，這正反應(yīng)了傅立葉變換中時(shí)域、頻域的對(duì)稱關(guān)系。它有十分重要的意義，由于時(shí)域上的采樣，使我們能夠采用數(shù)字技術(shù)來處理這些時(shí)域上的信號(hào)（序列），而DFT的理論不僅在時(shí)域，而且在頻域也離散化，因此使得在頻域采用數(shù)字技術(shù)處理成為可能。 FFT就是頻域數(shù)字處理中最有成效的一例。,44,2.1 小結(jié),傅里葉變換的幾種形式 離散傅里葉級(jí)數(shù)DFS 離散傅里葉變換DFT定義 離散傅里葉變換DFT性質(zhì),45,2.2 利用DFT作連續(xù)信號(hào)的頻譜分析,利用DFT對(duì)連續(xù)信號(hào)進(jìn)行頻譜分析的方法 混疊 泄漏 柵欄效應(yīng) DF

9、T的分辨率 周期信號(hào)的譜分析 參數(shù)選擇的原則,46,離散傅氏變換雖然適合于在計(jì)算機(jī)上計(jì)算實(shí)現(xiàn)，但它是針對(duì)有限長離散信號(hào)（或離散周期信號(hào)）定義的。對(duì)于一般的連續(xù)非周期信號(hào)x(t)，如何使用DFT計(jì)算頻譜？解決了這一問題DFT才具有實(shí)際意義。,47,利用DFT計(jì)算連續(xù)信號(hào)的頻譜,信號(hào)的頻譜分析：計(jì)算信號(hào)的傅里葉變換,2.2 利用DFT做連續(xù)信號(hào)的頻譜分析,48,49,要求：,1 采樣 混疊,50,解決辦法：提高采樣頻率；抗混疊濾波器,51,2 截短 泄漏,52,53,時(shí)間無限的信號(hào)，其頻帶寬度有限,在矩形函數(shù)頻譜的作用下，出現(xiàn)了頻譜泄漏。 時(shí)間有限的信號(hào)其頻帶寬度無限,54,解決頻譜泄漏的方法,增

10、加截短長度 選擇合適的窗函數(shù) 合理選取信號(hào)的截取部分,55,加窗,窗函數(shù)的旁瓣降低可以減小泄漏，但會(huì)導(dǎo)致主瓣變寬,56,3 時(shí)域周期化 柵欄效應(yīng),57,假設(shè)信號(hào)為100Hz，頻率分辨率為1Hz a中100Hz沒有柵欄效應(yīng) b中100.5Hz存在 C中100.2Hz存在,柵欄效應(yīng),58,4 取主值區(qū)域進(jìn)行計(jì)算,59,柵欄效應(yīng),DFT只計(jì)算離散點(diǎn)（基頻F0的整數(shù)倍處）的頻譜，而不是連續(xù)函數(shù),改善方法： 增加頻域抽樣點(diǎn)數(shù)N（時(shí)域補(bǔ)零），使譜線更密,60,DFT的頻率分辨率,誤解：加零可以增加頻率分辨率 通常規(guī)定DFT的頻率分辨率為 ，N是指信號(hào)x(n)的有效長度 不同長度的x(n)其DTFT的結(jié)果是

11、不同的；而相同長度的x(n)盡管補(bǔ)零的長度不同其DTFT的結(jié)果應(yīng)是相同的，他們的DFT只是反映了對(duì)相同的DTFT采用了不同的采樣密度。 提高DFT頻率分辨率的方法：增加采樣長度N,61,加零的效果,解釋X(k)的含義及加零的效果,62,參數(shù)選擇的一般原則：,（1）若已知信號(hào)的最高頻率 ，為防止混疊，選定采樣頻率 ； （2）根據(jù)頻率分辨率 ，確定所需DFT的長度 (3) 和N確定以后，即可確定相應(yīng)模擬信號(hào)的時(shí)間長度 這里T是采樣周期。,63,信號(hào)最高頻率與頻率分辨率之間的矛盾,要提高頻率分辨率,即 當(dāng)N給定,采樣頻率fs ，要不產(chǎn)生混疊,同時(shí)提高信號(hào)最高頻率和頻率分辨率，需要增加采樣點(diǎn)數(shù)N,64

12、,周期信號(hào)的譜分析,對(duì)于連續(xù)的單一頻率周期信號(hào) ， 為信號(hào)的頻率。 可以得到單一譜線的DFT結(jié)果，但這是和作DFT時(shí)數(shù)據(jù)的截取長度選得是否恰當(dāng)有關(guān)，截取長度N選得合理， 可完全等于 的采樣。,65,6,8,10,k,X(k),(a),(b),(c),(d),不同截取長度的正弦信號(hào)及其DFT結(jié)果,66,結(jié) 論,對(duì)于一般連續(xù)信號(hào)通過采樣、截?cái)?、周期化和主值?jì)算的處理，可以使用DFT計(jì)算其頻譜。處理過程中，可能產(chǎn)生混疊誤差、泄漏誤差和頻譜采樣?xùn)艡谛?yīng)。但只要采取適當(dāng)?shù)姆椒?，可以在滿足一定的精度要求之下，用DFT計(jì)算結(jié)果作為原連續(xù)信號(hào)頻譜。,混疊誤差處理：抗混疊濾波；提高采樣頻率。,泄漏誤差處理：截?cái)?/p>

13、窗函數(shù)的修正。,頻譜采樣?xùn)艡谛?yīng)：使頻譜的頻率分辨率滿足分析要求（頻率分辨率 F=1/NT），截?cái)鄶?shù)據(jù)長度N的選定，即連續(xù)信號(hào)分析時(shí)間為tp=NT。,67,2.2 小結(jié),利用DFT對(duì)連續(xù)信號(hào)進(jìn)行頻譜分析的方法 出現(xiàn)誤差及解決辦法 參數(shù)選擇的原則,68,69,DFT復(fù)習(xí),DFT與IDFT定義 DFT不區(qū)分周期信號(hào)與非周期信號(hào) DFT是周期函數(shù)，周期為N DFT以 對(duì)DTFT采樣 DFT標(biāo)號(hào)k對(duì)應(yīng)模擬頻率(單位為Hz)為 基于其有限的頻率分辨率，DFT會(huì)模糊頻譜的尖峰,例：DFT的濾波器解釋 例：心電圖的頻譜,70,2.3 快速傅里葉變換FFT,直接計(jì)算DFT的運(yùn)算量 按時(shí)間抽取的FFT 按頻率抽

14、取的FFT N為組合數(shù)的FFT和基四FFT（自學(xué)） Chrip-z變換（線性調(diào)頻z變換）（自學(xué)）,71,直接計(jì)算DFT的計(jì)算量,72,直接計(jì)算DFT的計(jì)算量,FFT不是一種新的傅里葉變換，只是DFT的一種快速算法,73,FFT基本思想,時(shí)間抽選法 DIT: Decimation-In-Time 頻率抽選法 DIF: Decimation-In-Frequency,74,DFT系數(shù)的性質(zhì),75,2.3.1 按時(shí)間抽取的FFT,76,按時(shí)間抽取的FFT算法原理,77,按時(shí)間抽取的FFT算法原理,78,按時(shí)間抽取的FFT算法原理,X1（k），X2（k）為N/2點(diǎn)的DFT，周期為N/2,79,按時(shí)間抽

15、取的FFT算法原理,80,按時(shí)間抽取的FFT蝶形運(yùn)算,(前一半),(后一半),1 1,1,1,-1,81,按時(shí)間抽取的FFT計(jì)算量分析,82,按時(shí)間抽取的FFT8點(diǎn)FFT例子,83,按時(shí)間抽取的FFT8點(diǎn)FFT例子,84,按時(shí)間抽取的FFT8點(diǎn)FFT例子,85,按時(shí)間抽取的FFT運(yùn)算量,由上述分析可知,N=8需三級(jí)蝶形運(yùn)算 N=23=8,由此可知,N=2L 共需L級(jí)蝶形運(yùn)算, 而且每級(jí)都由N/2個(gè)蝶形運(yùn)算 組成,每個(gè)蝶 形運(yùn)算有一次復(fù)乘,兩次復(fù)加。 因此,N點(diǎn)的FFT的運(yùn)算量為 復(fù)乘: mF =（N/2）L=（N/2） log2N 復(fù)加: aF =N L=N log2 N,86,按時(shí)間抽取的F

16、FT算法特點(diǎn),原位計(jì)算,輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器。,87,按時(shí)間抽取的FFT算法特點(diǎn),蝶形類型隨迭代次數(shù)成倍增加,第L級(jí)共有2L-1個(gè)系數(shù),88,按時(shí)間抽取的FFT算法特點(diǎn),蝶形運(yùn)算規(guī)律,第L級(jí)共有2L-1個(gè)系數(shù),89,按時(shí)間抽取的FFT算法特點(diǎn),序數(shù)重排,90,按時(shí)間抽取的FFT算法特點(diǎn),序數(shù)重排,n =0,0,n =1,0,n =0,1,n =1,1,n =0,1,n =1,1,0,1,0,1,0,1,0,1,(n2),x(000) 0,x(100) 4,x(010) 2,x(110) 6,x(001) 1,x(101) 5,x(011) 3,x(111) 7,（偶）

17、,（奇）,91,按時(shí)間抽取的FFT算法特點(diǎn),倒位序的實(shí)現(xiàn),0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7,自然順序n 二進(jìn)制n n n 倒位序二進(jìn)制n n n 倒位順序n,2 1 0 0 1 2,92,時(shí)域采樣造成頻域延拓,93,2.3.2 按頻率抽取的FFT,94,按頻率抽取的FFT-算法原理,95,按頻率抽取的FFT-蝶形運(yùn)算,先蝶形運(yùn)算再進(jìn)行DFT,96,按頻率抽取的FFT-8點(diǎn)FF

18、T例子,97,按頻率抽取的FFT-8點(diǎn)FFT例子,x(0) X(0) x (1) X(4) x(2) X(2) x(3) X(6) x(4) X(1) x(5) X(5) x(6) X(3) x(7) X(7),-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,98,按頻率抽取的FFT-運(yùn)算特點(diǎn),蝶形運(yùn)算,原位運(yùn)算,99,按頻率抽取的FFT-運(yùn)算特點(diǎn),蝶形類型隨迭代次數(shù)成倍減少,第L級(jí)共有2M-L個(gè)系數(shù),100,按頻率抽取的FFT-運(yùn)算特點(diǎn),蝶形運(yùn)算規(guī)律,第L級(jí)共有2L-1個(gè)系數(shù),101,按頻率抽取的FFT-運(yùn)算特點(diǎn),序數(shù)重排,102,DIT法與DIF法的異同,原位運(yùn)算

19、運(yùn)算量相同 序數(shù)重排 蝶形運(yùn)算,103,DIT與DIF算法的流圖對(duì)比,輸入變輸出 輸出變輸入 流圖反轉(zhuǎn),104,頻域采樣造成時(shí)域延拓,105,2.3.3 N為組合數(shù)的FFT和基四FFT,自學(xué) 基本思想是將DFT的運(yùn)算盡量分小，減少運(yùn)算量,106,2.3.4 Chrip-z變換線性調(diào)頻z變換,自學(xué) 不需要計(jì)算整個(gè)單位圓上z變換的取樣，如對(duì)于窄帶信號(hào)，只需要對(duì)信號(hào)所在的一段頻帶進(jìn)行分析，這時(shí),希望頻譜的采樣集中在這一頻帶內(nèi)，以獲得較高的分辨率，而頻帶以外的部分可不考慮。 對(duì)其它圍線上的z變換取樣感興趣，例如語音信號(hào)處理中，需要知道z變換的極點(diǎn)所在頻率，如極點(diǎn)位置離單位圓較遠(yuǎn)，則其單位圓上的頻譜就很

20、平滑，如果采樣不是沿單位圓而是沿一條接近這些極點(diǎn)的弧線進(jìn)行，則在極點(diǎn)所在頻率上的將出現(xiàn)明顯的尖峰，由此可較準(zhǔn)確地測(cè)定極點(diǎn)頻率。 要求能有效地計(jì)算當(dāng)N是素?cái)?shù)時(shí)序列的DFT。,107,2.3 小結(jié),按時(shí)間抽取的FFT 按頻率抽取的FFT,108,2.4 關(guān)于FFT應(yīng)用的幾個(gè)問題,用FFT計(jì)算IDFT 實(shí)數(shù)序列的FFT 線性卷積的FFT算法 用FFT計(jì)算相關(guān)函數(shù) 用FFT計(jì)算二維離散傅里葉變換,109,2.4.1 用FFT計(jì)算IDFT,110,2.4.2 實(shí)數(shù)序列的FFT,X(k)、 Y(k)復(fù)數(shù)序列,111,循環(huán)卷積與線性卷積的關(guān)系,DFT只能計(jì)算循環(huán)卷積，但實(shí)際使用中經(jīng)常要求的是兩個(gè)序列的線性卷積，所以有必要討論一下循環(huán)卷積與線性卷積的關(guān)系。,112,循環(huán)卷積線性卷積的條件,若LN1N21，則L點(diǎn)循環(huán)卷積等于線性卷積而不產(chǎn)生混疊。,113,2.4.3 線性卷積的FFT算法,補(bǔ)L-N1 個(gè)零點(diǎn),補(bǔ)L-N2 個(gè)零點(diǎn),IFFT,x,x(n