ch3-1-2离散傅里叶级数.ppt

1,第03章 离散傅里叶变换及其快速算法,伍凯宁 87544817-8263,华中科技大学电信系,2,内容提要,离散傅里叶变换 (Discrete Fourier Transform，DFT)是时间函数是离散的，而且频谱函数也是离散的变换。 讨论周期序列的傅里叶级数及其性质。 讨论有限长序列的离散傅里叶变换及其性质，其中包括循环卷积的重要概念。 利用循环卷积计算线性卷积。 讨论频率取样理论。 重点讨论FFT的时间抽选算法。 介绍变换点数为合数时的FFT算法。 介绍快速傅里叶变换算法的应用。,华中科技大学电信系,3,一.DFT是重要的变换 1.分析有限长序列的有用工具。 2.在信号处理的理论上有重要意义。 3.在运算方法上起核心作用，谱分析、 卷积、相关都可以通过DFT在计算机 上实现。,引言,华中科技大学电信系,4,二.傅氏变换的几种可能形式 (1).连续时间、连续频率的傅氏变换-FT,对于非周期的连续时间信号,华中科技大学电信系,5,对称性: 时域连续，则频域非周期。 反之亦然。,华中科技大学电信系,6,(2).连续时间、离散频率傅里叶变换-FS,对于周期为Tp的连续时间信号,华中科技大学电信系,7,*时域周期为Tp, 频域谱线间隔为2/Tp,华中科技大学电信系,8,(3).离散时间、连续频率的傅氏变换-DTFT,对于非周期的序列,抽样间隔T,华中科技大学电信系,9,共同的缺点：这三种变换总有一个域不是离散的，计算机不能直接计算；,希望的变换：不仅时间离散，频率也离散DFT。,华中科技大学电信系,10,华中科技大学电信系,11,3.1 离散傅里叶级数及其性质,3. 1. 1 离散傅里叶级数(DFS)定义（周期序列）,一个周期为N的周期序列,可表示为：,但是可以用离散傅里叶级数，即用复指数的加权和表示,用傅里叶级数表示，其基波频率为2p/N：,用复指数表示基波：,第k次谐波为：,所以，第k次谐波也是周期为N的序列。,不满足,，ZT不存在。,华中科技大学电信系,12,因此，对于离散傅里叶级数，只取下标从0到N-1的N个谐波分量就足以表示原来的信号。这样可把离散傅里叶级数表示为,式中，乘以系数1/N是为了下面计算的方便；,为k次谐波的系数。,将上式两边同乘以,并从n=0到N-1求和，得到：,华中科技大学电信系,13,由复指数序列的正交性：,所以，,得到周期序列的离散傅里叶级数表达式：,华中科技大学电信系,14,令,则得到周期序列的离散傅里叶级数(DFS)变换对,n和k均为离散变量。如果将n当作时间变量，k当作频率变量，则第一式表示的是时域到频域的变换，称为DFS的正变换。第二式表示的是频域到时域的变换，称为DFS的反变换。,由于,故 是周期为N的离散周期信号。,周期序列的信息可以用它在一个周期中的N个值来代表。,华中科技大学电信系,15,DFS总结:,和,2.,是离散和周期性的，且周期均为N；,5. DFS、IDFS具有唯一性.,3.离散周期序列既可用 ,也可用 表示；,1.周期性时间信号的频谱是离散的，离散时间信号的频谱是周期性的；周期性离散时间信号的频谱为周期性离散的；,4. n为离散时间变量，理解为nT；k是离散频率变量，理解为 kDw;,华中科技大学电信系,16,3.1.2 离散傅里叶级数的性质,1. 线性,设周期序列 和 的周期都为N，且,若,则有,2周期序列的移位,设,则,华中科技大学电信系,17,证明,证明：,* 和 都是以N为周期的周期函数。,华中科技大学电信系,18,3周期卷积,设,和,都是周期为N的周期序列，它们的,DFS系数分别为,令,则,上式表示的是两个周期序列的卷积，称为周期卷积。,两个周期为N的序列的卷积的离散傅里叶级数(DFS)等于它们各自DFS的乘积。,华中科技大学电信系,19,周期卷积的计算：,周期卷积中的序列 和 对m都是周期为N的周期序列，它们的乘积对m也是以N为周期的，周期卷积仅在一个周期内求和。,相乘和相加运算仅在m=0到N-1的区间内进行。计算出n=0到N-1(一个周期)的结果后，再将其进行周期延拓，就得到周期卷积 。详见周期卷积的过程。,周期卷积满足交换律,两个周期序列的乘积 的DFS为：,华中科技大学电信系,20,返回,华中科技大学电信系,21,周期卷积小结:,周期卷积的操作步骤与非周期序列的线性卷积相同，不同的是周期卷积仅在一个周期内求和； 周期卷积中,对m是周期性的，周期为N；,的周期为N；,周期卷积满足交换律。,华中科技大学电信系,22,3.2 离散傅里叶变换及其性质,3.2.1 离散傅里叶变换(DFT) 有限长序列的傅里叶变换称为离散傅里叶变换，简写为DFT。 DFT可以按3个步骤由 DFS推导出来： 将有限长序列延拓成周期序列； 求周期序列的DFS； 从DFS中取出一个周期便得到有限长序列的DFT。,将x(n)延拓成周期为N的周期序列 :,华中科技大学电信系,23,显然有,的第一个周期，即n=0到N-1的序列称为主值序列，n=0,到N-1的范围称为主值区间。,上述两式可分别表示为,其中RN(n)是矩形序列。符号(n)N表示n对模N的余数，即,这里k是商。,都表示周期序列,华中科技大学电信系,24,例如： (1) (2),华中科技大学电信系,25,同理，可以认为周期序列 的DFS系数 是有限长序列X(k)周期延拓的结果，而 X(k)是 的主值序列。即,华中科技大学电信系,26,由此便可以得出有限长序列的离散傅里叶变换(DFT)的表示式为:,由此可见，有限长序列x(n)的DFT即X(k)仍是有限长序列。,华中科技大学电信系,27,在一般情况下，X(k)是一个复量，可表示为,或,式中,例3. 1 求有限长序列,的DFT，其中a=0.8，N=8。,华中科技大学电信系,28,解：,因此得,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,华中科技大学电信系,29,例 已知,求X(k)的9点的IDFT.,解：,华中科技大学电信系,30,将x(n)的Z变换,与x(n)的DFT,进行对比，可以看出,式中，,表示z平面单位圆上辐角为,(k=0,1,N-1)的N个等间隔点。,Z变换在这些点上的取样值就是X(k)。,DFT与ZT的关系,华中科技大学电信系,31,DFT与DTFT的关系,有限长序列x(n)的DFT系数X(k)可看作其DTFT在一个周期(2p)内等间距取样的样本值，取样间隔为Dw=2p/N，即,DFT与DTFT的关系示意图,华中科技大学电信系,32,DTFT与ZT的关系,单位圆(z=ej)上的Z变换，即傅里叶变换X(ej)。,华中科技大学电信系,33,序列x(n)的DFT就是其ZT在单位圆上的等角距取样。,序列x(n)的DFT就是其DTFT在频率取样点的取值。,序列x(n)的DTFT就是其在单位圆上的ZT。,华中科技大学电信系,34,例 已知复序列 x(n)=xr(n)+jxi(n)，其中xr(n),xi(n)是实序列。序列x(n)的ZTX(z)的单位圆的下半部(pw2p)为0。求x(n)的DFTX(k)后一半的值，请说明理由。,解：,因为,华中科技大学电信系,35,例 已知序列,求其4点DFT，8点DFT，16点DFT？并画出,|X(k)|k的曲线图。,解：x(n)的FT为：,华中科技大学电信系,36,x(n)的4点DFT为：,1,华中科技大学电信系,37,x(n)的8点DFT为：,1,华中科技大学电信系,38,x(n)的16点DFT为：,1,华中科技大学电信系,39,4,8,12,16点：,8点：,4点：,华中科技大学电信系,40,华中科技大学电信系,41,对比：,离散时间信号的FT-DTFT： 时域离散，频域连续 离散的有限长信号的DFT： 时域离散，频域离散,华中科技大学电信系,42,离散傅里叶变换(DFT)总结,序列x(n)在时域是离散、有限长的(长度为N)，它的离散傅里叶变换X(k)也是离散、有限长的(长度也为N)。所以， x(n)和X(k)均可用计算机实现。 n为时域变量(nT)，k为频域变量(kDw)。 DFT与DFS没有本质区别，DFT实际上是DFS的主值，DFT也隐含有周期性。 离散傅里叶变换(DFT)具有唯一性。 DFT的物理意义：序列x(n)的Z变换在单位圆上的等角距取样。,华中科技大学电信系,43,N/2点的DFT:,N/4点的DFT:,华中科技大学电信系,44,旋转因子 的性质,对称性：,周期性：,换底：,k/2,N/2为整数,几个特殊值：,华中科技大学电信系,45,例. 令X(k)表示N点序列x(n)的N点DFT，X(k)本身也是一个N点序列，如果计算X(k)的DFT得到一个序列x1(n)，试用x(n)求x1(n)。,解：,华中科技大学电信系,46,华中科技大学电信系,47,3.2.2 离散傅里叶变换的性质,DFT隐含着周期性，因此在讨论DFT的性质时，常与DFS的概念联系起来，并把有限长序列看作周期序列的一个周期来处理。 设x1(n)和x2(n)的长度都为N，且它们对应的DFT分别为X1(k)和X2(k)。,1线性,设x3(n)=ax1(n)+bx2(n)，a和b都为常数，则,若它们长度不等，取长度最大者，将短的序列通过补零加长。 此性质可以直接由DFT的定义进行证明。,华中科技大学电信系,48,对于长为N的复序列x(n)，,证明：,（1）因为X(k)隐含周期性，所以,（2）对于实序列，,2对称性,华中科技大学电信系,49,这意味着,或,实序列的DFT系数X(k)的模是偶对称序列，辐角是奇对称序列,对于实序列的DFT，可以只计算一半：,华中科技大学电信系,50,3序列的循环移位,一个长度为N的序列x(n)的循环移位定义为,循环移位分3步计算：,(1)将x(n)延拓成周期为N的周期序列 ； (2)将 移位得 或x(n+m)N； (3)对x(n+m)N取主值得x(n+m)NRN(n)。 这个过程如下图所示。,华中科技大学电信系,51,从图中两虚线之间的主值序列的移位情况可以看出，当主值序列左移m个样本时，从右边会同时移进m个样本，而且好像是刚向左边移出的那些样本又从右边循环移了进来。因此取名“循环移位”。 显然，循环移位不同于线性移位。,华中科技大学电信系,52,将序列右移：,华中科技大学电信系,53,序列循环移位后的DFT为,证明：由周期序列的移位性质得,x(n+m)NRN(n)是 的主值序列,的DFS的主值，即,根据时域和频域的对偶关系，可以得出,若,则,它的DFT就是,华中科技大学电信系,54,例.已知,求出该信号的DFT ， X(k)=DFTx(n)，变换区间长度为8。,（提示：注意x(n)的区间不符合DFT要求的区间）,解:,其中,华中科技大学电信系,55,华中科技大学电信系,56,几种变换的时移性质汇总：,华中科技大学电信系,57,4循环卷积,设Y(k)=Xl(k)X2(k)，则,或,由上式表示的卷积称为循环卷积，常记为,(式3.36),华中科技大学电信系,58,证明：,利用DFT的隐含周期性，将Y(k)周期延拓计算后再取主值. m取值的0N-1范围是主值区间，故 因此,华中科技大学电信系,59,循环卷积的计算是对序列按循环移位后求对应项的乘积之和，实际上就是周期卷积取主值。,华中科技大学电信系,60,循环卷积的计算过程： x1(n)的N个值按顺时针方向均匀分布在内圆周上，x2(n)的N个值按反时针方向均匀分布在外圆周上，把内外圆周上对应的数值两两相乘，然后把乘积相加就得到y(0)。若将外圆周顺时针方向转动一格(如图3.6(b)所示)，将内外圆周上对应的数值两两相乘并把乘积相加，便得到y(1)。依次类推，可以得出y(n)的其它值。 循环卷积也叫做圆卷积或圆周卷积。,下图表示的是序列x1(n)和x2(n)的4点(即N=4)循环卷积的计算过程。图中，x1(n)=(n)+(n-1)+(n-2)，x2(n)=(n)+1.5(n-1)+2(n-2)+2.5(n-3)。,华中科技大学电信系,61,华中科技大学电信系,62,考虑到DFT关系的对偶性，可以证明，长为N的两序列之积的DFT等于它们的DFT的循环卷积除以N，即,这一计算过程分4步: （相当于求周期卷积的主值） (1)周期延拓和折叠 (2)移位和取主值 (3)相乘 (4)相加 注意：若x1(n)和x2(n)的长度不一致，可以根据需要添零延拓。,华中科技大学电信系,63,华中科技大学电信系,64,循环卷积小结: 循环卷积的过程与周期卷