第四章快速傅里叶变换(FFT)_肖太龙讲述.pptx

第四章快速傅里叶变换(FFT)_肖太龙讲述.pptx

  1. 1、本文档共35页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第四章快速傅里叶变换(FFT)_肖太龙讲述

第四章 快速傅里叶变换(FFT) 通信1402班 肖太龙 Contents 从DFT到FFT FFT的基本概念 FFT算法的实现原理 FFT的物理意义 DFT与FFT时间复杂度比较 从DFT到FFT的缘由 依次类推,N/2个点的时间复杂度为多少呢?N/4呢? 从哪个方面减少运算量呢? 周期性表现为: 对称性表现为: 1965年库利和图基提出一种DFT的快速算法,以此来解决DFT变换的效率问题。 算法的提出的初衷主要是为了减少乘法次数,又因为旋转因子的对称性和周期性能达到这一目标,因此在理论上是可以实现的。 FFT算法就是不断地把长序列的DFT分解为短序列的DFT的算法。最常用的是基2FFT算法。 浅谈FFT实现原理 FT算法基本上分为两大类: 时域抽取法FFT(Decimation In Time FFT,简称DIT-FFT)。 频域抽取法FFT(Decimation In Frequency FFT,简称DIF―FFT)。 我们主要来分析DIF-FFT算法。 DIF-FFT与DIT-FFT算法有什么异同? 算法理论推导: 设序列 的长度为N,且满足N=2M ,M为自然数。 按n奇偶把 分解为两个N/2点的子序列 则x(n)的DFT为 因为 所以 其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT,即 由于X1(k)和X2(k)均以N/2为周期,且 所以X(k)又可表示为 至此,一次时域抽取法的理论推导就完成了。从上面的两个式子中,我们定义一种新的运算符——蝶形运算符。 8点DFT一次时域抽取分解运算流图 完成一次蝶形运算需要一次复数乘法和两次复数加法运算。因此在8点DFT一次时域抽取分解中,共需要计算两个N/2点DFT运算和N/2个蝶形运算。 所以按照上图的计算DFT时,总的复数乘法次数为 复数加法次数为 类似地,我们将 按奇偶分解成两个N/4点子序列 ,其表达式分别如下: 那么, 又可表示为 式中 同理,由 的周期性和 的对称性 最后得到: 用同样的方法可以计算出 其中 8点DFT二次时域抽取分解运算 8点DIT-FFT运算流图 从上面的蝶形算法,当 时,其运算应该有M级蝶形,每一级都由N/2个蝶形运算构成。因此每一级运算都需要N/2次复数乘法和N次复数加法,所以M级蝶形运算的乘法次数为: 加法次数: 一个简单的算例 计算序列 的8点DFT。分别用基本的DFT算法和FFT算法实现,体会计算过程中的时间复杂度。 当然针对计算机来说,计算乘法所需要的时间远大于加法。一般的计算机,差不多相差十倍左右。 用计算机产生随机的1024个点构成序列,然后取N=1024.此时计算时间差距就会加大。N=2048时,时间差距会更大。 为了更进一步的体会FFT的物理意义,引入一个算例: 假设对某信号经过ADC之后,得到一个序列 ,此时我们不知道其具体的函数表达式。但是我们可以对其做FFT运算。现在我们做一个验证: 假设我们有一个信号,它含有2V的直流分量,频率为50Hz、相位为-30度、幅度为3V的交流信号,以及一个频率为75Hz、相位为90度、幅度为1.5V的交流信号。用数学表达式就是如下: S=2+3*cos(2*pi*50*t-pi*30/180)+1.5*cos(2*pi*75*t+pi*90/180) 现在对其进行变换,取样点为1024,采样频率为1024Hz 注意这里的取样频率只要满足原始频率的2倍即可,且取样点和取样频率根据频率分辨率来选取。 从图中的结果可以得出,当频率为0、50、75时,对应的幅度值依次为2、3、1.5,相位依次为0、90、-30。当然,这看上去几乎是没有误差的,因为我们取样频率和所取点数比较大,当N=Fs=256时,会存在误差,但是这个误差完全不影响我们对信号函数的分析与判断。从而进一步的验证了DFT与FFT算法的正确性。 上图是从模拟信号到频域离散信号的完整的过程。这其中对应有几个概念容易混淆。因此对此做出区分: 数字频率、模拟频率与采样频率:模拟频率通常用 表示,数字频率用 表示。此时的数字频率主要是针对序列而言,因此没有采样频率 就不会有数字频率的概念,所以数字频率与采样频率和模拟频率一定满足

文档评论(0)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档