第03章 離散傅氏變換DFT及其快速算法FFT《數(shù)字信號處理》程配清版課件

1、第三章 離散傅氏變換DFT及其快速算法FFT有時序列是有限時寬的，在這種特殊情況下可以導出另一種傅氏表示式，稱作離散傅氏變換DFT(Discret Fourier Transform)。DFT在理論上有重要意義，利用DFT的快速算法FFT，可以在實現(xiàn)各種數(shù)字信號處理的算法中起到核心作用。3.1 問題的提出3.2 DFS與DFT導出3.3 DFS與DFT的性質(zhì)3.4 z變換與DFS的關(guān)系3.5 快速傅氏變換算法FFT3.6 時間抽選法FFT3.7 頻率抽選法 FFT3.8 基4FFT算法3.9 提高FFT運算效率的一些方法3.10 IDFT的快速算法IFFT3.11 Chirpz變換CZT算法3

2、.12 用DFT求線性卷積3.13 利用FFT進行頻譜分析3.1 問題的提出本章所討論的DFT就是在xa(t)為有限時寬時解決這一問題的方法。3.2 DFS與DFT導出設(shè)一連續(xù)信號 xa(t)是有限時寬的，其傅氏變換是限帶的(根據(jù)信號理論，假設(shè)信號在時域內(nèi)受限，即它被乘以矩形窗函數(shù)，那么在頻域內(nèi)將是無限的，反之亦然，因此，必須要限帶)，如圖3-1(a)所示，它們之間的傅氏變換關(guān)系為式(3-1)。圖3-1 在時域或頻域中對某一函數(shù)抽樣，抽樣函數(shù)在另一域中的映射2. DFS的分析以上定性分析了推導DFS與DFT的過程，現(xiàn)在進行定量分析。如果在時域內(nèi)取樣，取樣周期為T，那么頻域周期延拓，可用傅氏級數(shù)

3、來描述為傅氏級數(shù)的系數(shù)xa(nT)正是 xa(t)的取樣函數(shù)，可寫成3. DFT的導出DFT的條件對時域取樣與頻域取樣間隔或取樣率的要求，是實現(xiàn)DFT的條件，即其中，s 是時域取樣頻率；l是頻域取樣間隔。3.3 DFS與DFT的性質(zhì)1. DFS的性質(zhì)(1) 線性(2) 序列的移位(3) 對稱性(4) 周期卷積2. DFT的性質(zhì)(1) 線性關(guān)系如果有兩個有限時寬序列x1(n)和x2(n)的線性組合，為x3(n)=ax1(n)+bx2(n)那么x3(n)的DFT為X3(k)=aX1(k)+bX2(k)式中a、b為任意常數(shù)(2) 序列的循環(huán)移位(3) 對稱性因此，有必要對xe(n)和xo(n)的定義

4、根據(jù)DFT的特點進行修改，給出一種新的定義，即周期共軛對稱分量和周期共軛反對稱分量xep(n)和xop(n)。3.4 z變換與DFS的關(guān)系1.z變換在單位圓上的取樣令x(n)是周期序列x(n)的一個周期，即z變換的內(nèi)插表示設(shè)有一非周期有限長序列x(n)，其只在0nN-1范圍內(nèi)有值，其余皆為零。那么x(n)的z變換為3.5 快速傅氏變換算法FFTFFT是Fast Fourier Transform的縮寫，換句話說，F(xiàn)FT是實現(xiàn) DFT(Discret Fourier Transform)的一種快速運算手段。FFT算法可分為時間抽選法和頻率抽選法。3.6 時間抽選法FFT時間抽選法，就是在時域內(nèi)逐

5、次將序列分解成奇數(shù)子序列和偶數(shù)子序列，通過求子序列的DFT而實現(xiàn)整個序列的DFT，將計算DFT的運算量從N2復乘減少到(N2)log2N次復乘。1.根本原理設(shè)輸入信號的列向量x(n)x(0)，x(1)，x(N-1)T，其DFT為X(k)X(0)，X(1)，X(N-1)T。將集合x(n)分解為兩個交錯集合，一個由偶數(shù)點組成，另一個由奇數(shù)點組成。采用如此分解方法，集合X(k)的前N2個元素可寫成圖3-6 8點DFT 分解為兩個4 點DFT圖3-7(a) 4點DFT分解為兩個2點DF圖3-7(b) 2點DFT信號流圖圖3-8 8點FFT 信號流圖圖3-9 FFT根本蝶形圖設(shè)共有復數(shù)乘法Mc次，那么M

6、c=N/2log2N/2對于復數(shù)加法，每次迭代有N次復數(shù)相加，共有l(wèi)og2N次迭代含有復數(shù)相加，設(shè)復數(shù)相加的總數(shù)為Ac，那么Ac=Nlog2N4. Matlab的實現(xiàn)3.7 頻率抽選法 FFT1.根本原理 頻率抽選法就是在頻域內(nèi)將X(k)逐次分解成偶數(shù)點子序列和奇數(shù)點子序列，然后對這些分解得越來越短的子序列進行DFT運算，就可得整個頻域內(nèi)序列的FFT流圖。 X(k)集合的元素也可分解成兩個交錯的子集，一個是偶數(shù)點序列，另一個是奇數(shù)點序列。偶數(shù)點序列可用兩個矩陣乘積來表示，即2.信號流圖偶數(shù)序列和奇數(shù)序列的X(k)可由TN/2方陣如圖3-10所示那樣得到。圖3-10 分解TN為兩個TN/2的根本

7、蝶形圖圖3-12頻率抽選法N=8的FFT運算流圖3.8 基4FFT算法與以前講過的比較，基2和基4的加法次數(shù)算法相同，與基2相比基4算法的復乘數(shù)可以節(jié)約25%。經(jīng)過分析可以得出基8比基4的復乘數(shù)相差不遠，節(jié)約有限。3.9 提高FFT運算效率的一些方法在同時要進行兩個長度相同的實序列的快速傅里葉變換時，可以用復序列的變換運算，一次求兩個實序列的變換，從而節(jié)約了運算量。假設(shè)有兩個長度相同的實序列h(n)和g(n)?？梢园阉鼈兘M合成一個復序列y(n)，即y(n)=h(n)+jg(n)3.8節(jié)已經(jīng)介紹了基4 FFT的算法，它比基2 FFT算法可節(jié)約25%以上的運算量。基8或更高基的FFT運算，節(jié)約運算

8、量有限。但基數(shù)越大，相應(yīng)的算法會越趨復雜，因此較少采用。3.10 IDFT的快速算法IFFT1. IFFT算法設(shè)有序列x(n)，其DFT為X(k)，那么IDFT為對于IFFT算法，輸入是X(k)，輸出是x(n)。在FFT的時間抽選法中得到了式(3-52)，即圖3-15 N4IFFT的信號流圖FFT的程序求IFFT的方法對DFT正變換式取共軛為再取一次共軛為得到利用FFT程序求IFFT的方法為(l) 將X(k)取共軛得X*(k)；(2) 將X*(k)進行FFT運算(用FFT程序)；(3) 對FFT的結(jié)果取共軛，并除以N得x(n)。3.11 Chirpz變換CZT算法1.Chirpz變換的推導Ch

9、irpz變換即線性調(diào)頻z變換，為了幫助理解線性調(diào)頻z變換這一概念我們先討論一下連續(xù)系統(tǒng)的情況。設(shè)有一連續(xù)系統(tǒng)，如圖3-16所示。圖3-16 連續(xù)CZT系統(tǒng)模型如果信號S(t)和h(t)都是線性調(diào)頻信號，它們的瞬時頻率以相反的變化率變化，輸入為f(t)Chirpz變換的步驟由圖3-18所示可以列出進行Chirpz變換(CZT)的幾個步驟。圖3-18 離散CZT模型(l) 選擇一個序列長度為LNM1，這個L是求離散卷積下出現(xiàn)重疊所需要的變換長度。選L為2的整數(shù)冪，以便進行FFT運算。(2) 構(gòu)成一個L點序列y(n)為3計算yn的L點DFT，可利用FFT算法求得Y(v)。4定義一個L點序列h(n)為

10、3.Matlab實現(xiàn)4. Chirpz變換的特點(2) 與FFT運算比較這種Chirpz變換與標準的FFT算法相比有以下特點。(1) 輸入與輸出序列的長度不需要相等，即不需要MN。(2) N與M不必是2的整數(shù)冪，即兩者都為合數(shù)或素數(shù)也可以。(3) zk點的間隔不必均勻相等，這樣可以得到任意的分辨率。3.12 用DFT求線性卷積1.問題的提出在實際問題中遇到的大多數(shù)是求解線性卷積。例如圖3-20所示的系統(tǒng)，輸入信號是x(n)，系統(tǒng)的單位取樣響應(yīng)是 h(n)，輸出信號是y(n)，那么它們的關(guān)系為圖3-20 離散系統(tǒng)的模型設(shè)長度都為N的兩個有限長序列x1(n)和x2(n)，它們的DFT分別為X1(K

11、)和X2(k), 如果有一序列x3(n)的DFT為X3(K)為那么X3(k) 的IDFT為下邊討論求循環(huán)卷積的方法。(1) 同心圓法將x1(n)與x2(n)分布在兩個同心圓上： 用兩個同心圓表示序列，如圖3-21所示。外圓按逆時針方向刻度x2(n)的值，內(nèi)圓按順時針方向刻度x1(n)的值，兩圓對應(yīng)的數(shù)兩兩相乘后求和得x3(0)； 將x2(n)順時針方向移一位，重復(a)得x3(1)； 依次類推得x3(n)，0nN1。圖3-21 用同心圓作圖求循環(huán)卷積(2) 波形作圖法(3) 解析式法(4) Matlab實現(xiàn)當符合式(3-85)的條件時，利用循環(huán)卷積可以實現(xiàn)線性卷積。這是一個很重要的結(jié)果，這是因

12、為存在如下定理假設(shè)那么式中y(n)=x(n)*h(n)。5.重疊相加法重疊相加法是將待過濾的信號分割成長為N1的幾段，每一段都可以和有限時寬單位取樣響應(yīng)作卷積，再將過濾后的各段重疊相加。6.重疊保存法重疊保存法相當于將xk(n)和h(n)作循環(huán)卷積，然后找出循環(huán)卷積中相當于線性卷積的局部。在這種情況下，將波形x(n)分為長為N的幾段，每個輸入段和前一段有M1個重疊點，將xk(n)定義為xk(n)=xn+k(N-M+1)0nN-1式中定義每一段的時間原點在該段的開始點而不是x(n)的原點。3.13 利用FFT進行頻譜分析在本節(jié)我們簡要地討論對于一個有限長、限帶信號x(t)，如何利用FFT算法求它的振幅頻譜、相位頻譜和功率譜。在第三章中較詳細地討論了對xa(t)在時域和頻域同時取樣可以得到DFS關(guān)系。進行頻譜分析的步驟如下所示。(1) 準備數(shù)據(jù)進行FFT運算首先要求序列的長度N=2L。對x(n)取L，使得