离散傅里叶变换(DFT)-bao

,*,*,第,3,章 离散傅里叶变换,(DFT),卢光跃 教授,通信与信息工程学院,gylu,3.1,离散傅里叶变换的定义,3.2,离散傅里叶变换的基本性质,3.3,频率域采样,3.4 DFT,的应用举例,第,3,章 离散傅里叶变换,(DFT),第三章 学习目标,理解,Fourier,变换的几种形式；,理解离散傅里叶变换及性质，掌握,循环移位,、,循环共轭对称性,，掌握 循环卷积、线性卷积及二者之间的关系；,掌握,频域采样理论,；,理解频谱分析过程,。,连续,=,非周期,离散,=,周期,四种傅里叶变换形式的归纳,时间函数,频率函数,连续和非周期,非周期和连续,连续和周期,（,T,p,）,非周期和离散,（,0,=2/T,p,）,离散,（,T,）,和非周期,周期,（,s,=2/T,）,和连续,离散,（,T,）,和周期,（,T,p,）,周期,（,s,=2/T,）,和离散,（,0,=2/T,p,）,周期延拓,取主值,周期延拓,取主值,DFT,IDFT,DFS,IDFS,DFT,即,DFS,只不过时、频域各取一个主值而已,3.1,离散傅里叶变换的定义,一,. DFT,的定义,1.,周期延拓（以,N,为周期）,用,(,n,),N,表示,（,n,mod,N,）,，,其数学上就是表示“,n,对,N,取余数”， 或称“,n,对,N,取模值”。 令,0,n,1,N,-1,m,为整数,则,n,1,为,n,对,N,的余数。,例如,:,是周期为,N,=8,的序列，则有：,2.,取主值,主值区间的范围,频域,3. DFT,定义式,时、频域各取一个主值区间,DFS,DFT,旋转因子的正交性,例：,x,(,n,)=,R,4,(,n,),，求,x,(,n,),的,4,点、,8,点,和,16,点,DFT,解：设变换区间,N,=8,，则,设变换区间,N=16,， 则,思考： 其,4,点的,DFT,结果？,X(e,jw,)=DTFTR,4,(n),讨论：,N,为,DFT,变换区间长度，即周期延拓的周期、频域的采样点数；,同一序列，,N,不同，,DFT,不同；,通过后补零使,N,增大，谱线变密,高密度谱,二,.,DFT,和,Z,变换的关系,设序列,x,(,n,),的长度为,N,，其,Z,变换和,DFT,分别为：,比较上面二式可得关系式,表明 是,Z,平面单位圆上幅角为 的 点，也即：,将,Z,平面单位圆,N,等分后的第,k,点，所以,X,(,k,),也就是对,X,(,z,),在,Z,平面单位圆上,N,点,等间隔采样值,。,DFT,与序列傅里叶变换的关系为,DFT,的物理意义,X,(,k,),可以看作序列,x,(,n,),的傅里叶变换,X,(,e,j,),在区间,0, 2,）,上的,N,点,等间隔采样，其采样间隔为,N,=2/,N,。,DFT,与序列傅里叶变换、,Z,变换的关系,第一采样点在正实轴上,三,. DFT,的隐含周期性,DFT,变换对中，,x,(,n,),与,X,(,k,),均为有限长序列，但由于,WN,kn,的周期性，使,x,(,n,),和,X,(,k,),均具有,隐含周期性,，且周期均为,N,。,对任意整数,m,，总有,三,. DFT,的隐含周期性,DFT,变换对中，,x,(,n,),与,X,(,k,),均为有限长序列，但由于,WN,kn,的周期性，使,x,(,n,),和,X,(,k,),均具有,隐含周期性,，且周期均为,N,。,对任意整数,m,，总有,1,使,DFT,具有特殊性质,(,如循环移位、循环卷积等,),的根本原因，也是学习,DFT,需要着重理解的性质！,2,不论原始有限长度序列的性质如何，只要对它做,DFT,运算，即将它看做是周期为,N,的周期序列,已知,x,(,n,),是长度为,N,的有限长度序列，,X(k,)=,DFTx(n,),，令 ，试求,Y(k,)=,DFTy(n,),与,X(k,),之间的关系。,例题：,解：,DFT,与,DFS,的关系：,有限长度序列的,DFT,正好是其周期延拓序列的,DFS,级数系数的主值序列！,3.2,离散傅里叶变换的基本性质,一,.,线性性质,x,1,(n),和,x,2,(n),是两个有限长序列，长度分别为,N,1,和,N,2,y(n,)=ax,1,(n)+bx,2,(n),式中,a,、,b,为常数，即,N,max,N,1, N,2,，,则,y(n),的,N,点,DFT,为：,（补零问题！）,Y(k,)=DFT,y(n),=aX,1,(k)+bX,2,(k), 0kN-1,其中,X,1,(k),和,X,2,(k),分别为,x,1,(n),和,x,2,(n),的,N,点,DFT,。,NmaxN,1,N,2,线性性质的验证,已知,x,(,n,),是长度为,N,的有限长度序列，其,N,点,DFT,为,X(k,)=,DFTx(n,),，在序列,前部,补,N,个,0,值，得到序列,试求,Y(k,)=,DFTy(n,),与,X(k,),之间的关系。,思考题：,二,.,循环移位,1.,定义,一个长度为,N,的有限长序列,x,(,n,),的,循环移位,定义为,y,(,n,)=,x,(,n+m,),N,R,N,(,n,),：,仍为长度为,N,的序列,！,循环移位过程示意图,移出主值区间的序列值又依次从另一侧移入主值区间,1,2,3,4,5,n,=0,N,=6,左移顺时针转 如：,x,(,n,+2),右移逆时针转 如：,x,(,n,-2),从时间起点开始，逆时针读取数据,2.,时域循环移位定理,设,x,(,n,),是长度为,N,的有限长序列，,y,(,n,),为,x,(,n,),循环移位，即,则循环移位后的,DFT,为,证：利用,周期序列的移位性质,加以证明,可直接按,IDFTY(k,),证明,再利用,DFS,和,DFT,关系,这表明，有限长序列的循环移位在离散频域中引入一个和频率成正比的,线性相移,，而对频谱的幅度没有影响,幅度谱的平移不变性,。,已知,x,(,n,),是长度为,N,的有限长度序列，,X(k,)=,DFTx(n,),，在序列前部补,N,个,0,值，得到序列,试求,Y(k,)=,DFTy(n,),与,X(k,),之间的关系。,思考题：,3.,频域循环移位定理,调制特性,对于频域有限长序列,X,(,k,),，,也可看成是分布在一个,N,等分的圆周上，所以对于,X,(,k,),的循环移位，利用频域与时域的对偶关系，可以证明以下性质：,这就是调制特性,时域序列的调制等效于频域的循环移位,。,序列反转,序列共轭,序列共轭反转,序列反转,四,.,循环卷积,1,、,时域循环卷积定理,有限长序列,x,1,(,n,),和,x,2,(,n,),，,长度分别为,N,1,和,N,2,，,N,=max,N,1,N,2,。,x,1,(,n,),和,x,2,(,n,),的,N,点,DFT,分别为,：,X,1,(,k,)=DFT,x,1,(,n,),，,X,2,(,k,)=DFT,x,2,(,n,),若,Y,(,k,)=,X,1,(,k,),X,2,(,k,),，,则,y,(,n,)=,IDFT,Y,(,k,),？,与教材上不同,N,N,循环卷积结果仍为有限长序列！,注意：循环卷积的长度！,计算步骤：,将,x,2,(,m,),周期化，形成,x,2,(,m,),N,；,再反转形成,x,2,(-,m,),N,，,取主值序列则得到,x,2,(-,m,),N,R,N,(,m,),，,通常称之为,x,2,(,m,),的循环反转,；,对,x,2,(,m,),的循环反转序列循环右移,n,，形成,x,2,(,n-m,),N,R,N,(,m,),；,当,n,=0,1,2,N,-1,时，分别将,x,1,(,m,),与,x,2,(,n-m,),N,R,N,(,m,),相乘，并在,m,=0,到,N,-1,区间内求和，便得到其循环卷积,y,(,n,),。,n,N,-1,0,n,N,-1,0,0,m,0,m,0,m,0,m,0,2,3,3,2,1,1,N-1,n,N,两个长度,小于等于,N,的,序列的,N,点,循环卷积,长度仍为,N,，,与线性卷积,不同,N=6,例题：,3 2 1,1 2 3 4,4 3 2 1,24 22 24 30,2 8 6 4,6 3 12 9,12 8 4 16,不进位乘法！,思考：若两序列作,N=5,点循环卷积，结果如,何,？,若两序列作,N,=5,点循环卷积，结果如,上,！,2,、频域循环卷积定理,x,1,(,n,),，,x,2,(,n,),皆为,N,点有限长序列，,y,(,n,),的,N,点,DFT,为,时域序列相乘，,乘积的,DFT,等于各个,DFT,的循环卷积再乘以,1/,N,。,N,),(,),(,1,),(,),(,),(,1,),(,),(,),(,1,),(,),(,2,1,1,1,0,2,2,1,0,1,k,X,k,X,N,k,R,l,k,X,l,X,N,k,R,l,k,X,l,X,N,n,y,DFT,k,Y,N,N,N,l,N,N,N,l,=,-,=,-,=,=,-,=,-,=,证明：对,Y(k,),两边取,IDFT,、利用调制定理即可！,1,、有限长共轭对称与共轭反对称,设有限长序列,x,(,n,),的长度为,N,点，则它的有限长共轭对称分量,x,ep,(,n,),和有限长共轭,反对称分量,x,op,(,n,),分别被,重新定义,为,:,n,N,-1,n,N,-1,三,.,有限长共轭对称性,4,2,1,3,关于,N/2,点的对称性,共轭对称性的基本概念,N,为偶数,n,=,N,/2-,n,x,ep,(n,),为实数点,为纯虚数点,N,=8,x,(,n,)=,x,ep,(,n,)+,x,op,(,n,) 0,n,N,-1,x,*,(,N,-,n,)=,x,ep,*,(,N-,n,),+x,op,*,(,N-n,),=,x,ep,(,n,)-,x,op,(,n,) 0,n,N,-1,复,序列对称性分析,序列,DFT,复,序列对称性分析,序列,DFT,实,序列对称性分析,序列,DFT,为零,为零,实序列的频谱具有有限长共轭对称性,实,偶,序列对称性分析,序列,为零,为零,于是：,DFT,：,实偶序列的频谱具有,偶,实,对称性,为零,实,奇,序列对称性分析,序列,为零,为零,于是：,DFT,：,实奇序列的频谱具有纯虚奇函数,x,(,n,),X,(,k,),实偶函数,偶实函数,实奇函数,虚奇函数,虚奇函数,实奇函数,虚偶函数,虚偶函数,N=9,应用举例：,(,),(,),。,(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),点,信号的,可同时求得两个独立实,点,一次,，,组合成一个复序列,和,长实序列,两个,DFT,N,DFT,N,2,1,2,1,N,2,2,1,1,2,1,2,1,k,jX,k,N,Y,k,Y,n,jx,DFT,k,Y,k,X,k,N,Y,k,Y,n,x,DFT,k,Y,n,y,DFT,k,Y,n,jx,n,x,n,y,n,x,n,x,op,ep,=,-,-,=,=,=,-,+,=,=,=,+,=,*,*,五,. DFT,形式下的帕塞伐定理,证：,令,x(n,)=,y(n,),DFT,性质表,(,序列长皆为,点,),例题：,设实序列,x(n,),，,N=14,，其,14,点,DFT,为,X(k,),，已知前,8,点值为：,X(0)=12 X(1)=-1+3j X(2)=3+4j,X(3)=1-5j X(4)=-2+2j X(5)=6+3j,X(6)=-2-3j X(7)=10,试确定,1,）,X(k,),在其他频率点的值；,2,）不通过计算,IDFTX(k,),，确定下列值：,x(0) x(7),X(0), X(1), X(2), , X(N-1),3.3,频率域采样,是否任意一个频率特性（例如，理想低通特性）都能用频域采样的办法去逼近呢？,其限制条件是什么？,频域采样后会带来什么样的误差？在什么条件下才能消除误差？,一、频域采样,一个,任意的,绝对可和的非周期序列,x,(,n,),，其,Z,变换为：,对,X,(,z,),在单位圆上进行,N,点等间隔采样：,分析：,有限长度序列 任意长度序列,由 得到的周期序列 是原非周期序列,x,(,n,),的周期延拓，其时域周期为频域采样点数,N,。,时域采样造成频域的周期,延拓，,频域采样同样会造成时域的周期延拓,。,x(n,),为无限长序列,时域周期延拓,必,会混叠失真，产生误差；,当,n,增加时信号衰减得越快，或频域采样越密（即采样点数,N,越大），则误差越小，即,x,N,(n,),越接近,x(n,),；,x(n,),为有限长序列，长度为,M,：,NM,，不混叠，可无失真恢复；,NM,，,不混叠,N=3M,，,混叠,其值为,1,x(n,)=,x,N,(n,),讨论：,z=exp(j2pikm/N),第,k,个内插函数的,零极点,零极点对消,恢复时，第,k,个采样点值仅由自己决定，不受其他采样点值影响。,用频域采样,X,(,k,),表示,X,(,e,j,w,),的内插公式,内插函数：,内插函数幅度特性与相位特性,(,N,=5),|,1,(w-2/N)|,当变量,=0,时，,(,)=1,；,当,（,i=,1, 2, ,N,-1),时,，,(,)=0,。,因而可知，,满足以下关系：,k,=0, 1, ,N,-1,也就是说，函数,在本采样点,，,而在其他采样点,上，函数,。,整个,X,(e,j,),就是由,N,个,函数分别乘上,X,(,k,),后求和。 所以很明显，在每个采样点上,X,(e,j,),就精确地等于,X,(,k,),（,因为其他点的插值函数在这一点上的值为零，没有影响）即,各采样点之间的,X,(e,j,),值由各采样点的加权插值函数在所求,点上的值的叠加得到的。 ,频率采样理论为,FIR,滤波器的结构设计，以及,FIR,滤波器传递函数的逼近提供了又一个有力的工具。,对时域序列,x(n,),，,X(z,),是按,z,的幂级数（即罗朗级数）展开的，,x(n,),为罗朗级数的系数；,对频域序列,X(k,),，,X(z,),是按函数集展开的，,X(k,),为展开系数；,对时域序列,x(n,),，频响,X(e,jw,),展成负正弦级数（傅立叶级数），,x(n,),为负正弦级数的谐波系数；,对频域序列,X(k,),，频响,X(e,jw,),展成内插函数的级数，,X(k,),为展开系数；,3.4,DFT,的应用举例,DFT,在数字通信、语言信号处理、图像处理、功率谱估计、仿真、系统分析、雷达理论、光学、医学、地震以及数值分析等各个领域都得到广,泛应用。,对时域连续信号的频谱进行分析,计算信号各个频率分量的幅值、相位和功率（功率谱具有突出主频率特性，在分析带有噪声干扰的信号时特别有用）。,卷积及,相关,运算,3.4.1,用,DFT,计算,线性卷积,如果,（,L,点循环卷积）,0,k,L,-1,则，由时域循环卷积定理有,Y,(,k,)=DFT,y,(,n,),=,X,1,(,k,),X,2,(,k,), 0,k,L,-1,由此可见，循环卷积既可在,时域直接计算,，也可以在频域计算，其计算框图如下图示。由于,DFT,有快速算法,FFT,，当,N,很大时，在频域计算的速度快得多，因而常用,DFT(FFT),计算循环卷积。,图,3.4.1,用,DFT,计算循环卷积,L,点的,DFT,运算！,在实际应用中，为了分析时域离散线性非移变系统或者对序列进行滤波处理等，需要计算两个序列的,线性卷积,！为了提高运算速度，也希望用,DFT,计算线性卷积。,存在的矛盾：,DFT,只能直接用来计算循环卷积,!,为此导需要导出线卷积和循环卷积之间的关系以及循环卷积与线性卷积相等的条件。,假设,h,(,n,),和,x,(,n,),都是有很长序列，长度分别是,N,和,M,。,它们的线性卷积和循环卷积分别表示如下：,(3.4.1),(3.4.2),其中，,Lmax,N, M,对照式,(3.4.1),可以看出， 上式中,(3.4.3),利用周期延拓概念,那么，循环卷积和线性卷积之间的关系即可以确定出来！,线性卷积周期延拓为循环卷积；循环卷积即为该周期信号的主值序列！,周期延拓,图,3.4.2,线性卷积与循环卷积,重叠时哪些点是不同的？哪那些点是相同的？,用,DFT,计算,线性卷积,框图,N,点序列,M,点序列,优点：当两个序列长度相当时，运算量小,缺点：,当两个序列长度相差较大时，运算量及存储量、时延的问题,当其中一个序列无穷长时,?,设序列,h,(,n,),长度为,N,，,x,(,n,),为无限长序列。将,x(n),均匀分段， 每段长度取,M,，,则,于是，,h,(,n,),与,x,(,n,),的线性卷积可表示为,(3.4.4),图,3.4.4,重叠,相加,法卷积示意图,线性谱估计（,传统谱估计,）,数据直接,FFT,求谱，对谱的模取平方运算得功率谱（周期图法），或对数据自相关函数求谱即为功率谱（自相关法）。对被处理数据以外数据作了不合理假设；,假设以被处理数据长度为一周期，以外为其周期延拓或全为零，准确程度受数据截取长度影响；,数据较短时，估计出来的值方差大，分辨率低，甚至面目全非。,DFT,进行谱估计,为便于数学处理，对截断信号做周期延拓，得到,虚拟的无限长信号,。,用计算机进行测试信号处理时，不可能对无限长的信号进行测量和运算，而是取其有限的时间片段进行分析，这个过程称信号截断。,周期延拓信号与真实信号是不同的：,能量泄漏误差,信号的时域波形分析,超门限报警,信号类型识别,基本参数识别,P,p-p,信号的频域分析,信号频域分析是采用傅立叶变换将时域信号,x,(,t,),变换为频域信号,X,(,f,),，,从而帮助人们从另一个角度来了解信号的特征。,8563A,SPECTRUM ANALYZER 9 kHz - 26.5 GHz,傅里叶变换,X(t)=,sin(2nft),0 t,0 f,信号频谱,X(f),代表了信号在不同频率分量成分的大小，能够提供比时域信号波形更直观、丰富的信息。,时域分析与频域分析的关系,时间,幅值,频率,时域分析,频域,分析,时域分析只能反映信号的幅值随时间的变化情况，除单频率分量的简谐波外，很难明确揭示信号的频率组成和各频率分量大小。,图例：受噪声干扰的多频率成分信号,大型空气压缩机传动装置故障诊断,故障诊断,通过振动信号频谱分析，确定最大频率分量，然后根据转速和传动链，找出故障点。,一、,用,DFT,对连续信号作谱分析的基本步骤,x,a,(t,),X,a,(j,),x(n,),x(n)d(n,),x,N,(n),N,x,N,(n,),X,a,(e,jw,),X,N,(k),N,X,N,(k,),抽样,t=,nT,s,截短,周期延拓,周期延拓,取一个周期,周期延拓,s,=2/T,s,X,a,(e,jw,)*,D,(e,jw,),卷积,抽样,0,=/N,周期延拓,取一个周期,FT,DTFT,DTFT,DFS,DFT,信号的频谱分析：计算信号的傅立叶变换,如何利用,X,N,(k,),近似,X,a,(j,),?,T,0,=NT=N/,f,s,F,0,=1/T,0,=1/NT=,f,s,/N,F,0,：频率分辨率,1.,近似,处理,(0,阶近似,),a.,b.,频域抽样,：一个周期分,N,段，采样间隔,F,0,时域周期延拓：周期为,T,0,=1/F,0,0,=2F,0,频域采样间隔,c.,步骤：,结论：,用,DFT,计算,理想低通滤波器,频响曲线,截取一段,T,0,=8s,f,s,=4Hz,T=0.25s,N=T,0,/T=32,F,0,=1/NT=0.125Hz,H(k,)=T,DFTh(n,) k=0,1,.31,h(n,)=h,a,(nT)R,32,(n),2.,低频处逼近好，高频处因混叠失真而逼近不好,二、谱分析误差及参数选择,1,、,混叠失真,抽样造成的误差,时域抽样：,f,s,2f,h,，,f,s,限制谱分析范围,频域抽样：,F,0,=1/T,0,，,F,0,为频谱分辨率,F,0,为频谱分辨率：谱分析中能够分辨的两个频率分量的最小间隔,分析如何提高频率分辨率？,若想同时提高最高频率与频率分辨率，必须,N,2,、,截短效应（降低频谱分辨率,混叠失真）,周期延拓后的信号与真实信号是不同的，下面我们就从数学的角度来看这种处理带来的误差情况。,将截断信号谱,X,T,(),与原始信号谱,X(),相比较可知，它已不是原来的两条谱线，而是两段振荡的连续谱,.,原来集中在,f0,处的能量被分散到两个较宽的频带中去了，这种现象称之为频谱能量泄漏,。,周期延拓信号与真实信号是不同的：,能量泄漏误差,克服方法：,增加窗函数的长度；,用缓慢截短方式，不加矩形窗。改用旁瓣能量较小的余弦窗、三角形窗、升余弦窗等。,克服方法：信号整周期截断,常用窗函数,3,、,为提高效率,通常采用,FFT,算法计算信号频谱，设数据点数为,N,，,采样频率为,F,s,。,则计算得到的离散频率点为,:,Xs(F,i,),，,F,i,= i *,F,s,/ N , i = 0,，,1,，,2,，,.,，,N/2,X(f),f,0,f,如果信号中的频率分量与频率取样点不重合，则只能按四舍五入的原则，取相邻的频率取样点谱线值代替。,栅栏效应误差实验：,能量泄漏与栅栏效应的关系,频谱的离散取样造成了栅栏效应，谱峰越尖锐，产生误差的可能性就越大。,例如，余弦信号的频谱为线谱。当信号频率与频谱离散取样点不等时，栅栏效应的误差为无穷大。,实际应用中，由于信号截断的原因，产生了能量泄漏，即使信号频率与频谱离散取样点不相等，也能得到该频率分量的一个近似值。,从这个意义上说，能量泄漏误差不完全是有害的。如果没有信号截断产生的能量泄漏，频谱离散取样造成的栅栏效应误差将是不能接受的。,能量泄漏分主瓣泄漏和旁瓣泄漏，主瓣泄漏可以减小因栅栏效应带来的谱峰幅值估计误差，有其好的一面，而旁瓣泄漏则是完全有害的。,N=T0/T=T0*,fs,=0.1*8K=800,为使频率分辨率提高一倍，,F,0,=5 Hz,，要求,只有通过增加信号的有效持续时间,T,0,来增加采样点数,N,才能得到,高分辨率谱,；,通过后补零使,N,增加得到,高密度谱,。,高分辨率谱和高密度谱差异比较,高密度谱是在,原有序列后插零,；,高分辨谱是,增加采样点,；,高密度谱呈许多谱线型,而且当补充,0,越多,谱线也越密集,；,高分辨率谱则在取样点达到一定程度后，,谱线一定了，也没有那种密集度。,3.,用,DFT,对序列进行谱分析,非周期序列：,我们已知道单位圆上的,Z,变换就是序列傅里叶变换，即,DFT,是其,DTFT,的等间隔采样，在满足频域采样定理时原始信号可以恢复出来！,对周期为,N,的周期序列 ，由,(2.3.10),式知道， 其频谱函数为,用,DFT,的隐含周期性知道， 截取 的主值序列,x(n,)=,R,N,(n,),，,并进行,N,点,DFT,得到,其中,如果截取长度,M,等于,(n),的整数个周期， 即,M=,mN,，,m,为正整数，则,令,n=n +,rN, r=0, 1, , m-1, n=0, 1, , N-1,则,因为,k/m=,整数,k/m,整数,在任意周期内求和,如果 的周期预先不知道， 可先截取,M,进行,DFT,，,即,k/m=,整数,k/m,整数,再将截取长度扩大一倍， 截取,例：,x(n,),为周期序列，周期,N=14,所以抽样点数至少为,14,点,。,或者因为频率分量分别为,500,、,600,、,700HZ,；,得,F,0,=100HZ,最大公约数,N=f,s,/F,0,=1400/100=14,所以最少记录点数,N=14,。,T,0,=NT=512*(1/3000)=0.17,利用,DFT,可将时域难以辨识的小信号在频域轻易辨别出来,K,f,对一个连续时间信号,x,a,(t,),采样,1,秒得到一个,4096,个采样点的序列：,（,1,）若采样后没有发生频谱混叠，,x,a,(t,),的最高截止频率是多少？,（,2,）若计算采样信号的,4096,点,DFT,，频率采样值,X(k,),两点之间的模拟频率间隔是多少,Hz,？,思考题,单位圆与非单位圆采样,线性卷积具有重要的物理意义（求解,LTI,系统输出），循环卷积不具有此物理意义；,时域循环卷积在频域上相当于两序列的,DFT,的乘积，而计算,DFT,可以采用它的快速算法,快速傅里叶变换,（,FFT,），,因此循环卷积与线性卷积相比，计算速度可以大大加快；,如果信号以及系统的单位脉冲响应都是有限长序列， 那么是否能用求解循环卷积来代替线性卷积运算而不失真呢？,时间反转且线性移位,循环的作时间反转且相对第一个序列循环移位,3,、有限长序列的线性卷积与循环卷积关系,设,x,1,(,n,),是,N,1,点的有限长序列,（,0,n,N,1,-1,），,x,2,(,n,),是,N,2,点的有限长序列,（,0,n,N,2,-1,）。,（,1,）,线性卷积,x,1,(,m,),的非零区间为,0,m,N,1,-1,x,2,(,n-m,),的非零区间为,0,n-m,N,2,-1,y,1,(,n,),是,N,1,+,N,2,-1,点有限长序列，即线性卷积的长度等于参与卷积的两序列的长度之和减,1,。,（,2,）,x,1,(,n,),与,x,2,(,n,),的循环卷积。,进行,N,点的循环卷积，讨论,N,取何值时，循环卷积才能代表线性卷积？,Nmax,N,1, N,2,N,N,循环卷积正是周期卷积取主值序列,循环卷积等于线性卷积以循环卷积点数,N,为周期的周期延拓序列的主值序列,NN,1,+N,2,-1,，,循环卷积等于线性卷积,；,NN,1,+N,2,-1,，,线性卷积延拓发生混叠,，,两者部分相等,（,N,1,+N,2,-1-N,nN,-1,），,部分不等,；,N,N,N,1,+N,2,-1,NN,1,+N,2,-1,，不混叠,y,c,(n,)=,y,l,(n,),NN,1,+N,2,-1,，混叠,y,c,(n,),y,l,(n,),N,N,1,+N,2,-1,N,N,1,+N,2,-1-N,nN,-1,L,N,1,+N,2,-1,L,+,混叠,+,与线卷相等部分,=,发生混叠后循环卷积结果,N,1,=5,N,2,=4,N,1,+N,2,-1 =8,L=6,4,、快速卷积,用,DFT,计算线性卷积,DFT,DFT,IDFT,y,c,(n,),x,1,(n),x,2,(n),用,DFT,计算循环卷积,X,1,(k),X,2,(k),x,1,(n)*x,2,(n),用,DFT,计算线性卷积,补,N-N,1,个零,补,N-N,2,个零,N,点,DFT,N,点,DFT,N,点,IDFT,x,1,(n),x,2,(n),x,1,(n) 0,1,2,N,1,-1,.,N-1,x,2,(n) 0,1,2,N,2,-1,.,N-1,NN,1,+N,2,-1,用,DFT,计算线性卷积的运算量是多少？,当计算线性卷积的两序列的长度相差很大的时候，用上述框图所示的方法直接计算线性卷积会产生什么问题？,短序列补很多零，长序列需全部输入后才能计算,存储容量大,运算时间长，处理延时很大，难于实时处理,怎么解决？,块卷积,思考问题：,例 ：一个有限长序列为,（,1,） 计算序列,x,(,n,),的,10,点离散傅里叶变换。 ,（,2,） 若序列,y,(,n,),的,DFT,为,式中，,X,(,k,),是,x,(,n,),的,10,点离散傅里叶变换，求序列,y,(,n,),。,解,：,（,1,）,y,(,n,)=,x,(,n,+2),10,R,10,(,n,)=2,(,n,-3)+,(,n,-8),（,2,）,X,(,k,),乘以一个,W,N,km,形式的复指数相当于是,x,(,n,),循环移位,m,点。 本,题中,m,=-2,x,(,n,),向左循环移位了,2,点， 就有,（,3,）若,10,点序列,y,(,n,),的,10,点离散傅里叶变换是,式中,X,(,k,),是序列,x,(,n,),的,10,点,DFT,，,W,(,k,),是序列,w,(,n,),的,10,点,DFT,0,n,6,其他,求序列,y,(,n,),。,解：,（,3,）,X,(,k,),乘以,W,(,k,),相当于,x,(,n,),与,w,(,n,),的循环卷积。为了进行循环卷积，可以先计算线性卷积再将结果周期延拓并取主值序列。,x,(,n,),与,w,(,n,),的线性卷积为,z,(,n,)=,x,(,n,)*,w,(,n,)=,1, 1, 1, 1, 1, 3, 3, 2, 2, 2, 2, 2,循环卷积为,在,0,n,9,求和中，仅有序列,z,(,n,),和,z,(,n,+10),有非零值，用表列出,z,(,n,),和,z,(,n,+10),的,值，对,n,=0, 1, 2, , 9,求和，得到：,n,0 1 2 3 4 5 6 7 8 9,10 11,Z,(,n,),z,(,n,+10),1 1 1 1 1 3 3 2 2 2,2 2 0 0 0 0 0 0 0 0,2,0 0,y,(,n,),3 3 1 1 1 3 3 2 2 2,_ _,10,点循环卷积为,y,(,n,)=,3, 3, 1, 1,，,1, 3, 3, 2, 2, 2,