北京郵電大學(xué)《數(shù)字信號(hào)處理》課件-第3章 離散傅里葉變換（DFT）

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

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

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

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

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

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

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

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

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

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

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

[0，2π]上的N點(diǎn)等間隔取樣。實(shí)現(xiàn)了頻域離散化

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

DFT變換對(duì)中，具有周期性：其中k，m，N均為整數(shù)

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

對(duì)n求余數(shù)，即如果

n=mN+n1，0≤n1≤N-1，m為整數(shù)

則((n))N=

((n1+mN))N=n1

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

于是19X(k)與x((n))N的離散傅里葉級(jí)數(shù)系數(shù)的關(guān)系如果x(n)的長(zhǎng)度為N，且，則可寫(xiě)出的離散傅里葉級(jí)數(shù)表達(dá)式

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

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

實(shí)質(zhì)上是x((n))N

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

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

0≤k≤N－1

注意：如果N1和N2不相等，則以N為DFT變換長(zhǎng)度時(shí)，其中相對(duì)較短的序列就通過(guò)補(bǔ)零增加到長(zhǎng)度為N。

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

則其中，0≤k≤N-1時(shí)域循環(huán)移位定理24時(shí)域循環(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)，則證明方法與時(shí)域循環(huán)移位定理類似。26式中，L稱為循環(huán)卷積區(qū)間長(zhǎng)度，L≥max［N，M］。上式顯然與第1章介紹的線性卷積不同，為了區(qū)別線性卷積，用表示循環(huán)卷積，用表示L點(diǎn)循環(huán)卷積，即yc(n)=h(n)

x(n)。觀察上式，x((n－m))L是以L為周期的周期信號(hào)，n和m的變化區(qū)間均是［0,L－1］，1、兩個(gè)有限長(zhǎng)序列的循環(huán)卷積設(shè)序列h(n)和x(n)的長(zhǎng)度分別為N和M。h(n)與x(n)的L點(diǎn)循環(huán)卷積定義為3.2.3循環(huán)卷積定理h0h7h6h5h4h3h2h1x0x7x5x6x4x3x2x127【例3.2.1】計(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)卷積矩陣形式為h(n)與x(n)的8點(diǎn)循環(huán)卷積矩陣形式為h(n)和x(n)及其4點(diǎn)和8點(diǎn)循環(huán)卷積結(jié)果分別如圖(a)、(b)、(c)和(d)所示。請(qǐng)計(jì)算驗(yàn)證本例的8點(diǎn)循環(huán)卷積結(jié)果等于h(n)與x(n)的線性卷積結(jié)果。后面將證明，當(dāng)循環(huán)卷積區(qū)間長(zhǎng)度L大于等于y(n)=h(n)*x(n)的長(zhǎng)度時(shí)，循環(huán)卷積結(jié)果就等于線性卷積。

28

圖3.2.2序列及其循環(huán)卷積波形29例1.3線性卷積首先將h(n)用h(m)表示，并將波形翻轉(zhuǎn)，得到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)的一個(gè)值。對(duì)所有的n重復(fù)這種計(jì)算,最后得到卷積結(jié)果，如圖1.3.2(f)所示,y(n)表達(dá)式為y(n)={1,2,3,4,3,2,1}30畫(huà)出h(m)與x(m)將x(m)周期化得到x((m))N再反轉(zhuǎn)形成x((-m))N取主值序列得到x((-m))NRN(m)對(duì)x

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

則x(n)的N點(diǎn)DFT為N

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

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

因?yàn)樯鲜街幸訬為周期，所以對(duì)其在任一周期上的求和結(jié)果不變，因此0≤k≤N-1時(shí)域循環(huán)移位定理討論34頻域循環(huán)移位定理討論x(n)=x1(n)?x2(n)則或如果N

N

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

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

表示有限長(zhǎng)共軛對(duì)稱序列xop(n)

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

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

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

和的N點(diǎn)DFT。解：構(gòu)造新序列

對(duì)進(jìn)行N點(diǎn)DFT

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

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

頻域采樣指對(duì)序列的傅里葉變換進(jìn)行取樣。由時(shí)域取樣定理，在一定的條件下，可以通過(guò)時(shí)域離散取樣信號(hào)恢復(fù)原來(lái)的連續(xù)信號(hào)。對(duì)有限長(zhǎng)序列而言，由DFT的討論可知，N點(diǎn)DFT就是在頻域?qū)π蛄懈道锶~變換X(jω)在[0,2π]上的N點(diǎn)等間隔取樣，即實(shí)現(xiàn)了頻域取樣。44對(duì)于任意序列x(n)，假設(shè)存在Z變換，且收斂域包括單位圓在單位圓上對(duì)X(z)進(jìn)行N點(diǎn)等間隔取樣，得到

問(wèn)題：能否利用取樣值X(k)恢復(fù)原始的時(shí)域信號(hào)x(n)？

3.3頻率域采樣

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

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

的意義

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

，產(chǎn)生時(shí)域混疊現(xiàn)象。只有當(dāng)頻域取樣點(diǎn)數(shù)N≥M時(shí)這就是頻域采樣定理。483.4離散傅里葉變換的應(yīng)用

用DFT計(jì)算線性卷積用DFT對(duì)連續(xù)信號(hào)進(jìn)行譜分析用DFT對(duì)序列進(jìn)行譜分析493.4.1用DFT計(jì)算線性卷積

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

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

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

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