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

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

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

3、连续时间、连续频率的傅氏变换-FTdtetxjXtj)()(:正dejXtxtj)(21)(:反0t)(tx0)( jX对于非周期的连续时间信号对于非周期的连续时间信号时域信号时域信号频域信号频域信号连续的连续的非周期的非周期的非周期的非周期的连续的连续的对称性对称性: 时域连续，则频域非周期。时域连续，则频域非周期。 反之亦然。反之亦然。(2).连续时间、离散频率傅里叶变换连续时间、离散频率傅里叶变换-FS2/2/00)(1)(:ppTTtjkpdtetxTjkX正0tpT)(tx-ktjkejkXtx0)()(:0反0)(0jkXpT20对于周期为对于周期为Tp的连续时间信号的连续时间信号

4、时域信号时域信号频域信号频域信号连续的连续的周期的周期的非周期的非周期的离散的离散的*时域周期为时域周期为Tp, 频域谱线间隔为频域谱线间隔为2/Tp (3).离散时间、连续频率的傅氏变换离散时间、连续频率的傅氏变换-DTFT :()()jjnnXex n Te 正)(TjjeXeX或1:()()2jjnx nTX eed反对于非周期的序列对于非周期的序列0Ts2-抽样间隔抽样间隔Tx(nT)-T0T2Ttx(nT)T-T0T2Tt时域信号时域信号频域信号频域信号离散的离散的非周期的非周期的周期的周期的连续的连续的*,2T时域抽样间隔为频域的周期为共同的缺点：这三种变换总有一个域不是离散的，共

5、同的缺点：这三种变换总有一个域不是离散的，计算机不能直接计算；计算机不能直接计算； 希望的变换：不仅时间离散，频率也离散希望的变换：不仅时间离散，频率也离散DFT。 3.1 离散傅里叶级数及其性质离散傅里叶级数及其性质3. 1. 1 离散傅里叶级数离散傅里叶级数(DFS)定义周期序列）定义周期序列） 一个周期为一个周期为N的周期序列的周期序列可表示为：可表示为： 但是可以用离散傅里叶级数，即用复指数的加权和表示但是可以用离散傅里叶级数，即用复指数的加权和表示用傅里叶级数表示，其基波频率为用傅里叶级数表示，其基波频率为2p/N：用复指数表示基波：用复指数表示基波：第第k次谐波为：次谐波为：所以，

6、第所以，第k次谐波也是周期为次谐波也是周期为N的序列。的序列。21jnNee2jnkNkee22()jn k NjnkNNk Nkeeee( )nnx n r 不满足不满足，ZT不存在。不存在。因而，对于离散傅里叶级数，只取下标从因而，对于离散傅里叶级数，只取下标从0到到N-1的的N个谐个谐波分量就足以表示原来的信号。这样可把离散傅里叶级波分量就足以表示原来的信号。这样可把离散傅里叶级数表示为数表示为 式中，乘以系数式中，乘以系数1/N是为了下面计算的方便；是为了下面计算的方便； 为为k次谐波的系数。次谐波的系数。将上式两边同乘以将上式两边同乘以并从并从n=0到到N-1求和，得到：求和，得到：

7、由复指数序列的正交性：由复指数序列的正交性：所以，所以，得到周期序列的离散傅里叶级数表达式：得到周期序列的离散傅里叶级数表达式：2221()()0()101NNNNjk r njk r Nnjk rNkreekre 令令则得到周期序列的离散傅里叶级数则得到周期序列的离散傅里叶级数(DFS)变换对变换对n和和k均为离散变量。如果将均为离散变量。如果将n当作时间变量，当作时间变量，k当作频率当作频率变量，则第一式表示的是时域到频域的变换，称为变量，则第一式表示的是时域到频域的变换，称为DFS的正变换。第二式表示的是频域到时域的变换，称为的正变换。第二式表示的是频域到时域的变换，称为DFS的反变换。

8、的反变换。由于由于故故 是周期为是周期为N的离散周期信号。的离散周期信号。周期序列的信息可以用它在一个周期中的周期序列的信息可以用它在一个周期中的N个值来代表。个值来代表。DFS总结总结:( )X k( )x n%和和2.是离散和周期性的，且周期均为是离散和周期性的，且周期均为N； 5. DFS、IDFS具有唯一性具有唯一性. 3.离散周期序列既可用离散周期序列既可用 ,也可用也可用 表示；表示； ( )x n%( )X k1.周期性时间信号的频谱是离散的，离散时间信号的频谱周期性时间信号的频谱是离散的，离散时间信号的频谱是周期性的；周期性离散时间信号的频谱为周期性离散是周期性的；周期性离散时

9、间信号的频谱为周期性离散的；的； 4. n为离散时间变量，理解为为离散时间变量，理解为nT；k是离散频率变量，理是离散频率变量，理解为解为 kDw; 3.1.2 离散傅里叶级数的性质离散傅里叶级数的性质1. 线性线性设周期序列设周期序列 和和 的周期都为的周期都为N，且，且假设假设则有则有2周期序列的移位周期序列的移位 设设那么那么证明证明证明：证明：10 ()()NnkNnDFS x nmx nm W%* 和和 都是以都是以N为周期的周期函数。为周期的周期函数。( )x n%mkNW10()Nk n mmkNNnx nm WW%1( )NmktmkNNtmx t W W %10( )( )N

10、mknkmkNNNnWx n WWX k%( )X k, ,3周期卷积周期卷积设设和和都是周期为都是周期为N的周期序列，它们的的周期序列，它们的DFS系数分别为系数分别为令令那么那么上式表示的是两个周期序列的卷积，称为周期卷积。上式表示的是两个周期序列的卷积，称为周期卷积。两个周期为两个周期为N的序列的卷积的离散傅里叶级数的序列的卷积的离散傅里叶级数(DFS)等于等于它们各自它们各自DFS的乘积。的乘积。周期卷积的计算：周期卷积的计算：周期卷积中的序列周期卷积中的序列 和和 对对m都是都是周期为周期为N的周期序列，它们的乘积对的周期序列，它们的乘积对m也是以也是以N为周期的，为周期的，周期卷积

11、仅在一个周期内求和。周期卷积仅在一个周期内求和。 相乘和相加运算仅在相乘和相加运算仅在m=0到到N-1的区间内进行。计算的区间内进行。计算出出n=0到到N-1(一个周期一个周期)的结果后，再将其进行周期延的结果后，再将其进行周期延拓，就得到周期卷积拓，就得到周期卷积 。详见周期卷积的过程。详见周期卷积的过程。 周期卷积满足交换律周期卷积满足交换律两个周期序列的乘积两个周期序列的乘积 的的DFS为：为：返回返回133周期卷积小结周期卷积小结:)(),(21mnxmx)(ny周期卷积的操作步骤与非周期序列的线性卷积相同，周期卷积的操作步骤与非周期序列的线性卷积相同，不同的是周期卷积仅在一个周期内求

12、和；不同的是周期卷积仅在一个周期内求和；周期卷积中周期卷积中对对m是周期性的，周期为是周期性的，周期为N；的周期为的周期为N N；周期卷积满足交换律。周期卷积满足交换律。3.2 离散傅里叶变换及其性质离散傅里叶变换及其性质3.2.1 离散傅里叶变换离散傅里叶变换(DFT) 有限长序列的傅里叶变换称为离散傅有限长序列的傅里叶变换称为离散傅里叶变换，简写为里叶变换，简写为DFT。DFT可以按可以按3个步骤由个步骤由 DFS推导出来：推导出来：将有限长序列延拓成周期序列；将有限长序列延拓成周期序列；求周期序列的求周期序列的DFS；从从DFS中取出一个周期便得到有限长中取出一个周期便得到有限长序列的序

13、列的DFT。将将x(n)延拓成周期为延拓成周期为N的周的周期序列期序列 :显然有显然有的第一个周期，即的第一个周期，即n=0到到N-1的序列称为主值序列，的序列称为主值序列，n=0到到N-1的范围称为主值区间。的范围称为主值区间。上述两式可分别表示为上述两式可分别表示为 其中其中RN(n)是矩形序列。符号是矩形序列。符号(n)N表示表示n对模对模N的余数，即的余数，即 这里这里k是商。是商。 都表示周期序列都表示周期序列例如：例如：(1)(2)7252792259,2591nNnNn5455949,49NnNn同理，可以认为周期序列同理，可以认为周期序列 的的DFS系数系数 是有限长序列是有限

14、长序列X(k)周期延拓的结果，而周期延拓的结果，而 X(k)是是 的主值序列。即的主值序列。即 101010( )( )( )( )( )( )( )01( )0NknNnNknNNNnNknNnX kx n WX kRkx n WRnx n WkNX k%其他由此便可以得出有限长序列的离散傅里叶变换由此便可以得出有限长序列的离散傅里叶变换(DFT)的表的表示式为示式为:由此可见，有限长序列由此可见，有限长序列x(n)的的DFT即即X(k)仍是有限长序列。仍是有限长序列。在一般情况下，在一般情况下，X(k)是一个复量，可表示为是一个复量，可表示为或或式中式中例例3. 1 求有限长序列求有限长序

15、列的的DFT，其中，其中a=0.8，N=8。 解：解：因此得因此得 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.46235X(5)= 0.47017+j0.16987X(6)= 0.50746+j0.40597X(7)= 0.71063+j0.92558例例 知知50( )218kX kk求求X(k)的的9点的点的IDFT.88990011( )( )329912 ( )0,1,.,83knknkkx nX k WWnn89090,=01,.,8knknWn其中解：解

16、： 将将x(n)的的Z变换变换与与x(n)的的DFT进行对比，可以看出进行对比，可以看出式中，式中，表示表示z平面单位圆上辐角为平面单位圆上辐角为(k=0,1,N-1)的的N个等间隔点。个等间隔点。Z变换在这些点上的取样值就是变换在这些点上的取样值就是X(k)。DFT与与ZT的关系的关系2/2/( )()()jk Njk NX kX eX eDFT与与DTFT的关系的关系有限长序列有限长序列x(n)的的DFT系数系数X(k)可看作其可看作其DTFT在在一个周期一个周期(2p)内等间距取样的样本值，取样间隔内等间距取样的样本值，取样间隔为为Dw=2p/N，即，即DFT与与DTFT的关系示意图的关

17、系示意图210( )( )NjknNnX kx n e10()( )Njj nnX ex n eDTFT与与ZT的关系的关系单位圆单位圆(z=ej)上的上的Z变换，即傅里叶变换变换，即傅里叶变换X(ej)。()( )jjz eX eX z10()( )Njj nnX ex n e10( )( )NnnX zx n z2( )()jk NX kX e2( )( )( )kjkNNz Wz eX kX zX z()( )jjz eX eX z序列序列x(n)的的DFT就是其就是其ZT在单位圆上的等角距取样。在单位圆上的等角距取样。序列序列x(n)的的DFT就是其就是其DTFT在频率取样点的取值。在

18、频率取样点的取值。序列序列x(n)的的DTFT就是其在单位圆上的就是其在单位圆上的ZT。例例 已知复序列已知复序列 x(n)=xr(n)+jxi(n)，其中，其中xr(n),xi(n)是实序列。序列是实序列。序列x(n)的的ZTX(z)的单位圆的下半部的单位圆的下半部(pw2p)为为0。求。求x(n)的的DFTX(k)后一半的值，后一半的值，请说明理由。请说明理由。解：解： 1,.,12,2, 0)(NNNkkX2( )( )( )kjkNNz Wz eX kX zX z因为因为 例例 已知序列已知序列103( )0nx nothers求其求其4点点DFT，8点点DFT，16点点DFT？并画出

19、？并画出|X(k)|k的曲线图。的曲线图。 4322222221()( )1()sin(2 )()sin()2jjj njnjjjjjjjeX ex n eeeeeeeee解：解：x(n)的的FT为：为：x(n)的的4点点DFT为：为：3424sin()( )()sin()4jkjkkX kX eek1 1x(n)的的8点点DFT为：为：3828sin()2( )()sin()8jkjkkX kX eek1 1x(n)的的16点点DFT为：为：316216sin()4( )()sin()16jkjkkX kX eek1 1481216点：点：8点：点：4点：点：对比：对比：离散时间信号的离散时

20、间信号的FT-DTFT： 时域离散，频域连续时域离散，频域连续离散的有限长信号的离散的有限长信号的DFT： 时域离散，频域离散时域离散，频域离散离散傅里叶变换离散傅里叶变换(DFT)总结总结序列序列x(n)在时域是离散、有限长的在时域是离散、有限长的(长度为长度为N)，它，它的离散傅里叶变换的离散傅里叶变换X(k)也是离散、有限长的也是离散、有限长的(长度长度也为也为N)。所以，。所以， x(n)和和X(k)均可用计算机实现。均可用计算机实现。n为时域变量为时域变量(nT)，k为频域变量为频域变量(kDw)。DFT与与DFS没有本质区别，没有本质区别，DFT实际上是实际上是DFS的的主值，主值

21、，DFT也隐含有周期性。也隐含有周期性。离散傅里叶变换离散傅里叶变换(DFT)具有唯一性。具有唯一性。DFT的物理意义：序列的物理意义：序列x(n)的的Z变换在单位圆上的变换在单位圆上的等角距取样。等角距取样。N/2点的点的DFT: 1202( )( )0,1,2,.,12NknNnNX kx n Wk1404( )( )0,1,2,.,14NknNnNX kx n WkN/4点的点的DFT: 旋转因子旋转因子 的性质的性质 NjNeW2对称性：对称性： kNNkNWW)*(周期性：周期性： kNmNkNWW换底：换底： 22kmkkNmNNWWW,k/2,N/2,k/2,N/2为整为整数数

22、几个特殊值：几个特殊值： 1kNNW21NNW 4NNWj 34NNWj例例. 令令X(k)表示表示N点序列点序列x(n)的的N点点DFT，X(k)本身也本身也是一个是一个N点序列，如果计算点序列，如果计算X(k)的的DFT得到一个序列得到一个序列x1(n)，试用，试用x(n)求求x1(n)。解：解：111100 011 00( )( )( )( )NNNknknknNNNkknNNk n nNnkx nX k Wx n WWx nW 111 00( )( )NNk n nNnkx nx nW()( )( )NlNNNxnNl RnNxnRn 10,0Nk n nNkNnnNl lZW其他3.

23、2.2 离散傅里叶变换的性质离散傅里叶变换的性质 DFT隐含着周期性，因此在讨论隐含着周期性，因此在讨论DFT的性质时，常与的性质时，常与DFS的概的概念联系起来，并把有限长序列看作周期序列的一个周期来处理。念联系起来，并把有限长序列看作周期序列的一个周期来处理。设设x1(n)和和x2(n)的长度都为的长度都为N，且它们对应的，且它们对应的DFT分别为分别为X1(k)和和X2(k)。1线性线性 设设x3(n)=ax1(n)+bx2(n)，a和和b都为常数，那么都为常数，那么 若它们长度不等，取长度最大者，将短的序列通过补零加长。若它们长度不等，取长度最大者，将短的序列通过补零加长。 此性质可以

24、直接由此性质可以直接由DFT的定义进行证明。的定义进行证明。对于长为对于长为N的复序列的复序列x(n)，*( )()DFT x nXNk*10)(*)()(NnnkNNWnxkNX10)(*)(NnnkNNWnx10*)(NnknNWnx)(*nxDFT证明：证明：（1因为因为X(k)隐含周期性，所以隐含周期性，所以*()( )DFT xNnXk（2对于实序列，对于实序列，* ( )( )()DFT x nX kXNk2对称性对称性 这意味着这意味着或或( )0,.,2 1()( )X kkNX NkXk实序列的实序列的DFTDFT系数系数X(k)X(k)的模是偶对称序列，辐角是奇对称序列的模

25、是偶对称序列，辐角是奇对称序列*()( )XNkX k对于实序列的对于实序列的DFT，可以只计算一半：，可以只计算一半：3序列的循环移位序列的循环移位 一个长度为一个长度为N的序列的序列x(n)的循环移位定义为的循环移位定义为 循环移位分循环移位分3步计算：步计算：(1)将将x(n)延拓成周期为延拓成周期为N的周期序列的周期序列 ； (2)将将 移位得移位得 或或x(n+m)N；(3)对对x(n+m)N取主值得取主值得x(n+m)NRN(n)。这个过程如下图所示。这个过程如下图所示。 从图中两虚线之从图中两虚线之间的主值序列的间的主值序列的移位情况可以看移位情况可以看出，当主值序列出，当主值序

26、列左移左移m个样本时，个样本时，从右边会同时移从右边会同时移进进m个样本，而个样本，而且好像是刚向左且好像是刚向左边移出的那些样边移出的那些样本又从右边循环本又从右边循环移了进来。因此移了进来。因此取名取名“循环移循环移位位”。 显然，循环移位显然，循环移位不同于线性移位。不同于线性移位。 将 序 列将 序 列右移：右移：序列循环移位后的序列循环移位后的DFT为为 证明：由周期序列的移位性质得证明：由周期序列的移位性质得x(n+m)NRN(n)是是 的主值序列的主值序列的的DFS的主值，即的主值，即根据时域和频域的对偶关系，可以得出根据时域和频域的对偶关系，可以得出假设假设那那么么它的它的DF

27、T就是就是例例.知知othersnnx, 03| , 1)(求出该信号的求出该信号的DFT DFT ， X(k)=DFTx(n) X(k)=DFTx(n)，变换区间长度为，变换区间长度为8 8。（提示：注意（提示：注意x(n)x(n)的区间不符合的区间不符合DFTDFT要求的区间）要求的区间） 1( )(3)x nx n)(nx0n)(nx6 61othersnnx, 06 , 5 , 4 , 3 , 2 , 1 , 0, 1)(1解解: :, ,其中其中)()()3()(138881kXWnRnxDFTkXk1(3)( )x nx nkjkjnknnkneeWWnxkX44760870811

28、11)()(733443481441( )( )11jkjkj kjkkjkjkeeeX kWX keee几种变换的时移性质汇总：几种变换的时移性质汇总： 0)()(0tjFTejXttx0)()(0stLTesXttxmZTzzXmnx)()(kmNDFTWkXmnx)()(4循环卷积循环卷积 设设Y(k)=Xl(k)X2(k)，那么，那么或或由上式表示的卷积称为循环卷积，常记为由上式表示的卷积称为循环卷积，常记为)( )()(1021nRmnxmxNNm( (式式3.36)3.36)证明：证明： 利用利用DFT的隐含周期性，将的隐含周期性，将Y(k)周期延拓计算后再取周期延拓计算后再取主值

29、主值.m取值的取值的0N-1范围是主值区间，故范围是主值区间，故因而因而循环卷积的计算是对序列按循环移位后求对应循环卷积的计算是对序列按循环移位后求对应项的乘积之和，实际上就是周期卷积取主值。项的乘积之和，实际上就是周期卷积取主值。循环卷积的计算过程：循环卷积的计算过程： x1(n)的的N个值按顺时针方向均匀分布在内圆周上，个值按顺时针方向均匀分布在内圆周上，x2(n)的的N个值按反时针方向均匀分布在外圆周上，把内个值按反时针方向均匀分布在外圆周上，把内外圆周上对应的数值两两相乘，然后把乘积相加就得到外圆周上对应的数值两两相乘，然后把乘积相加就得到y(0)。若将外圆周顺时针方向转动一格。若将外圆周顺时针方向转动一格(如图如图3.6(b)所示所示)，将内外圆周上对应的数值两两相乘并把乘积相加，便得