離散傅里葉變換

1、第三章離散傅立葉變換(DFT)31 引言有限長序列在數(shù)字信號處理是很重要的一種序列，當然可以用Z變換和傅里葉變換來研究它，但是，可以導出反映它的"有限長"特點的一種有用工具是離散傅里葉變換(DFT)。離散傅里葉變換除了作為有限長序列的一種傅里葉表示法在理論上相當重要之外，而且由于存在著計算離散傅里葉變換的有效快速算法，因而離散傅里葉變換在各種數(shù)字信號處理的算法中起著核心的作用。有限長序列的離散傅里葉變換(DFT)和周期序列的離散傅里葉級數(shù)(DFS)本質(zhì)上是一樣的。為了更好地理解DFT，需要先討論周期序列的離散傅里葉級數(shù)DFS。而為了討論離散傅里葉級數(shù)及離散傅里葉變換，我們首

2、先來回顧并討論傅里葉變換的幾種可能形式。(連續(xù)時間信號：如果在討論的時間間隔內(nèi)，除若干不連續(xù)點之外，對于任意時間值都可給出確定的函數(shù)值，此信號就稱為連續(xù)時間信號。)一、連續(xù)時間、連續(xù)頻率連續(xù)傅立葉變換（FT）設(shè)x(t)為連續(xù)時間非周期信號，傅里葉變換關(guān)系如下圖所示：連續(xù)，非周期非周期，連續(xù)可以看出時域連續(xù)函數(shù)造成頻域是非周期的譜，而時域的非周期造成頻域是連續(xù)的譜。二、連續(xù)時間，離散頻率-傅里葉級數(shù)設(shè)f(t)代表一個周期為T1的周期性連續(xù)時間函數(shù)，f(t)可展成傅里葉級數(shù)，其傅里葉級數(shù)的系數(shù)為，f(t)和組成變換對，表示為:（）注意符號：如果是周期性的采樣脈沖信號p(t)，周期用T表示（采樣間隔

3、）。采樣脈沖信號的頻率為可以看出時域連續(xù)函數(shù)造成頻域是非周期的譜，而時域的周期造成頻域是離散的譜連續(xù)，周期 （時域周期為T1）非周期，離散 （離散間隔為W1）三、離散時間，連續(xù)頻率-序列的傅里葉變換正變換：DTFTx(n)=反變換：DTFT-1級數(shù)收斂條件為|=可以看出時域離散函數(shù)造成頻域是周期的譜，而時域的非周期造成頻域是連續(xù)的譜離散，非周期 （離散時間間隔為T）周期，連續(xù) （頻域周期為2p=Ws T）四、離散時間，離散頻率-離散傅里葉變換上面討論的三種傅里葉變換對，都不適用在計算機上運算，因為至少在一個域(時域或頻域)中，函數(shù)是連續(xù)的。因為從數(shù)字計算角度，我們感興趣的是時域及頻域都是離散的

4、情況，這就是我們這里要談到的離散傅里葉變換。時域抽樣間隔T，頻域周期Ws=2p/T，時域周期T1，頻域抽樣間隔W1=2p/T1周期序列的離散傅里葉級數(shù)（DFS）設(shè)是周期為N的一個周期序列，即，r為任意整數(shù)。和連續(xù)時間周期信號一樣，周期序列可用離散傅里葉級數(shù)來表示。離散傅里葉級數(shù)（DFS）對：正變換=DFS = = 反變換=IDFS=式中，和均為整數(shù)。觀察=。是一個周期序列嗎？如是，周期為多少？=。所以。是一個周期序列，周期為N。，周期為N，周期也為N。觀察=，與連續(xù)時間信號與系統(tǒng)中的傅里葉級數(shù)對應，表明將周期序列分解成N個獨立諧波分量。第0次諧波序列，基波序列，第k次諧波序列，第N-1次諧波序

5、列。諧波頻率，k=0，1，2，N-1，幅度為。例如：基波分量的頻率為2p/N，幅度是。一個周期序列可以用其DFS表示它的頻譜分布規(guī)律。例題：如圖所示，求的DFS解：=DFS = = =，|如下圖所示。離散傅立葉變換（DFT）周期序列實際上只有有限個序列值才有意義，因而它的離散傅里葉級數(shù)表示式也適用于有限長序列，這就可以得到有限長序列的傅里葉變換(DFT)。設(shè)x(n)是一個長度為M的有限長序列，正變換=DFT = = k=0，1，2，N-1 （）反變換=IDFT=n=0，1，2，N-1 （）式中，N稱為DFT變換區(qū)間長度，NM。例311：= R4(n)，求的8點和16點DFT。解：（1）DFT變

6、換區(qū)間N=8，則：=，k=0，1，7（2）DFT變換區(qū)間N=16，則：=，k=0，1，15DFS與DFT的關(guān)系1、 有限長序列和周期序列的關(guān)系設(shè)x(n)是一個長度為M的有限長序列，以N（NM）為周期進行周期延拓得。是x(n)的周期延拓。如下圖所示：M=4，N=8，以N=8進行周期延拓。的周期為8 。用式子表示：或x(n 模 N)x(n)N，(n 模 N)表示n對N取余數(shù)例：設(shè)是以N=8周期對有限長序列x(n)（長度M=4）進行周期延拓得到的。x(3)，=x(2)。有限長序列進行周期延拓得到周期序列。定義：周期序列中從n=0到N-1的第一個周期為的主值區(qū)間，而主值區(qū)間上的序列稱為的主值序列周期序

7、列的主值序列是有限長序列利用前面的矩形序列符號RN(n)RN(n)= 1 ，0nN-1 0 ，其他nx(n)=RN(n)x(n)的周期延拓序列是；x(n)N的主值序列是x(n)； x(n)=RN(n)同理把頻域周期序列也看作是有限長序列X(k)的周期延拓。 X(k)是的主值序列X(k)的周期延拓序列是；X(k)N的主值序列是X(k)； X(k)= RN(n)具體而言，我們把時域周期序列看作是有限長序列x(n)的周期延拓；同理把頻域周期序列也看作是有限長序列X(k)的周期延拓。這樣我們只要把DFS的定義式兩邊取主值區(qū)間，就得到了一個關(guān)于有限長序列的時頻域?qū)淖儞Q對。這就是數(shù)字信號處理課程里最重

8、要的變換-離散傅里葉變換(DFT)。離散傅立葉級數(shù)（DFS）對：正變換=DFS = = 反變換=IDFS=式中，和均為整數(shù)。離散傅里葉變換(DFT) 正變換：DFTx(n)= ，0kN-1反變換：x(n)=IDFT=，0nN-1或：RN(k)RN(k) x(n)= RN(n) = RN(n)DFT隱含有周期性。DFT和Z變換的關(guān)系設(shè)序列x(n)的長度為N，其Z變換和DFT分別為：DFTx(n)= ，0kN-1比較上面兩式可以得到：|，0kN-1 （）或=|，0kN-1 （）（）表明序列x(n)的N點DFT是x(n)的Z變換在單位圓上的N點等間隔采樣。（）表明是x(n)的傅立葉變換在區(qū)間0，2上

9、的N點等間隔采樣。這就是DFT的物理意義。由此可見，DFT的變換區(qū)間長度N不同，表示對在0，2區(qū)間上的采樣間隔和采樣點數(shù)不同，所以DFT的變換結(jié)果不同。例311中，= R4(n)， DFT變換區(qū)間長度N分別取8點和16點，結(jié)果不同。下圖為R4(n)的傅立葉變換和R4(n)的8點、16點的對應圖。32 離散傅立葉變換的性質(zhì)一、線性設(shè)x1(n)、x2(n)是兩個有限長序列，長度分別為N1，N2，且y(n)=a x1(n)+b x2(n)，a，b為常數(shù)。N=maxN1，N2。x1(n) 有限長序列，長度為N；x2(n) 有限長序列，長度為N；y(n) 有限長序列，長度為N；x1(n)的N點DFT為：

10、X1(k)=DFTx1(n)= 0kN-1 x2(n)的N點DFT為：X2(k)=DFTx2(n)= 0kN-1y(n)的N點DFT為：Y(k)=DFTy(n) =a X1(k)+b X2(k)0kN-1二、循環(huán)移位定理1、 序列的循環(huán)移位設(shè)x(n)為有限長序列，長度為N，則x(n)的循環(huán)移位定義為（）（）表明先將x(n)以N為周期進行周期延拓得到序列= x(n)N，再將左移得到，最后取主值區(qū)間（n=0到N-1）上的序列值，則得到有限長序列x(n)的循環(huán)移位序列。過程如下圖所示：2、 時域循環(huán)移位定理設(shè)x(n)為有限長序列，長度為N，為 x(n)的循環(huán)移位序列，即，則DFT=其中=DFTx(n

11、)，0kN-1證明： =令n+m=n，則有=由于上式中求和項以N為周期，所以對其在任一周期上的求和結(jié)果相同。將上式的求和區(qū)間改在主值區(qū)間，則得：=，0kN-13、 頻域循環(huán)移位定理如果=DFTx(n)，0kN-1=則：y(n)=IDFT=x(n)證明：y(n) =IDFT= =令=，則有：y(n)= =（）=（）=（）=x(n)三、循環(huán)卷積定理有限長序列x1(n)和x2(n)，長度分別為N1和N2， N=maxN1，N2。x1(n)和x2(n)的N點DFT分別為：X1(k)=DFTx1(n)X2(k)=DFTx2(n)如果X(k)= X1(k) X2(k)則：x(n)= IDFTX(k)= 循

12、環(huán)卷積過程：循環(huán)卷積過程中，要求對循環(huán)反轉(zhuǎn)，循環(huán)移位，特別是兩個長度位N的序列的循環(huán)卷積長度仍為N。顯然與一般的線性卷積不同，故稱為循環(huán)卷積。記為：x(n) = 四、復共軛序列的DFT設(shè)是的復共軛序列，長度為N，已知DFT，則 DFT= 0kN-1且證明：DFT=RN(k) =RN(k) =RN(k) =RN(k)=，0kN-1已知DFT，則 DFT=證明：DFT，即=IDFT= = = = =IDFT即DFT=五、DFT的共軛對稱性第二章2.2節(jié)中已詳細討論了序列傅立葉變換的對稱性，那里的對稱性是指關(guān)于坐標原點的縱坐標對稱性。DFT也有對稱性，但由于DFT中討論的序列及其離散傅立葉變換均為有

13、限長序列，且定義區(qū)間為0到N-1，所以這里的對稱性是指關(guān)于N/2點的對稱性。下面討論DFT的共軛對稱性質(zhì)。1、 有限長共軛對稱序列和共軛反對稱序列為了區(qū)別于序列傅立葉變換中所定義的共軛對稱和共軛反對稱序列，下面用和分別表示有限長共軛對稱序列和共軛反對稱序列。二者的定義如下：=，0nN-1=，0nN-1(關(guān)于N/2點的對稱性)當N 為偶數(shù)時，將上式的n換成N/2-n，得到=，0nN/2-1當N為奇數(shù)時，將上式的n換成(N-1)/2-n，得到=，0n(N-1)/2-1任意有限長序列可表示成共軛對稱分量和共軛反對稱分量之和。=+ 0nN-1將上式中的n換成N-n，并取復共軛，得到：=+=-=（+）=

14、（）2、 DFT 的共軛對稱性（1）將有限長序列x(n)分成實部與虛部，即：=+j則：證明：=（+） DFT=（+） =j=（）DFTj=（） =（2）將有限長序列x(n)分成共軛對稱部分和共軛反對稱部分，即=+，0nN-1則：證明：=（+）DFT=（+） =（）DFT=（） =33 頻率域抽樣理論時域采樣定理告訴我們，在一定條件下，可以由時域采樣信號恢復原來的連續(xù)信號。那么能不能也由頻域采樣信號恢復頻域連續(xù)信號？頻域采樣理論是什么？已知序列及序列的長度為M。的Z變換為：。因為收斂域包含單位圓，所以其序列傅立葉變換存在。對在區(qū)間0，2 上進行N點等間隔采樣（對X(z)在單位圓上進行N點等間隔采

15、樣），得到或|=，0kN-1 將進行IDFS得周期序列，取的主值序列，與原序列相等嗎？相等的條件是什么？由此導出頻域采樣定理。=IDFS=，r為整數(shù)=式中= 1 m=n+rN，r為整數(shù) 0 其他m從上式得：X(z)在單位圓上的N點等間隔采樣的IDFS，為原序列以N為周期的周期延拓序列。=RN(n)=RN(n) (3.3.3)所以只有當頻域采樣點數(shù)NM時，才有=IDFT=即可由頻域采樣恢復原序列，否則產(chǎn)生時域混疊現(xiàn)象。這就是頻域采樣定理。滿足頻域采樣定理，NM，即可由頻域采樣來表示的。設(shè)序列長度為M，在頻域02之間等間隔采樣N點，NM。|，0kN-1 根據(jù)頻域抽樣定理，=IDFT=，稱為內(nèi)插函數(shù)

16、=，稱為內(nèi)插公式當z=時，=進一步化簡，可得：=在數(shù)字濾波器的結(jié)構(gòu)與設(shè)計中，我們將會看到，頻域采樣理論及有關(guān)公式可提供一種有用的濾波器結(jié)構(gòu)和濾波器設(shè)計途徑。3. 4 DFT的應用舉例一、求兩個不同實序列、的N點DFT。=+j（+）（）利用DFT的共軛對稱性 DFT=（+） =DFTj=（） =DFT=（）二、用DFT計算線性卷積1、 線性卷積線性移不變系統(tǒng) h(n)x(n)y(n)y(n)=x(n)*h(n)= 設(shè)兩序列分別的長度是N和M，線性卷積后的序列長度為（N+M-1）2、 循環(huán)卷積和的N點DFT分別為：X1(k)=DFTX2(k)=DFT如果X(k)= X1(k) X2(k)，0kN-

17、1則：x(n)= IDFTX(k)= x(n) 3、 循環(huán)卷積的計算由于DFT有快速算法FFT，當N很大時，在頻域計算的速度快得多，因而常用DFT（FFT）計算循環(huán)卷積。4、 利用循環(huán)卷積計算線性卷積在實際應用中，為了分析時域離散線性系統(tǒng)對序列進行濾波處理等，需要計算兩個序列的線性卷積。與計算循環(huán)卷積一樣，為了提高運算速度，也希望用DFT（FFT）計算線性卷積。而DFT只能直接用來計算循環(huán)卷積。線性卷積和循環(huán)卷積之間有什么關(guān)系？假設(shè)h(n)和x(n)都是有限長序列，長度分別是N和M。它們的線性卷積=x(n)* h(n)= h(n)*x(n)=，長度為N+M-1。取LmaxN，M，h(n)和x(

18、n)的循環(huán)卷積 h(n) éx(n) = x(n)L = = (3.4.3)上式說明，等于以L為周期進行周期延拓序列的主值序列。的長度為N+M-1，因此只有當循環(huán)卷積長度LN+M-1時，等于。例如：如下圖所示，N=4，M=5，線性卷積長度=8，當取循環(huán)卷積長度為6時，當取循環(huán)卷積長度為8時，=當取循環(huán)卷積長度為10時，=小結(jié)：取L=N+M-1，可用DFT計算線性卷積。這種方法稱為快速卷積。用DFT計算線性卷積的框圖如下：當MN時，L=N+M-1，h(n)需補很多零點，且長序列必須全部輸入后才能進行快速計算。因此要求存儲容量大，運算時間長，如在處理地震信號和語音信號時。實際中采用的方法

19、是將長序列分段計算，這種分段處理方法有兩種：重疊相加法和重疊保留法。5、 重疊相加法設(shè)序列h(n)長度為N，x(n)為無限長序列。將x(n)均勻分段，每段長度取M，則式中h(n)和x(n)的線性卷積 h(n)*x(n)= h(n)* = =式中運算過程如下圖所示：每一分段卷積的長度為N+M-1，因此與有N-1個點重疊，必須把重疊部分的與相加，才能得到完整的卷積序列。這種方法不要求大的存儲容量，且運算和延時也大大減少。三、用DFT對信號進行譜分析所謂信號的譜分析，就是計算信號的傅立葉變換。連續(xù)信號與系統(tǒng)的傅立葉分析顯然不便于直接用計算機進行計算，使其應用受到限制，而DFT是一種時域和頻域均離散化

20、的變換，適合數(shù)值運算。對連續(xù)信號和系統(tǒng)，可以通過時域采樣，應用DFT進行近似譜分析。1、 用DFT對連續(xù)信號進行譜分析傅立葉變換理論：若信號持續(xù)時間有限長，則其頻譜無限寬；若頻譜有限寬，則其持續(xù)時間無限長。所以，嚴格地講，持續(xù)時間有限的帶限信號是不存在的。但在工程中，常用DFT對連續(xù)信號進行譜分析。對于持續(xù)時間無限長的信號，采樣點數(shù)太多以至無法存儲和計算，只好截取有限點；對于頻譜很寬的信號，為防止時域采樣后頻譜混疊失真，可用預濾波法濾除幅度較小的高頻成分，使連續(xù)信號的帶寬小于折疊頻率。這樣，連續(xù)信號持續(xù)時間為有限長，為有限帶寬。為了利用DFT對進行頻譜分析，先對進行時域采樣得x(n)，再對x(

21、n)進行DFT得到X(k)，X(k)為x(n)的傅立葉變換在頻率區(qū)間0，2p上的N點等間隔采樣。這里X(k)和x(n)均為有限長。所以用DFT對連續(xù)信號進行譜分析是近似的，其近似程度與信號帶寬、采樣頻率和截取長度有關(guān)。設(shè)連續(xù)信號持續(xù)時間為，最高頻率為對以采樣間隔采樣得x(n)=。設(shè)共采樣N點，并對作零階近似，t=nT，dt=T 得：。顯然，仍是f的連續(xù)周期函數(shù)，如上圖b所示。對在區(qū)間0，上等間隔采樣N點，采樣間隔為F，如下圖c所示。參數(shù)、N、F的關(guān)系：=，=，=F=/N=將代入，得到的采樣：，0kN-1令=，x(n)=，= (3.4.7)用同樣的方法，由=推出：= t=nT，df=F， x(n

22、)= = (3.4.8)(3.4.7)說明，連續(xù)信號的頻譜特性可以通過對連續(xù)信號采樣并進行DFT再乘以T的近似方法得到。時域采樣信號可由(3.4.8)得到。2、 用DFT進行譜分析存在的問題柵欄效應：只能看見N個離散采樣點的譜特性，看不到的全部頻譜特性。由于柵欄效應，有可能漏掉(擋住)大的頻譜分量。為了把原來被“柵欄”擋住的頻譜分量檢測出來，可以采用在原序列尾部補零的方法，改變序列長度N(即改變DFT變換區(qū)間長度)，從而增加頻域采樣點數(shù)和采樣點位置，使原來漏掉的某些頻譜分量被檢測出來。頻率響應的混疊失真及參數(shù)選擇：設(shè)信號最高頻率為，按時域抽樣定理，抽樣頻率2，采樣間隔（時域抽樣之前用預濾波器將高于頻率的信號分量加以濾除），否則會產(chǎn)生頻率響應的混疊失真。一般情況下取=（2.53.0）對于DFT，頻率函數(shù)也要抽樣變成離散序列，抽樣間隔為F，時域周期為=。F稱為頻率分辨率，顯然F越小，譜分析的結(jié)果