数字信号处理DSP_Chapter3_离散傅立叶变换.ppt

《数字信号处理DSP_Chapter3_离散傅立叶变换.ppt》由会员分享，可在线阅读，更多相关《数字信号处理DSP_Chapter3_离散傅立叶变换.ppt（103页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数字信号处理数字信号处理DSP_Chapter3_离散离散傅立叶变换傅立叶变换Overview 1.傅立叶变换2.离散时间傅立叶变换(DTFT)3.离散傅立叶变换(DFT)4.离散傅立叶变换的卷积DSP:Digital Signal Processing 2页1 傅立叶变换Basic Observation:周期信号可以分解为不同频率的正弦信号之和.i.e.x(t)=x(t+T)2k/T 为基波频率2/T的谐波频率.DSP:Digital Signal Processing 3傅立叶序列Fourier Series:对称方波i.e.DSP:Digital Signal Processing 4

2、傅立叶变换x(t)可以等价地由傅立叶系数确定:复数形式为:DSP:Digital Signal Processing 5傅立叶分析Question:如何求出系数ck的模|ck|和幅角arg(ck)?与复正弦信号e-jkt两边作内积,DSP:Digital Signal Processing 6傅立叶分析如果 k,s 都为整数,则DSP:Digital Signal Processing 7抽样函数 sinc =1 when x=0,=0 when x=r,r 0,r=1,2,3,DSP:Digital Signal Processing 8傅立叶分析令 ck=ak-jbk,则 c-k=ak+j

3、bk ck cos(kt)+j sin(kt)=akcos(kt)+bksin(kt)+j(aksin(kt)-bkcos(kt)c-k cos(kt)-j sin(kt)=akcos(kt)+bksin(kt)+j(-aksin(kt)+bkcos(kt)两式相加得 DSP:Digital Signal Processing 9傅立叶变换对于周期信号的傅立叶级数,很自然地推广为任意信号的傅立叶变换:傅立叶逆变换离散指标k 连续频率.DSP:Digital Signal Processing 10傅立叶变换两个函数之间的映射:X()DSP:Digital Signal Processing 1

4、1Sine 函数的傅立叶变换假设 由于 因此 X()=2(-0).(x)为Dirac delta 函数 i.e.(x x0)f(x)dt=f(x0)x(t)=A ej0t X()=A 2(-0)DSP:Digital Signal Processing 12傅立叶变换时间频率傅立叶序列连续周期函数x(t)离散的无穷序列 ck傅立叶变换(FT)连续的非周期函数x(t)连续函数X()离散时间FT-DTFT离散无穷序列x(n)连续周期函数X(ej)离散FT-DFT离散序列x(n)离散X(k)DSP:Digital Signal Processing 132 离散时间傅立叶变换-DTFT对于离散序列的

5、傅立叶变换(DTFT)定义为和不可积离散频率变量为参数为ej,不仅仅是.DSP:Digital Signal Processing 14DTFT Example e.g.DSP:Digital Signal Processing 15X(ej)的周期性X(ej)关于变量的周期为2:由于ej的相比较模糊,使得它的周期性比较隐蔽.DSP:Digital Signal Processing 16DTFT的逆变换具有与其它IFT变换的基本形式因此DSP:Digital Signal Processing 17Inverse DTFT(IDTFT)Sinc 函数cos 部分一样.DSP:Digital

6、Signal Processing 18IDTFTIDTFT把一个连续周期函数变换为一个离散无穷序列.IDTFT实际上是一个傅立叶级数展开(除了的符号不同之外).DSP:Digital Signal Processing 19简单序列的DTFTx(n)=(n)i.e.x(n)X(ej)(n)1DSP:Digital Signal Processing 20简单序列的DTFT :X(ej)=2(-0)in-0的DTFT,令 a 0,则得到符号函数sgn(n)的DTFT:X(ej)=2/(1-e-j)DSP:Digital Signal Processing 23简单序列的DTFT因此 x(n)=

7、(n)=1/2+1/2 sgn(n)的DTFT:i.e.DSP:Digital Signal Processing 24单位阶跃函数的Fourier 变换考虑单位阶跃函数的Fourier 变换.构造函数 DSP:Digital Signal Processing 25单位阶跃函数的Fourier 变换DSP:Digital Signal Processing 26DTFT的性质线性:时移:令 y(n)=x(n n0)则DSP:Digital Signal Processing 27DTFT的性质频移特性:令 则它的DTFT为 i.e.在频域延迟DSP:Digital Signal Proces

8、sing 28DTFT examplex(n)=(n)+n(n-1)?=(n)+n-1(n-1)DSP:Digital Signal Processing 29DTFT的对称性如果 x(n)X(ej)那么 x(-n)X(e-j)(由定义可得)x*(n)X*(e-j)From(ej)*=e-j Rex(n)XCS(ej)=1/2(X(ej)+X*(e-j)jImx(n)XCA(ej)=1/2(X(ej)-X*(e-j)由 Rex(n)=1/2(x(n)+x*(n),jImx(n)=1/2(x(n)-x*(n)和DTFT的线性性质可得.DSP:Digital Signal Processing 3

9、0DTFT的对称性 ReX(ej)1/2(x(n)+x*(-n)=xcs(n)jImX(ej)1/2(x(n)-x*(-n)=xca(n)DSP:Digital Signal Processing 31实信号x(n)DTFT的对称性X(ej)的实部ReX(ej)是的偶函数X(ej)的虚部ImX(ej)是的奇函数实信号DTFT的Hermitian 对称性 X*(ej)=X(e-j)DSP:Digital Signal Processing 32实信号x(n)DTFT的对称性X(ej)的幅频响应是的偶函数X(ej)的相频响应是的奇函数DSP:Digital Signal Processing 33

10、实信号x(n)DTFT的对称性ReX(ej)cos(n)和ImX(ej)sin(n)是的偶函数,因此DSP:Digital Signal Processing 34实信号x(n)DTFT的对称性如果x(n)是实偶函数,则即实函数x(n)的DTFT变换X(ej)也是偶函数.DSP:Digital Signal Processing 35实信号x(n)DTFT的对称性如果x(n)是实的奇函数,则即信号x(n)的DTFT变换X(ej)也是偶函数.DSP:Digital Signal Processing 36时域卷积定理令 y(n)=x(n)*h(n)则 Y(ej)=H(ej)X(ej)Proof:

11、DSP:Digital Signal Processing 37频域卷积定理如果 y(n)=x(n)h(n)则 Y(ej)=H(ej)*X(ej)Proof:DSP:Digital Signal Processing 38时域相关定理 y(n)为 x(n)和 h(n)的相关函数,i.e.Proof:如果Ex(ej)为x(n)的自相关函数rx(m)的DTFT则 Sx(ej)=|X(ej)|2 为x(n)的DTFT的幅值平方.DSP:Digital Signal Processing 39Parseval 定理假设 rx(m)为序列x(m)的自相关函数,则DSP:Digital Signal Pr

12、ocessing 40Parseval 定理信号x(n)在频域与时域的能量相等Proof:DSP:Digital Signal Processing 41能量密度谱信号x(n)的能量 Ex=n|x(n)|2 由Parseval 定理得 定义能量密度谱(EDS)为DSP:Digital Signal Processing 42Wiener-Khinchin(维纳辛钦)定理如果x(n)为功率信号,其自相关函数为则它的DTFT为 DSP:Digital Signal Processing 43Wiener-Khinchin 定理功率信号x(n)的自相关函数和其功率谱是一对DTFT,称为确定性信号的维

13、纳辛钦定理.信号x(n)的总功率为DSP:Digital Signal Processing 44卷积与DTFT由于 g(n)*h(n)G(ej)H(ej)可以通过如下方法计算卷积:计算 g,h的DTFT G,H 相乘 GH 把相乘结果求IDTFT,g*hDSP:Digital Signal Processing 45DTFT卷积举例x(n)=n(n),|1 h(n)=(n)-(n-1)y(n)=h(n)*x(n)y(n)=(n)DSP:Digital Signal Processing 46DTFT的应用令x(n)=(n-m),求X(ej)并讨论其幅频和相频响应.解 幅频响应为|X(ej)|

14、=1相频响应为DSP:Digital Signal Processing 47相频响应图 m 0-0.5-0.4-0.3-0.2-0.100.10.20.30.40.5-3-2-10123w/2pi m 0DSP:Digital Signal Processing 49DTFT应用举例-矩形窗函数Example:一个有限长信号xN(n),n=0,1,N-1可以看作是一个无限长信号x(n),n=-+,乘以一个矩形窗函数 作自然截断的结果.研究d(n)对原信号频谱的影响.解:先研究 d(n)的频谱特点.DSP:Digital Signal Processing 50矩形窗函数d(n)函数的频谱:D

15、SP:Digital Signal Processing 51矩形窗函数Dg(ej)=sin(N/2)/sin(/2)为D(ej)的增益,可正可负.当=0时,Dg(ej)=N,当 =2k/N时,Dg(ej)=0.主瓣:Dg(ej)在=0两边第一个过零点间的部分称为Dg(ej)的主瓣,对矩形窗,该主瓣宽度为 B=4/N.旁瓣:主瓣以外的部分称为Dg(ej)的旁瓣.DSP:Digital Signal Processing 52矩形窗函数增益Dg(ej)的图形DSP:Digital Signal Processing 53矩形窗函数的平滑作用xN(n)=x(n)d(n)XN(ej)=X(ej)*D

16、(ej),卷积的结果是D(ej)的主瓣对X(ej)起到了平滑作用,降低了X(ej)中谱峰的分辨能力.对窗函数,希望其主瓣越窄越好,旁瓣越小并且衰减越快越好.DSP:Digital Signal Processing 543 离散傅立叶变换(DFT)DFT 离散有限序列/周期序列变换为离散有限序列/周期序列.一个有限或者周期序列只有N个不同的值:x(n)0 n N.它的频谱完全由N个不同的频率采样点所确定.对 0 2 进行 N 等份 k=2k/N.DSP:Digital Signal Processing 55DFT对DTFT进行等份采样:DFT:WN =e-j2/N ,i.e.对一个圆周进行N

17、等分.DSP:Digital Signal Processing 56IDFTInverse DFT:验证:以上利用了等比数列的求和公式和性质:DSP:Digital Signal Processing 57IDFT的直接解法对于有限序列的DFT,实际上为一线性变换:X=WN x,求IDFT相当于求变换矩阵WN的逆矩阵.在DFT变换 两边乘以 并且对k 求和得:DSP:Digital Signal Processing 58DFT Example有限脉冲序列:周期序列DSP:Digital Signal Processing 59DFT的矩阵形式序列x(n)的离散傅立叶变换DFT可以表示为矩阵

18、的形式:i.e.XN=WN xNDSP:Digital Signal Processing 60IDFT的矩阵形式DFT:X=WN x IDFT:x=W-1N XDSP:Digital Signal Processing 61DFT与DTFTDTFT 无限长序列x(n)变换为连续频率.DFT 有限长序列x(n),0 n N,离散频率k N/2.DFT为DTFT的离散频率采样值.DSP:Digital Signal Processing 62DFT与MATLABMATLAB处理的是序列而不是象X(ej)的连续函数.我们使用DFT以任意精度的网格对X(ej)进行采样:X=freqz(x,1,w);

19、对序列x的DTFT以存储在w内的角频率进行采样.X=fft(x);对N个点x(n)进行快速离散傅立叶变换.DSP:Digital Signal Processing 63DTFT From DFTN个点的DFT完全确定了有限长序列x(n)的连续DTFT.DSP:Digital Signal Processing 64Sinc函数的周期性DSP:Digital Signal Processing 65Sinc 函数的周期性sin(Nx)/sin x由插值:X(k)X(ej)DSP:Digital Signal Processing 66DFT From Over length DTFT如果x(n

20、)不只N个点,仍然可得 IDFT将只能得到N个点 那么x(n)与 有什么联系?DSP:Digital Signal Processing 67DFT From Over length DTFTDSP:Digital Signal Processing 68DFT From DTFT Example如果 x(n)=8,5,4,3,2,2,1,1 (8 points)通过对X(ej)在 频率=0,/2,3/2处采样得到 X(k),k=0,1,2,3.X(k)的IDFT只有4个点只有当 r=-1时具有重叠 DSP:Digital Signal Processing 69DFT From DTFT E

21、xamplex(n)x(n+N):r=-1 为时间偏移或者折叠.DSP:Digital Signal Processing 70DFT的性质线性:如果 x1(n),x2(n)都是N点序列,其DFT分别为X1(k),X2(k)则 DFT x1(n)+x2(n)=X1(k)+X2(k)正交性:令 XN=X(0),X(1),X(N-1)T xN=x(0),x(1),x(N-1)T WN 为DFT的变换矩阵,则 XN=WN xNDSP:Digital Signal Processing 71DFT的移位性质DFT与DTFT的性质雷同,除了以下两个性质之外.DFT的时间移位后还处于一个N点窗口内:对序列

22、xn求模保持在 0 N-1之间DSP:Digital Signal Processing 72 DFT的循环时移性质DSP:Digital Signal Processing 73DFT的循环时移性质对于g(n)的移位认为是整个序列的移位,即前面移出去后,后面的就移进来:象一个转桶DSP:Digital Signal Processing 74DFT的循环时移性质时间反转不只是简单的进行对称反射,而是应该对序列x(n)进行求模:5点周期序列时间反转周期序列DSP:Digital Signal Processing 75DFT的Parseval定理Parseval 定理表示信号在时域变换到频域后

23、能量保持不变.令XN=WN xN并且利用变换矩阵WN的正交性得:DSP:Digital Signal Processing 764 DFT与卷积的关系我们可以利用DTFT来计算卷积:问题:以上需用计算连续频率的函数H(ej),G(ej)而计算机只能计算一些离散点.DSP:Digital Signal Processing 77DTFT的离散化现在对Y(ej)进行 N 点抽样DSP:Digital Signal Processing 78线性卷积的频率离散化DSP:Digital Signal Processing 79时域循环卷积时域循环卷积 设N点序列g(n),h(n)的DFT为G(k),H

24、(k),g(n)和h(n)的循环卷积定义为:表示以N为模对n求余数.DSP:Digital Signal Processing 80循环卷积举例对于4点序列g(n),h(n):DSP:Digital Signal Processing 81循环卷积的矩阵表示对两个N点序列,它的循环卷积可以用矩阵形式表示为:矩阵H称为循环矩阵,由第一列开始,依次向下移动一个元素,移出去的元素又在下一列的最上边出现,它的每一列元素都由h(0),h(1),h(N-1)这N个元素循环移动生成.DSP:Digital Signal Processing 82时域循环卷积定理y(n),g(n),h(n)都是N点序列,它的

25、DFT分别为Y(k),G(k),H(k)则 y(n)=g(n)h(n)Y(k)=G(k)H(k).Proof:证明思路为:通过验证y(n)为G(k)H(k)的IDFT得到证明,而IDFT具有唯一性,因此可知定理结论成立.在以下的证明中利用了等比数列求和性质:NDSP:Digital Signal Processing 83时域循环卷积定理DSP:Digital Signal Processing 84频域循环卷积定理同理可证频域循环卷积定理:y(n)=g(n)h(n)Y(k)=G(k)H(k).验证G(k)H(k)为g(n)h(n)的DFT变换.NNDSP:Digital Signal Pro

26、cessing 85频域循环卷积定理DSP:Digital Signal Processing 86对偶性质DFT与IDFT非常相象,都把N点序列映射为N点序列.对偶性:如果 g(n)G(k)那么 G(n)NgN 如果把DFT当成是一个时间序列,那么它的结果也具有对称性.Proof:DSP:Digital Signal Processing 87DFT性质总结时域循环卷积:频域循环卷积:对偶性:G(n)NgN Parseval 定理DSP:Digital Signal Processing 88线性卷积与循环卷积DFT:g(n)h(n)=IDFTG(k)H(k)g(n),h(n)的DFT变换G

27、(k),H(k)有快速傅立叶变换,它的计算复杂度为1/2 N log N,而直接计算两个函数 g(n),h(n)的卷积复杂度为N2.但是我们需要的是线性卷积,而不是循环卷积.现希望 y(n)=g(n)*h(n)=IDFTG(k)H(k)=IDFTY(k)NDSP:Digital Signal Processing 89用DFT计算线性卷积但是对于 L点序列g(n)和M点序列h(n),它们的线性卷积y(n)是 M+L-1点序列.y(0)=g(0)h(0)y(1)=g(0)h(1)+g(1)h(0)y(2)=g(0)(2)+g(1)h(1)+g(2)h(0)y(L+M-2)=g(L-1)h(M-1

28、)因此如果我们希望利用DFT计算线性卷积只能通过扩展点列g(n)和h(n)使得DFT点列:NL+M-1.DSP:Digital Signal Processing 90用DFT计算线性卷积运算步骤:填充L点列g(n)至少 M-1个零点.N点DFT:G(k),k=0 N-1填充M点列h(n)至少 L-1个零点.N点DFT:H(k),k=0N-1Y(k)=G(k)H(k)为 的精确采样IDFTY(k)=-r yL(n+r N)=yL(n)注意此时的循环卷积与线性卷积相等.DSP:Digital Signal Processing 91用DFT计算线性卷积Question:线性卷积与循环卷积什么情况

29、下相等,即循环卷积的长度N取多大?假设有L点序列g(n)和M点序列h(n),并且把它们扩充成N点序列:DSP:Digital Signal Processing 92用DFT计算线性卷积把h(n)延拓为以N为周期的周期序列:计算N点序列h(n)和g(n)的循环卷积:DSP:Digital Signal Processing 93用DFT计算线性卷积因此g(n)和h(n)的循环卷积y(n)为线性卷积yN(n)以N为周期的延拓序列的主值序列.线性卷积yN(n)有M+L-1个非零值,因此当延拓周期 N M+L-1 时各延拓周期才不会重叠.y(n)的前M+L-1个值正好是y(n)的全部非零值,也正是

30、y(n),y(n)剩下的N-(L+M-1)个点则为补充的零值.DSP:Digital Signal Processing 94用DFT计算线性卷积注意线性卷积由于当yN(n)的延拓周期 N M+L-1时,各个周期不会重叠,因此当N=M+L-1时线性卷积等于循环卷积.DSP:Digital Signal Processing 95DFT计算线性卷积举例g(n)=2,1,1,h(n)=2,2,1用循环卷积计算线性卷积.解:M=3,L=3,所以 N=M+L-1=5.把g(n),h(n)分别扩展为 g(n)=2,1,1,0,0,h(n)=2,2,1,0,0 y(0)=22+10+10+03+02=4y

31、(1)=22+12+10+00+00=6y(2)=6,y(3)=3,y(4)=1y(n)=4,6,6,3,1.DSP:Digital Signal Processing 96叠接相加卷积超长序列g(n)分割成小段gi(n),每一小段gi(n)与h(n)做卷积,叠接相加 控制DFT的规模,实现实时处理.使得 g(n)=i gi(n)h(n)*g(n)=i h(n)*gi(n)称为叠接相加卷积 Overlap-Add(OLA)convolutionDSP:Digital Signal Processing 97Overlap-Add Convolution由于h(n)的长度为M,gi(n)的长度为

32、N,则 yi(n)=h(n)*gi(n)的长度为 M+N-1.我们考虑相邻两段g0(n),g1(n)与h(n)的卷积,则它们共有2(M+N-1)个有效值.y(n)为g(n)=g0(n)+g1(n)与h(n)的卷积只有 M+2N-1个有效值.因此yi(n)与 yi+1(n)有 M-1=2(M+N-1)-(M+2N-1)长度重叠.当 2N N+M-1即 N M-1时,只有相邻两段yi(n),yi+1(n)有重叠.y3 的第一个元素为2N.DSP:Digital Signal Processing 98叠接相加卷积计算公式由以上讨论,我们可以得到如下的叠接相加卷积的计算公式:y(k N)=yk(N)

33、+yk+1(0)y(k N+1)=yk(N+1)+yk+1(1)y(k N+M-2)=yk(N+M-2)+yk+1(M-2)k为g(n)的分段序号,N为g(n)分段后的长度,M为h(n)的长度.DSP:Digital Signal Processing 99叠接相加卷积计算的程序实现具体的程序实现为:开一个长度为 KN+M-1的数组y(n)并且赋初值为0:y(n)0,n=0,1,.KN+M-2.y(n)=y1(n),n=0,1,N+M-1 y(k N+j)=y(k N+j)+yk+1(j),k=0,1,K-1,j=0,1,M-2.y(k N+j)=yk+1(j),j=M-1,N+M-2.程序实

34、现主要利用了递推关系.DSP:Digital Signal Processing 100Overlap-Add ConvolutionDSP:Digital Signal Processing 101叠接相加卷积举例设g(n)分成长 N=5的小段,h(n)的长度M=3,则 N M-1,所以只有相邻两小段的卷积yi(n),yi+1(n)有重叠,重叠长度为M-1=2.每一小段的卷积长度为 N+M-1=7.把它们之间的关系整理成如下表格.DSP:Digital Signal Processing 102叠接相加卷积举例y(n)=g(n)*h(n)y(n)=g1(n)*h(n)y(n)=g1(n)*h

35、(n)y(0)=h0 g0y1(0)=h0 g0y(1)=h0 g1+h1 g0y1(1)=h0 g1+h1 g0y(2)=h0 g2+h1 g1+h2 g0y1(2)=h0 g2+h1 g1+h2 g0y(3)=h0 g3+h1 g2+h2 g1y1(3)=h0 g3+h1 g2+h2 g1y(4)=h0 g4+h1 g3+h2 g2y1(4)=h0 g4+h1 g3+h2 g2y(5)=h0 g5+h1 g4+h2 g3y1(5)=h1 g4+h2 g3y2(0)=h0 g5y(6)=h0 g6+h1 g5+h2 g4y1(6)=h2 g4y2(1)=h0 g6+h1 g5y(7)=h0 g7+h1 g6+h2 g5y2(2)=h0 g7+h1 g6+h2 g5y(8)=h0 g8+h1 g7+h2 g6y2(3)=h0 g8+h1 g7+h2 g6y(9)=h0 g9+h1 g8+h2 g7y2(4)=h0 g9+h1 g8+h2 g7y(10)=h0 g10+h1 g9+h2 g8y2(5)=h1 g9+h2 g8DSP:Digital Signal Processing 103