ch离散傅里叶级数PPT课件

1、1第第03章章 离散傅里叶离散傅里叶变换及其快速算法变换及其快速算法伍凯宁伍凯宁 87544817-8263第1页/共66页2内容提要 离散傅里叶变换 (Discrete Fourier Transform，DFT)是时间函数是离散的，而且频谱函数也是离散的变换。 讨论周期序列的傅里叶级数及其性质。 讨论有限长序列的离散傅里叶变换及其性质，其中包括循环卷积的重要概念。 利用循环卷积计算线性卷积。 讨论频率取样理论。 重点讨论FFT的时间抽选算法。 介绍变换点数为合数时的FFT算法。 介绍快速傅里叶变换算法的应用。第2页/共66页3一.DFT是重要的变换 1.分析有限长序列的有用工具。 2.在信

2、号处理的理论上有重要意义。 3.在运算方法上起核心作用，谱分析、 卷积、相关都可以通过DFT在计算机 上实现。引言第3页/共66页4(1).连续时间、连续频率的傅氏变换-FT0t)(tx0)( jX对于非周期的连续时间信号第4页/共66页5时域信号频域信号连续的非周期的非周期的连续的对称性: 时域连续，则频域非周期。 反之亦然。第5页/共66页6(2).连续时间、离散频率傅里叶变换-FS0t-0对于周期为Tp的连续时间信号第6页/共66页7时域信号频域信号连续的周期的非周期的离散的*时域周期为Tp, 频域谱线间隔为2/Tp第7页/共66页8 (3).离散时间、连续频率的傅氏变换-DTFT 对于

3、非周期的序列0Ts2-抽样间隔Tx(nT)-T0T2Ttx(nT)T-T0T2Tt第8页/共66页9时域信号频域信号离散的非周期的周期的连续的共同的缺点：这三种变换总有一个域不是离散的，计算机不能直接计算； 希望的变换：不仅时间离散，频率也离散DFT。 第9页/共66页10第10页/共66页113.1 离散傅里叶级数及其性质3. 1. 1 离散傅里叶级数(DFS)定义（周期序列） 一个周期为N的周期序列可表示为： 但是可以用离散傅里叶级数，即用复指数的加权和表示用傅里叶级数表示，其基波频率为2/N：用复指数表示基波：第k次谐波为：所以，第k次谐波也是周期为N的序列。21jnNee2jnkNke

4、e22()jn k NjnkNNk Nkeeee( )nnx n r 不满足，ZT不存在。第11页/共66页12因此，对于离散傅里叶级数，只取下标从0到N-1的N个谐波分量就足以表示原来的信号。这样可把离散傅里叶级数表示为 式中，乘以系数1/N是为了下面计算的方便； 为k次谐波的系数。将上式两边同乘以并从n=0到N-1求和，得到：第12页/共66页13由复指数序列的正交性：所以，得到周期序列的离散傅里叶级数表达式：2221()()0()101NNNNjk r njk r Nnjk rNkreekre 第13页/共66页14令则得到周期序列的离散傅里叶级数(DFS)变换对n和k均为离散变量。如果

5、将n当作时间变量，k当作频率变量，则第一式表示的是时域到频域的变换，称为DFS的正变换。第二式表示的是频域到时域的变换，称为DFS的反变换。由于故 是周期为N的离散周期信号。周期序列的信息可以用它在一个周期中的N个值来代表。第14页/共66页15DFS总结:( )X k和2.是离散和周期性的，且周期均为N； 5. DFS、IDFS具有唯一性. 3.离散周期序列既可用 ,也可用 表示； ( )X k1.周期性时间信号的频谱是离散的，离散时间信号的频谱是周期性的；周期性离散时间信号的频谱为周期性离散的； 4. n为离散时间变量，理解为nT；k是离散频率变量，理解为 kDw; 第15页/共66页16

6、3.1.2 离散傅里叶级数的性质1. 线性设周期序列 和 的周期都为N，且若则有2周期序列的移位 设则第16页/共66页17证明证明：* 和 都是以N为周期的周期函数。10()Nk n mmkNNnx nm WW%1( )NmktmkNNtmx t W W %( )X k,第17页/共66页183周期卷积设和都是周期为N的周期序列，它们的DFS系数分别为令则上式表示的是两个周期序列的卷积，称为周期卷积。两个周期为N的序列的卷积的离散傅里叶级数(DFS)等于它们各自DFS的乘积。第18页/共66页19周期卷积的计算：周期卷积中的序列 和 对m都是周期为N的周期序列，它们的乘积对m也是以N为周期的

7、，周期卷积仅在一个周期内求和。 相乘和相加运算仅在m=0到N-1的区间内进行。计算出n=0到N-1(一个周期)的结果后，再将其进行周期延拓，就得到周期卷积 。详见周期卷积的过程。 周期卷积满足交换律两个周期序列的乘积 的DFS为：第19页/共66页20返回133第20页/共66页21周期卷积小结:)(),(21mnxmx)(ny周期卷积的操作步骤与非周期序列的线性卷积相同，不同的是周期卷积仅在一个周期内求和；周期卷积中对m是周期性的，周期为N；的周期为N；周期卷积满足交换律。第21页/共66页223.2 离散傅里叶变换及其性质3.2.1 离散傅里叶变换(DFT) 有限长序列的傅里叶变换称为离散

8、傅里叶变换，简写为DFT。DFT可以按3个步骤由 DFS推导出来：将有限长序列延拓成周期序列；求周期序列的DFS；从DFS中取出一个周期便得到有限长序列的DFT。将x(n)延拓成周期为N的周期序列 :第22页/共66页23显然有的第一个周期，即n=0到N-1的序列称为主值序列，n=0到N-1的范围称为主值区间。上述两式可分别表示为 其中RN(n)是矩形序列。符号(n)N表示n对模N的余数，即 这里k是商。 都表示周期序列第23页/共66页24例如：(1)(2)第24页/共66页25同理，可以认为周期序列 的DFS系数 是有限长序列X(k)周期延拓的结果，而 X(k)是 的主值序列。即 1010

9、10( )( )( )( )( )( )( )01( )0NknNnNknNNNnNknNnX kx n WX kRkx n WRnx n WkNX k%其他第25页/共66页26由此便可以得出有限长序列的离散傅里叶变换(DFT)的表示式为:由此可见，有限长序列x(n)的DFT即X(k)仍是有限长序列。第26页/共66页27在一般情况下，X(k)是一个复量，可表示为或式中例3. 1 求有限长序列的DFT，其中a=0.8，N=8。 第27页/共66页28解：因此得 X(0)=4.16114 X(1)=0.71063-j0.92558 X(2)=0.50746-j0.40597 X(3)=0.47

10、017-j0.16987 第28页/共66页29例 已知50( )218kX kk求X(k)的9点的IDFT.88990011( )( )329912 ( )0,1,.,83knknkkx nX k WWnn89090,=01,.,8knknWn其中解： 第29页/共66页30将x(n)的Z变换与x(n)的DFT进行对比，可以看出式中，表示z平面单位圆上辐角为(k=0,1,N-1)的N个等间隔点。Z变换在这些点上的取样值就是X(k)。DFT与与ZT的关系的关系第30页/共66页312/2/( )()()jk Njk NX kX eX ewwDFT与与DTFT的关系的关系有限长序列x(n)的DF

11、T系数X(k)可看作其DTFT在一个周期(2)内等间距取样的样本值，取样间隔为Dw=2/N，即DFT与与DTFT的关系示意图的关系示意图210( )( )NjknNnX kx n e10()( )Njj nnX ex n eww第31页/共66页32DTFT与与ZT的关系的关系单位圆(z=ej)上的Z变换，即傅里叶变换X(ej)。()( )jjz eX eX zww10()( )Njj nnX ex n eww10( )( )NnnX zx n z第32页/共66页332( )()jk NX kX eww2( )( )( )kjkNNz Wz eX kX zX z()( )jjz eX eX

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

13、出|X(k)|k的曲线图。 4322222221()( )1()sin(2 )()sin()2jjj njnjjjjjjjeX ex n eeeeeeeeewwwwwwwwwwwww解：x(n)的FT为：第35页/共66页36x(n)的4点DFT为：3424sin()( )()sin()4jkjkkX kX eekww1第36页/共66页37x(n)的8点DFT为：3828sin()2( )()sin()8jkjkkX kX eekww1第37页/共66页38x(n)的16点DFT为：316216sin()4( )()sin()16jkjkkX kX eekww1第38页/共66页394812

14、16点：8点：4点：第39页/共66页40第40页/共66页41对比：离散时间信号的FT-DTFT： 时域离散，频域连续离散的有限长信号的DFT： 时域离散，频域离散第41页/共66页42离散傅里叶变换离散傅里叶变换(DFT)总结总结序列序列x(n)在时域是离散、有限长的在时域是离散、有限长的(长度为长度为N)，它它的离散傅里叶变换的离散傅里叶变换X(k)也是离散、有限长的也是离散、有限长的(长度长度也为也为N)。所以，所以， x(n)和和X(k)均可用计算机实现。均可用计算机实现。n为时域变量为时域变量(nT)，k为频域变量为频域变量(kDwDw)。DFT与与DFS没有本质区别，没有本质区别

15、，DFT实际上是实际上是DFS的的主值，主值，DFT也隐含有周期性。也隐含有周期性。离散傅里叶变换离散傅里叶变换(DFT)具有唯一性。具有唯一性。DFT的物理意义：序列的物理意义：序列x(n)的的Z变换在单位圆上的变换在单位圆上的等角距取样。等角距取样。第42页/共66页43N/2点的DFT: 1202( )( )0,1,2,.,12NknNnNX kx n Wk1404( )( )0,1,2,.,14NknNnNX kx n WkN/4点的DFT: 第43页/共66页44旋转因子旋转因子 的性质的性质 NjNeW2对称性： kNNkNWW)*(周期性： kNmNkNWW换底： 22kmkkN

16、mNNWWW,k/2,N/2为整数 几个特殊值： 1kNNW21NNW 4NNWj 34NNWj第44页/共66页45例. 令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 第45页/共66页46111 00( )( )NNk n nNnkx nx nW()( )( )NlNNNxnNl RnNxnRn 10,0Nk n nNkNnnNl lZW其他第46页

17、/共66页473.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的定义进行证明。第47页/共66页48对于长为N的复序列x(n)，*( )()DFT x nXNk*10)(*)()(NnnkNNWnxkNX10)(*)(NnnkNNWnx10*)(NnknNWnx)

18、(*nxDFT证明：（1）因为X(k)隐含周期性，所以*()( )DFT xNnXk（2）对于实序列，* ( )( )()DFT x nX kXNk2对称性 第48页/共66页49这意味着或( )0,.,2 1()( )X kkNX NkXk实序列的DFT系数X(k)的模是偶对称序列，辐角是奇对称序列*()( )XNkX k对于实序列的DFT，可以只计算一半：第49页/共66页503序列的循环移位 一个长度为N的序列x(n)的循环移位定义为 循环移位分3步计算：(1)将x(n)延拓成周期为N的周期序列 ； (2)将 移位得 或x(n+m)N；(3)对x(n+m)N取主值得x(n+m)NRN(n

19、)。这个过程如下图所示。第50页/共66页51 从图中两虚线之间的主值序列的移位情况可以看出，当主值序列左移m个样本时，从右边会同时移进m个样本，而且好像是刚向左边移出的那些样本又从右边循环移了进来。因此取名“循环移位”。 显然，循环移位不同于线性移位。 第51页/共66页52将序列右移：第52页/共66页53序列循环移位后的DFT为 证明：由周期序列的移位性质得x(n+m)NRN(n)是 的主值序列的DFS的主值，即根据时域和频域的对偶关系，可以得出若则它的DFT就是第53页/共66页54othersnnx, 03| , 1)(求出该信号的DFT ， X(k)=DFTx(n)，变换区间长度为

20、8。（提示：注意x(n)的区间不符合DFT要求的区间） 1( )(3)x nx n)(nx0n)(nx6 61othersnnx, 06 , 5 , 4 , 3 , 2 , 1 , 0, 1)(1解:,其中)()()3()(138881kXWnRnxDFTkXk1(3)( )x nx n第54页/共66页55kjkjnknnkneeWWnxkX4476087081111)()(733443481441( )( )11jkjkj kjkkjkjkeeeX kWX keee第55页/共66页56几种变换的时移性质汇总： 0)()(0tjFTejXttx0)()(0stLTesXttxmZTzzXm

21、nx)()(kmNDFTWkXmnx)()(第56页/共66页574循环卷积 设Y(k)=Xl(k)X2(k)，则或由上式表示的卷积称为循环卷积，常记为)( )()(1021nRmnxmxNNm(式3.36)第57页/共66页58证明：证明： 利用利用DFT的隐含周期性，将的隐含周期性，将Y(k)周期延拓计算后再取周期延拓计算后再取主值主值.m取值的取值的0N-1范围是主值区间，故范围是主值区间，故因此因此第58页/共66页59循环卷积的计算是对序列按循环移位后求对应项的乘积之和，实际上就是周期卷积取主值。第59页/共66页60循环卷积的计算过程： x1(n)的N个值按顺时针方向均匀分布在内圆周上，x2(n)的N个值按反时针方向均匀分布在外圆周上，把内外圆周上对应