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

《ch3-1-2离散傅里叶级数.ppt》由会员分享，可在线阅读，更多相关《ch3-1-2离散傅里叶级数.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第03章章 离散傅里叶变换及离散傅里叶变换及其快速算法其快速算法伍凯宁伍凯宁 87544817-82631内容提要内容提要离散傅里叶变换离散傅里叶变换(Discrete Fourier Transform，DFT)是时间函数是离散的，而且频谱函数也是离散的是时间函数是离散的，而且频谱函数也是离散的变换。变换。讨论讨论周期序列周期序列的傅里叶级数及其性质。的傅里叶级数及其性质。讨论讨论有限长序列有限长序列的离散傅里叶变换及其性质，其中包的离散傅里叶变换及其性质，其中包括循环卷积的重要概念。括循环卷积的重要概念。利用循环卷积计算线性卷积。利用循环卷积计算线性卷积。讨论频率取样理论。讨论频率取样理

2、论。重点讨论重点讨论FFT的时间抽选算法。的时间抽选算法。介绍变换点数为合数时的介绍变换点数为合数时的FFT算法。算法。介绍快速傅里叶变换算法的应用。介绍快速傅里叶变换算法的应用。2华中科技大学电信系华中科技大学电信系一一.DFT是重要的变换是重要的变换 1.分析有限长序列的有用工具。分析有限长序列的有用工具。2.在信号处理的理论上有重要意义。在信号处理的理论上有重要意义。3.在运算方法上起核心作用，谱分析、在运算方法上起核心作用，谱分析、卷积、相关都可以通过卷积、相关都可以通过DFT在计算机在计算机 上实现。上实现。引言引言3华中科技大学电信系华中科技大学电信系二二.傅氏变换的几种可能形式傅

3、氏变换的几种可能形式(1).连续时间、连续频率的傅氏变换连续时间、连续频率的傅氏变换-FT对于非周期的连续时间信号对于非周期的连续时间信号4华中科技大学电信系华中科技大学电信系时域信号时域信号频域信号频域信号连续的连续的非周期的非周期的非周期的非周期的连续的连续的对称性对称性:时域连续，则频域非周期。时域连续，则频域非周期。反之亦然。反之亦然。5华中科技大学电信系华中科技大学电信系(2).连续时间、离散频率傅里叶变换连续时间、离散频率傅里叶变换-FS0t-0对于周期为对于周期为Tp的连续时间信号的连续时间信号6华中科技大学电信系华中科技大学电信系时域信号时域信号频域信号频域信号连续的连续的周期

4、的周期的非周期的非周期的离散的离散的7华中科技大学电信系华中科技大学电信系 (3).离散时间、连续频率的傅氏变换离散时间、连续频率的傅氏变换-DTFT 对于对于非周期的序列非周期的序列抽样间隔抽样间隔T8华中科技大学电信系华中科技大学电信系时域信号时域信号频域信号频域信号离散的离散的非周期的非周期的周期的周期的连续的连续的共同的缺点：这三种变换总有一个域不是离散的，共同的缺点：这三种变换总有一个域不是离散的，计算机不能直接计算；计算机不能直接计算；希望的变换：不仅时间离散，频率也离散希望的变换：不仅时间离散，频率也离散DFT。9华中科技大学电信系华中科技大学电信系10华中科技大学电信系华中科技

5、大学电信系3.1离散傅里叶级数及其性质离散傅里叶级数及其性质3.1.1离散傅里叶级数离散傅里叶级数(DFS)定义定义（周期序列）（周期序列）一个周期为一个周期为N的周期序列的周期序列可表示为：可表示为：但是可以用离散傅里叶级数，即用复指数的加权和但是可以用离散傅里叶级数，即用复指数的加权和表示表示用傅里叶级数表示，其基波频率为用傅里叶级数表示，其基波频率为2p p/N：用复指数表示基波：用复指数表示基波：第第k次谐波为：次谐波为：所以，第所以，第k次谐波也是周期为次谐波也是周期为N的序列。的序列。不满足不满足，ZT不存在。不存在。11华中科技大学电信系华中科技大学电信系因此，对于离散傅里叶级数

6、，只取下标从因此，对于离散傅里叶级数，只取下标从0到到N-1的的N个谐个谐波分量就足以表示原来的信号。这样可把离散傅里叶级数波分量就足以表示原来的信号。这样可把离散傅里叶级数表示为表示为式中，乘以系数式中，乘以系数1/N是为了下面计算的方便；是为了下面计算的方便；为为k次谐波的系数。次谐波的系数。将上式两边同乘以将上式两边同乘以并从并从n=0到到N-1求和，得到：求和，得到：12华中科技大学电信系华中科技大学电信系由复指数序列的正交性：由复指数序列的正交性：所以，所以，得到得到周期序列的离散傅里叶级数表达式：周期序列的离散傅里叶级数表达式：13华中科技大学电信系华中科技大学电信系令令则得到周期

7、序列的离散傅里叶级数则得到周期序列的离散傅里叶级数(DFS)变换对变换对n和和k均为离散变量。如果将均为离散变量。如果将n当作时间变量，当作时间变量，k当作频率当作频率变量，则第一式表示的是时域到频域的变换，称为变量，则第一式表示的是时域到频域的变换，称为DFS的正变换。第二式表示的是频域到时域的变换，称为的正变换。第二式表示的是频域到时域的变换，称为DFS的反变换。的反变换。由于由于故故是周期为是周期为N的离散周期信号。的离散周期信号。周期序列的信息可以用它在一个周期中的周期序列的信息可以用它在一个周期中的N个值来代表。个值来代表。14华中科技大学电信系华中科技大学电信系DFS总结总结:和和

8、2.是是离散和周期性的，且周期均为离散和周期性的，且周期均为N；5.DFS、IDFS具有唯一性具有唯一性.3.离散周期序列既可用离散周期序列既可用,也可用也可用表示；表示；1.周周期期性性时时间间信信号号的的频频谱谱是是离离散散的的，离离散散时时间间信信号号的的频频谱谱是周期性的；周期性离散时间信号的频谱为周期性离散的；是周期性的；周期性离散时间信号的频谱为周期性离散的；4.n为为离离散散时时间间变变量量，理理解解为为nT；k是是离离散散频频率率变变量量，理理解为解为kDwDw;15华中科技大学电信系华中科技大学电信系3.1.2离散傅里叶级数的性质离散傅里叶级数的性质1.线性线性设周期序列设周

9、期序列和和的周期都为的周期都为N，且且若若则有则有2周期序列的移位周期序列的移位设设则则16华中科技大学电信系华中科技大学电信系证明证明证明：证明：*和和 都是以都是以N为周期的周期函数。为周期的周期函数。,17华中科技大学电信系华中科技大学电信系3周期卷积周期卷积设设和和都是周期为都是周期为N的周期序列，它们的的周期序列，它们的DFS系数分别为系数分别为令令则则上式表示的是两个周期序列的卷积，称为上式表示的是两个周期序列的卷积，称为周期卷积周期卷积。两个周期为两个周期为N的序列的卷积的离散傅里叶级数的序列的卷积的离散傅里叶级数(DFS)等于等于它们各自它们各自DFS的乘积。的乘积。18华中科

10、技大学电信系华中科技大学电信系周期卷积的计算：周期卷积的计算：周期卷积中的序列周期卷积中的序列和和对对m都是都是周期为周期为N的周期序列，它们的乘积对的周期序列，它们的乘积对m也是以也是以N为周期的，为周期的，周期卷积周期卷积仅在一个周期内求和仅在一个周期内求和。相乘和相加运算仅在相乘和相加运算仅在m=0到到N-1的区间内进行。计算的区间内进行。计算出出n=0到到N-1(一个周期一个周期)的结果后，再将其进行周期延的结果后，再将其进行周期延拓，就得到周期卷积拓，就得到周期卷积。详见周期卷积的过程。详见周期卷积的过程。周期卷积满足交换律周期卷积满足交换律两个周期序列的乘积两个周期序列的乘积的的D

11、FS为：为：19华中科技大学电信系华中科技大学电信系返回返回20华中科技大学电信系华中科技大学电信系周期卷积小结周期卷积小结:周期卷积的操作步骤与非周期序列的线性卷积相同，周期卷积的操作步骤与非周期序列的线性卷积相同，不同的是周期卷积仅在一个周期内求和；不同的是周期卷积仅在一个周期内求和；周期卷积中周期卷积中对对m是周期性的，周期为是周期性的，周期为N；的周期为的周期为N；周期卷积满足交换律。周期卷积满足交换律。21华中科技大学电信系华中科技大学电信系3.2 离散傅里叶变换及其性质离散傅里叶变换及其性质3.2.1 离散傅里叶变换离散傅里叶变换(DFT)有限长序列有限长序列的傅里叶变换称为离散傅

12、的傅里叶变换称为离散傅里叶变换，简写为里叶变换，简写为DFT。DFT可以按可以按3个步骤由个步骤由 DFS推导出来：推导出来：将有限长序列延拓成周期序列；将有限长序列延拓成周期序列；求周期序列的求周期序列的DFS；从从DFS中取出一个周期便得到有限长中取出一个周期便得到有限长序列的序列的DFT。将将x(n)x(n)延延拓拓成成周周期期为为N的的周周期期序列序列 :22华中科技大学电信系华中科技大学电信系显然有显然有的第一个周期，即的第一个周期，即n=0到到N-1的序列称为主值序列，的序列称为主值序列，n=0到到N-1的范围称为主值区间。的范围称为主值区间。上述两式可分别表示为上述两式可分别表示

13、为 其中其中RN(n)是矩形序列。符号是矩形序列。符号(n)N表示表示n对模对模N的余数，即的余数，即这里这里k是商。是商。都表示周期序列都表示周期序列23华中科技大学电信系华中科技大学电信系例如：例如：(1)(2)24华中科技大学电信系华中科技大学电信系同理，可以认为周期序列同理，可以认为周期序列的的DFS系数系数是有限长序列是有限长序列X(k)周期延拓的结果，而周期延拓的结果，而X(k)是是的主值序列。即的主值序列。即25华中科技大学电信系华中科技大学电信系由此便可以得出有限长序列的离散傅里叶变换由此便可以得出有限长序列的离散傅里叶变换(DFT)的的表示式为表示式为:由此可见，有限长序列由

14、此可见，有限长序列x(n)的的DFT即即X(k)仍是有限长序列。仍是有限长序列。26华中科技大学电信系华中科技大学电信系在一般情况下，在一般情况下，X(k)是一个复量，可表示为是一个复量，可表示为或或式中式中例例3.1求有限长序列求有限长序列的的DFT，其中其中a=0.8，N=8。27华中科技大学电信系华中科技大学电信系解：解：因此得因此得X(0)=4.16114X(1)=0.71063-j0.92558X(2)=0.50746-j0.40597X(3)=0.47017-j0.16987X(4)=0.46235X(5)=0.47017+j0.16987X(6)=0.50746+j0.40597

15、X(7)=0.71063+j0.9255828华中科技大学电信系华中科技大学电信系例例已知已知求求X(k)的的9点的点的IDFT.解：解：29华中科技大学电信系华中科技大学电信系将将x(n)的的Z变换变换与与x(n)的的DFT进行对比，可以看出进行对比，可以看出式中，式中，表示表示z平面单位圆上辐角为平面单位圆上辐角为(k=0,1,N-1)的的N个等间隔点。个等间隔点。Z变换在这些点上的取样值就是变换在这些点上的取样值就是X(k)。DFT与与ZT的关系的关系30华中科技大学电信系华中科技大学电信系DFT与与DTFT的关系的关系有有限限长长序序列列x(n)的的DFT系系数数X(k)可可看看作作其

16、其DTFT在在一一个个周周期期(2p p)内内等等间间距距取取样样的的样样本本值值，取取样样间间隔隔为为DwDw=2p p/N，即，即DFT与与DTFT的关系示意图的关系示意图31华中科技大学电信系华中科技大学电信系DTFT与与ZT的关系的关系单位圆单位圆(z=ej)上的上的Z变换，即傅里叶变换变换，即傅里叶变换X(ej)。32华中科技大学电信系华中科技大学电信系序列序列x(n)的的DFT就是其就是其ZT在单位圆上的等角距取样。在单位圆上的等角距取样。序列序列x(n)的的DFT就是其就是其DTFT在频率取样点的取值。在频率取样点的取值。序列序列x(n)的的DTFT就是其在单位圆上的就是其在单位

17、圆上的ZT。33华中科技大学电信系华中科技大学电信系例例已已知知复复序序列列x(n)=xr(n)+jxi(n)，其其中中xr(n),xi(n)是是实实序序列列。序序列列x(n)的的ZTX(z)的的单单位位圆圆的的下下半半部部(pw2p2p)为为0。求求x(n)的的DFTX(k)后后一一半半的的值值，请请说说明理由。明理由。解：解：因为因为 34华中科技大学电信系华中科技大学电信系例例已知序列已知序列求其求其4点点DFT，8点点DFT，16点点DFT？并画出？并画出|X(k)|k的曲的曲线图线图。解：解：x(n)的的FT为：为：35华中科技大学电信系华中科技大学电信系x(n)的的4点点DFT为：

18、为：1 136华中科技大学电信系华中科技大学电信系x(n)的的8点点DFT为：为：1 137华中科技大学电信系华中科技大学电信系x(n)的的16点点DFT为：为：1 138华中科技大学电信系华中科技大学电信系481216点：点：8点：点：4点：点：39华中科技大学电信系华中科技大学电信系40华中科技大学电信系华中科技大学电信系对比：对比：离散时间信号的离散时间信号的FT-DTFT：时域离散，频域连续时域离散，频域连续离散的有限长信号的离散的有限长信号的DFT：时域离散，频域离散时域离散，频域离散41华中科技大学电信系华中科技大学电信系离散傅里叶变换离散傅里叶变换(DFT)总结总结序列序列x(n

19、)在时域是离散、有限长的在时域是离散、有限长的(长度为长度为N)，它它的离散傅里叶变换的离散傅里叶变换X(k)也是离散、有限长的也是离散、有限长的(长度长度也为也为N)。所以，所以，x(n)和和X(k)均可用计算机实现。均可用计算机实现。n为时域变量为时域变量(nT)，k为频域变量为频域变量(kDwDw)。DFT与与DFS没有本质区别，没有本质区别，DFT实际上是实际上是DFS的主的主值，值，DFT也隐含有周期性。也隐含有周期性。离散傅里叶变换离散傅里叶变换(DFT)具有唯一性。具有唯一性。DFT的物理意义：序列的物理意义：序列x(n)的的Z变换在单位圆上的变换在单位圆上的等角距取样。等角距取

20、样。42华中科技大学电信系华中科技大学电信系N/2点的点的DFT:N/4点的点的DFT:43华中科技大学电信系华中科技大学电信系旋转因子旋转因子 的性质的性质 对称性：对称性：周期性：周期性：换底：换底：,k/2,N/2为整为整数数 几个特殊值：几个特殊值：44华中科技大学电信系华中科技大学电信系例例.令令X(k)表示表示N点序列点序列x(n)的的N点点DFT，X(k)本身也本身也是一个是一个N点序列，如果计算点序列，如果计算X(k)的的DFT得到一个序列得到一个序列x1(n)，试用试用x(n)求求x1(n)。解：解：45华中科技大学电信系华中科技大学电信系46华中科技大学电信系华中科技大学电

21、信系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都为常数，则都为常数，则若它们长度不等，取长度最大者，将短的序列通过补零加长。若它们长度不等，取长度最大者，将短的序列通过补零加长。此性质可以直接由此

22、性质可以直接由DFT的定义进行证明。的定义进行证明。47华中科技大学电信系华中科技大学电信系对于长为对于长为N的的复序列复序列x(n)，证明：证明：（1）因为）因为X(k)隐含周期性，所以隐含周期性，所以（2）对于实序列，）对于实序列，2对称性对称性48华中科技大学电信系华中科技大学电信系这意味着这意味着或或实序列实序列的的DFT系数系数X(k)的的模是偶对称序列，辐角是奇对称序列模是偶对称序列，辐角是奇对称序列对于对于实序列实序列的的DFT，可以只计算一半：，可以只计算一半：49华中科技大学电信系华中科技大学电信系3序列的循环移位序列的循环移位一个长度为一个长度为N的序列的序列x(n)的循环

23、移位定义为的循环移位定义为循环移位分循环移位分3步计算：步计算：(1)将将x(n)延拓成周期为延拓成周期为N的周期序列的周期序列；(2)将将移位得移位得或或x(n+m)N；(3)对对x(n+m)N取主值得取主值得x(n+m)NRN(n)。这个过程如下图所示。这个过程如下图所示。50华中科技大学电信系华中科技大学电信系 从图中两虚线之从图中两虚线之间的主值序列的间的主值序列的移位情况可以看移位情况可以看出，当主值序列出，当主值序列左移左移m个样本时，个样本时，从右边会同时移从右边会同时移进进m个样本，而个样本，而且好像是刚向左且好像是刚向左边移出的那些样边移出的那些样本又从右边循环本又从右边循环

24、移了进来。因此移了进来。因此取名取名“循环移位循环移位”。显然，循环移位显然，循环移位不同于线性移位。不同于线性移位。51华中科技大学电信系华中科技大学电信系将将 序序 列列右移：右移：52华中科技大学电信系华中科技大学电信系序列循环移位后的序列循环移位后的DFT为为证明：由周期序列的移位性质得证明：由周期序列的移位性质得x(n+m)NRN(n)是是的主值序列的主值序列的的DFS的主值，即的主值，即根据时域和频域的对偶关系，可以得出根据时域和频域的对偶关系，可以得出若若则则它的它的DFT就是就是53华中科技大学电信系华中科技大学电信系例例.已知已知求出该信号的求出该信号的DFT ，X(k)=D

25、FTx(n)，变换区间长度为变换区间长度为8 8。（提示：注意（提示：注意x(n)的区间不符合的区间不符合DFT要求的区间）要求的区间）解解:,其中其中54华中科技大学电信系华中科技大学电信系55华中科技大学电信系华中科技大学电信系几种变换的时移性质汇总：几种变换的时移性质汇总：56华中科技大学电信系华中科技大学电信系4循环卷积循环卷积设设Y(k)=Xl(k)X2(k)，则则或或由上式表示的卷积称为由上式表示的卷积称为循环卷积循环卷积，常记为，常记为(式式3.36)3.36)57华中科技大学电信系华中科技大学电信系证明：证明：利用利用DFT的隐含周期性，将的隐含周期性，将Y(k)周期延拓计算后

26、再取周期延拓计算后再取主值主值.m取值的取值的0N-1范围是主值区间，故范围是主值区间，故因此因此58华中科技大学电信系华中科技大学电信系循环卷积的计算是对序列按循环移位后求对应循环卷积的计算是对序列按循环移位后求对应项的乘积之和，实际上就是项的乘积之和，实际上就是周期卷积取主值。周期卷积取主值。59华中科技大学电信系华中科技大学电信系循环卷积的计算过程：循环卷积的计算过程：x1(n)的的N个值按顺时针方向均匀分布在内圆周上，个值按顺时针方向均匀分布在内圆周上，x2(n)的的N个值按反时针方向均匀分布在外圆周上，把内个值按反时针方向均匀分布在外圆周上，把内外圆周上对应的数值两两相乘，然后把乘积

27、相加就得到外圆周上对应的数值两两相乘，然后把乘积相加就得到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

28、-1)+2(n-2)+2.5(n-3)。60华中科技大学电信系华中科技大学电信系61华中科技大学电信系华中科技大学电信系考虑到考虑到DFT关系的对偶性，可以证明，长为关系的对偶性，可以证明，长为N的两序列之积的的两序列之积的DFT等于它们的等于它们的DFT的循环卷积除以的循环卷积除以N，即即这一计算过程分这一计算过程分4步步:（相当于求周期卷积的主值）（相当于求周期卷积的主值）(1)周期延拓周期延拓和折叠和折叠(2)移位和移位和取主值取主值(3)相乘相乘(4)相加相加注意：若注意：若x1(n)和和x2(n)的长度不一致，可以根据需要添零延拓。的长度不一致，可以根据需要添零延拓。62华中科技大学

29、电信系华中科技大学电信系63华中科技大学电信系华中科技大学电信系循环卷积小结循环卷积小结:循环卷积的过程与周期卷积一样，只取周期卷积循环卷积的过程与周期卷积一样，只取周期卷积的主值；的主值；循环卷积隐含周期性；循环卷积隐含周期性；循环卷积在主值区间内进行，参与卷积的两个序循环卷积在主值区间内进行，参与卷积的两个序列的长度和结果序列的长度均相等；列的长度和结果序列的长度均相等；线性卷积与循环卷积计算步骤比较：线性卷积与循环卷积计算步骤比较：线性卷积：线性卷积：折叠折叠、平移、相乘、相加；、平移、相乘、相加；循环卷积：周期化、循环卷积：周期化、折叠折叠、平移、取主值、相乘、平移、取主值、相乘、相加

30、。相加。64华中科技大学电信系华中科技大学电信系线性卷积：线性卷积：不受主值区间限制不受主值区间限制,对序列长度无要求对序列长度无要求周期卷积：周期卷积：是线性卷积的周期延拓是线性卷积的周期延拓循环卷积：循环卷积：是周期卷积的主值是周期卷积的主值,要求两个序列长度相等。要求两个序列长度相等。例如：两个长度都为例如：两个长度都为N的因果序列的循环卷积仍是一个长度为的因果序列的循环卷积仍是一个长度为N的的序列，而它们的线性卷积却是一个长度为序列，而它们的线性卷积却是一个长度为2N-1的序列。的序列。3种卷积比较种卷积比较：65华中科技大学电信系华中科技大学电信系66华中科技大学电信系华中科技大学电信系