離散傅里葉變換(DFT)及其快速算法-莊.ppt

第三章 離散傅里葉變換（DFT） 及其快速算法,2,連續(xù)時間非周期信號的傅里葉變換為,傅里葉變換,3,傅里葉級數(shù),當x(t)為連續(xù)時間周期信號時，可展開為傅里葉級數(shù),4,對離散序列x(n)，其傅里葉變換為,若x(n)是信號x(t)的采樣序列，采樣間隔為T,則有：,序列的傅里葉變換,5,6,上述三種情況至少在一個變換域有積分(連續(xù))，因而不適合進行數(shù)字計算。,時域的離散造成頻域的延拓（周期性）。根據(jù)對偶性，頻域的離散也會造成時域的延拓（周期性）。,離散傅里葉變換,7,對序列的傅里葉變換在頻域上加以離散化， 令 從而,8,9,四種形式歸納,10,傅里葉變換是以時間為自變量的“信號”與以頻率為自變量的“頻譜”函數(shù)之間的某種變換關系。 離散傅里葉變換（DFT）則建立離散時域與離散頻域之間的關系。 DFT是分析有限長序列的有用工具，在各種信號的處理中起著核心作用。 FFT的出現(xiàn)使DFT對信號處理的發(fā)展起了巨大的推動作用。 DFT的實質(zhì)是有限長序列傅里葉變換的有限點離散采樣，是使得頻域離散化，使數(shù)字信號處理可以在頻域采用數(shù)字運算的方法進行。,離散傅里葉（DFT）變換的重要性,11,從傅里葉變換到離散傅里葉變換，及其應用要解決兩個問題： 離散與量化， 快速運算。,DFT是現(xiàn)代信號處理橋梁,12,3.1離散傅里葉變換的定義,3.1.1 DFT的定義 設x（n）是一個長度為M的有限長序列，x（n）的N點傅里葉變換： N稱為DFT變換區(qū)間長度， 令 ，記作旋轉(zhuǎn)因子 傅里葉變換與逆變換對為：,13,例3.1.1 分別計算序列的8點、16點DFT,解:8點DFT 16點DFT,14,是 在頻率區(qū)間 上的等間隔采樣。,15,一.預備知識 如果 ， m為整數(shù)；則有： 此運算符表示n被N除，商為m，余數(shù)為 。 是 的解，或稱作取余數(shù)，或說作n對N取模值，或簡稱為取模值，n模N。,16,例如： (1) (2),17,3.1.2 DFT與DFS、ZT、FT之間的關系,1. DFT與DFS之間的關系 有限長序列 周期序列 主值區(qū)間序列,是 主值區(qū)間序列,18,19,20,周期序列 與有限長序列X(k)的關系,同樣， 周期序列 是有限長序列X(k)的周期延拓。,而有限長序列X(k)是周期序列 的主值序列。,21,周期序列的DFS,有限長序列的DFT,是 的主值區(qū)間序列，成立條件NM,22,DFS,DFT,23,DFT與DFS之間的關系:,有限長序列x(n)的DFT變換X(k)，就是x(n)的周期延拓序列 的DFS系數(shù) 的主值序列,24,DFS與FT之間的關系:,周期延拓序列的頻譜特性由傅里葉級數(shù)的系數(shù) 確定，幅度相差一個常數(shù)因子 DFT: 是 的主值區(qū)間序列， 因此 能表示周期序列的頻譜特性，即DFT能夠描述FT的特征,25,2.DFT與FT、ZT之間的關系,有限長序列 DFT與ZT、FT、DFS,26,DFT與z變換,DFT與DTFT變換,序列x(n)的N點DFT是 x(n)的Z變換在單位圓上的N點等間隔采樣； X(k)為x(n)的傅里葉變換 在區(qū)間 上的N點等間隔采樣。這就是DFT的物理意義。,27,例：,解：,28,3.1.3 DFT的矩陣方程表示（1）,29,3.1.3 DFT的矩陣方程表示（2）,IDFT的矩陣表示,30,小結(jié),DFT 引入的目的 DFT 的定義 DFT與DFS、ZT、FT之間的關系 DFT、IDFT的計算 DFT的矩陣表示,3.2 離散傅里葉變換（DFT） 的主要性質(zhì),32,1線性性質(zhì),設x1(n)，x2(n)為有限長序列，長度分別為 它們的離散付里葉變換分別為 若 則,33,和 的長度N1和N2不等時， 選擇 為變換長度,短者進行補零達到N點。,34,2.DFT的隱含周期性,由于,所以X(k)滿足：,物理意義：X(k)為 在區(qū)間 上的N點等間隔采樣。 以2為周期，X(k)以N為周期。,35,3. 循環(huán)移位性質(zhì),循環(huán)移位: 有限長序列x(n),序列長度為M，對序列進行周期延拓，周期NM x(n)的循環(huán)移位序列： 左移m個單位，取主值序列 循環(huán)移位序列的DFT與原序列x(n)的DFT有何關系？,36,37,圓周位移的含義 由于我們?nèi)≈髦敌蛄?，即只觀察n=0到N-1這一主 值區(qū)間，當某一抽樣從此區(qū)間一端移出時，與它相同 值的抽樣又從此區(qū)間的另一端進來。如果把 排列 一個N等分的圓周上，序列的移位就相當于 在圓 上旋轉(zhuǎn)，故稱作圓周移位。當圍著圓周觀察幾圈時， 看到就是周期序列 : 。,38,n=0,N=6,循環(huán)移位序列的DFT與原序列x(n)的DFT有何關系？,39,序列循環(huán)移位后的DFT,則 證明:,40,同樣，對于頻域有限長序列X(k)的循環(huán)移位，有如下反變換特性：,41,4復共軛序列的DFT,設 為 的復共軛序列，長度為N 則 證明： 類似地：,42,5DFT的共軛對稱性,DFT變換涉及到的x(n)和X(k)均為有限長序列，定義區(qū)間為 0到N-1，所以這里的對稱性是指關于N/2點的對稱性。 有限長共軛對稱序列 當N為偶數(shù)時，用N/2-n替代n,43,共軛反對稱序列,當N為偶數(shù)時，用N/2-n替代n 對于任何有限長序列x(n)，均可表示為 用N-n替代n，取共軛 于是,44,DFT的共軛對稱性,將序列分成實部與虛部之和 則：,45,將序列分成共軛對稱和共軛反對稱之和 則：,46,DFT的共軛對稱性小結(jié)：,實部 共軛對稱分量 J虛部 共軛反對稱分量,47,實序列DFT的特點,設x(n)為長度為N的實序列，且X(k)=DFTx(n)，則 寫成極坐標形式 則 關于k=N/2點偶對稱 關于k=N/2點奇對稱,48,實數(shù)序列的DFT滿足共軛對稱性，利用這一特性，只要知道一半數(shù)目的 X（k），就可得到另一半的 X（k），這一特點在DFT運算中可以加以利用，以提高運算效率。 計算一個復序列的N點DFT，可求得兩個不同實序列的DFT 例 是實序列，長度均為N DFT,49,實序列2N點的DFT，拆分重組為N點復序列的DFT,例 是實序列，長度為2N 拆分 重組 N點DFT,50,6. 循環(huán)卷積定理,兩個有限長序列的循環(huán)卷積 序列 的長度分別為N和M 與 的L點循環(huán)卷積定義為,L點循環(huán)卷積 循環(huán)卷積 線性卷積,51,52,0,m,0,m,0,m,0,m,53,54,最后結(jié)果：,55,利用矩陣計算循環(huán)卷積,形成 的循環(huán)倒相序列,形成的序列為,56,當n、m從0變換到L-1時，得到 的矩陣,第一行是 的循環(huán)倒相序列 前一行向右循環(huán)移位形成其它行 與諸對角線平行的線上，各元的值相等,57,循環(huán)卷積矩陣計算公式,58,例3.2.1計算序列 的4點和8點循環(huán)卷積,解 4點循環(huán)卷積,59,8點循環(huán)卷積,循環(huán)卷積結(jié)果等于線性卷積 循環(huán)卷積計算復雜,60,DFT的時域循環(huán)卷積定理（1）,序列 的長度分別為N和M 與 的L點循環(huán)卷積定義為 且 則,61,DFT的時域循環(huán)卷積定理（2）,證明：,62,DFT的時域循環(huán)卷積定理（3）,以L為周期,DFT： 時域循環(huán)卷積 頻域乘積,63,序列循環(huán)卷積運算框圖,64,序列 的長度分別為N和M 則 證明：,DFT的頻域循環(huán)卷積定理,65,7. 離散巴塞伐爾定理（1）,序列 的長度為N DFT 則,66,7. 離散巴塞伐爾定理（2）,證明,序列在時域計算的能量等于其在頻域計算的能量,67,3.3 頻域采樣,時域采樣定理 采樣頻率大于等于奈奎斯特采樣頻率，可以由離散信號恢復原來的連續(xù)信號 頻域采樣定理,頻域抽樣呢？,抽樣條件？,內(nèi)插公式？,68,任意序列x(n)，其Z變換為 若Z變換X(z)的收斂域包含單位圓，即序列絕對可和，在單位圓上對X(z)等間隔采樣得到 是以N為周期的周期序列,69,由 恢復出x(n)的條件 x(n)序列長度有限； N大于x(n)序列長度,70,原若序列x(n)長度為M，其傅里葉變換為 對 在頻率區(qū)間 等間隔采樣得到 只有當頻域采樣點數(shù): 有 即可由頻域采樣 不失真地恢復原信號 ，否則產(chǎn)生時域混疊現(xiàn)象。,截取 的主值序列 一對DFT,71,72,序列x(n)長度為M，其Z變換為 其中 ，滿足頻域采樣定理 在Z平面的單位圓上，對X(z)進行采樣，采樣點數(shù)為N,3.3 頻域內(nèi)插公式,用頻域采樣 表示 的內(nèi)插公式?,73,問題：如何由 恢復,74,Z域內(nèi)插函數(shù),75,76,用 表示 的內(nèi)插公式和內(nèi)插函數(shù),77,保證了各采樣點上的值與原序列的頻譜相同； 采樣點之間，為采樣值與對應點的內(nèi)插公式相乘，并疊加而成。,78,小結(jié),頻域采樣定理 條件，以保證恢復原序列 x(n) 頻域的內(nèi)插公式,3.4 DFT的快速算法 快速傅里葉變換（FFT）,80,3.4.1問題的提出,4點序列2，3，3，2 DFT的計算復雜度,復數(shù)加法,N(N-1),復數(shù)乘法,N 2,如何提高DFT的運算效率?,81,1. 將長序列DFT分解為短序列的DFT,2. 利用旋轉(zhuǎn)因子 的周期性、對稱性。,解決問題的思路,82,旋轉(zhuǎn)因子 的性質(zhì),1)周期性,2) 對稱性,83,將時域序列逐次分解為一組子序列，利用旋轉(zhuǎn)因子的特性，由子序列的DFT來實現(xiàn)整個序列的DFT。,基2時間抽取(Decimation in time)DIT-FFT算法,基2頻率抽取(Decimation in frequency)DIF-FFT算法,3.4.2 基2FFT算法,84,序列 的 N 點DFT為 奇偶分解,DIT-FFT算法,85,分解為2個DFT 均以N/2為周期 利用 及DFT的隱含周期性，得,86,運算量 復數(shù)乘 復數(shù)加,87,蝶形圖及運算功能,C,A+CB,A,B,A-CB,88,4點基2時間抽取FFT算法流圖,X10,X11,X20,X21,X 0,X 1,X 2,X 3,-1,-1,89,8點DFT一次時域抽取分解運算流圖,N/2點 DFT,G(0),G(1),G(2),G(3),X(0),X(1),X(2),X(3),x(0),x(2),x(4),x(6),N/2點 DFT,H(0),H(1),H(2),H(3),X(4),X(5),X(6),X(7),x(1),x(3),x(5),x(7),WN1,WN2,WN3,-1,-1,-1,兩個4點DFT組成8點DFT,WN0,90,N/4點,N/4點,N/4點,N/4點,由四個2點DFT組成8點DFT,91,基2時間抽取FFT算法流圖,第一級,第二級,第三級,92,2. DIT-FFT的運算效率,N=2M的序列，通過M級分解最后成為1點的DFT運算。構(gòu)成M級運算過程。 每一級運算都由N/2個蝶形運算構(gòu)成。每一級運算含N/2次復乘和N次復加， 總運算量： 復乘 復加,93,運算效率,運算效率為204.8 運算效率為372.37,3.5 DFT（FFT）應用舉例,95,3.5.1用DFT（FFT）兩個有限長序列的線性卷積,求離散系統(tǒng)響應； 直接計算時間較長； 間接計算 DFT可計算循環(huán)卷積 FFT可加快運算速度 DFT能否計算線性卷積? 如可以，條件？,96,循環(huán)卷積與線性卷積等價的條件,循環(huán)卷積 線性卷積,97,圓周卷積是線性卷積的周期延拓序列的主值序列。,98,循環(huán)卷積計算線性卷積稱快速卷積法,99,例3.5.1,求,100,3.5.2有限長序列和無限長序列的線性卷積,問題： h(n) 為某濾波器的單位脈沖響應,長度有限； 輸入信號 x(n)很長； h(n) 要補許多零再進行計算,計算量有很大的浪費； 解決方案 重疊相加法 重疊保留法,101,1. 重疊相加法,分段。將 分段，每段長度為M 各段與 卷積 長度為N+M-1 求和,102,的定義區(qū)間 的定義區(qū)間為 的定義區(qū)間為 的定義區(qū)間為 的定義區(qū)間為 重疊區(qū)間,與,重疊區(qū)間,對應點相加,103,(1) 重疊相加法由分段卷積的各段相加構(gòu)成總的卷積輸出,h(n),x(n),104,105,基于FFT的重疊相加法的計算步驟,計算并保存 讀入 ，用L點FFT計算 Yi(k)=H(k)Xi(k) 用L點IFFT求 將重疊部分相加 i=i+1，返回2,實現(xiàn)實時計算！,106,例3.5.2 設 用重疊相加法實現(xiàn),L=41;N=5;M=10; hn=ones(1,N);hn1=hn zeros(1,L-N); %產(chǎn)生h(n)，補零是為了繪圖好看 n=0:L-1; xn=cos(pi*n/10)+cos(2*pi*n/5); %產(chǎn)生x(n)的L個樣值 yn=fftfilt(hn,xn,M); %調(diào)用fftfilt計算卷積 %= %以下為繪圖部分,107,3.5.3 用DFT對序列進行頻譜分析（1）,序列 的長度為M，序列 點DFT的物理意義： 序列的頻譜函數(shù) 在頻率區(qū)間 上的N點等間隔采樣 FFT是DFT的快速算法。 問題：如何確定N？,108,3.5.3 用DFT對序列進行頻譜分析（2）,根據(jù)頻率分辨率的要求確定N。 例：要求頻率分辨率為D弧度 滿足基2FFT對點數(shù)N的要求， i為正整數(shù)。 計算DFT，注意自變量k所對應的數(shù)字頻率為： N可依據(jù)先驗知識和實驗進行確定,109,例3.5.3