北京郵電大學《數字信號處理》課件-第3章 離散傅里葉變換（DFT）

第3章離散傅里葉變換（DFT）北京郵電大學《數字信號處理》2本章主要內容離散傅里葉變換的定義及物理意義離散傅里葉變換的基本性質頻率域采樣離散傅里葉變換的應用3引言各種形式的傅里葉變換非周期實連續(xù)時間信號的傅里葉變換:頻譜是一個非周期的連續(xù)函數

周期性連續(xù)時間信號的傅里葉變換:頻譜是非周期性的離散頻率函數

非周期離散時間信號的傅里葉變換:頻率函數是周期的連續(xù)函數離散周期序列的傅里葉變換:具有既是周期又是離散的頻譜，即時域和頻域都是離散的、周期的4各種形式的傅里葉變換示意圖5傅里葉變換的一般規(guī)律如果信號頻域是離散的，則該信號在時域就表現為周期性的時間函數。相反，在時域上是離散的，則該信號在頻域必然表現為周期性的頻率函數。如果時域信號離散且是周期的，由于它時域離散，其頻譜必是周期的，又由于時域是周期的，相應的頻譜必是離散的，離散周期序列一定具有既是周期又是離散的頻譜，即時域和頻域都是離散周期的。得出一般的規(guī)律：一個域的離散就必然造成另一個域的周期延拓。6離散傅里葉變換的導出由于數字計算機只能計算有限長離散的序列，因此有限長序列在數字信號處理中就顯得很重要。Z變換和傅里葉變換無法直接利用計算機進行數值計算。針對有限長序列“時域有限”這一特點，導出一種更有用的離散傅里葉變換DFT(DiscreteFourierTransform)。

73.1離散傅里葉變換的定義DFT的定義DFT和z變換、序列的傅里葉變換的關系DFT的隱含周期性83.1.1離散傅里葉變換的定義離散傅里葉正變換(DFT)定義0≤k≤N-1

0≤n≤N-1x(n)長度為M，其x(n)的N點離散傅里葉變換為：離散傅里葉反變換(IDFT)定義N稱為DFT變換區(qū)間長度，9例3.1：設有限長序列為x(n)=R4(n)，求x(n)的傅里葉變換，以及4點、8點、16點DFT。

解（1）x(n)的傅里葉變換

（2）x(n)的4點DFT例：離散傅里葉變換10（3）x(n)的8點DFTk=0，1，…，7

（4）x(n)的16點DFTk=0，1，…，15

15157711例3.1的圖形顯示同一序列不同點數的DFT是不相同的。x(n)的N點DFT是x(n)的傅里葉變換X(ejw)在區(qū)間[0，2π]上的N點等間隔取樣。123.1.2DFT和Z變換、序列的傅里葉變換的關系

設序列x(n)的長度為N，其Z變換、傅里葉變換和DFT分別為，0≤k≤N-113三種變換的關系

0≤k≤N-10≤k≤N-1比較三式可得式(3.3)表明，序列x(n)的N點DFT相當于是x(n)的z變換在單位圓上進行N點等間隔取樣，同時第一個取樣點應取在z=1處。式(3.4)說明，X(k)是x(n)的傅里葉變換X(ejw)在區(qū)間[0，2π]上的N點等間隔取樣。(3.3)(3.4)14DFT和Z變換的關系0≤k≤N-1N＝8時，單位圓上的8個等間隔采樣點示意圖如下：15DFT和序列的傅里葉變換的關系物理意義：X(k)是x(n)的傅里葉變換X(ejω)在區(qū)間

[0，2π]上的N點等間隔取樣。實現了頻域離散化

0≤k≤N-1163.1.3DFT的隱含周期性

DFT變換對中，具有周期性：其中k，m，N均為整數

因此有結論：X(k)具有隱含周期性，且周期均為N。同理可得IDFT也隱含周期性：式中17周期序列與周期延拓序列任何周期為N的周期序列都可以看作長度為N的有限長序列x(n)的周期延拓序列，而x(n)則是的一個周期，稱為的主值區(qū)序列（簡稱主值序列），即為了簡單，引入運算符((n))N，表示模N

對n求余數，即如果

n=mN+n1，0≤n1≤N-1，m為整數

則((n))N=

((n1+mN))N=n1

18例:序列的周期延拓例如，N=8，，則有

于是19X(k)與x((n))N的離散傅里葉級數系數的關系如果x(n)的長度為N，且，則可寫出的離散傅里葉級數表達式

式中結論：有限長序列x(n)的離散傅里葉變換X(k)，正好是x(n)的周期延拓序列x((n))N的離散傅里葉級數系數的主值序列。完全確定了x((n))N

的頻譜特性，所以，X(k)

實質上是x((n))N

的頻譜特性。這樣就容易理解R4(n)的4點DFT只有零頻率成分了。（因為R4((n))N正是一個直流序列）203.2離散傅里葉變換的基本性質

線性性質循環(huán)移位性質循環(huán)卷積定理復共軛序列的DFTDFT的共軛對稱性213.2.1線性性質設x1(n)和x2(n)長度分別為N1和N2，且取N≥max[N1，N2]，則y(n)的N點DFT為

0≤k≤N－1

注意：如果N1和N2不相等，則以N為DFT變換長度時，其中相對較短的序列就通過補零增加到長度為N。

223.2.2循環(huán)移位性質1、序列的循環(huán)移位設x(n)長度為N，則x(n)的循環(huán)移位定義為將x(n)以N為周期進行周期延拓得到再將左移m得到，最后取的主值序列則得到有限長序列x(n)的循環(huán)移位序列y(n)?？梢姡h(huán)移位的本質是周期移位。232、時域循環(huán)移位定理設x(n)是長度為N的有限長序列，y(n)為x(n)的循環(huán)移位，即

則其中，0≤k≤N-1時域循環(huán)移位定理24時域循環(huán)移位定理證明證明令n+m=n'，則有25頻域循環(huán)移位定理3、頻域循環(huán)移位定理如果X(k)=DFT[x(n)]N，0≤k≤N-1，Y(k)=X((k+l))NRN(k)，則證明方法與時域循環(huán)移位定理類似。26式中，L稱為循環(huán)卷積區(qū)間長度，L≥max［N，M］。上式顯然與第1章介紹的線性卷積不同，為了區(qū)別線性卷積，用表示循環(huán)卷積，用表示L點循環(huán)卷積，即yc(n)=h(n)

x(n)。觀察上式，x((n－m))L是以L為周期的周期信號，n和m的變化區(qū)間均是［0,L－1］，1、兩個有限長序列的循環(huán)卷積設序列h(n)和x(n)的長度分別為N和M。h(n)與x(n)的L點循環(huán)卷積定義為3.2.3循環(huán)卷積定理h0h7h6h5h4h3h2h1x0x7x5x6x4x3x2x127【例3.2.1】計算下面給出的兩個長度為4的序列h(n)與x(n)的4點和8點循環(huán)卷積。解h(n)與x(n)的4點循環(huán)卷積矩陣形式為h(n)與x(n)的8點循環(huán)卷積矩陣形式為h(n)和x(n)及其4點和8點循環(huán)卷積結果分別如圖(a)、(b)、(c)和(d)所示。請計算驗證本例的8點循環(huán)卷積結果等于h(n)與x(n)的線性卷積結果。后面將證明，當循環(huán)卷積區(qū)間長度L大于等于y(n)=h(n)*x(n)的長度時，循環(huán)卷積結果就等于線性卷積。

28

圖3.2.2序列及其循環(huán)卷積波形29例1.3線性卷積首先將h(n)用h(m)表示，并將波形翻轉，得到h(－m)，然后將h(－m)移位n，得到h(n－m)，n>0,序列右移；n<0，序列左移。如n=1，得到h(1-m)，接著將

x(m)和h(n－m)相乘后，再相加,得到y(tǒng)(n)的一個值。對所有的n重復這種計算,最后得到卷積結果，如圖1.3.2(f)所示,y(n)表達式為y(n)={1,2,3,4,3,2,1}30畫出h(m)與x(m)將x(m)周期化得到x((m))N再反轉形成x((-m))N取主值序列得到x((-m))NRN(m)對x

(m)循環(huán)反轉序列循環(huán)移位n,得到x((n-m))NRN(m)當n=0,1,…N-1時，分別將h(m)與x((n-m))NRN(m)相乘，并對m在0~(N-1)區(qū)間上求和，得到的h(n)與x(n)循環(huán)卷積31有限長序列x1(n)和x2(n)的長度分別為N1和N2，N=max［N1,N2］，x1(n)和x2(n)的N點循環(huán)卷積為

則x(n)的N點DFT為N

（3.2.9）2、循環(huán)卷積定理

（3.2.8）其中32循環(huán)卷積定理證明令n－m=n'，則有證明33

因為上式中以N為周期，所以對其在任一周期上的求和結果不變，因此0≤k≤N-1時域循環(huán)移位定理討論34頻域循環(huán)移位定理討論x(n)=x1(n)?x2(n)則或如果N

N

353.2.4復共軛序列的DFT復共軛序列的DFT設x*(n)是x(n)的復共軛序列，長度為N，0≤k≤N-1(3.17)則且又由X(k)的隱含周期性，有X(N)=X(0)用同樣的方法可以證明證明36

3.2.5DFT的共軛對稱性1、有限長共軛對稱序列和共軛反對稱序列xep(n)

表示有限長共軛對稱序列xop(n)

表示有限長共軛反對稱序列01234567xep(n)***01234xop(n)567***注意：

DFT的共軛對稱性是關于N/2點的對稱性37可得將上式中的n換成N－n，并取復共軛，得到：N為偶數時，將上式中的n換成N/2－n任何序列可表示為：38如果將x(n)表示為x(n)=xr(n)+jxi(n)其中2．DFT的共軛對稱性分別對實部和虛部DFT得：Xep(k)=DFT［xr(n)］是X(k)的共軛對稱分量Xop(k)=DFT［jxi(n)］是X(k)的共軛反對稱分量由DFT的線性性質即可得39

(2)如果將x(n)表示為x(n)的共軛對稱分量x(n)的共軛反對稱分量因此其中40如果序列x(n)的DFT為X(k)，則x(n)的實部和虛部（包括j）的DFT分別為X(k)的共軛對稱分量和共軛反對稱分量；x(n)的共軛對稱分量和共軛反對稱分量的DFT分別為X(k)的實部和虛部乘以j。DFT的共軛對稱性質41例題利用DFT的共軛對稱性，設計一種高效算法，通過計算一個N點DFT，就可以計算出兩個實序列

和的N點DFT。解：構造新序列

對進行N點DFT

42設x(n)是長度為N的實序列，且X(k)=DFT［x(n)］，則X(k)滿足如下對稱性：(1)X(k)共軛對稱，即X(k)=X*(N-k)k=0,1,…,N-1(2)如果x(n)是偶對稱序列，即x(n)=x(N－n)，則X(k)實偶對稱，即

X(k)=X(N－k)(3)如果是奇對稱序列，即x(n)=－x(N－n)，則X(k)純虛奇對稱，即X(k)=－X(N－k)433.3頻率域采樣

頻域采樣指對序列的傅里葉變換進行取樣。由時域取樣定理，在一定的條件下，可以通過時域離散取樣信號恢復原來的連續(xù)信號。對有限長序列而言，由DFT的討論可知，N點DFT就是在頻域對序列傅里葉變換X(jω)在[0,2π]上的N點等間隔取樣，即實現了頻域取樣。44對于任意序列x(n)，假設存在Z變換，且收斂域包括單位圓在單位圓上對X(z)進行N點等間隔取樣，得到

問題：能否利用取樣值X(k)恢復原始的時域信號x(n)？

3.3頻率域采樣

該式表示在區(qū)間[0,2π]上對x(n)的傅里葉變換的N點等間隔采樣X(k)看做長度為N的有限長序列xN(n)的DFTxN(n)=IDFT[X(k)]推導xN(n)與原序列x(n)之間的關系，即可得到頻率采樣定理

45將X(k)看成是長度為N的有限長序列的DFT，即0≤n≤N-1定義由于所以46代入頻率取樣值，得由于所以47

的意義

是原序列x(n)以N為周期的周期延拓序列。時域的取樣造成頻域的周期延拓，頻域上的取樣，同樣也造成時域的周期延拓，這正是傅里葉變換時域和頻域之間對偶關系的反映。如果序列x(n)的長度為M，當N<M

，產生時域混疊現象。只有當頻域取樣點數N≥M時這就是頻域采樣定理。483.4離散傅里葉變換的應用

用DFT計算線性卷積用DFT對連續(xù)信號進行譜分析用DFT對序列進行譜分析493.4.1用DFT計算線性卷積

設h(n)和x(n)都是長度為L的有限長因果序列，它們的L點循環(huán)卷積為且由時域循環(huán)卷積定理有0≤k≤L-1L50用DFT計算循環(huán)卷積方框圖用DFT計算循環(huán)卷積方框圖理由：DFT運算存在快速算法（FFT）。51循環(huán)卷積與線性卷積相等的條件條件：兩個長度分別為N和M的序列，其線性卷積可用L點循環(huán)卷積來代替，但必滿足條件

L≥N+M-1下面證明該條件。52卷積相等條件的討論假設h(n)長度為N，x(n)長度為M，則線性卷積為L點循環(huán)卷積為其中，L≥max[N，M]，53由上可得上式中因此54yc(n)是yl(n)以L為周期的周期延拓序列的主值序列。

由于卷積yl(n)的長度為N+M-1，因此當循環(huán)卷積的長度L≥N+M-1時，以L為周期的周期延拓才不會出現混疊現象，此時取主值序列顯然滿足yc(n)＝y(tǒng)l(n)

。說明：用DFT計算線性卷積的原理框圖（L≥N+M-1)55h(n)與x(n)的線性卷積可表示為設序列h(n)長度為N，x(n)為無限長序列。將x(n)等長分段，每段長度取M，則，兩個序列的長度相差很大的情況（M>>N）式中說明：計算h(n)與x(n)的線性卷積時，可先計算分段線性卷積yk(n)=h(n)*xk(n)，然后把分段卷積結果疊加起來即可，每一段卷積yk(n)的長度為N＋M－1，因此相鄰分段卷積yk(n)與yk＋1(n)有N－1個點重疊，必須把重疊部分的yk(n)與yk＋1(n)相加，才能得到正確的卷積序列y(n)。所以，稱之為重疊相加法。56圖3.4.3用重疊相