1、第3章 離散傅里葉變換(DFT),本章內(nèi)容,3.1 離散傅里葉變換的定義及物理意義 3.2 離散傅里葉變換的基本性質(zhì) 3.3 頻率域采樣 3.4 DFT的應(yīng)用舉例,引言,DFT是重要的變換 1、分析有限長(zhǎng)序列的有用工具，在信號(hào)處理的理論上有重要意義。 2、有相應(yīng)的快速算法（快速傅里葉變換FFT) 可在計(jì)算機(jī)上實(shí)現(xiàn)其算法。 3、在運(yùn)算方法上起核心作用，卷積、相關(guān)、譜分析都可以通過(guò)轉(zhuǎn)換成DFT在計(jì)算機(jī)上實(shí)現(xiàn)。,DFT要解決兩個(gè)問題： 一是頻譜的離散化； 二是算法的快速計(jì)算(FFT)。 這兩個(gè)問題都是為了使計(jì)算機(jī)能夠?qū)崟r(shí)處理信號(hào)。,引言,時(shí)域周期化頻域離散化 時(shí)域離散化頻域周期化,引言,序列的傅里葉

2、變換,離散時(shí)間、連續(xù)頻率的傅立葉變換（序列的傅立葉變換）,時(shí)域離散、非周期 頻域連續(xù)、周期,連續(xù)：不適合計(jì)算機(jī)處理,由DTFT到DFT,離散時(shí)間、離散頻率的傅立葉變換（DFT） 由上述分析可知，對(duì)DTFT，要想在頻域上離散化，那么在時(shí)域上必須作周期延拓。 對(duì)長(zhǎng)度為M的有限長(zhǎng)序列x(n)，以N為周期延拓（NM）。 注意：離散傅里葉變換（DFT）只對(duì)有限長(zhǎng)序列作周期延拓或周期序列成立。,3.1 離散傅里葉變換的定義及物理意義,一、 DFT的定義 設(shè)x(n)是一個(gè)長(zhǎng)度為M的有限長(zhǎng)序列，則定義x(n)的N點(diǎn)離散傅里葉變換為,旋轉(zhuǎn)因子的性質(zhì),例1、已知 ，分別求8和16點(diǎn)DFT,解：,頻率采樣點(diǎn)數(shù)不同，

3、DFT的長(zhǎng)度不同，DFT 的結(jié)果也不同。,1、求模（余數(shù)）運(yùn)算 如果整數(shù) 則稱n1是n對(duì)N的模（余數(shù)），記作： 或n模N等于n1,7,5,二、DFT的隱含周期性,2、有限長(zhǎng)序列x(n)和周期序列 的關(guān)系,周期序列 是有限長(zhǎng)序列x(n)的周期延拓。,有限長(zhǎng)序列x(n)是周期序列 的主值序列。,或,二、DFT的隱含周期性,如：,定義從n=0 到（N-1）的第一個(gè)周期為主值序列或區(qū)間。,二、DFT的隱含周期性,周期序列 是有限長(zhǎng)序列X(k)的周期延拓。,有限長(zhǎng)序列X(k)是周期序列 的主值序列。,3、頻域周期序列 與有限長(zhǎng)序列X(k)的關(guān)系,二、DFT的隱含周期性,這里的周期延拓僅看作數(shù)學(xué)處理方法，

4、或者說(shuō)借助時(shí)域周期延拓實(shí)現(xiàn)有限長(zhǎng)序列頻譜的離散化。 在DFT中，有限長(zhǎng)序列都是作為周期序列的一個(gè)周期來(lái)表示的，總是隱含周期性。,二、DFT的隱含周期性,若x(n)是一個(gè)有限長(zhǎng)序列，長(zhǎng)度為N,即,三、DFT與序列傅里葉變換、Z變換的關(guān)系,比較Z變換與DFT，我們看到，當(dāng) 時(shí),DFT與Z變換的關(guān)系,所以X(k)也就是對(duì)X(z)在Z平面單位圓上N點(diǎn)等間隔采樣值。,DFT與序列傅里葉變換的關(guān)系,若x(n)是一個(gè)有限長(zhǎng)序列，長(zhǎng)度為N,X(k)也可以看作序列x(n)的傅里葉變換X(ej)在區(qū)間0, 2上的N點(diǎn)等間隔采樣，其采樣間隔為N=2/N,DFT與序列傅里葉變換的關(guān)系,3.2 DFT的基本性質(zhì),一、線

5、性 1、如果兩序列都是N點(diǎn)的有限長(zhǎng)序列時(shí)，且有 則有：,2. 和 的長(zhǎng)度N1和N2不等時(shí)，怎辦？,選擇 為變換長(zhǎng)度,短者進(jìn)行補(bǔ)零達(dá)到N點(diǎn)。,二、循環(huán)移位性質(zhì),1、序列的循環(huán)移位（圓周移位）定義： 一個(gè)有限長(zhǎng)序列 的圓周移位定義為 ,循環(huán)移位,循環(huán)移位,2、循環(huán)移位的含義 （1）主值區(qū)間: n=0N-1；,（3）如果把x(n)首尾排列(n=0N-1)在一個(gè)N等分的圓周上，序列的移位就相當(dāng)于x(n) 在圓上旋轉(zhuǎn)，故又稱作圓周移位。當(dāng)圍著圓周觀察幾圈時(shí)，看到的就是周期序列,（2）當(dāng)某序列值從此區(qū)間一端移出時(shí)，與它相同的序列值又從此區(qū)間的另一端移進(jìn)來(lái);,循環(huán)移位,時(shí)域圓周移位的性質(zhì),3、時(shí)域圓周移位的

6、性質(zhì),頻域圓周移位的性質(zhì),4、頻域圓周移位的性質(zhì)（調(diào)制特性） 或： 時(shí)域序列的調(diào)制等效于頻域的圓周移位。,1、兩個(gè)有限長(zhǎng)序列的循環(huán)卷積 設(shè)序列h(n)和x(n)的長(zhǎng)度分別為N和M。h(n)與x(n)的L點(diǎn)循環(huán)卷積定義為 其中L為循環(huán)卷積區(qū)間長(zhǎng)度，Lmax(N，M) 表示方法: 或,三、循環(huán)卷積定理,L,2、循環(huán)卷積的計(jì)算方法矩陣相乘 x(n) 序列: x(0), x(1), x(2) , x(L1) x(n)的循環(huán)倒相序列： 令n = 0, m = 0, 1, , L-1，x(n-m)L形成的序列為,循環(huán)卷積的計(jì)算方法,令n = 1, m = 0, 1, , L-1，x(n-m)L形成的序列為

7、 該序列相當(dāng)于x(n)的循環(huán)倒相序列向右循環(huán)移1位。再令n = 2, m = 0, 1, , L1，此時(shí)得到的序列又是上面的序列向右循環(huán)移1位。依次類推，當(dāng)n和m均從0變化到L-1時(shí)，得到一個(gè)關(guān)于x(nm)L的矩陣如下：,循環(huán)卷積的計(jì)算方法,循環(huán)卷積矩陣：,循環(huán)卷積的計(jì)算方法,說(shuō)明： 1、如果x(n)或 h(n)的長(zhǎng)度小于L，則需要在序列末尾補(bǔ)0，使序列長(zhǎng)度為L(zhǎng)。 2、循環(huán)卷積滿足交換律。,循環(huán)卷積的計(jì)算方法,例2、 計(jì)算下面給出的兩個(gè)長(zhǎng)度為4的序列h(n)與x(n)的4點(diǎn)和8點(diǎn)循環(huán)卷積。,解: h(n)與x(n)的4點(diǎn)循環(huán)卷積矩陣形式為,循環(huán)卷積的計(jì)算方法,h(n)與x(n)的8點(diǎn)循環(huán)卷積矩

8、陣形式為,循環(huán)卷積的計(jì)算方法,三、循環(huán)卷積定理,2、時(shí)域循環(huán)卷積定理 設(shè) 和 為長(zhǎng)度分別為N1和N2的有限長(zhǎng)序列，Nmax（N1,N2）且 ， 則,3、頻域循環(huán)卷積定理 設(shè) 和 均為長(zhǎng)度分別為N1和N2的有限長(zhǎng)序列，Nmax（N1,N2）且 ， 則,三、循環(huán)卷積定理,例3、一個(gè)有限長(zhǎng)序列為,（1） 計(jì)算序列x(n)的10點(diǎn)離散傅里葉變換。 （2） 若序列y(n)的DFT為,式中，X(k)是x(n)的10點(diǎn)離散傅里葉變換，求序列y(n)。,（3）若10點(diǎn)序列y(n)的10點(diǎn)離散傅里葉變換是,式中, X(k)是序列x(n)的10點(diǎn)DFT，W(k)是序列w(n)的10點(diǎn)DFT,求序列y(n),綜合例

9、題,（2）X(k)乘以WNkm相當(dāng)于是x(n)循環(huán)移位m點(diǎn)。 本題中m=-2, x(n)向左循環(huán)移位了2點(diǎn)， 則,y(n)=x(n+2)10R10(n)=2(n-3)+(n-8),（3）X(k)乘以W(k)相當(dāng)于x(n)與w(n)的循環(huán)卷積。結(jié)果為3, 3, 1, 1, 1, 3, 3, 2, 2, 2 ,綜合例題,四、復(fù)共軛序列的DFT,證明：,五、DFT的共軛對(duì)稱性,序列的傅里葉變換的共軛對(duì)稱性，其對(duì)稱性是關(guān)于坐標(biāo)原點(diǎn)的對(duì)稱性。 共軛對(duì)稱： 共軛反對(duì)稱： 在DFT中，涉及的序列x(n)及其離散傅里葉變換X(k)均為有限長(zhǎng)序列，且定義區(qū)間為 0 到N1，所以，這里的對(duì)稱性是指關(guān)于N/2 點(diǎn)的

10、對(duì)稱性。,1 有限長(zhǎng)共軛對(duì)稱序列 2 有限長(zhǎng)共軛反對(duì)稱序列,五、DFT的共軛對(duì)稱性,3、任意有限長(zhǎng)序列都可以表示成一個(gè)共軛對(duì)稱分量和一個(gè)共軛反對(duì)稱分量之和，即,五、DFT的共軛對(duì)稱性,同理，對(duì)于頻域函數(shù)X(k)也可以表示成一個(gè)共軛對(duì)稱分量和一個(gè)共軛反對(duì)稱分量之和，即,五、DFT的共軛對(duì)稱性,4、DFT的共軛對(duì)稱性,有限長(zhǎng)序列實(shí)部的DFT等于序列DFT的共軛對(duì)稱分量； 有限長(zhǎng)序列虛部乘j后的DFT等于序列DFT的共軛反對(duì)稱分量。,（1）將序列分成實(shí)部和虛部的形式,五、DFT的共軛對(duì)稱性,（2）將序列表示成共軛對(duì)稱分量和共軛反對(duì)稱分量,有限長(zhǎng)序列共軛對(duì)稱分量的DFT等于序列DFT的實(shí)部； 有限長(zhǎng)序

11、列共軛反對(duì)稱分量的DFT等于序列DFT的虛部乘j 。,五、DFT的共軛對(duì)稱性,實(shí)際中經(jīng)常需要對(duì)實(shí)序列進(jìn)行DFT，利用上述對(duì)稱性質(zhì)，可減少DFT的運(yùn)算量，提高運(yùn)算效率。 （1）若x(n)是實(shí)序列，則X(k)只有共軛對(duì)稱分量，即滿足 X(k)=X*(N-k) k=0, 1, , N-1 （2）若x(n)是純虛序列，則X(k)只有共軛反對(duì)稱分量，即滿足 X(k)=-X*(N-k) k=0, 1, , N-1,5、其他共軛對(duì)稱性,五、DFT的共軛對(duì)稱性,(3) 如果x(n)是實(shí)偶序列，即x(n)=x(Nn)，則X(k)是實(shí)偶對(duì)稱，即 X(k)=X(Nk) (4) 如果x(n)是實(shí)奇序列，即x(n)=x

12、(Nn)，則X(k)純虛奇對(duì)稱，即 X(k)=X(Nk),五、DFT的共軛對(duì)稱性,例4、利用DFT的共軛對(duì)稱性，設(shè)計(jì)一種高效算法，通過(guò)計(jì)算一個(gè)N點(diǎn)DFT，就可以計(jì)算出兩個(gè)實(shí)序列x1(n)和x2(n)的N點(diǎn)DFT。 解：構(gòu)造新序列x(n)=x1(n)+jx2(n)，對(duì)x(n)進(jìn)行DFT，得到：,五、DFT的共軛對(duì)稱性,所以，由X(k)可以求得兩個(gè)實(shí)序列x1(n)和x2(n)的N點(diǎn)DFT：,五、DFT的共軛對(duì)稱性,3.3 頻率域采樣,頻域采樣定理： 如果序列x(n)的長(zhǎng)度為M，則只有當(dāng)頻域采樣點(diǎn)數(shù)NM時(shí)，才有 即可由頻域采樣X(k)恢復(fù)原序列x(n)，否則產(chǎn)生時(shí)域混疊現(xiàn)象。,3.4 DFT的應(yīng)用舉

13、例,一、循環(huán)卷積的DFT計(jì)算方法,用DFT計(jì)算循環(huán)卷積的原理框圖,3.4 DFT的應(yīng)用舉例,二、線性卷積與循環(huán)卷積的關(guān)系,1、線性卷積 它們線性卷積為 下面推理線性卷積的非零值范圍。,的非零區(qū)間為 的非零區(qū)間為 兩不等式相加得 也就是 不為零的區(qū)間. 例如:下面兩個(gè)有限長(zhǎng)序列的線性卷積 非零值區(qū)間為n=05，非零值為1,2,3,3,2,1。,線性卷積與循環(huán)卷積的關(guān)系,2、用圓周卷積計(jì)算線性卷積 圓周卷積是線性卷積的周期延拓序列取主值序列。 先將2個(gè)序列 都補(bǔ)零成L點(diǎn)的序列，然后再對(duì)它們進(jìn)行周期延拓 ，即,線性卷積與循環(huán)卷積的關(guān)系,線性卷積與循環(huán)卷積的關(guān)系,由于 有 個(gè)非零值,所以周期L必須滿足

14、:,又由于循環(huán)卷積是周期卷積的主值序列，所以循環(huán)卷積是線性卷積的周期延拓序列的主值序列，即：,循環(huán)卷積為線性卷積的周期延拓，其周期為L(zhǎng)。,線性卷積與循環(huán)卷積的關(guān)系,已知x1(n)=1,1,1,1，x2(n)=1,1,1,1,1，求x1(n)*x2(n),并分別求x1(n)與x2(n)的6點(diǎn)、8點(diǎn)及10點(diǎn)循環(huán)卷積。,線性卷積與循環(huán)卷積的關(guān)系,課堂練習(xí),1、已知y(n)=x(n)*h(n)， x(n)和h(n) 的長(zhǎng)度分別為M和N。 x(n)和h(n)的L點(diǎn)循環(huán)卷積（LM，LN）用w(n)表示，w(n)=y(n)的條件是_。 LM+N-1,2、對(duì)6點(diǎn)有限長(zhǎng)序列5，1，3，0，5，2進(jìn)行向左2點(diǎn)圓周移位后得到序列_。 3，0， 5，2，5，1,課堂練習(xí),3、離散傅里葉變換中，有限長(zhǎng)序列都是作為周期序列的一個(gè)周期來(lái)表示的，都隱含有周期性的意思。( ),對(duì),4、 已知長(zhǎng)度為N=1