《三章离散傅立叶变换及其快速算法》由会员分享，可在线阅读，更多相关《三章离散傅立叶变换及其快速算法（34页珍藏版）》请在金锄头文库上搜索。
1、楞预也讨匈己闻漫烂蛊雷暗谰糊爵皋剖玄了叉迭放炸姓脸扩滇凤肃烧枣给三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法第三章第三章 离散傅立叶变换及其快速算法离散傅立叶变换及其快速算法周期序列的离散傅里叶级数周期序列的离散傅里叶级数离散傅立叶变换离散傅立叶变换频域采样定理频域采样定理DFT的快速算法的快速算法FFTDFT与与FFT的应用的应用缔膜酉忠店垒砒胎膊袋匡妆拼肘阵鲤洽更娩色氦胺销呈临众谷私丝锣殴枪三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法11 周期序列的离散傅立叶级数周期序列的离散傅立叶级数l周期序列的傅立叶级数周期序列的傅立叶级数对于周期为对于周期为N N的周
2、期序列的周期序列 用用基序列基序列 将其展开。将其展开。 的的基频基频为为 ，其，其基基波波为为 , , 第第k k次谐波次谐波为为 也是以也是以N N为周期的周期序列为周期的周期序列故基序列故基序列 只有只有N N个是独立的，可以用这个是独立的，可以用这N N个基个基序列将序列将 展开。展开。咀惨顽评掐搪戌口狄毫造劝锦槐胡恰麻业诱锑避捕汤螟择拧椎菊嘱奉屡迟三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究2第三章第1讲周期序列的傅立叶级数周期序列的傅立叶级数lW WN N的性质的性质1. 1.周期性周期性2. 2.共轭对称性共轭对称性3. 3.可约性可约性4. 4
3、.正交性正交性l周期序列的傅立叶级数周期序列的傅立叶级数正变换正变换反变换反变换显然具有周期性题陕瞩竟悬股惨附痒达决胯身冶照棚脸疹言盒戈次谨卑艇兵剧猪俭童背礁三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究3第三章第1讲周期序列的傅立叶级数周期序列的傅立叶级数l周期序列的离散傅立叶级数的意义周期序列的离散傅立叶级数的意义周期序列的离散傅立叶级数表明：周期序列的离散傅立叶级数表明：可将周期为可将周期为可将周期为可将周期为N N N N的序列的序列的序列的序列分解成分解成N N个离散的谐波分量的加权和，各谐波的频率为个离散的谐波分量的加权和，各谐波的频率为 ，幅度为幅
4、度为 ，其中，其中注意：注意： 和 都可取任何整数值，这表明 和 都是无限长的，但由于它们的周期性，只需要知道一个周期，其它周期可通过周期延拓得到。l离散傅立叶级数（离散傅立叶级数（DFSDFS）的性质）的性质1 1、线性性、线性性2 2、移位性、移位性疗绑桥禄少戎恤冷吴榴炮锣弓您鞋拢榴产园橇如婚蹬吧垄坷屯填湛伤友乱三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究4第三章第1讲周期序列的傅立叶级数周期序列的傅立叶级数l离散傅立叶级数（离散傅立叶级数（DFSDFS）的性质）的性质3 3、频域移位（调制）性、频域移位（调制）性4 4、周期卷积定理、周期卷积定理设设 和
5、和 具有相同的周期具有相同的周期N N，定义：，定义： 为这两个序列的为这两个序列的周期卷积。周期卷积。周期卷积与第二章所讨论的线性卷积不同，其特点是： 和 都是周期为N的序列。注注意意地代淹馅氮宏坚硼揣渺铜稽捣柏努漏昏捎害渠搁篙根母想巾稗晓籍匈麓场三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究5第三章第1讲周期序列的傅立叶级数周期序列的傅立叶级数l离散傅立叶级数（离散傅立叶级数（DFSDFS）的性质）的性质5 5、频域周期卷积定理、频域周期卷积定理l例：例：两个周期为两个周期为N=6N=6的序列的序列 和和 的周期卷积过程的周期卷积过程类似于线性卷积，首先进类
6、似于线性卷积，首先进行变量代换：行变量代换： ，再将其中一个序列进行反再将其中一个序列进行反褶、移位、相乘，然后相褶、移位、相乘，然后相加。加。运算仅在运算仅在m=0m=0到到m=N-1m=N-1内进行，计算出一个周期内进行，计算出一个周期的结果，再进行周期延拓的结果，再进行周期延拓得到整个序列得到整个序列 。砂谜雹千孪躯攒尾顽墟陷槽宗脯哈泞顺唉龙歌负揭差册扣毅坷羹瞅桥咸形三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究6第三章第1讲l定义定义周期序列的傅立叶变换周期序列的傅立叶变换序列傅立叶变换存在的条件是满足绝对可和或平方可和，但对周期序列这两个条件都不满足，
7、因为当 时，序列的值或平方值都不趋于0。若引入频域的冲击函数 ，也可求得其傅立叶变换。周期为周期为N N的周期序列的周期序列 的傅立叶变换为：的傅立叶变换为：傅立叶反变换为：傅立叶反变换为：参见P87页例题肿轰赦完钮叛荚漂朴挖搭嚷注肿绢宙榴葡怕测萤独锈嗽既懈痛经主哇桶冷三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究7第三章第1讲楞预也讨匈己闻漫烂蛊雷暗谰糊爵皋剖玄了叉迭放炸姓脸扩滇凤肃烧枣给三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法2 离散傅立叶变换离散傅立叶变换问题的引入：问题的引入：由第二章曾讨论过的“序列的傅立叶变换序列的傅立叶变换”我们
8、知道：序序列的傅立叶变换就是序列的频谱，它是数字频率列的傅立叶变换就是序列的频谱，它是数字频率 的连的连续变量函数，且序列的长度不受限制续变量函数，且序列的长度不受限制。但在实际利用计算机或数字设备进行频谱分析时，只能处理有限长数据且必须将 离散化。有限长序列的傅立叶变换及频率离散化问题有限长序列的傅立叶变换及频率离散化问题离散傅离散傅立叶变换（立叶变换（DFT）有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换离散傅立叶变换的性质离散傅立叶变换的性质离散频率、数字频率和模拟频离散频率、数字频率和模拟频率间的关系率间的关系枯叹翘弃佳荷寇焕拟虐卢尿过肩研信胃盎鞠坐赏羡篱力考倍弗赂雕藏俄挫三章离
9、散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法8有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换lDFT的定义的定义长度为长度为N N的因果序列的因果序列 其频谱为：其频谱为：上式中仅管 是离散序列，但 却是连续变量，且 是 的周期为 的周期函数，故实际上只需计算 在区间 上的值。同时，由于 为连续变量，在 中有无限多个点，而实际只能计算有限个点，故必须将 离散化。蓑十伞注淘宁紧镣欧居仑峰乡缎疗杨烬赵醇僚迹倪奈苑镭摈伦将锁倔淹蔷三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究9第三章第1讲有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换在在 上从上
10、从0 0开始等间隔的取开始等间隔的取N N个点，相应的个点，相应的 （k=0,N-1),k=0,N-1),则上式变为：则上式变为：定义式其中 为序列 在离散频率点 上的频谱值。 踞峡轮酋央染澳制良陡簿幼纠仲软赌插把掐吻给舟腐它偿映愉榨系肢赛护三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究10第三章第1讲lDFT的意义的意义有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换有限长序列 的离散傅立叶变换（简称离散傅立叶变换（简称DFT）的意义：1、 为序列 在离散频率点 上的频谱值。 2、 相当于频谱 在 范围内实施了等间隔采样，采样间隔为l离散傅立叶反变换离散傅
11、立叶反变换(IDFT)畴菜爪鹊盲亭驶苹饺胡颁胺萌跑壬皱仕骸啥聘匈毋驴眠咎痪犹搪项种狞圈三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究11第三章第1讲lDFT的周期性以及与的周期性以及与DFS的关系的关系有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换据DFT和IDFT的定义知：有限长序列的有限长序列的DFTDFT是是 的周期序列，周期为的周期序列，周期为N N； 而由而由IDFTIDFT所求得的所求得的 也变成了一个周期为也变成了一个周期为N N的周期的周期序列，即通过序列，即通过IDFTIDFT将原将原 进行了周期延拓。进行了周期延拓。将由有限长序列 以N
12、为周期进行延拓后所得的序列记为 ，并称原 为 的主值区主值区。其中 表示 对N除法求余，即若 则，例如：病镜痹湿摇灯旨伪镇函递汛王胳湖惋奏赏止伸胁卖骄老碴绒趟陨矾铆金羊三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究12第三章第1讲有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换l有限长序列有限长序列 的的DFT 与周期序列与周期序列 的的DFS 之间的关系之间的关系lDFT与与Z变换的关系变换的关系长度为长度为N N的序列的序列 其其Z Z变换：变换：与离散傅立叶变换（与离散傅立叶变换（DFTDFT）相比较有：）相比较有： 可见序列的可见序列的N N点点DF
13、TDFT是是x x( (n n) )的的Z Z变换在单位圆上变换在单位圆上N N点的等间隔采样。点的等间隔采样。显然，对于同一序列当频率采样点数不同时，其显然，对于同一序列当频率采样点数不同时，其DFTDFT的值也不的值也不同。同。l有限长序列有限长序列 与周期序列与周期序列 的关系的关系有限长序列有限长序列 是周期序列是周期序列 的主值序列，即：的主值序列，即：唤栏式膏固禁幅尤勉拖鲸涤谐浑闲满矩龋盈谚迄婪代狗沪绍蠢贸敷撂叭愉三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究13第三章第1讲l例例1：典典 型型 例例 题题已知 ，分别求 和 时的 。 解：解：由该例
14、可知：由该例可知：频率采样点数不同，DFT的长度不同，DFT 的结果也不同。芭琴今睦育丈属榴枝腻绎眩城眩堂苇便逛据匀沤维咖偶霖您员驯胖镊跋妊三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究14第三章第1讲lDFT的性质的性质1 1、线性性、线性性若x(n)与y(n)是同样长的序列，则对任何实数或复数有： 2 2、循环移位性、循环移位性若x(n) 是长为n的有限长序列，定义： 为 的循环移位序列循环移位序列。离散傅立叶变换的性质离散傅立叶变换的性质闺窥抒镁氮分充桑艺乾异贵姚冯谍坤朔淤素慑吵徐坠稠瘴蔡韵噬蒲池陪矾三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速
15、算法版权所有 违者必究15第三章第1讲循环移位示意图循环移位示意图循环移位的实质循环移位的实质：将原序列 左移 位，而移出主值区的各序列值又依次从右侧进入主值区。离散傅立叶变换的性质离散傅立叶变换的性质煞够舅咽蔫杯竟砍庶闹扎昧宵土边细慎做云溶柑谁遂艘验螺落瘁汪媚绦礼三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究16第三章第1讲离散傅立叶变换的性质离散傅立叶变换的性质lDFT的性质的性质3、频域移位定理、频域移位定理4、共轭复序列的、共轭复序列的DFT5、共轭对称性、共轭对称性实部虚部虚部水羽肖胶责边灼幼置逸怔挡峭卑盲概稗达糠尊店脓漫廉纫劝以规扳郝氨象三章离散傅立
16、叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究17第三章第1讲离散傅立叶变换的性质离散傅立叶变换的性质说明：说明： 和和 均是有限长序列，定义区间为（均是有限长序列，定义区间为（0 0N-1N-1），与第二章中的对称性不同，这里所谓的对称），与第二章中的对称性不同，这里所谓的对称是指关于是指关于N/2N/2点的对称，而不是关于原点的对称。点的对称，而不是关于原点的对称。奢衫讥峰钧卯困套滨劈坤盘滥锈宗欲稗李姜阎锦恤报晋纵极伸纶床憎雇湾三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究18第三章第1讲离散傅立叶变换的性质离散傅立叶变换的性质特别地：特
17、别地：若若 为实序列，则其为实序列，则其DFTDFT满足共轭对称特性满足共轭对称特性若若 为纯虚序列，则其为纯虚序列，则其DFTDFT满足共轭反对称性满足共轭反对称性l例：例：设 ， 和 为实序列，已知求: 和解：解：骋佃甚锅颤裳罐懒豺碳缄匠缝贪扶津胆醒罩绩疗鞭幅刻沃颐嗡兰幅起阀童三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究19第三章第1讲离散傅立叶变换的性质离散傅立叶变换的性质lDFT的性质的性质6、循环卷积定理、循环卷积定理设设 和和 是两个具有相同长度是两个具有相同长度N N的有限长序列，的有限长序列，定义循环卷积：定义循环卷积：7、频域循环卷积定理、频
18、域循环卷积定理设刊氧牢戚吟歪胺栏磊秉粹市浸疤用术叭贫锐杜歇认菩湛龙尸催舍美乔锚三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究20第三章第1讲离散傅立叶变换的性质离散傅立叶变换的性质【附：附：附：附：循环卷积的计算循环卷积的计算循环卷积的计算循环卷积的计算】反褶反褶反褶反褶 循环移位循环移位循环移位循环移位 乘积乘积乘积乘积 累加累加累加累加l例：例：已知已知作作N=8N=8的循环卷积的循环卷积解：解： 变量代换：将变量代换：将 变成变成 将将 周期延拓为周期延拓为 反褶后得到反褶后得到 从从n=0n=0开始，对每一个开始，对每一个 n=0,1,N-1, n=0,
19、1,N-1,分别对分别对 进行循环移位并取主值形成进行循环移位并取主值形成 分别将分别将 与与 对应的对应的mm点点从从m=0,1,N-1m=0,1,N-1逐点相乘，并将乘积累加就得到了各个逐点相乘，并将乘积累加就得到了各个点点n=0,1,N-1 n=0,1,N-1 的的y(n)y(n)。其计算过程见下图：。其计算过程见下图：挝吼守什稍赁丁潮疹册冰桃狭昔突昏遭浆逛牙筛棘怂幂蔷跨诫愁襄部嘘亮三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究21第三章第1讲离散傅立叶变换的性质离散傅立叶变换的性质株蒙磺桓爵咎郝庶怀墓腐哮屑涪愿遭差饿己股么恢睫琅挂骋爱薯滓三泛将三章离散傅
20、立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究22第三章第1讲离散傅立叶变换的性质离散傅立叶变换的性质lDFT的性质的性质8、循环相关定理、循环相关定理设设 和和 是两个具有相同长度是两个具有相同长度N N的有限长实序列，的有限长实序列，定义以下序列为定义以下序列为 和和 的的循环互相关序列循环互相关序列循环互相关序列循环互相关序列：9、Parseval定理定理亨屯庶斩揍标茸牙噎簧右阔妊较市尿悬摇挞棕景污谓赋愉箩芒洛很爷人莆三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究23第三章第1讲离散频率、数字频率和模拟频率间的关系离散频率、数字频率和
21、模拟频率间的关系l模拟频率模拟频率l l离散（信号数字）频率离散（信号数字）频率离散（信号数字）频率离散（信号数字）频率 或或 ，分别表示，分别表示模拟频率模拟频率模拟频率模拟频率与与模拟角频率模拟角频率模拟角频率模拟角频率。单位分。单位分别为赫兹（别为赫兹（HzHz）和弧度）和弧度/ /秒（秒（rad/srad/s）。两者关系为：）。两者关系为： ，单单位位为为弧弧度度（radrad）。通通过过采采样样信信号号的的频频谱谱，可可建建立模拟频率与离散（信号数字）频率之间的关系：立模拟频率与离散（信号数字）频率之间的关系： 的取值范围：对应于模拟频率能取的最高频率对应于模拟频率能取的最高频率 就
22、是离散（信号数字）频率能取的最高频率 此时，虽然信号在时域时离散的，但此时，虽然信号在时域时离散的，但 仍然是连续的仍然是连续的注意注意赴宗甜绅多蹭戊究籍鳃憋倦默艇额遵群镭贾陇耻蓬真炙挥淹掩旅喜蒂持丝三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究24第三章第1讲离散频率、数字频率和模拟频率间的关系离散频率、数字频率和模拟频率间的关系l数字频率数字频率它是将它是将离散（信号数字）频率离散（信号数字）频率离散（信号数字）频率离散（信号数字）频率 离散化后的结果，用离散化后的结果，用 表示。表示。 ，因此可得出离散频率，因此可得出离散频率 、数字频数字频率率 和模拟频
23、率和模拟频率 之间的对应关系为：之间的对应关系为：以上所讨论的三种频率变量之间的关系，在对模对模拟信号进行数字处理拟信号进行数字处理以及利用模拟滤波器设计数利用模拟滤波器设计数字滤波器字滤波器乃至整个数字信号处理中十分重要，望同学们高度重视。拾葱胯板手仪辉议都羡紫病啸檄馏昭盏店商惭奴泻庭哺铰领夕疆唱死烛浑三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究25第三章第1讲楞预也讨匈己闻漫烂蛊雷暗谰糊爵皋剖玄了叉迭放炸姓脸扩滇凤肃烧枣给三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法3 频域采样定理频域采样定理频域采样不失真恢复的条件频域采样不失真恢复的条件
24、内插公式内插公式问题的提出：问题的提出：时域：时域：通过满足通过满足“时域采样定理时域采样定理”的采样的采样频域：频域：？嚷篓困碘负瞅屉洪籽熄廉王印擞湘胚小誓渠压告切滞谰仰旧驳疚戎钙抠酝三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法26频域采样不失真恢复的条件频域采样不失真恢复的条件l频域采样后能不失真恢复原序列的条件频域采样后能不失真恢复原序列的条件频率离散化的采样点数频率离散化的采样点数N N必须必须大于大于大于大于序列的长度序列的长度L L【推导过程推导过程推导过程推导过程】设设 的长度为的长度为 （没有限制）（没有限制）频域采样频域采样欲恢复原信号，即腿变掉俘擞毅哦掌敲腆
25、楷融拾微纤役蝎嫌零儿棠鸵据张伸校鹰弛猩颤当犯三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究27第三章第1讲频域采样不失真恢复的条件频域采样不失真恢复的条件由该式可知：由该式可知： 是原序列是原序列 的周期延拓，周期为的周期延拓，周期为N N，然后取主值。然后取主值。纵浪告省吱稀叶前宇吓蹬琐读砧使勾冶沁果废药气据砧炙疵名仲孜获婿踞三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究28第三章第1讲频域采样不失真恢复的条件频域采样不失真恢复的条件结论：结论：结论：结论：若序列长度为若序列长度为若序列长度为若序列长度为L L，频域采样点数（或
26、，频域采样点数（或，频域采样点数（或，频域采样点数（或DFT DFT 的长度）的长度）的长度）的长度）为为为为N N，且，且，且，且LNLNLN，则频域采样后不能不失真地恢复原序列。，则频域采样后不能不失真地恢复原序列。，则频域采样后不能不失真地恢复原序列。，则频域采样后不能不失真地恢复原序列。识邮缕烛疯丁咖埂姑魁绅烷鞍烃沙杏肺椰蜗辗漾循萤哥乏烷系软默良它哈三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究29第三章第1讲内插公式内插公式l用用X(k)表示表示X(z)设序列长度为设序列长度为N N，由，由傅里叶变换对傅里叶变换对傅里叶变换对傅里叶变换对得得折仰脯哄蜡
27、掂柏喻整胸楼旺谣溶厕膨田饭壕纽息捷躇绪剐藉遁碰域悲能书三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究30第三章第1讲内插公式内插公式l用用X(k)表示表示X(ej) )时域采样定理中的内插函数相相似似群植累邵犁纤酞峪光空碱台换科号瓢局表棕内忆记雪搁撰造躬玛启蝇垢劲三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究31第三章第1讲内插公式内插公式以上所讨论的两种情形的内插公式内插公式是用频域采样法设用频域采样法设计计FIR数字滤波器数字滤波器重要的理论基础，虽然此处无从体现，但后面有关FIR数字滤波器的结构与设计中常用到这些结论。炎碘慎
28、增苫摩需乓堪洗厄条庚随丝塌腕抽酶处懦痰瘤系骤螺疮劈痈棉共咕三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究32第三章第1讲l内插函数零极点与内插函数零极点与（ ）的幅）的幅）的幅）的幅频频频频特性示意特性示意特性示意特性示意图图图图内插公式内插公式奋抄钵折逢特慕勾弛蜡苗展垂憨团举炯傅拽跳痘人矿桓蔬避页潘田表旭屿三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究33第三章第1讲典典 型型 例例 题题例：例：已知 ，对 在单位 圆上等间隔采样N点解：解：廓复场浮酝撞低叶住璃藉伪舞寞滨淳宽奔失遁沥湍噶嫉诅鸯李箩渐吕莽帧三章离散傅立叶变换及其快速算法三章离散傅立叶变换及其快速算法版权所有 违者必究34第三章第1讲
