1、1本章主要内容本章主要内容 离散傅立叶变换离散傅立叶变换定义定义 离散傅立叶变换离散傅立叶变换性质性质（与（与DTFTDTFT的关系，圆周移位和圆周卷积，的关系，圆周移位和圆周卷积，DFTDFT的对称性，的对称性，DFTDFT定理）定理）DFTDFT的的应用应用（实序列的（实序列的DFTDFT计算，用计算，用DFTDFT计算计算线性卷积）线性卷积）离散余弦变换离散余弦变换25.1 正交变换正交变换对信号的分析思路是对信号的分析思路是：找一个找一个正交的函数集正交的函数集，从而将从而将任意信号任意信号分解为该函数集上各个元素的分解为该函数集上各个元素的线性组合线性组合。设设 是是基本序列基本序列
2、，长度为，长度为N。则其满足：。则其满足：,k n101,1,0,Nnlkk nl nlkN称称 为为正交序列正交序列。,k n35.1 正交变换正交变换正交变换对正交变换对的一般形式：的一般形式：1010 ,011 ,01NnNkX kx nk nkNx nX kk nnNN综合式综合式分析式分析式将要讨论的将要讨论的离散傅立叶变换离散傅立叶变换是是正交变换正交变换的一的一种。种。45.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)DTFT是是离散时间信号离散时间信号的的傅里叶变换，傅里叶变换，时域离散时域离散，频域连续频域连续，周期为周期为2
3、。由于由于计算机计算机只能处理只能处理数字信号数字信号，而不能，而不能处理连续信号，所以必须把处理连续信号，所以必须把信号连续的信号连续的频谱频谱离散化离散化。5 时域时域 频域频域 连续，非周期连续，非周期 FT 连续，非周期连续，非周期 连续，周期连续，周期 FST 离散，非周期离散，非周期 离散，非周期离散，非周期 DTFT 周期，连续周期，连续 离散周期离散周期 DFS 离散周期离散周期5.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)补充补充DFS内容内容6已知周期冲激函数的傅立叶变换：已知周期冲激函数的傅立叶变换：T 2T-T-2TT
4、(t)t0020-0-2000()00=2/T()()TnttnT02()()TkFTtkT 00()()Tt 7周期化，离散化信号周期化，离散化信号x(t)X(j)P(j)00=2/TsxnTX(j)q(t)TFTDFSDTFTQ(j)00=2/TQ(j)00=2/TP(t)Ts85.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)21100:01NNjknknNNnnDFTX kx n ex n WkN101:,01NknNkIDFTx nX k WnNNDFTDFT的定义的定义时域中N点的序列xn的DFT9DFT定义中引入一个常用的符号定义中
5、引入一个常用的符号NjNeW25.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)证明IDFT表达式：1110001NNNlnknlnNNNnnkx nWX k WWN10,110NnWkXNnxNkknN证明：在两边同乘以证明：在两边同乘以 WNln，从，从 n=0到到n=N-1作作105.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)1110001NNNlnknlnNNNnnkx nWX k WWN 11001NNk l nNnkX k WN 11001NNk l nNknX kWX lN2211
6、2/00101jk lNNjl k nk l nNNjk lNnnNk lrNeWeotherwisee 其中有：115.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)例例 5.1 有限长有限长单点单点非零样本的非零样本的DFT计算计算 10(1)011nx nnN10010NNnknNWxWnxkX10Nk其其N点的点的 DFT：125.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)例例 5.1 有限长有限长单点单点非零样本的非零样本的DFT计算计算 1(2)001,11nmy nnmmnN 10
7、 NknkmkmNNNnY ky n Wy m WW10Nk其其N点点 DFT 为：为：135.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)例例 5.2 有限长有限长正弦序列正弦序列的的DFT计算计算 cos 2/01 01x nrn NnNrN 解：解：2/2/1122jnr Njnr NnrnrNNx neeWW 110012NNkr nrk nNNnnXkWW1()00Nk r nNnNkrlNl is evenWotherwise14 110012NNrk nrk nNNnnXkWW/2/20NkrNkNrotherwise5.2 离散
8、傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)例例 5.2 有限长有限长正弦序列正弦序列的的DFT计算计算155.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)DFT的矩阵关系的矩阵关系 01-101-1TTxxxx NXXXX N令，可以重写为：可以重写为：-10 ,0-1NknNnX kx n WkNDFT的定义的定义NXD x165.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)DFT的矩阵关系的矩阵关系1212124211(1)11111111NNNN
9、NNNNNNNNNNNNNXD xWWWDWWWWWW 其中17类似的类似的,IDFT 关系也可以表示为：关系也可以表示为：5.2 离散傅里叶变换离散傅里叶变换Discrete Fourier Transform(DFT)DFT的矩阵关系的矩阵关系11121*21241211(1)111111111 x D X：其 中NNNNNNNNNNNNNNNNNNIDFTWWWDDWWWNNWWW185.2.3 用用Matlab计算计算DFTDFT Computation Using MATLAB在在matlab中有四个用来计算中有四个用来计算DFT和和IDFT的内的内置函数：置函数：fft(x),ff
10、t(x,M),ifft(X),ifft(X,M)在在matlab信号处理工具箱中的函数信号处理工具箱中的函数dftmtx(N)用来计算用来计算N N阶阶DFT矩阵矩阵DN例例 5.3 用用matlab计算如下计算如下N点序列的点序列的M点点DFT101 0nNu notherwise19%Program 5_1%Illustration of DFT Computation%Read in the length N of sequence and the%desired length M of the DFTN=input(Type in the length of the sequence=
11、);M=input(Type in the length of the DFT=);%Generate the length-N time-domain sequenceu=ones(1,N);%Compute its M-point DFTU=fft(u,M);%Plot the time-domain sequence and its DFTt=0:1:N-1;stem(t,u)20title(Original time-domain sequence)xlabel(Time index n);ylabel(Amplitude)pausesubplot(2,1,1)k=0:1:M-1;st
12、em(k,abs(U)title(Magnitude of the DFT samples)xlabel(Frequency index k);ylabel(Magnitude)subplot(2,1,2)stem(k,angle(U)title(Phase of the DFT samples)xlabel(Frequency index k);ylabel(Phase)210123456700.10.20.30.40.50.60.70.80.91O rig in a l tim e-d o m a in s e q u e n c eT im e in d e x nAmplitude05
13、101502468Magnitude of the DFT samplesFrequency index kMagnitude051015-2-1012Phase of the DFT samplesFrequency index kPhase22例例 5.4 用用matlab计算计算IDFT01 0k KkKV kotherwise%Program 5_2%Illustration of IDFT Computation%Read in the length K of the DFT and the desired%length N of the IDFTK=input(Type in th
14、e length of the DFT=);N=input(Type in the length of the IDFT=);%Generate the length-K DFT sequencek=0:K-1;V=k/K;%Compute its N-point IDFTv=ifft(V,N);23%Plot the DFT and its IDFTstem(k,V)xlabel(Frequency index k);ylabel(Amplitude)title(Original DFT samples)pausesubplot(2,1,1)n=0:N-1;stem(n,real(v)tit
15、le(Real part of the time-domain samples)xlabel(Time index n);ylabel(Amplitude)subplot(2,1,2)stem(n,imag(v)title(Imaginary part of the time-domain samples)xlabel(Time index n);ylabel(Amplitude)240123456700.10.20.30.40.50.60.70.80.9F re q u e n c y in d e x kAmplitudeO rig in a l D F T s a m p le s024
16、681012-0.200.20.40.6Real part of the tim e-dom ain sam plesTim e index nAmplitude024681012-0.2-0.100.10.2Im aginary part of the tim e-dom ain sam plesTim e index nAmplitude255.3 FT与与DFT之间的关系之间的关系一一.DFT与与DTFT之间的关系之间的关系10()Njj nj nnnX ex n ex n e长度为长度为N的序列的序列 的的DTFT为：为：,01x nnN在在=0，2 对对X(ej )进行进行的的N点点
17、等间隔采样：等间隔采样：2120(),01 NjknjNknNX ex n ekNX k26说明：说明：x(n)的的N点点DFT是是x(n)的的Z变换在单位圆变换在单位圆 上的上的N点等间隔采样点等间隔采样。X(k)为为x(n)的傅立叶变换的傅立叶变换X(ej )在区间在区间 0，2 上的上的N点等间隔采样点等间隔采样。22()(),01jkNjkz eNX kX eX zkN 275.3 FT与与DFT之间的关系之间的关系二二.使用使用DFT进行傅立叶变换的数值计算进行傅立叶变换的数值计算 01x nnN，已知已知jX e,其傅立叶变换为其傅立叶变换为希望以频率间隔希望以频率间隔 来估计来估
18、计 ，其中，其中2/01kk MkM，jX eMN解：解：01 011ex nnNx nNnM 112/00kkNNjjnjkn MnnX ex n ex n e定义新序列定义新序列28则：12/012/0kNjjkn MnMjkn MeenXex n exn eXk上式是上式是M点点序列序列xen的的M点点DFT序列序列Xek5.3 FT与与DFT之间的关系之间的关系二二.使用使用DFT进行傅立叶变换的数值计算进行傅立叶变换的数值计算295.3 FT与与DFT之间的关系之间的关系二二.使用使用DFT进行傅立叶变换的数值计算进行傅立叶变换的数值计算150),16/6cos(nnnx例例 5.5
19、 使用使用matlab计算计算DTFT 程序程序5_3.m%Program 5_3%Numerical Computation of Fourier transform Using DFTk=0:15;w=0:511;x=cos(2*pi*k*3/16);%Generate the length-16 sinusoidal sequence30%Compute its 16-point DFTX=fft(x);%Compute its 512-point DFTXE=fft(x,512);%Plot the frequency response and the 16-%point DFT sa
20、mplesplot(k/16,abs(X),o,w/512,abs(XE)xlabel(omega/pi);ylabel(Magnitude)例例 5.5 使用使用matlab计算计算DTFT 程序程序5_3.m31 例例-5_3.m 150),16/6cos(nnnx如下所示：如下所示：5.3 FT与与DFT之间的关系之间的关系二二.使用使用DFT进行傅立叶变换的数值计算进行傅立叶变换的数值计算00.10.20.30.40.50.60.70.80.910123456789/Magnitude325.3 FT与与DFT之间的关系之间的关系三三.通过插值由通过插值由DFT获得傅立叶变换获得傅立叶
21、变换 01x nnN，给定给定，其其N点点DFT序列序列 X kjX e通过通过 唯一地确定唯一地确定 X kDFTDTFT 插值 111000112/0011NNNjj nknj nnnnkNNj njkn NknX ex n eX k WeNX keeN 33 212/2/02/1/2112sin22sin2jNkNjk N njk Nnjk NNeeeNkeNkN其中 12/1/202sin122sin2Njk NNjkNkX eX keNkNN所以：所以：345.3 FT与与DFT之间的关系之间的关系四四.傅立叶变换的抽样傅立叶变换的抽样频域采样定理频域采样定理v为了便于计算机计算为了
22、便于计算机计算,一般采取在一般采取在频率域采样频率域采样 的方法的方法,来计算来计算有限长序列有限长序列的的傅立叶变换傅立叶变换。v那么那么,是否任何一个序列的频谱（或任何一个是否任何一个序列的频谱（或任何一个 频率频率 特性）都能用频率抽样的方法去逼近呢特性）都能用频率抽样的方法去逼近呢?其其限制条件限制条件是什么是什么?02)(jeX35()jjnnX ex n e22(),01jknjNknNY kX ex n ekN频域采样定理频域采样定理推导过程推导过程:设任意序列设任意序列 xn 存在傅立叶变换存在傅立叶变换问题在于这样采样以后是否能恢复出原序列问题在于这样采样以后是否能恢复出原序
23、列xn ,01y nIDFT Y knN对对 在在 上的上的N个个均分点均分点采样采样,则得到则得到 jX e0,2 36 ,01y nIDFT Y knN my nx nmN经推导得经推导得说明说明：在在 的的N点等间隔采样点等间隔采样 Xk 的的 IDFT 为：原序列为：原序列xn以以N为周期的为周期的周期延拓周期延拓序列的序列的主值序列主值序列.频域抽样频域抽样造成造成时域信号时域信号的的周期延拓周期延拓,其延拓周期为采其延拓周期为采样点数样点数N.若若xn不是不是有限长的有限长的,则延拓后必然则延拓后必然造成混迭现象造成混迭现象,若若xn 是是有限长的有限长的,长度为长度为M,当抽样点
24、数不够密时当抽样点数不够密时(N=Mx nn06x n n06x n n0 y nn040当当N0(则它是一个右圆周移位则它是一个右圆周移位),上式可上式可以写为：以写为：0000010Nx n nnnNxn nx Nnnnn435.4.1 序列的圆周移位序列的圆周移位Circular Shift of a Sequence 一个有限长序列的圆周移位图示一个有限长序列的圆周移位图示nx16nx56nx46nx26nx向右向右圆周移位圆周移位 n0 个抽样周期个抽样周期等效于等效于向左向左圆周圆周移位移位N-n0 个抽样周期个抽样周期44xn-1xn没圆周移位没圆周移位圆周移位圆周移位5.4.1
25、 序列的圆周移位序列的圆周移位Circular Shift of a Sequence45循环移位的过程示意图循环移位的过程示意图xnn 2 NNy nx nRnnn2x n lx nx nlNn x nn465.4.2 圆周卷积圆周卷积Circular Convolution圆周卷积与线性卷积：圆周卷积与线性卷积：考虑两个长度考虑两个长度N的序列的序列 gn 和和hn它们的它们的线线性卷积性卷积是是长度为长度为(2N-1)的序列的序列 yLn：22010NnmnhmgnyNmL,gn 和和hn 的的圆周卷积圆周卷积是是长度为长度为N 的序列的序列ycn10,10NnmnhmgnyNmNC47
26、5.4.2 圆周卷积圆周卷积Circular Convolution10 ,01NCNmyng m h nmnN 上面的运算通常称之为上面的运算通常称之为N 点圆周卷积，点圆周卷积，表示为：表示为：N Cyng nh n481120121012 ()()NNNmNNNmx nx m xnmRnx m xnmRnx nx nN计算圆周卷积计算圆周卷积5.4.2 圆周卷积圆周卷积Circular Convolution49圆周卷积的计算圆周卷积的计算m1 x m2 x mm2Nx mm2Nxmm50m21Nxmm1 x m23Nxmm2Nxmmm22Nxmm21Nxmm22Nxm51,1021ng
27、1122nhn321012ngn321012nh5.4.2 圆周卷积圆周卷积Circular Convolution Cy ngnhn430 03Nmg m h nmn例例 5.7-确定两个长度为确定两个长度为4的序列的圆周卷积的序列的圆周卷积:52yn=6n+7n-1+6n-2+5n-3gn=n+2 n-1+n-3hn=2n+2n-1+n-2+n-3hmgmgmgmgmgmy06y17y26y354hm4 1hm4 3hm4 2hm533040mCmhmgy 1 3223 1 00hghghghg621101221)()()()(,304mCmnhmgnhngny430 n由上我们得到：由上
28、我们得到：5.4.2 圆周卷积圆周卷积Circular Convolution 4032121 12hmhhhh 结果为长度为结果为长度为4的序列的序列 yCn：54 同样同样3041 1 mCmhmgy23320110hghghghg711102221)()()()(30422mCmhmgy33021120hghghghg611202211)()()()(5.4.2 圆周卷积圆周卷积Circular Convolution5530433mCmhmgy03122130hghghghg521201211)()()()(nyC5.4.2 圆周卷积圆周卷积Circular Convolution56
29、5.4.2 圆周卷积圆周卷积Circular Convolution NCyng nh n 10NNmg m hnm 001210110121221032112301CCCCyhh Nh Nhgyhhh NhgyhhhhgyNh Nh Nh Nhg N可用矩阵形式表示：可用矩阵形式表示：矩阵中矩阵中每一行的元素，每一行的元素，都是将都是将上一行元素上一行元素向右向右圆周移位圆周移位一位得到的。一位得到的。575.5 有限长序列的分类有限长序列的分类5.5.1 基于共轭对称的分类基于共轭对称的分类*,01,01cscsNcacaNxnxnnNxnxnnN 当当N为偶数时，将上式中的为偶数时，将上
30、式中的n换成换成N/2-n,得得*(/2)(/2),0/2 1(/2)(/2),0/2 1cscscacaxNnxNnnNxNnxNnnN有限长有限长共轭对称序列共轭对称序列和和共轭反对称序列共轭反对称序列58nn csxn caxn0 1 2 3 4 5 6 759 ,01cscax nx nx nnN 任一有限长序列任一有限长序列xn可以表示如下可以表示如下其中其中，*1()21()2csNcaNxnx nxnxnx nxn605.5 有限长序列的分类有限长序列的分类5.5.2 几何对称分类几何对称分类对于长度为N的实序列，对称分为两类：对称序列：对称序列：1x nx Nn N=7（奇数）
31、（奇数）063nN=8（偶数）（偶数）063n1型：奇长度对称序列型：奇长度对称序列2型：偶长度对称序列型：偶长度对称序列615.5 有限长序列的分类有限长序列的分类5.5.2 几何对称分类几何对称分类反对称序列：反对称序列：1x nx Nn N=8（偶数）（偶数）N=7（奇数）（奇数）063n073n3型：奇长度反对称序列型：奇长度反对称序列4型：偶长度反对称序列型：偶长度反对称序列625.6 DFT对称关系对称关系v设设 是是xnxn 的复共轭序列，长度为的复共轭序列，长度为N N，且且*x n()X kDFT x n则则*(),01NDFT x nX NkXkkN且且0X NX同理同理*
32、()()NDFT xnXk一一.复序列的复序列的DFTDFT635.6 DFT对称关系对称关系二二.DFT.DFT的对称性的对称性 reimx nxnjxn其中其中*1 Re()21()Im()2reimxnx nx nx njxnjx nx nx n则则 reimcscaX kDFT x nDFT xnDFTjxnXkXk（1）如果）如果64 ,01cscax nxnxnnN其中其中*1 21 2cscaxnx nx Nnxnx nx Nn则则 Re Im()()cscaRIX kDFT x nDFT xnDFT xnX kjX kXkjXk（2）如果）如果65总结总结如果如果xn的的DFT
33、为为Xk，则则Xn的的实部实部和和虚部（包括虚部（包括j）的的DFT分别为分别为Xk的的共轭对称分量共轭对称分量和和共轭反对称分量共轭反对称分量；Xn的的共轭对称分量共轭对称分量和的和的共轭反对称分量共轭反对称分量的的DFT分别为分别为Xk的的实部实部和和虚部（包括虚部（包括j）DFTDFT的共轭对称性的共轭对称性66复序列的离散傅立叶变换的对称关系复序列的离散傅立叶变换的对称关系 Re x n x n*x n*NXk*Nxn*Xk*1 2csNXkX kXkIm jx n*1 2caNXkX kXk csxnRe X k caxnIm jX k X k67实序列的离散傅立叶变换的对称关系实序
34、列的离散傅立叶变换的对称关系 x n Re Im X kX kjX k evxnRe X k odxnIm jX k*NX kXkRe ReNX kXkIm ImNX kXk|NX kXkarg argNX kXk 对称关系对称关系 685.7 离散傅立叶变换定理离散傅立叶变换定理 g nh n0-Ng n n0 k nNWg n g n h n G k H k10 NNmg m h n m g n h n1122001|NNnkx nX kN kG kH0 knNWG k0NG kk()()G k H k101 NNmG m HkmN 线性线性 圆周时移圆周时移圆周频移圆周频移圆周卷积圆周卷
35、积相乘相乘 帕斯瓦尔公式帕斯瓦尔公式对偶性对偶性 G nNN gk69有限长序列的有限长序列的圆周移位圆周移位在频域中只引入在频域中只引入一个一个和频率成正比和频率成正比的的线性相移线性相移 002jknknNNWe对频谱的幅度没有影响。对频谱的幅度没有影响。2.2.圆周时移定理圆周时移定理0-Ng n n0 knNWG kDFT703.3.圆周频移定理圆周频移定理0 k nNWg n0NG kkDFT时域序列的调制等效于频域的圆周移位。时域序列的调制等效于频域的圆周移位。即即 乘以乘以 ，则离散傅立叶变换向右则离散傅立叶变换向右 圆周移位圆周移位 位，位，相当于将相当于将 进行复调制，其结果
36、使整个频谱产生搬移进行复调制，其结果使整个频谱产生搬移。0k nNW g n g n0k0 k nNWg n714.4.圆周卷积定理圆周卷积定理10 NNmg m h n m G k H kDFTN点点DFTN点点DFT g n h nIDFT G k H k Y k y n可以利用可以利用DFT求圆周卷积，思路如图：求圆周卷积，思路如图：72n321012ngn321012nh4210/kjeggkG464432/kjkjegeg3021232keekjkj,/gn 的的DFT Gk长度为长度为4，表达如下：，表达如下：例例 5.11 用用DFT计算圆周卷积计算圆周卷积73 因此因此,212
37、12G,jjjG1211jjjG1213,41210G4210/kjehhkH464432/kjkjeheh同样同样例例 5.11 用用DFT计算圆周卷积计算圆周卷积322 1 2,03kjkjG keek 322 22,03kkjjj kH keeek74 因此因此,611220H,011222H,jjjH11221jjjH11223两个两个 4点长的序列的点长的序列的DFT还可以通过矩阵还可以通过矩阵运算得到。运算得到。322 22,03kkjjj kH keeek例例 5.11 用用DFT计算圆周卷积计算圆周卷积75jjjjjj12141021111111111111g3g2g1g0DG
38、3G2G1G04jjjjjj10161122111111111111h3h2h1h0DH3H2H1H04D4是长度为是长度为4 的的DFT 矩阵矩阵利用利用矩阵运算矩阵运算求求两个两个 4点长的序列的点长的序列的DFT例例 5.11 用用DFT计算圆周卷积计算圆周卷积76 若若YCk 是是 长度为长度为4的序列的序列yCn的的 DFT，则：则：因此：因此：00024111222203332CCCCYGHYGHjYGHYGHj 03cY kG k H kk例例 5.11 用用DFT计算圆周卷积计算圆周卷积77 YCk的的 IDFT 如下：如下：3Y2Y1Y0YD413y2y1y0yCCCC*4C
39、CCC56762022411111111111141jjjjjj例例 5.11 用用DFT计算圆周卷积计算圆周卷积4111111D111111jjjj其中Matlab中圆周卷积函数：circonv785.9 实序列的实序列的DFT计算计算在绝大多数应用中，我们感兴趣的是在绝大多数应用中，我们感兴趣的是实序列实序列。利用。利用DFT的性质的性质可以可以提高提高实序列实序列DFT的的计算效率计算效率。一一.用用N点点DFT计算两个实序列的计算两个实序列的DFT 和和 为长度为为长度为N的的实序列，以下是实序列，以下是高效算法：高效算法：g n h n设：x ng njh n，则，则 X kDFT
40、x n根据根据DFT的对称性可知：的对称性可知：1 2csNG kXkX kXk795.9 实序列的实序列的DFT计算计算1 2caNjH kXkX kXk1 2NH kX kXkj1 2csNG kXkX kXk所以：80 21112122220001120011200222101221021NNNnknknkNNNnnnNNnknkkNNNnnNNnkknkNNNnnkNNNg nvnh nvnnNV kv n Wvn WvnWg n Wh n W Wg n WWh n WGkWHkkN，二二.用用N点点DFT计算计算2N点实序列的点实序列的DFT5.9 实序列的实序列的DFT计算计算设8
41、15.10 用用DFT实现线性卷积实现线性卷积Linear Convolution Using the DFT在绝大多数信号处理领域中，线性卷积都是在绝大多数信号处理领域中，线性卷积都是很重要的一种运算。很重要的一种运算。因而运用因而运用DFT实现线性卷积的方法就变得很实现线性卷积的方法就变得很有研究意义。有研究意义。82例 5.12n321012ngn321012nh,03 0,46eg nng nn令,03 0,46eh nnh nn求：670 eemy ng m hnm83有限长序列存在两种形式的卷积有限长序列存在两种形式的卷积线性卷积：实际系统的输出线性卷积：实际系统的输出yn=xn*
42、hn循环卷积：与循环卷积：与DFT相对应，有快速算法相对应，有快速算法问题：问题：如何用循环卷积代替线性卷积如何用循环卷积代替线性卷积？设设h(n)和和x(n)都是有限长序列，长度分别为都是有限长序列，长度分别为N和和M ly nh nx n长度为长度为N+M-1的有限长序列的有限长序列将将hn和和x n均视为长度均视为长度为为L的有限长序列的有限长序列 cy nh nLx nL=maxN,M84循环卷积循环卷积 和线性卷积和线性卷积 的关系的关系10 Nlmy nh nx nh m x nm cy nhnL xn设设h(n)和和x(n)都是有限长序列，长度分别为都是有限长序列，长度分别为N和
43、和M10 LLmh m x nm其中，其中，L=maxN,M,Lqx nx nqL所以，所以，10 NcLmqy nh mx nmqLR n8510 NcLmqy nh mx nmqLR n10 NLqmh m x nqLmR n对照式对照式10 Nlmy nh nx nh m x nm可知，可知，10 Nlmh m x nqLmy nqL即即 clLqy ny nqLR n86经推导可得经推导可得 clLqy ny nqLR n可见可见 是是 以以 L 为周期，进行延为周期，进行延拓后，在拓后，在 0 L-1 范围内所取的主值序列。范围内所取的主值序列。cy n ly n若若则则1MNL c
44、ly ny n循环卷积和循环卷积和线性线性卷积的关系卷积的关系875.10用DFT实现线性卷积Linear Convolution Using the DFT 令令gn 和和 hn 为长度为为长度为 N 和和 M的有限长序的有限长序列列 其中其中 L=N+M-1 定义两个长度为定义两个长度为L 的序列：的序列：1-LnN0,1-Nn0gn,gen1-LnM0,1-Mn0hn,hen885.10用DFT实现线性卷积Linear Convolution Using the DFT 因此，因此，yLn=gn*hn=yCn=gen*hen 图示如下：图示如下：895.10.2有限长序列和无限长序列的线
45、性卷积Linear Convolution of a Finite-Length Sequence with an Infinite-Length Sequence 建立一种基于建立一种基于DFT的方法：的方法：nxnhnxhnyM10*hn是一个是一个长度为长度为 M的有限长序列，的有限长序列，xn 是一个是一个无限长序列无限长序列(或者是长度远大或者是长度远大于于M M的有限长序列的有限长序列)90重叠相加法Overlap-Add Method0mmmNnxnx其中其中otherwise010,NnmNnxnxm首先分割首先分割 xn,（假设是因果序列），得到（假设是因果序列），得到一一组
46、长度为组长度为 N 的连续有限长子序列的连续有限长子序列 xmn:91分割分割 xn,例如例如N=7920mmmNnynxnhny*其中其中nxnhnymm*因为因为 hn的长度是的长度是 M，xmn 的长度是的长度是 N,所以所以线性卷积线性卷积 的的长度是长度是 N+M-1 mh nxn重叠相加法Overlap-Add Method0 mmx nxnmN因此，因此，93 结果是结果是，yn被分成被分成了了无限个无限个长度为长度为 N+M-1 的的短短长度的长度的线性卷积线性卷积的的和和。每个短卷积每个短卷积ymn都可都可利用利用DFT求得求得，其中，其中 DFT（和（和IDFT）在）在N+
47、M-1个点的基础上进行个点的基础上进行计算。计算。nxnhnymm*重叠相加法Overlap-Add Method0mmmNnynxnhny*940mmmNnyny长度是长度是 N+M-1，定义在区间定义在区间 0 n N+M-200nxnhny*nxnhnymm*重叠相加法Overlap-Add Method中的第一个短卷积中的第一个短卷积 :0 y n y n950mmmNnyny长度是长度是 N+M-1，叠加区间叠加区间 N n N+M-211 y nh nx n*nxnhnymm*重叠相加法Overlap-Add Method中的第二个短卷积中的第二个短卷积 :1 y n y n96重
48、叠相加法Overlap-Add Method 这表明这这表明这两个短线性卷积两个短线性卷积之间有之间有M-1个样个样本是本是重叠重叠的。的。同样同样,第三个短卷积是第三个短卷积是 长度是长度是N+M-1 叠加区间叠加区间 2N n 2N+M-22nynxnh2*0mmmNnynynxnhnymm*97重叠相加法Overlap-Add Method通常通常,在短卷积在短卷积 和和 叠加时，会有叠加时，会有M-1 个样本的重叠，个样本的重叠，重叠的范围为重叠的范围为 rN n rN+M-2nxnhr 1*nxnhr*980 mmx nxnmN例如例如M=5 和和 N=799AddAdd0mmmNn
49、yny例如例如M=5 和和 N=7100 因此，通过因此，通过 xn和和hn的线性卷积得到的的线性卷积得到的期望序列期望序列yn：,nyny0,710nynyny,71nyny,14721nynyny,142nyny60 n107 n1311 n1714 n2018 n重叠相加法Overlap-Add Method101 由于短线性卷积的结果重叠，且需要将重由于短线性卷积的结果重叠，且需要将重叠部分加起来得到正确的最后结果，所以叠部分加起来得到正确的最后结果，所以上面的实现过程称为重叠相加法上面的实现过程称为重叠相加法 M文件文件fftfilt可以用来实现上面的方法。可以用来实现上面的方法。重
50、叠相加法Overlap-Add Method102快速傅立叶变换快速傅立叶变换(FFT)1.FFT是是DFT的一种快速算法的一种快速算法2.提出与发展提出与发展由库利由库利(J.K.Cooly)和图基和图基(J.K Tuky)相继出现了桑得相继出现了桑得(G.Sand)-图基等快速算法图基等快速算法3.价值价值使运算效率提高了使运算效率提高了12个数量级个数量级推动了数字信号处理技术的应用和发展推动了数字信号处理技术的应用和发展103直接计算直接计算DFTDFT的问题及改进的方法的问题及改进的方法DFT的定义的定义两者形式类似，差别只在于的指数符号不两者形式类似，差别只在于的指数符号不同，及常
