《离散傅里叶变换》PPT课件.ppt

1,离散傅里叶变换,Discrete Fourier Transform,2,内容提要,离散傅里叶变换 (Discrete Fourier Transform，DFT)是时间函数是离散的，而且频谱函数也是离散的变换。 离散傅里叶变换定义 DFT物理意义 DFT基本性质 讨论频率取样理论。 DFT的应用,3,傅里叶变换的各种形式,连续时间、离散频率的傅里叶变换 对于周期为T的连续时间信号，可以采用傅里叶级数展开： 连续时间、连续频率的傅里叶变换 对于非周期的连续时间信号，可以进行傅里叶变换：,它在时域和频域都是连续的。,4,离散时间、连续频率的傅里叶变换 对于非周期的序列，其傅里叶变换在频域是以2为周期的连续函数。,5,3.1 离散傅里叶变换(DFT) 设x(n)是一个长度为M的有限长序列， 则定义x(n)的N点离散傅里叶变换为,X(k)的离散傅里叶逆变换为,式中， ， N称为DFT变换区间长度, NM， 通常称(3.1.1)式和(3.1.2)式为离散傅里叶变换对。 Note:有限长序列x(n)的DFT即X(k)仍是有限长序列。,6,例 3.1.1 x(n)=R4(n) ，求x(n)的8点和16点DFT. 解： 设变换区间N=8， 则,7,对长度为M的序列x(n)，其Z变换,N点DFT,进行对比，可以看出,式中，,表示z平面单位圆上辐角,(k=0,1,N-1)的N个等间隔点。,3.1.2 DFT与FT、Z变换的关系,8,说明：序列x(n)的N点DFT是其Z变换在单位圆上的N点等角距取样，如图3.4(a)。序列x(n)的DFT是其FT在区间0,2上的N点等间隔取样。如图3.4(b)。,9,3.2.3 DFT的隐含周期性,DFT变换对中,均为整数,所以式(3.1.1) 中， X(k)满足,同理可证明式(3.1.2) 中 x(n+mN)=x(n),10,任何周期为N的周期序列 都可以看做长度为N的有限长序列x(n)的周期延拓序列，而x(n)是 的一个周期,(3.1.5),(3.1.6),11,定义：,为叙述方便，将式(3.1.5)该写成,表示x(n)以N为周期的周期延拓序列，符号(n)N表示n对模N的余数，即,这里k是商。,的主值区间：周期序列 中从n=0到N-1的范围,的主值序列：主值区间上的序列,12,由此对长度为N的序列x(n)，且 ，则 的DFS为,结论：与DFT定义比较，可见有限长序列x(n)的DFT即X(k)是x(n)的周期延拓序列 的离散傅里叶级数系数 的主值序列。,例如，N=7, =x(n)7，则有,13,解：,因此得,X(0)=4.16114 X(1)=0.71063-j0.92558 X(2)=0.50746-j0.40597 X(3)=0.47017-j0.16987,X(4)=0.46235 X(5)= 0.47017+j0.16987 X(6)= 0.50746+j0.40597 X(7)= 0.71063+j0.92558,Matlab实现 fft1.m,例3. 1 求有限长序列,的DFT，其中a=0.8，N=8。,14,关于离散傅里叶变换(DFT)：,序列x(n)在时域是有限长的(长度为N)，它的离散傅里叶变换X(k)也是离散、有限长的(长度也为N)。 n为时域变量，k为频域变量。 DFT的物理意义：序列x(n)的Z变换在单位圆上的等角距取样。序列傅里叶变换在区间0,2上的等间隔取样。 离散傅里叶变换(DFT)具有唯一性。 离散傅里叶变换与离散傅里叶级数没有本质区别，DFT实际上是离散傅里叶级数的主值，DFT也隐含有周期性。,15,DFT隐含着周期性，因此在讨论DFT的性质时，常与DFS的概念联系起来，并把有限长序列看作周期序列的一个周期来处理。 设x1(n)和x2(n)的长度都为N，且它们对应的DFT分别为X1(k)和X2(k)。,1线性,设x3(n)=ax1(n)+bx2(n)，a和b都为常数，则,若它们长度不等，取长度最大者，将短的序列通过补零加长，注意此时DFT与未补零的DFT不相等。,3.2 离散傅里叶变换的性质,16,2循环移位性质,一个长度为N的序列x(n)的循环移位定义为,循环移位分3步计算：,(1)将x(n)延拓成周期为N的周期序列 ； (2)将 移位得 或 x(n+m)N； (3)对 x(n+m)N 取主值得 x(n+m)NRN(n)。 这个过程如下图所示。,a) 序列的循环移位：,17,从图中两虚线之间的主值序列的移位情况可以看出，当主值序列左移m个样本时，从右边会同时移进m个样本，而且好像是刚向左边移出的那些样本又从右边循环移了进来。因此取名“循环移位”。 显然，循环移位不同于线性移位,18,19,20,对长度为N的有限长序列x(n)，其循环移位后序列y(n)的DFT为,证明：,b) 时域循环移位定理,令n+m=n，则有：,因为 以N为周期，上式中的求和区间任取一个周期即可，取主值区间为求和区间，得证。,21,若,则,c) 频域循环移位定理,22,3.2.3 循环卷积定理,长度分别为N1和N2的有限长序列x1(n)和x2(n)的N点DFT分别为： （ N=max N1, N2 ）。,则,由上式表示的卷积称为循环卷积,X1(k)=DFTx1(n) X2(k)=DFTx2(n),如果,X(k)=X1(k)X2(k),23,循环卷积的过程：,(1)周期延拓 x2(m)x2(m)N (2)折叠 x2(m)Nx2(-m)N (3) 移位和取主值 x2(-m)Nx2(n-m)NRN(m) (4)相乘 x2(n-m)NRN(m) x1(m) x2(n-m)NRN(m) (5)相加 summ0,1,N-1,循环反转序列,Note: 两个长度为N的序列的循环卷积长度仍为N，（与线性卷积不同），记为：,24,25,26,循环卷积计算说明：x1(n)的N个值按顺时针方向均匀分布在内圆周上，x2(n)的N个值按反时针方向均匀分布在外圆周上，把内外圆周上对应的数值两两相乘，然后把乘积相加就得到y(0)。若将外圆周顺时针方向转动一格，将内外圆周上对应的数值两两相乘并把乘积相加，便得到y(1)。依次类推，可以得出y(n)的其它值。因此循环卷积也叫做圆卷积。,考虑到DFT关系的对偶性，可以证明，长为N的两序列之积的DFT等于它们的DFT的循环卷积除以N，即,频域循环卷积定理,27,28,3.2.4 复共轭序列的DFT,是长度为N的序列x(n)的复共轭序列，,则,且,类似,Note：对实序列有,29,3.2.5 DFT的共轭对称性,1. 有限长共轭对称序列和共轭反对称序列,分别用xep(n)和xop(n) 表示有限长共轭对称序列和共轭反对称序列， 则二者满足如下定义式： xep(n)=x*ep(N-n), 0nN-1 (3.2.9) xop(n)=-x*op(N-n), 0nN-1 (3.2.10),当N为偶数时， 将上式中的n换成N/2-n可得到,30,图 3.2.3 共轭对称与共轭反对称序列示意图,（图中*表示对应点为序列取共轭后的值）,31,如同任何实函数都可以分解成偶对称分量和奇对称分量一样， 任何有限长序列x(n)都可以表示成其共轭对称分量和共轭反对称分量之和， 即 x(n)=xep(n)+xop(n), 0nN-1 (3.2.11) 将上式中的n换成N-n， 并取复共轭， 再将式(3.2.9) 和式(3.2.10) 代入得到 x*(N-n)=x*ep(N-n)+x*op(N-n)=xep(n)-xop(n) (3.2.12) xep(n)=1/2x(n)+x*(N-n) (3.2.13) xop(n)=1/2x(n)-x*(N-n) (3.2.14),32,2. DFT的共轭对称性,(a) 若将序列x(n)分成实部xr(n)与虚部xi(n)，即 x(n)=xr(n)+jxi(n) 根据复共轭序列的DFT可得,再由DFT的线性性质可得,33,(b) 若将序列x(n)分成共轭对称部分xep(n)与共轭反对称部分xop(n)，即 x(n)=xep(n)+xop(n) 根据复共轭序列的DFT可得,因此,34,结论： 如果序列x(n)的DFT为X(k),则 x(n)的实部和虚部（包括j）的DFT分别为X(k)的共轭对称分量和共轭反对称分量； x(n)的共轭对称部分和共轭反对称部分的DFT分别为X(k)的实部和虚部乘以j.,35,有限长实序列DFT的共轭对称性： 对长度为N的实序列，X(k)=DFTx(n)，则 X(k)共轭对称，即 若x(n)=x(N-n),则X(k)实偶对称，即 若x(n)=-x(N-n)，则X(k)纯虚奇对称，即,36,这意味着，对于时间有限信号，可以像频带有限信号进行时域采样而不丢失任何信息一样，可以在频域上进行采 样而不丢失任何信息。这正是傅里叶变换中时域和频域对偶关系的反映，这有着十分重要的意 义。DFT实现了频域离散化，开辟了在频域采用数字技术处理的新领域。 这使我们自然想到，对于任意一个频率特性，是否均能用频域采样的办法来逼近，这是一个很吸引人的问题，因为用频率采样来逼近，可使问题大大简化。因此我们要讨论频率采样的可行性以及所带来的误差。,3. 3 频率域采样,37,频率取样是指对序列的傅里叶变换或系统的频率特性进行取样 。,本节讨论在什么条件下能够用得到的频谱取样值无失真地恢复原信号或系统。,设任意长序列x(n)绝对可和，其Z变换表示为,如果在单位圆上对X(z)进行等角距取样，取样点数为N，则得,根据DFT的定义，对X(k)求反变换,38,根据上面两式可得：,因为,所以,上式表明，在z平面的单位圆上对序列的Z变换进行等角距取样，将导致时间序列的周期延拓。这一结果与对连续时间信号取样导致频谱周期延拓类似。,现在我们来考察xp(n)与原序列x(n)的关系，看它如何才能代表原序列x(n)。,39,xp(n)是原非周期信号x(n)的周期延拓序列，因此xp(n)是一个周期序列，其主值为,在x(n)为有限长度M的情况下，如果取样点NM，那么x(n)周期延拓的结果不会产生混叠。这时，xp(n)的主值xN(n)与原序列x(n)一样，因此xN(n)完全能代表原序列x(n)，可由频域采样X(k)恢复x(n)。 如果NM，即延拓的周期N小余有限序列的长度M，则x(n)周期延拓后一定产生混叠，因而xN(n)不能无失真地代表原信号x(n)。在x(n)为无限长的情况下，对Z变换取样必然导致混叠失真，因此xN(n)不能代表原序列x(n)。,40,因此，对于长度为M的有限长序列，对Z变换取样即频率取样不失真的条件，是取样点数 N应等于或大于原序列的长度M，即NM。在NM时，Z变换的取样即DFT X(k)，利用IDFT公式可由X(k)恢复原序列x(n)，即,这就是频域采样定理。,41,对于有限长序列x(n)，满足频域采样定理时，N点频域采样X(k)就足以不失真地代表序列的特性。因此，由此N个采样值X(k)应能完全地表达整个X(z)函数及频率特性X(ej)。即由N点X(k)可内插恢复出X(z)或X(ej)。,式中,所以,设序列x(n)长度为M，在频域02之间等间隔采样N点，N=M，则有,42,令,则,上式就是用X(z)在单位圆上的N个取样值X(k)表示X(z)的内插公式，内插函数为 。,因为,所以,43,如果 则可以得到傅里叶变换的内插公式， 结论： 长度为N的序列x(n)，其N个频域取样值X(k)可以不失真地代表它，X(k)还能完整的表示序列的Z变换X(z)和傅里叶变换 。,44,3. 4 DFT应用举例,1. 线性卷积,实际应用中一般以线性卷积和相关运算处理为依据，如一个FIR数字滤波器的输出等于输入与滤波器的单位取样响应的线性卷积。DFT计算循环卷积,DFT的快速算法FFT的出现， 使DFT在数字通信、 语言信号处理、 图像处理、 功率谱估计、 仿真、 系统分析、 雷达理论、 光学、 医学、 地震以及数值分析等各个领域都得到广泛应用。,2. 谱分析,45,线性卷积 线性卷积不受主值区间限制 循环卷积 在一定条件下与线性卷积相等。 两个长度都为N的因果序列的循环卷积仍是一个长度为N的序列，而它们的线性卷积却是一个长度为2N-1的序列。,3. 4.1 利用循环卷积计算线性卷积,46,如果能将线性卷积转化成循环卷积，那么根据DFT的循环卷积性质，就能够用循环卷积来计算线性卷积，而循环卷积可以用FFT 进行快速计算。因此，首先需要讨论在什么条件下，循环卷积与线性 卷积相等的问题。,设h(n)和x(n)分别是长度为N和M的有限长序列，它们的线性卷积和循环卷积分别为,其中，L=maxN,M,47,所以,对照线性卷积的公式，可以看出,因 为,48,yc(n)是yl(n)以L为周期的周期延拓序列的主值序列。而yl(n)是个长度为N+M-1的序列，所以,(1)如果LN+M-1，则yl(n)周期延拓必有一部分非零值序列相重叠，从而产生混叠失真，这时L点的循环卷积不等于线性卷积。 (2)如果LN+M-1，则yl(n)的周期延拓不会产生混叠失真，这时,由此得出结论：两个长度为分别为N和M的序列的线性卷积可用长度为L的循环卷积来代替，但L必须满足条件 L M+N-1 。这时N/M到L之间的值用零填充。,即,49,图 3.4.2 线性卷积与循环卷积,50,图 3.4.3 用DFT计算线性卷积框图,51,两个序列的长度相差很大时的处理 （如滤波器长度有限，而输入序列长度不定或无限长） 问题：对短序列补很多0，存贮容量大，运算时间长，实时处理困难 解决途径：长序列分段处理 重叠相加法：由分段卷积的各段相加构成总的卷积输出 重叠保留法：由重叠分段卷积的各段组合构成总的卷积输出,52,重叠相加法,将无限长序列x(n)均匀分成长度的M的段，则第k段序列,于是输出可分解为,x(n)可表示为xk(n)之和，即,对h(n)和xk(n)都增添零取样值，使它们的长度都为L=N+M-1。计算h(n)与xk(n)的L点循环卷积，得到,53,重叠相加法用FFT处理的步骤归纳如下 对h(n)，xk(n)补零长度L。（L=2P=N+M-1） 计算L点DFTh(n), DFTxk(n) 计算 Yk(n)=Xk(n)H(K) 用L点IFFT求yk(n)=IDFTYk(k) 将yk(n)的重叠部分相加，最后输出为,由于yk(n)的长度为N+M-1，而xk(n)长度为M，所以相邻两段yk(n)序列必然有N-1个点发生重叠，如图3.4.4所示。这些重叠部分应该相加起来才能构成最后的输出序列，这就是“重叠相加法”这一名称的由来。,54,图 3.4.4 重叠相加法卷积示意图,55,3. 4.2 用DFT对信号进行谱分析,所谓信号的谱分析就是计算信号的频谱，包括振幅谱、相位谱和功率谱。 处理对象：连续信号和离散信号,1 用DFT对连续信号进行谱分析（近似分析）,设连续信号xa(t)（经预滤波和截取处理的有限长带限信号）持续时间为Tp， 最高频率为fc， 如图3.4.5所示。 xa(t)的傅里叶变换为,56,对xa(t)以采样间隔T1/2fc(即fs=1/T2fc)采样得x(n)= xa(nT)。 x(n)的傅里叶变换为X(ej).,X(ej)与 的关系为,(3.4.6),X(n)的长度为,将 代入,57,X(n)的N点DFT,代入式（3.4.6），可得,所以，令,58,可得,F表示对模拟信号的频谱的采样间隔，称为频率分辨率，即频域取样中两相邻点间的频率间隔。 说明：由上式可得，对连续信号采样并进行DFT再乘以T，就可近似得到模拟信号频谱的周期延拓函数在第一个周期0,Fs上的N点等间隔采样。如图3.4.5.,59,60,结论： 对满足假设的持续时间有限的带限信号，在满足时域采样定理时， 包含了模拟信号频谱的全部信号，可由X(k）恢复 。 缺点： 栅栏效应 对持续时间有限的带限信号,61,截断效应用DFT分析理想低通滤波器单位冲激响应的频率响应特性,截取理想低通滤波器的单位冲激响应的一段Tp：,假设Tp=8 s， 采样间隔T=0.25 s(即采样速度fs=4 Hz)， 采样点数N=Tp/T=32。 此时频域采样间隔F=1/NT=0.125 Hz。 则,Ha(kF)=TDFTh(n), 0k16,其中 h(n)=ha(nT)R32(n),注意：对实信号，其频谱函数具有共轭对称性，只需分析正频率频谱,62,图 3.4.7 用DFT计算理想低通滤波器频响曲线,63,从上图(c)可看出： 低频部分近似理想低通频响特性； 高频误差较大 截断效应 整个频响都有波动,减少截断效应的途径： 加长信号分析时间Tp，增加采样点数 先用窗函数处理,64,连续信号谱分析的参数选择原则： 关心的问题：谱分析范围0,Fs/2和频率分辨率F 为避免频谱混叠现象，Fs 2fc 谱分辨率F=Fs/N, 若N不变，要提高频谱分辨率，必须降低Fs 若Fs不变，为提高频谱分辨率，可增加采样点数N，即增加观察时间Tp。,选取原则：,65,例3.4.2 对实信号进行谱分析， 要求谱分辨率F10 Hz，信号最高频率fc=2.5 kHz， 试确定最小记录时间Tpmin， 最大的采样间隔Tmax， 最少的采样点数Nmin。 如果fc不变， 要求谱分辨率增加一倍， 最少的采样点数和最小的记录时间是多少? 解： 因此Tpmin=0.1 s， 因为要求fs2fc， 所以,66,为使频率分辨率提高一倍， F=5 Hz， 要求,67,2 用DFT对序列进行谱分析,单位圆上的Z变换序列的傅里叶变换 序列的DFT：0,2上对傅里叶变换的N点等间隔采样。 频谱分辨率： 2/N可用DFT计算序列的FT,周期为N的周期序列 的频谱函数：,其中,Note: 周期序列的频谱结构可用其离散傅里叶级数系数表示,68,由DFT的隐含周期性， 截取 的主值序列 并进行N点DFT得到,因此可用X(k)表示 的频谱结构。,如果截取长度M等于 的整数个周期， 即M=mN， m为正整数， 则,69,令 n=n+i N, i=0, 1, , m-1, n=0, 1, , N-1,则,因为,k/m=整数,k/m整数,70,k/m=整数,k/m整数,结论： k=im时，表示周期序列的第i次谐波谱线，幅度扩大m倍，故截取周期序列的整数个周期进行DFT可得到其频谱结构。,周期序列的周期不知道时的处理：,截取M点做DFT,截取长度扩大1倍做DFT,分析主谱频率差别,71,在实际应用中，有时只对信号的某一频段感兴趣，或只需计算单位圆上某一段的频谱值。例如，在对窄带信号进行分析时，常希望在窄频带内对频率的取样很密集，以便提高频率分辨率，而在窄频带外不予以考虑。,对于这种情况，如果采用DFT方法，则需要在窄频带内外都增加频域取样点，而窄频带外的计算量是浪费的。此外，有时对非单位圆上的取样感兴趣，例如在语音信号处理中，常常需要知道其Z变换的极点所在处的复频率，这时就需要在这些极点附近的曲线上进行频域取样，这样，就要沿着螺旋线对Z变换取样。这种沿螺旋线上取样点计算的Z变换，称为线性调频Z变换(Chirp Z Transform，简称CZT)。,72,图 3.4.7 单位圆与非单位圆采样,73,要计算序列在半径为r的圆上的频谱， 那么N个等间隔采样点为 , k=0, 1, 2, , N-1， zk点的频谱分量为,令,若要计算有限角度2/M内的N点等间隔频谱采样，可取L=MN，作N点DFT，只取分析角度内的N点等间隔采样。对曲线，分别计算很多弧线上的采样，运算量大，效率低。,74,3 Chirp-Z变换,一个长度为N的序列x(n)，其Z变换为,为了使z可以沿着z平面更一般的路径(不只是单位圆)取值，可以沿一段螺旋线对z作等分角取样，这些取样点上的zk表示为,其中M为所要分析的复频谱的点数，不一定等于N。W和A为任意复数，极坐标下可表示为,得到,A0，W0正实数,75,取样点zk所在的路径如图所示,(1)A0表示起始取样点z0的矢量长度，通常A01，否则将处于单位圆|z|=1之外。 (2)0表示起始取样点z0的矢量的相角，它可以是正值或负值。 (3)0表示两相邻取样点矢量之间的角度差。0