资源预览内容
第1页 / 共66页
第2页 / 共66页
第3页 / 共66页
第4页 / 共66页
第5页 / 共66页
第6页 / 共66页
第7页 / 共66页
第8页 / 共66页
第9页 / 共66页
第10页 / 共66页
亲,该文档总共66页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第03章 离散傅里叶变换及 其快速算法伍凯宁 wukntom.com 87544817-82631内容提要 离散傅里叶变换 (Discrete Fourier Transform, DFT)是时间函数是离散的,而且频谱函数也是离散的 变换。 讨论周期序列的傅里叶级数及其性质。 讨论有限长序列的离散傅里叶变换及其性质,其中包 括循环卷积的重要概念。 利用循环卷积计算线性卷积。 讨论频率取样理论。 重点讨论FFT的时间抽选算法。 介绍变换点数为合数时的FFT算法。 介绍快速傅里叶变换算法的应用。2一.DFT是重要的变换1.分析有限长序列的有用工具。2.在信号处理的理论上有重要意义。3.在运算方法上起核心作用,谱分析、卷积、相关都可以通过DFT在计算机上实现。引言3二.傅氏变换的几种可能形式(1).连续时间、连续频率的傅氏变换-FT对于非周期的连续时间信号4时域信号频域信号连续的非周期的非周期的连续的对称性:时域连续,则频域非周期。反之亦然。5(2).连续时间、离散频率傅里叶变换-FS0t-0对于周期为Tp的连续时间信号6时域信号频域信号连续的周期的非周期的离散的*时域周期为Tp, 频域谱线间隔为2/Tp7(3).离散时间、连续频率的傅氏变换-DTFT对于非周期的序列抽样间隔T8时域信号频域信号离散的非周期的周期的连续的共同的缺点:这三种变换总有一个域不是离散的 ,计算机不能直接计算; 希望的变换:不仅时间离散,频率也离散DFT。 9103.1 离散傅里叶级数及其性质3. 1. 1 离散傅里叶级数(DFS)定义(周期序列) 一个周期为N的周期序列可表示为:但是可以用离散傅里叶级数,即用复指数的加权和表示 用傅里叶级数表示,其基波频率为2p/N:用复指数表示基波:第k次谐波为:所以,第k次谐波也是周期为N的序列。不满足,ZT不存在。11因此,对于离散傅里叶级数,只取下标从0到N-1的N个谐 波分量就足以表示原来的信号。这样可把离散傅里叶级数 表示为 式中,乘以系数1/N是为了下面计算的方便; 为k次谐波的系数。将上式两边同乘以并从n=0到N-1求和,得到:12由复指数序列的正交性:所以,得到周期序列的离散傅里叶级数表达式:13令则得到周期序列的离散傅里叶级数(DFS)变换对n和k均为离散变量。如果将n当作时间变量,k当作频率 变量,则第一式表示的是时域到频域的变换,称为DFS 的正变换。第二式表示的是频域到时域的变换,称为 DFS的反变换。 由于故 是周期为N的离散周期信号。周期序列的信息可以用它在一个周期中的N个值来代表。14DFS总结:和2.是离散和周期性的,且周期均为N; 5. DFS、IDFS具有唯一性. 3.离散周期序列既可用 ,也可用 表示; 1.周期性时间信号的频谱是离散的,离散时间信号的频谱 是周期性的;周期性离散时间信号的频谱为周期性离散的 ; 4. n为离散时间变量,理解为nT;k是离散频率变量,理 解为 kDw; 153.1.2 离散傅里叶级数的性质1. 线性 设周期序列 和 的周期都为N,且若 则有2周期序列的移位 设则16证明证明:* 和 都是以N为周期的周期函数。,173周期卷积设和都是周期为N的周期序列,它们的DFS系数分别为令则上式表示的是两个周期序列的卷积,称为周期卷积。 两个周期为N的序列的卷积的离散傅里叶级数(DFS)等于 它们各自DFS的乘积。18周期卷积的计算: 周期卷积中的序列 和 对m都是 周期为N的周期序列,它们的乘积对m也是以N为周期的 ,周期卷积仅在一个周期内求和。 相乘和相加运算仅在m=0到N-1的区间内进行。计算 出n=0到N-1(一个周期)的结果后,再将其进行周期延拓 ,就得到周期卷积 。详见周期卷积的过程。 周期卷积满足交换律 两个周期序列的乘积 的DFS为:19返回 20周期卷积小结:周期卷积的操作步骤与非周期序列的线性卷积相同 ,不同的是周期卷积仅在一个周期内求和;周期卷积中对m是周期性的,周期为N; 的周期为N;周期卷积满足交换律。213.2 离散傅里叶变换及其性质3.2.1 离散傅里叶变换(DFT)有限长序列的傅里叶变换称为离散傅 里叶变换,简写为DFT。 DFT可以按3个步骤由 DFS推导出来: 将有限长序列延拓成周期序列; 求周期序列的DFS; 从DFS中取出一个周期便得到有限长 序列的DFT。将x(n)延拓成周期为N的周期序列 :22显然有的第一个周期,即n=0到N-1的序列称为主值序列,n=0到N-1的范围称为主值区间。上述两式可分别表示为 其中RN(n)是矩形序列。符号(n)N表示n对模N的余数,即 这里k是商。 都表示周期序列23例如: (1)(2)24同理,可以认为周期序列 的DFS系数 是有限长序列 X(k)周期延拓的结果,而 X(k)是 的主值序列。即 25由此便可以得出有限长序列的离散傅里叶变换(DFT)的表 示式为:由此可见,有限长序列x(n)的DFT即X(k)仍是有限长序列。26在一般情况下,X(k)是一个复量,可表示为或式中例3. 1 求有限长序列的DFT,其中a=0.8,N=8。 27解:因此得 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.9255828例 已知求X(k)的9点的IDFT.解: 29将x(n)的Z变换与x(n)的DFT进行对比,可以看出式中,表示z平面单位圆上辐角为(k=0,1,N-1)的N个等间隔点。Z变换在这些点上的取样值就是X(k)。DFT与ZT的关系30DFT与DTFT的关系有限长序列x(n)的DFT系数X(k)可看作其DTFT在 一个周期(2p)内等间距取样的样本值,取样间隔 为Dw=2p/N,即DFT与DTFT的关系示意图31DTFT与ZT的关系单位圆(z=ej)上的Z变换,即傅里叶变换X(ej)。32序列x(n)的DFT就是其ZT在单位圆上的等角距取样。序列x(n)的DFT就是其DTFT在频率取样点的取值。序列x(n)的DTFT就是其在单位圆上的ZT。33例 已知复序列 x(n)=xr(n)+jxi(n),其中xr(n),xi(n)是 实序列。序列x(n)的ZTX(z)的单位圆的下半部 (pw<2p)为0。求x(n)的DFTX(k)后一半的值,请说 明理由。解: 因为 34例 已知序列求其4点DFT,8点DFT,16点DFT?并画出|X(k)|k的曲线图线图 。 解:x(n)的FT为:35x(n)的4点DFT为:136x(n)的8点DFT为:137x(n)的16点DFT为:138481216点:8点:4点:3940对比:离散时间信号的FT-DTFT:时域离散,频域连续离散的有限长信号的DFT:时域离散,频域离散41离散傅里叶变换(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变换在单位圆上的 等角距取样。42N/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)。解:45463.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对于长为N的复序列x(n),证明:(1)因为X(k)隐含周期性,所以(2)对于实序列,2对称性 48这意味着或实序列的DFT系数X(k)的模是偶对称序列,辐角是奇对称序列对于实序列的DFT,可以只计算一半:493序列的循环移位 一个长度为N的序列x(n)的循环移位定义为 循环移位分3步计算:(1)将x(n)延拓成周期为N的周期序列 ; (2)将 移位得 或x(n+m)N;(3)对x(n+m)N取主值得x(n+m)NRN(n)。这个过程如下图所示。50从图中两虚线之 间的主值序列的 移位情况可以看 出,当主值序列 左移m个样本时 ,从右边会同时 移进m个样本, 而且好像是刚向 左边移出的那些 样本又从右边循 环移了进来。因 此取名“循环移位 ”。显然,循环移位 不同于线性移位 。 51将序列 右移:52序列循环移位后的DFT为 证明:由周期序列的移位性质得x(n+m)NRN(n)是 的主值序列的DFS的主值,即根据时域和频域的对偶关系,可以得出 若则它的DFT就是53例.已知求出该信号的DFT , X(k)=DFTx(n),变换区间长度为8。(提示:注意x(n)的区间不符合DFT要求的区间) 解:,其中5455几种变换的时移性质汇总: 564循环卷积 设Y(k)=Xl(k)X2(k),则或由上式表示的卷积称为循环卷积,常记为(式3.36)57证明: 利用DFT的隐含周期性,将Y(k)周期延拓计算后再取 主值.m取值的0N-1范围是主值区间,故 因此58循环卷积的计算是对序列按循环移位后求对应 项的乘积之和,实际上就是周期卷积取主值。59循环卷积的计算过程: 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)。6061考虑到DFT关系的对偶性,可以证明,长为N的两序列之积的 DFT等于它们的DFT的循环卷积除以N,即 这一计算过程分4步: (相当于求周期卷积的主值) (1)周期延拓和折叠 (2)移位和取主值 (3)相乘
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号