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

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