第三章离散傅里叶变换及其快速计算方法(DFT、FFT)

DFS和DFT的导出DFS和DFT的性质Z变换与DFS的关系FFTIDFT频谱分析,第三章DFT离散付氏变换,2,连续信号xa(t)，其傅里叶变换为：xa(t)为时域连续信号Xa()为频域连续信号,3.1问题的提出：连续信号的傅里叶变换,3,离散信号在两种变换域中的表示方法（1）离散时间傅里叶变换DTFT-提供了绝对可加的离散时间序列在频域（）中的表示方法。（2）Z变换-提供任意序列的z域表示。,这两种变换有两个共同特征：（1）变换适合于无限长序列（2）它们是连续变量或z的函数,3.1问题的提出：离散信号的变换,4,问题：X(z)，X(ejw)都是连续的，利用计算机处理有困难，例如使用Matlab，因此提出了在频域内取样，使频谱离散化的问题；必须截断序列，得到有限个点的序列。目标：我们需要得到一个可进行数值计算的变换方法：（1）DTFT-频域中原始信号频谱的周期拓展（2）对DTFT在频域中采样-DFS（3）将DFS推广到有限持续时间序列DFT（DFT避免了前面提到的那两个问题，并且它是计算机可实现的变换方式。）DFT已成为DSP算法中的核心变换，原因：（1）有限长序列傅里叶变换的重要方法（2）有快速算法,3.1问题的提出：可计算性,5,3.1问题的提出：傅里叶变换的四种形式（1）,非周期连续时间傅里叶变换(FT)连续频率周期连续时间傅里叶级数(FS)离散频率非周期离散时间离散时间傅里叶变换(DTFT)连续频率周期离散时间离散傅里叶级数(DFS)离散频率,6,3.1问题的提出：傅里叶变换的四种形式（2）,1.连续信号（非周期）的付氏变换,时域连续函数造成频域是非周期的谱时域的非周期造成频域是连续的谱,7,2.周期连续时间信号：傅里叶级数FS,时域连续函数造成频域是非周期的谱。频域的离散对应时域是周期函数。,3.1问题的提出：傅里叶变换的四种形式（3）,时域周期频域离散,8,3.非周期离散信号：离散时间傅里叶变换DTFT,时域的离散化造成频域的周期延拓时域的非周期对应于频域的连续,3.1问题的提出：傅里叶变换的四种形式（4）,时域离散频域周期,取样定理,9,4.周期离散时间信号：离散傅里叶级数DFS,一个域的离散造成另一个域的周期延拓离散傅里叶级数的时域和频域都是离散的和周期的,3.1问题的提出：傅里叶变换的四种形式(5),时域周期、离散频域周期、离散,10,四种傅里叶变换形式的归纳总结：,离散时间函数的取样间隔：T1，取样频率：,离散频率函数的取样间隔：F0，时间周期：,3.1问题的提出：傅里叶变换的四种形式（6）,结论：时域中函数取样(离散)（映射）频域中函数周期重复；频域中函数取样（映射）时域中函数周期重复；取样间隔（映射）周期（2/间隔）,0,时域中函数的取样和频域中函数的取样,3.1问题的提出：傅里叶变换的四种形式(7),12,由以上讨论可以清楚地看到，时域取样将引起频域的周期延拓，频域取样也将引起时域的周期延拓。因此可以设想，如果同时对频域和时域取样，其结果是时域和频域的波形都变成离散、周期性的波形，从而我们可以利用付氏级数这一工具，得到它们之间的离散付氏级数DFS关系。,3.2DFS及其性质,13,基本关系式若r，m都是整数,则:,其中:,DFS定义：预备知识,证明:对于r=m：不论k取何值，显然等式成立。对于rm：,14,为了推导的关系，作下列变量代换：时域：频域：则得：,?,DFS定义：正变换,15,周期离散序列的Z变换存在（收敛）的问题因为周期离散序列，而对于周期信号，严格数学意义上讲，其Z变换不收敛，因为：而对于找不到衰减因子使它绝对可和（收敛）。为此，定义新函数，其Z变换：,DFS定义：正变换,16,其频谱：（是连续变量，需要对其离散化）,DFS定义：正变换,（取的一个主周期进行Z变换）,17,频域取样X(ej)是连续变量的周期函数，周期为2。把离散化，即在02区间内等间隔取N个点，取样间隔为2/N。另一个角度看，X(ej)是Z平面单位圆上的Z变换。连续变量的离散化也可以认为是把单位圆分N等分，每分为2/N。其中：称为频域中的取样间隔，也称为频率分辨率。,DFS定义：正变换,18,DFS定义：正变换,19,DFS：,DFS定义：正变换,也仅有0，1，N-1个独立值,周期为N。,因为,所以,20,反变换IDFS正变换两端乘以，m=0,1,N-1然后令k=0，1，N-1求和，得：,DFS定义：反变换,用正交条件：,21,DFS定义：反变换,即,（只有m=n时，才有值，而m不等于n时，为零，因此，x(n)只取x(m)）,变量m替换为n，得,22,DFS变换对：时域周期序列与频域周期序列间的关系,DFS定义：反变换,其中,23,在什么条件下不产生混迭失真？频率取样频率取样：若时间信号有限长，当满足下列条件时，X(ej)的样本值X(k)能不失真的恢复成原信号。为了避免时间上的混迭：（1）必须是时间限制（有限时宽）（2）取样频率间隔小于,DFS定义：几点说明,24,频率分量如果变量DFS可表示为：因此，时域n及频域k都是有物理意义的。,DFS定义：几点说明,（指数项kn不变）,25,更具体地，傅里叶系数的标号k和频率f的关系为：所以：对应关系：傅里叶系数标号k：0N数字频率：02模拟频率f：0fs,DFS定义：几点说明,26,DFS定义：几点说明,频率成份直流分量：当k=0时，此时得到的傅里叶级数的系数称为信号的直流分量（DCComponent），是信号的平均值；交流分量：其它频率（k0）称为周期信号的谐波，此时的傅里叶级数系数称为信号的交流分量。k=1时的频率为信号的一次谐波，或基频，频率大小为fs/N，时间为NTs，等于完成一个周期所需要的时间。其它谐波为基频的整数倍。离散傅里叶级数包含了0到(N-1)fs/N的频率，因而N个傅里叶级数的系数位于从0直到接近取样频率的频率上。,时域,27,DFS定义：几点说明,周期信号的频谱由傅里叶系数可得到的幅度频谱和相位频谱，不难证明，如果是实序列，那么幅度频谱是周期性偶函数，相位频谱是周期性奇函数。周期信号由离散傅里叶级数DFS得到的频谱，和非周期信号由离散时间傅里叶变换DTFT得到的频谱之间有重要区别。DTFT产生连续频谱，这意味着频谱在所有的频率处都有值，因而非周期信号的幅度和相位频谱是光滑无间断的曲线。与之相反，DFS仅有N点的频谱，仅包含有限个频率，因而周期信号的幅度和相位频谱是线谱，即相等间隔的竖线，当频谱的横坐标变量用实际频率f代替k时，谱线间隔为fs/N。并不是所有的周期信号都含有全部谐波，例如有些频谱只有奇次谐波，比如三角波，偶次谐波为0，而有些频谱仅在一些谐波处的值为0。,28,DFS的Matlab的实现,由DFS的定义可以看出它是一种可进行数值计算表示式，它可由多种方式实现。（1）利用循环语句for.end实现为了计算每个样本，可用for.end语句实现求和。为了计算所有的DFS系数，需要另外一个for.end循环，这将导致运行嵌套的两个for.end循环。显然，这种方法的效率较低。,29,设和代表序列x(n)和X(k)主周期的列向量，则DFS的正反变换表达式由下式给出：其中矩阵WN由下式给出：,矩阵WN为方阵，叫做DFS矩阵.,（2）利用矩阵矢量乘法,30,functionXk=dfs(xn,N)n=0:1:N-1;%rowvectorfornk=0:1:N-1;%rowvecorforkWN=exp(-j*2*pi/N);%Wnfactornk=n*k;%createsaNbyNmatrixofnkvaluesWNnk=WN.nk;%DFSmatrixXk=xn*WNnk;%rowvectorforDFScoefficientsfunctionxn=idfs(Xk,N)n=0:1:N-1;%rowvectorfornk=0:1:N-1;%rowvecorforkWN=exp(-j*2*pi/N);%Wnfactornk=n*k;%createsaNbyNmatrixofnkvaluesWNnk=WN.(-nk);%IDFSmatrixxn=(Xk*WNnk)/N;%rowvectorforIDFSvalues,DFS的Matlab的实现,例：求出下面周期序列的DFS表示式,解：上述序列的基本周期为N=4，因而W4=e-j2/4=-j，,例:下面给出一周期“方波”序列：其中，m=0,1,2,，N是基本周期，L/N是占空比。(a)确定一种用L与N描述的的表达式。(b)分别画出当L=5,N=20；L=5，N=40；L=5，N=60；L=7，N=60时表达式。(c)对所得结果进行讨论。,解：(a)由DFS定义可得,而：,的幅值可表示为：,b.Matlab程序如下：%Chapter3:Example3.03L=5;N=20;(改变参数）x=ones(1,L),zeros(1,N-L);xn=x*ones(1,3);xn=(xn(:);n=-N:1:2*N-1;subplot(1,1,1);subplot(2,1,2);stem(n,xn);xlabel(n);ylabel(xtilde(n)title(Threeperiodsofxtilde(n)axis(-N,2*N-1,-0.5,1.5),%Part(b)L=5;N=20;(改变参数）xn=ones(1,L),zeros(1,N-L);Xk=dfs(xn,N);magXk=abs(Xk(N/2+1:N)Xk(1:N/2+1);k=-N/2:N/2;subplot(2,2,1);stem(k,magXk);axis(-N/2,N/2,-0.5,5.5)xlabel(k);ylabel(Xtilde(k)title(DFSofSQ.wave:L=5,N=20),注意：是周期信号，图中只画出了从N/2到N/2的部分。c.从图中可以看到，方波的DFS系数的包络像“Sinc”函数，K=0时的幅度等于L；同时函数的零点位于N/L（占空比的倒数）的整数倍处；L=5不变，N变大（即填0，但有效信息没有增加），则形状不变，只是更平滑，即获得了一个高密度谱；N=60不变，L变大（即增加了原始数据长度），则变换后得形状发生了变化，获得了更多的信息，即高分辨率谱。,例：设当N=5、10、20、50时，分别对其Z变换在单位圆上取样，研究不同的N对时域的影响。,%Frequency-domainsampling%x(n)=(0.7)n*u(n)%X(z)=z/(z-0.7);|z|0.7subplot(1,1,1)N=5;(改变参数）k=0:1:N-1;wk=2*pi*k/N;zk=exp(j*wk);Xk=(zk)./(zk-0.7);xn=real(idfs(Xk,N);%只取实部，去掉产生的虚部误差xtilde=xn*ones(1,8);%画出8个周期xtilde=(xtilde(:);subplot(2,2,1);stem(0:39,xtilde);axis(0,40,-0.1,1.5);xlabel(n);ylabel(xtilde(n);title(N=5),从图中清楚地表明在时域中出现的混叠，尤其是当N=5与N=10时。对于大的N值，其x(n)的尾部足够小，实际上不会导致明显的混迭。这对于变换前，有效截取无限序列，是非常有效的。,1.2020,1.0291,1.0008,1.0000,42,线性,且：,则,a,b为任意常数,DFS的性质：线性,43,序列的周期移位（时域）若是周期序列，其周期为N，移位后仍为周期序列，且：,DFS的性质：序列的周期移位,证明：,44,调制特性（频域周期移位）,DFS的性质：调制特性,证明：,45,周期卷积（时域）,若,则,频域相乘时域卷积周期卷积：两个周期序列在一个周期上的线性卷积，是一种特殊的卷积计算形式。,DFS的性质：周期卷积（1）,46,DFS的性质：周期卷积（2）,证明：,47,DFS的性质：周期卷积（3）,（1）x1(n)和x2(n)是周期的。（2）求和范围为一个周期（3）周期序列周期卷积后，序列的长度仍然是周期的；,位置保持不变,48,序列的线性卷积与周期卷积的几点区别：线性卷积的求和对参与卷积的两个序列无任何要求，而周期卷积要求两个序列是周期相同的周期序列。线性卷积的求和范围由两个序列的长度和所在的区间决定，而周期卷积的求和范围是一个周期N。线性卷积所得序列的长度(M+N-1)由参与卷积的两个序列的长度确定，而周期卷积的结果仍是周期序列，且周期与原来的两个序列周期相同。周期卷积等同于两个周期序列在一个周期上的线性卷积计算。,DFS的性质：周期卷积（4）,解：,例：已知序列x1(n)=R4(n)，x2(n)=(n+1)R5(n)，分别将序列以周期为N=6拓展成周期序列，求两个周期序列的周期卷积和。,1,5,4,5,1,2,51,频域周期卷积利用DFS的对偶性有：,若,则,时域相乘频域卷积,DFS的性质：周期卷积(5),注意频域卷积的求和号前面有1/N。,52,DFS的性质：共轭对称性,由任一周期性序列，定义如下两个序列：共轭偶对称周期性序列共轭奇对称周期性序列,且具有如下关系：,其它对称性质见教科书,53,DFS定义和性质：小结,时域周期序列与频域周期序列的关系DFSDFS的性质重点：周期移位调制特性周期卷积,54,对于一段有限长信号（连续），分析频谱问题是付氏积分问题，进行时域周期重复和取样两过程，就可把广义积分问题变成有限项求和，即由CTFTDFS。DFS变换：周期离散时间函数与一周期离散频率函数的组合，它们是有限求和（而不是积分），常用DFS来逼近连续时间过程的傅氏变换。也即要用数字运算能完全计算出付氏积分，必须对时间函数和频率函数取样（即DFS），选择时间有限和频率有限的信号。时间取样：取样频率大于信号最高频率两倍；频率取样：取样间隔足够小，使时间函数的周期（单位圆上等分（取样）的点数）大于信号的时域长度。结果：频域和时域中均不出现混迭现象。,3.3有限离散傅里叶变换及其性质(1),55,离散傅氏级数提供了一种对离散时间傅氏变换作数值计算的技巧，它在时域和频域都是周期的，但在实际中大多数信号不具有周期性，它们很可能具有有限持续时间。对这些信号，怎样探讨一种可数值计算的傅氏表达式？理论上，可通过构造一周期信号，其基本形状为有限持续时间信号，然后计算此周期信号的DFS。实际上，这也就是定义了一种新的变换，称为离散傅氏变换（DFT），它是DFS的主周期。DFT是对任意有限持续时间序列可数值计算的傅氏变换。,3.3有限离散傅里叶变换及其性质(2),56,同样：X(k)也是一个N点的有限长序列,关系?,其中:,DFT定义：表达式(1),周期序列的表示,57,DFT定义：表达式(2),若n=n1+n2N成立，且n1满足0n1N-1，则把n1称做n对N的模数，用符号(n)N表示，即：n模N=(n)N=n1，也就是n对N取余数。例:是周期为N=6的序列，求n=19及n=-2两数对N的余数。解：n=19=1+36，(19)6=1n=-2=(-1)6+4，(-2)6=4即：,58,在无混迭的情况下，我们看如何把DFS变成DFT?,DFS:,DFT定义：表达式(3),因无混迭，则时域中一个周期长的主值序列对应于频域中一个周期长的主值序列。从DFS的时域和频域中各取出一个周期，即得到有限长度离散序列的时域和频域傅氏变换。,59,有限长序列的DFT正变换和反变换：,其中：,DFT,DFT定义：表达式(4),或,注意：从工程角度看，DFS和DFT的表达式没有本质区别。,60,DFT的矩阵表示形式,若令：,则：,DFT定义：表达式(5),61,DFT定义：表达式(6),DFT图形解释,62,不仅浓缩了的全部内容，同时也浓缩了的全部内容。能够如实、全面地表示的频域特征，所以DFT具备明确的物理含义。,DFT定义：表达式（7）,DFT意义,63,由上面的讨论可知，在0nN-1上，DFS和DFT相同。因此，可用类似的方法实现DFT。把原先名为dfs和idfs的Matlab函数改名为dft和idft函数，即可实现离散傅氏变换DFT。实际中，我们用的更多的是DFT的快速算法FFT，见后续内容。,DFT定义：Matlab实现,64,例：x(n)是一个4点序列：（1）计算离散时间傅氏变换X(ejw)，并画出它的幅度和相位。（2）计算x(n)的4点DFT。,DFT定义：举例,65,解：（1）离散时间傅氏变换为：,因而,DFT定义：举例,66,DFT定义：举例,67,(2)用X4(k)表示4点DFT:,DFT定义：举例,%b)4-pointDFTN=4;w1=2*pi/N;k=0:N-1;X=dft(x,N);magX=abs(X),phaX=angle(X)*180/pisubplot(2,1,1);plot(w*N/(2*pi),magH,-);axis(-0.1,4.1,-1,5);holdonstem(k,magX);,68,k,DFT定义：举例,69,例:怎样得到DTFTX(ejw)的其他样本？解：显然，我们的采样频率应更小一些，也就是说，应增加N的长度。有两种方法，一种是采样时就采样更多的样本；另一种是在序列后面添加一定长度的零，叫做填零运算，在实际中，为了得到一个较密的频谱，这种运算是必要的。,3.3.1DFT定义：举例,70,（a）给x(n)后附加4个零得到一个8点序列。x(n)=1,1,1,1,0,0,0,0设X8(k)为一8点DFT，则在这种情况下，频率分辨率为w1=2/8=/4。,DFT定义：举例,71,%b)8-pointDFTN=8;w1=2*pi/N;k=0:N-1;x=x,zeros(1,4);X=dft(x,N);magX=abs(X),phaX=angle(X)*180/pi结果如下：magX=4.00002.61310.00001.08240.00001.08240.00002.6131phaX=0-67.5000-153.4349-22.5000-90.000022.5000-53.130167.5000,DFT定义：举例,72,DFT定义：举例,73,（b)更进一步，给x(n)填充12个零，变成一个16点序列，即：x(n)=1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0在这种情况下，频率分辨率为w1=2/16=/8。,DFT定义：举例,74,%c)16-pointDFTsubplot(1,1,1)N=16;w1=2*pi/N;k=0:N-1;x=x,zeros(1,8);X=dft(x,N);magX=abs(X),phaX=angle(X)*180/pisubplot(2,1,1);plot(w*N/(2*pi),magH,-);axis(-0.1,16.1,-1,5);holdonstem(k,magX);xlabel(k);ylabel(|X(k)|);title(MagnitudeoftheDFT:N=16)holdoffsubplot(2,1,2);plot(w*N/(2*pi),phaH*180/pi,-);axis(-0.1,16.1,-200,200);holdonstem(k,phaX);xlabel(k);ylabel(Degrees);title(AngleoftheDFT:N=16),DFT定义：举例,75,DFT定义：举例,76,结论：基于以上两个例子，可以得到以下结论。填零是给原始序列填零的运算。这导致较长的DFT，它会给原始序列的离散时间傅氏变换提供间隔更密的样本。在Matlab中，用zeros函数实现填零运算。为精确地画出离散时间傅氏变换X(ejw)，只需要4点DFTX4(k)。这是因为x(n)仅有4个非零样本，因此，可通过填零得到X8(k)、X16(k)等等，用它们来填充X(ejw)的值。填零运算提供了一个较密的频谱和较好的图示形式，但因为在信号中只是附加了零，而没有增加任何新的信息，因此，它不能提供更高分辨率的频谱。为了得到更高分辨率的频谱，需要获得更多的数据。其他的先进方法则是利用边缘信息和非线性技术。,DFT定义：举例,77,例：为了说明高密度频谱和高分辨率频谱之间的区别，考察序列求出它基于有限个样本的频谱。（a）当0n10时，确定并画出x(n)的离散傅氏变换。（b）当0n100时，确定并画出x(n)的离散傅氏变换。,DFT定义：举例,78,(a)首先确定x(n)的10点DFT，得到其离散时间傅氏变换的估计%Highresolutionspectrumbasedon100samplesofthesignalx(n)subplot(1,1,1);n=0:1:99;x=cos(0.48*pi*n)+cos(0.52*pi*n);%Spectrumbasedonthefirst10samplesofx(n)n1=0:1:9;y1=x(1:1:10);subplot(2,1,1);stem(n1,y1);title(signalx(n),0=n=9);xlabel(n)axis(0,10,-2.5,2.5);Y1=dft(y1,10);magY1=abs(Y1(1:1:6);k1=0:1:5;w1=2*pi/10*k1;subplot(2,1,2);stem(w1/pi,magY1);%(只画了一半的点，原因是镜像对称的点）title(SamplesofDTFTMagnitude);xlabel(frequencyinpiunits);axis(0,1,0,10);disp(PressRETURNtocontinue);pause;,DFT定义：举例,79,DFT定义：举例,80,填充90个零以得到较密的频谱%Highdensityspectrum(100samples)basedonthefirst10samplesofx(n)n2=0:1:99;y2=x(1:1:10)zeros(1,90);subplot(2,1,1);stem(n2,y2);title(signalx(n),0=n=9+90zeros);xlabel(n)axis(0,100,-2.5,2.5)Y2=dft(y2,100);magY2=abs(Y2(1:1:51);k2=0:1:50;w2=2*pi/100*k2;subplot(2,1,2);plot(w2/pi,magY2);Holdon;stem(w2/pi,magY2);title(DTFTMagnitude);xlabel(frequencyinpiunits)axis(0,1,0,10)disp(PressRETURNtocontinue);holdoff;pause;,DFT定义：举例,81,DFT定义：举例,从结果图中可以看到，此序列在w=0.5处有一主频率，原始序列则没有说明这一点。填零运算提供了更加平滑,高密度的频谱曲线,82,（b）为得到更多的频谱信息，采集更多的样本，用x(n)的100个样本来确定它的DFT。%Highresolutionspectrumbasedon100samplesofthesignalx(n)subplot(2,1,1);stem(n,x);title(signalx(n),0=n=99);xlabel(n)axis(0,100,-2.5,2.5)X=dft(x,100);magX=abs(X(1:1:51);k=0:1:50;w=2*pi/100*k;subplot(2,1,2);plot(w/pi,magX);title(DTFTMagnitude);xlabel(frequencyinpiunits)axis(0,1,0,60)disp(PressRETURNtocontinue);,DFT定义：举例,83,DFT清楚地表明了两个靠得很紧的频率，这是x(n)的高分辨率的频谱,采样更多的数据提供了更多的信息,DFT定义：举例,84,DFT从整体上可看成是由窄带相邻滤波器组成的滤波器组DFT的每个分量X(k)可看成是窄带滤波器的输出，此窄带滤波器的中心位于数字频率2k/N弧度，带宽为2/N。此概念的一个典型应用是数字音频压缩中的分析滤波器，例如AC3和MPEGAudio都是如此。分辨率（子带带宽）N点DFT覆盖了0到fs（取样频率）的频率范围。因此，频率取样点以fs/N为间隔。该频率间隔称为DFT的频率分辨率，它描述了DFT分辨相邻信号频率的程度。频率间隔越小，分辨率越好；间隔越大，DFT分辨率越差。假定取样频率保持不变，当取样点越大时，DFT分辨率就会越好，这样频率间隔小，可获得频谱的许多细节。从滤波器组的角度看，分辨率好的DFT是由大量非常窄的带通滤波器构成的。,DFT定义：DFT频谱,85,DFT定义：DFT频谱,滤波器的中心频率DFT分量X(k)位于以下频率处：如果画出对频率f（Hz）而不是对k的频谱，则更容易从实际角度解释DFT频谱。当k=N/2时，f到达了fs/2奈奎斯特频率。因而，k=0到k=N/2的DFT点携带了DFT全部必要的幅度和相位信息。其余点只是基带重要信号频率的镜像副本，是取样的人为结果。即幅度频谱是周期性的偶对称。,86,例:为了体会DFT的滤波器组解释，x(t)由两个余弦信号和随机噪声构成：取样频率fs=6.4Hz。请分析其频谱。解：x(t)包含两个频率1/16Hz和3/8Hz，以6.4Hz取样后，相应的数字频率由=T=2f/fs，分别为1=2/102.4和2=6/51.2弧度。则在40秒内以6.4Hz进行取样，共得406.4=256个取样点。,DFT定义：DFT频谱,87,3.3.1DFT定义：DFT频谱,15,88,在上图中随机噪声采用的是正态分布的高斯白噪声（randn函数），由于白噪声信号中所有频率的贡献均相等，所以白噪声频谱近似平坦。对于N=256点DFT，每个标号k对应于数字频率2k/256弧度。由于DFT可以看作一组相邻窄带滤波器构成，每个滤波器以数字频率2k/256弧度为中心。因而频谱峰值应位于2k/256=2/102.4和2k/256=6/51.2，即k=2.5（非整数）和k=15（整数）处。由于k必须是整数，k=2.5处的峰值又分成k=2和k=3处的两个小峰。当DFT变换的长度N是多个数字频率公倍数的整数倍时，即数字频率正好位于子带滤波器的中心频率上时，则得到理想的谱线。DFT是在频谱中对连续频谱进行取样，因此DFT不能超过DFT频率分辨率所允许的范围而去准确定位频率。即当信号谱线所在位置与DFT频率分辨率位置保持一致时，则能准确定位此谱线；当DFT中没有频率与所分析信号的重要频率相符时，DFT就将导致真实频谱的模糊。,DFT定义：DFT频谱,89,例:以256Hz取样频率对信号取样，得到离散信号x(n)，计算其频谱。解：数字频率：数字信号：数字周期：数字周期为64，覆盖了15个模拟信号周期。,DFT定义：DFT频谱,90,对上述离散信号进行N=128和N=130点DFT，因为128是64的整数倍（2倍），从图中看，128点DFT的幅度频谱中有两个理想尖锋，第二个尖锋是第一个的镜像，频谱中的理想尖锋就标志着正弦的频率。而当N=130不是该数字信号的数字周期64的整数倍，尖锋变宽并变小了，这就是频谱模糊现象。,3.3.1DFT定义：DFT频谱,30,91,序列x(n)的Z变换在单位圆上进行N等分，即2/N，就是序列的DFT变换。(取样）Z变换和DFT的关系是取样和内插的关系，这在实际应用中很重要。,DFT与DTFT和Z变换的关系,92,取样Z变换设x(n)为一个长度为N的有限长序列，则有：,DFT与Z变换的关系：取样Z变换,93,从DTFT的角度看：有限长序列的DFT结果包含了N个离散频率点处的DTFT结果，这个离散频率点等间隔地分布在区间0，2)内；,从Z变换的角度看：DFT结果包含了z平面上N个离散点处的Z变换结果，这N个离散点均匀地分布在单位圆上，由此也称DFT为单位圆上的取样Z变换。,DFT与Z变换的关系：取样Z变换,94,频域取样定理：若序列长度为M，则只有当频域采样点数N满足NM时，才有:即可由频域取样X(k)不失真地恢复原信号x(n)，否则产生时域混叠现象。此时可由N个取样值X(k)内插恢复出X(z)或X(ejw)。,DFT与Z变换的关系：z域内插,时域取样定理：在满足奈奎斯特定理条件下，时域取样信号可以不失真地还原原连续信号。频域取样情况如何？取样条件？内插公式？,95,Z域内插公式：由DFTX(k)可以确定z平面上任一点处的X(z),DFT与Z变换的关系：z域内插,z平面内插公式,内插函数,96,内插函数的零极点分布极点：(N-1)阶极点z=0；一阶极点z=1；零点：N个一阶零点:抵消：z=1处的一阶极点和一阶零点互相抵消，一阶零点数量变为（N-1）个。,3.3.2DFT与Z变换的关系：z域内插,(z)的零、极点分布,97,3.3.2DFT与Z变换的关系：F域内插,F域内插公式：由频域取样DFTX(k)表示DTFTX(ejw),98,即:,其中:,频域内插函数,频域内插公式,3.3.2DFT与Z变换的关系：F域内插,99,F内插函数的零极点分布根据(z)的零极点分布规律可知：(零极点对系统频率响应的影响)极点：ej到极点z=0的距离恒为1，对幅频特性没有影响零点：在区间0,2内，|()|存在(N-1)个零值点存在(N-1)个极值点，分别为：,(z)的零、极点分布,3.3.2DFT与Z变换的关系：F域内插,100,插值函数的幅度特性与相位特性（N=5),DFT与Z变换的关系：F域内插,101,频域内插的物理含义,只有当频域取样点数N大于序列长度M时，中不会出现混迭现象，这时能够从中如实恢复x(n)，即能够由X(k)准确重建X(z)和X(ejw)。对序列作DFT变换点数不应低于序列的长度。X(k)浓缩了x(n)在变换域中的全部特性。,DFT与Z变换的关系：F域内插,102,这里，序列长度及DFT点数均为N若不等，分别为N1、N2，则需补零使两序列长度相等，均为N，且,若两序列x1(n)和x2(n)的长度均为N，且其N点DFT分别为：,则：,DFT的性质：线性,a,b为任意常数,103,对于周期序列，有：其中：周期共轭偶对称分量周期共轭奇对称分量又定义：又由于则：即有限长序列由共轭偶对称和共轭奇对称两部分组成。,DFT的性质：对称性,共轭奇对称分量,共轭偶对称分量,104,DFT的性质：对称性,105,若存在有限长序列x(n)，长度为N，其N点DFT的结果为X(k)，则有，,证明：,DFT的性质：帕斯瓦尔定理,该定理表明:可利用序列的DFT结果表示信号的能量，序列在时域计算的能量与在频域计算的能量相等，即变换前后的能量保持不变。这进一步说明，虽然DFT有别于DTFT，但其仍然具有明确的物理含义。,106,DFT的性质：反转定理,循环反转的定义如果x(n)是长度为N的序列，则称x(-n)NRN(n)为x(n)的循环反转运算。,循环反转运算是有限长序列所特有的一种运算，其结果仍然是集合0,1,.,(N-1)上的有限长序列，特别注意n=0时情况。计算过程：（1）补零为N；（2）周期延拓；（3）纵轴镜像；（4）取主值序列。,107,DFT的性质：反转定理,循环反转的DFT,若,则,证明：,108,DFT的性质：序列的循环移位(圆周移位),循环移位的定义：,称其为循环移位的原因在于，当序列从一端移出范围时，移出的部分又会从另一端移入该范围。线性移位：若N点序列沿一方向线性移位，它将不再位于区间0nN-1上。,109,DFT的性质：序列的循环移位(圆周移位),有的书上称为圆周移位。把x(n)看作排列在N等分的圆周上，循环移位就相当于序列x(n)在圆周上移动，故称为圆周移位。实际上重复观察几周时，看到的就是周期序列。,110,例：设x(n)=10(0.8)n，0n10为11点序列(a)画出x(n+4)11R11(n)，也就是向左循环移位4个样本的序列；(b)画出x(n-3)15R15(n)，也就是假定x(n)为15点序列，向右循环移位3个样本。,DFT的性质：序列的循环移位(圆周移位),111,(b)在这种情况下，给x(n)后填充4个零，将其看作一个15点序列。此时的循环移位与N=11时不同，看起来像线性移位x(n-3)。因此，序列的周期长度是非常重要的一个参数。,DFT的性质：序列的循环移位(圆周移位),112,结论：有限长序列的循环移位，在离散频域中只引入了一个和频率成正比的线性相移，对幅频特性没有影响。,DFT的性质：序列循环移位后的DFT,若,，则,证明：,113,时域序列的调制等效于频域的循环移位,DFT的性质：频域循环移位后的IDFT,频域循环移位后的IDFT（调制特性）由DFT所具有的对偶特性不难看出，在频域内循环移位时，将有类似的结果，即：,证明：,114,DFT的性质：频域循环移位后的IDFT,证明：,115,DFT的性质：循环卷积(圆周卷积),循环卷积定义：设x1(n)和x2(n)都是长度为N的有限长序列，把它们分别拓展为周期序列和，定义循环卷积为：,周期序列卷积后取主值,116,因为上式的求和范围是m由0到N-1，因此第一个序列x1(m)可以不作周期拓展，即注意两个N点序列的线性卷积将导致一个更长的序列。而循环卷积将区间限制在0nN-1，结果仍为N点序列，它与线性卷积的结构类似。不同点在于求和范围和N点循环移位。它与N有关，也叫做N点循环卷积。,DFT的性质：循环卷积(圆周卷积),N,窗函数限定了循环卷积的范围,117,循环卷积过程：（1）补零（2）周期延拓（3）反转，取主值序列（循环反转）（4）对应位相乘，然后求和，得到n=0时的卷积结果。（5）向右循环移位（圆周移位）（6）重复，n=1(N-1),DFT的性质：循环卷积(圆周卷积),注意n=0时的循环反转,118,循环卷积的时频映射关系由DTFT的性质可知，两个序列时域上的线性卷积运算在频域上表现为两个序列DTFT结果的乘积。同样的，若则即当在频域中进行两个N点DFT相乘时，在时域中映射为循环卷积（而不是通常的线性卷级！）。,DFT的性质：循环卷积(圆周卷积),119,证明：将X1(k)和X2(k)作周期延拓，分别得到X1(k)N和X2(k)N。,则,再设,于是,DFT的性质：循环卷积(圆周卷积),令,120,因为,所以,此时上式最后一个求和号中，已不对r求和，故此求和号可以去掉，因此，,因而，,即,DFT的性质：循环卷积(圆周卷积),121,利用时域、频域的对偶性可得频域循环卷积:,若,则,时域循环卷积可在频域中完成:,DFT的性质：循环卷积(圆周卷积),122,（1)同心圆法（2)利用求周期卷积的作图法（3)解析式法（4)Matlab方法,DFT的性质：循环卷积计算方法,123,同心圆法可用两个同心圆来表示：x1(n)：内圆顺时针方向排列x2(n)：外圆逆时针方向排列x1(0)与x2(0)对齐。,DFT的性质：循环卷积计算方法,124,两圆上对应数两两相乘后求和，得x3(0);将x2(n-m)移位一位，即外圆顺时针转动一位，重复（1）步骤，得x3(1)；依次下去，求得,DFT的性质：循环卷积计算方法,125,作图法(1)x1(m)和x2(m)在m轴上周期延拓，成为(2)将反转；(3)计算周期卷积(4)取一个周期，得到,DFT的性质：循环卷积计算方法,上述过程：只需将x1(n)和x2(n)分别做周期延拓，得到和，再按照计算周期卷积的作图法，计算出n由0到N-1的周期卷积，即为循环卷积。,127,DFT的性质：循环卷积计算方法,例:设x1(n)=1,2,2，x2(n)=1,2,3,4，计算4点循环卷积解：注意x1(n)为3点序列，进行循环卷积之前在其尾部填一个零，使其成为4点序列，分别在时域和频域中求解这个问题。,128,（1）时域方法4点循环卷积由下式给出对每个n产生一个循环移位序列，将它的样本逐个与x1(m)相乘，然后求和，得此n值的循环卷值，在0n3上重复此过程。考虑x1(m)=1,2,2,0和x2(m)=1,2,3,4。n=0时,DFT的性质：循环卷积计算方法,注意此为x2(0)，而不是4,3,2,1,129,n=2时，,DFT的性质：循环卷积计算方法,n=3时，,因此，,130,(2)频域方法：首先计算x1(n)和x2(n)的4点DFT，逐个样本相乘，取IDFT，得到循环卷积。,DFT的性质：循环卷积计算方法,则（注意：X1(k)和X2(k)对应位相乘）,IDFT后，得,表面看来，这样做反而更复杂，且涉及复数运算。但后面我们会看到，DFT有快速算法FFT，特别是当N很大时，效率会显著提高。,131,利用DFT求离散线性卷积条件：NN1+N2-1方法：时域转换到频域，处理后再转换回时域用DFT进行信号频谱分析参数选择频谱泄漏栅栏效应,DFT的应用,132,DFT的应用：线性卷积求解,133,线性卷积：,N点循环卷积：,DFT的应用：线性卷积求解,循环卷积和线性卷积的关系,134,讨论线性卷积y(n)=x(n)*h(n)的长度从x(m)看，非零值区为：0mN-1从h(n-m)看，非零值区为：0n-mM-1将二不等式相加，得到y(n)的非零区：0nM+N-2在此区间之外，不是x(m)=0，就是h(n-m)=0，即y(n)=0，因此，y(n)的长度为M+N-1,DFT的应用：线性卷积求解,135,讨论循环卷积的长度循环卷积是周期卷积的主值序列。为了研究长度不等的两个序列的周期卷积，构造周期序列，使它们的长度相等，且均为L。,表示为,DFT的应用：线性卷积求解,136,周期卷积如下：,周期卷积是线性卷积的周期延拓，周期为L。当周期为LN+M-1时，不会发生混迭，线性卷积正好是周期卷积的一个周期。循环卷积又是周期卷积的主值序列。,DFT的应用：线性卷积求解,因为，即0mL-1范围内x(m+qL)只有一个周期。,137,由于循环卷积是周期卷积的主值序列。因此，此时循环卷积与线性卷积完全相同。即：,因此，循环卷积等于线性卷积的条件是：即对于N长度的x(n)，M长度的h(n)，在它们后面补零，使其长度均变为LM+N-1。,DFT的应用：线性卷积求解,139,讨论,若序列的长度为，序列的长度为，且有大于，那么，和的点循环卷积结果为：,其中，,此时，两序列的线性卷积结果的长度，对其在时域作周期为的延拓相加得到序列,主值序列的前个点存在混迭。因此，在中也就是说，序列中最后个点与两序列的线性卷积结果相同。,答：（1）719点（2）27点,142,即时域循环卷积频域相乘,DFT的应用：线性卷积求解,设,若,则,用DFT求解线性卷积,143,如果循环卷积的长度N满足NN1+N2-1，则此循环卷积Y(k)就等于x(n)和h(n)的线性卷积。用流程图表示法求y(n)=x(n)*h(n)的过程如下：因为DFT、IDFT都有快速算法，因此，线性卷积可以实现快速算法。,DFT的应用：线性卷积求解,144,DFT的应用：线性卷积求解,乘法次数循环卷积：在上述DFT求解线性卷积过程中，需要3次DFT（FFT）运算，后面我们会讲到N点FFT所需要的乘法次数为，因此，用DFT求线性卷积所需要的总的乘法次数：,线性卷积：每一个输入值x(n)都必须和全部的h(n)值乘一次，因此，总共需要N1N2次乘法运算，ML=N1N2。,设,若N1=N2时，则,145,DFT的应用：线性卷积求解,结论：N1=N2越长，循环卷积的优越性越大。但当其中一个序列很长时，例如x(n)当很长时，即：,这时,Cm下降，循环卷积快速算法的优点不能发挥出来。,克服的办法：分段卷积将长序列分段，每一段分别与短序列进行循环卷积（即用FFT运算）分为重叠相加法，重叠保留法。,146,线性卷积求解小结时域直接求解,z变换法,DFT法,DFT的应用：线性卷积求解,147,上面介绍的是两个有限长序列x1(n)、x2(n)的线性卷积。但有时其中某个序列会很长或无限长，若等长序列存储或输入完后再做卷积运算，将产生问题：(1)存储量过大，运算量也太大；(2)等待输入的时间很长，引起不能忍受的延迟；(3)采用DFT/FFT快速算法的效率降低,具体方法：重叠保留法、重叠相加法,解决此问题的思路：把长序列分段，每一分段分别与短序列进行卷积分段卷积。,DFT的应用：分段卷积,148,误差分析在分析分段卷积之前，我们首先分析两个有限长度序列的循环卷积的误差情况。设x(n)为N1点序列，h(n)为N2点序列，由前面分析知道，线性卷积y(n)和循环卷积yC(n)关系为：,DFT的应用：分段卷积,一般地讲，循环卷积是线性卷积的一种混叠形式。但当NN1+N2-1，没有混迭产生，此时线性卷积y(n)和循环卷积yN(n)相等。,149,为了用DFT计算线性卷积，必须选择适当的N，但实际中却可能做不到这一点，尤其是当一个序列的长度很大而存储空间有限时。当选择比所需要的小的N值进行循环卷积时，会引入误差。下面我们计算此误差的大小。,DFT的应用：分段卷积,首先Nmax(N1,N2)，假设此时，循环卷积yc(n)的取值范围为而线性卷积y(n)的非零范围为,150,有上式可知，误差为：,DFT的应用：分段卷积,151,因为max(N1,N2)N（N1N21），上面的求和式中只剩下对应于r=1的项，其它的r值超出了max(N1,N2)N（N1N21）。因此，,一般来讲，如果x(n)和h(n)为因果序列，则y(n)也为因果序列，即：因此,DFT的应用：分段卷积,152,它说明当时，样本n处的误差与线性卷积中第n+N个样本相等。（N1+N21）个样本后，线性卷积结果为零。这说明循环卷积中的头M个样本存在误差，M等于线性卷积长度和循环卷积长度之差，而剩下的则为正确的线性卷积样本。,DFT的应用：分段卷积,0,循环卷积长度N,N1+N2-1-N,y(n),线性卷积长度N1+N2-1,循环卷积的错误样本,153,此结论在用分段处理法实现长卷积时是非常有用的。,DFT的应用：分段卷积,错误样本数=线性卷积长度循环卷积长度,154,例：设x1(n)和x2(n)是两个四点序列：x1(n)=1,2,2,1，x2(n)=1,-1,-1,1计算当N=6，5，4时的循环卷积，并在每种情况下，验证它们的误差。,DFT的应用：分段卷积,155,当N=5时，得到5点序列的循环卷