第四章 快速付里叶变换(FFT) Fast Fourier Transforming

Slides:



Advertisements
Similar presentations
“ 上海市科研计划课题预算编制 ” 网上教程 上海市科委条财处. 经费预算表 表 1 劳务费预算明细表 表 2 购置设备预算明细表 表 3 试制设备预算明细表 表 4 材料费预算明细表 表 5 测试化验与加工费预算明细表 表 6 现有仪器设备使用费预算明细表 小于等于 20 万的项目,表 2 ~表.
Advertisements

遥远而神秘的大陆 —— 非洲, 有着悠久的历史,辽阔的地域、 奇特的风景和古朴的民俗;更 有那极具感染力、热情奔放的 音乐和舞蹈。 让我们一起走进非洲,去 聆听、感受和体验那具有独 特魅力的非洲歌舞音乐! 非洲正以其独特的、近乎原汁原味的风光和文化吸 引着全世界的目光, 也吸引了你我的目光。
平台的优点: ( 1 )永久免费: 学校和老师使用校讯通平台发送短信 是免费的,并且通过使用平台,可获得部分购物卡补贴。 ( 2 )移动办公: 校讯通不受时间和空间的限制,只要 有一台可以上网的电脑,老师便可以通过互联网发送短信 给家长,能够实现移动办公,节省老师的工作时间。 ( 3 )简单易用:
第七讲 管理类文体写作 管理类文书分为两类:公文、事务文书。 一,公文概述(教材P174-) (一)定义、范围、类别:
社交礼仪.
損益表 原則: 收益與費用的計算,實際上是在實現或發生時所產生,與現金收付當時無關。
无锡商业职业技术学院 机电工程学院党总支孙蓓雄
2016年全国中级会计资格考试 经济法 主讲老师:葛江静.
《中国共产党发展党员工作细则》 学习提纲 中共进贤县委组织部 宋 剑
严格发展程序,提高工作能力 黄 玉 2010年9月.
发展党员的流程和要求 党委组织部 萧炽成.
全面了解入党程序 认真履行入党手续 第一讲 主讲人:陈亭而.
中共湖北大学知行学院委员会党校 入党材料规范填写指导 学工处 李华琼 二〇一三年十二月.
云南财经大学2010年党员发展培训—— 党员发展工作培训 校党委组织部 2010年9月17日.
第五章 信号采集与数字分析原理及技术 与模拟分析相比,数字信号分析有以下一些优点: 高度的灵活性,极好的稳定性和可靠性 可多工处理,分时复用
教育年鉴条目的撰写.
余文森 教授、博士生导师 教育部福建师范大学基础教育课程研究中心
第8课 列方程(组)解应用题.
22.3 实际问题与一元二次方程(1).
莫让情感之船过早靠岸 兴庆回中 赵莉.
医师变更执业注册申请审核表 填写说明 医务部.
《老年人权益保障》 --以婚姻法.继承法为视角
行政公文写作 第七章 2004年8月 行政公文写作.
论文撰写的一般格式和要求 孟爱梅.
启事的写作 一、启事的含义 启事可以张贴在允许张贴的公共场所,也可刊登在报刊杂志上,或由电台、电视台播出。 二 、启事的作用
第十章 图像的频域变换.
經濟部工業局 產業升級創新平台輔導計畫 (創新優化計畫)
102年10月17日 臺北市公共運輸處 報告人:陳榮明處長
第三讲 事务性文书的写作 (计划 总结 调查报告 ).
归档文件整理规则 & 机关文件材料归档范围及文书档案保管期限规定 2015年4月 市档案局 业务指导科 刘薇
中国人事科学院学术咨询中心 主任 甄源泰 研究员
几种常见应用文体示例.
网络条件下老干部工作信息的应用与写作 齐齐哈尔市委老干部局 山佐利.
咨询师的个人成长 第一课:如何撰写个人成长报告以及答辩.
第三章 幼儿园课程内容的编制与选择.
公 文 写 作 第一讲 主讲教师:娄淑华          学时:32.
第八章 诉讼法 第一节 诉讼法概述 第二节 民事诉讼法 第三节 行政诉讼法 第四节 刑事诉讼法.
第三章  电话、电子通讯   本章重难点:     打电话的方法、         接听电话的方法。
实验十:FFT的实现与应用 信息工程学院 网络工程系 强文萍.
第一章 绪论.
《社交礼仪分享》 阳晨牧业科技有限公司 市场中心 二O一二年四月十八日.
普及纳米知识 推动科技进步.
上海市绩效评价培训 数据分析与报告撰写 赵宏斌 上海财经大学副教授
会议文书.
第七章 傅利葉轉換 7.1 前言 傅利葉轉換是影像處理中重要的基礎,不但可以做到用其他方式無法得到的結果,也比其他方式來得有效率。
如何写入团申请书.
第三章 DFT 离散傅里叶变换.
通 知 通知是批转下级机关的公文,转发上级机关和不相隶属机关的公文,传达要求下级机关办理和需要有关单位周知或执行的事项,任免人员时使用的公文。
XX信托 ·天鑫 9号集合资金信托计划 扬州广陵
第11周 工作计划.
第二章 离散傅里叶变换 及其快速算法(8学时 )
引言 1.DFT是信号分析与处理中的一种重要变换。 年,Cooley, Tukey《机器计算傅里叶级数的一种算法》
第三章 付里叶分析 离散付氏级数的数学解释(The Mathematical Explanation of DFS)
第三章学习目标 1.理解傅里叶变换的几种形式 2.理解离散傅里叶变换及性质,掌握圆周移位、共轭对称性,掌握圆周卷积、线性卷积及两者之间的关系
第九章 結 帳 9-1 了解結帳的意義及功能 9-2 了解虛帳戶結清之會計處理 9-3 了解實帳戶結轉的會計處理
项目名称:XXXXXXXXXXXX 研究科室:XXX 主要研究者:XXX 日期:xxxx年XX月XX日.
主标题 副标题 日期.
Xxxx集团有限公司 封面页.
新课标人教版课件系列 《高中数学》 必修5.
第四章 模拟信号分析 模拟信号分析是直接对连续时间信号进行分析处理的过程,利用一定的数学模型所组成的运算网络来实现的。从广义讲,它包括了调制与解调、滤波、放大、微积分、乘方、开方、除法运算等。 本章主要介绍模拟信号分析处理中的调制与解调、滤波、微分、积分以及积分平均等问题。
第4章 快速傅立叶变换 问题的提出 解决问题的思路与方法 基2时间抽取FFT算法 基2时间抽取FFT算法的计算复杂度
中国大连高级经理学院博士后入站申请汇报 汇报人:XXX.
內部控制作業之訂定與執行 報告人:許嘉琳 日 期:
第三章 DFT 离散傅里叶变换.
第三节 二项式定理.
現 金 第一節 現金之管理 第二節 銀行調節表 第三節 零用金.
新课导入 请欣赏一首诗: 太阳下山晚霞红,我把鸭子赶回笼; 一半在外闹哄哄,一半的一半进笼中; 剩下十五围着我,共有多少请算清.
在下列空格中,填入適當的式子: (1)(-3x)‧9x=__________ -27x2 (2)(3x2)2 =__________
8的乘法口诀 导入 新授 练习.
Presentation transcript:

第四章 快速付里叶变换(FFT) Fast Fourier Transforming

第一节 引 言

一、快速付里叶变换FFT 有限长序列通过离散傅里叶变换 (DFT)将其频 域离散化成有限长序列.但其计算量太大(与N的平方成正比), 很难 实时地处理问题 , 因 此 引 出 了 快 速 傅 里 叶 变 换(FFT) . FFT 并 不 是 一 种 新 的 变 换 形 式 ,它 只 是 DFT 的 一 种 快 速 算 法 . 并 且 根 据 对 序 列 分 解 与 选 取 方 法 的 不 同 而 产 生 了 FFT 的 多 种 算 法 . FFT 在 离 散 傅 里 叶 反 变 换 、 线 性 卷 积 和 线 性 相 关 等 方 面 也 有 重 要 应 用。

二、FFT产生故事 当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基(J.W.Turkey)正在写有关付里叶变换的文章,因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法,它实质上就是后来的著名的库利(Cooley J.W)图基算法。在加文的迫切要求下,库利很快设计出一个计算机程序。1965年库利--图基在<计算数学>、Mathematic of Computation 杂志上发表了著名的“机器计算付里级数的一种算法”文章,提出一种快速计算DFT的方法和计算机程序--揭开了FFT发展史上的第一页,促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成,电子数字计算机的发明, 使DFT的运算大大简化了。

三、本章主要内容 1.直接计算DFT算法存在的问题及改进途径。 2.多种DFT算法(时间抽取算法DIT算法,频率抽取算法DIF算法,线性调频Z变换即CZT法) 3.FFT的应用

第二节 直接计算DFT算法存在的问题及改进途径

一、直接计算DFT计算量 问题提出: 设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算,共需多大的运算工作量?

1.比较DFT与IDFT之间的运算量 其中x(n)为复数, 也为复数 所以DFT与IDFT二者计算量相同。

2.以DFT为例,计算DFT复数运算量 N*N次复数相乘和N*(N-1)次复数加法 计算一个X(k)(一个频率成分)值,运算量为 例k=1则 所以,要完成整个DFT运算[X(k)有N个点 ],其计算量为: N*N次复数相乘和N*(N-1)次复数加法

3.一次复数乘法换算成实数运算量 复数运算要比加法运算复杂,需要的运算时间长。 一个复数乘法包括4次实数乘法和2次实数加法。 (a+jb)(c+jd)=(ac-bd)+j(bc+ad) 4次实数乘法 2次实数加法

4.计算DFT需要的实数运算量 每运算一个X(k)的值,需要进行 4N次实数相乘和 2N+2(N-1)=2(2N-1)次实数相加. 整个DFT运算量为:4N2次实数相乘和2N(2N-1)次实数相加. 由此看出:直接计算DFT时,乘法次数与加法次数都是和N2成比例的。当N很大时,所需工作量非常可观。

例子 例1:当N=1024点时,直接计算DFT需要: N2=220=1048576次,即一百多万次的复乘运算 例2:石油勘探,24道记录,每道波形记录长度5秒,若每秒抽样500点/秒, 每道总抽样点数=500*5=2500点 24道总抽样点数=24*2500=6万点 DFT运算时间=N2=(60000)2=36*108次

作业 P200页,第1题

二、改善DFT运算效率的基本途径 利用DFT运算的系数 的固有对称性和周期性,改善DFT的运算效率。 1.合并法:合并DFT运算中的某些项。

利用DFT运算的系数 的固有对称性和周期性,改善DFT的运算效率 的对称性: 的周期性: 因为: 由此可得出:

例子 例: 利用以上特性,得到改进DFT直接算法的方法.

(1) 合并法:步骤1-分解成虚实部 合并DFT运算中的有些项 对虚实部而言 所以代入DFT中:

(1) 合并法:步骤2-代入DFT中 展开:

(1) 合并法:步骤3-合并有些项 根据: 有:

(1) 合并法:步骤4-结论 由此找出其它各项的类似归并方法:乘法次数可以减少一半。 例:

2、将长序列DFT利用对称性和周期性分解为短序列DFT--思路 因为DFT的运算量与N2成正比的 如果一个大点数N的DFT能分解为若干小点数DFT的组合,则显然可以达到减少运算工作量的效果。

2、将长序列DFT利用对称性和周期性分解为短序列DFT--方法 把N点数据分成二半: 其运算量为: + = 再分二半: + + = + 这样一直分下去,剩下两点的变换。

2、将长序列DFT利用对称性和周期性分解为短序列DFT--结论 快速付里时变换(FFT)就是在此特性基础上发展起来的,并产生了多种FFT算法,其基本上可分成两大类: 按抽取方法分: 时间抽取法(DIT);频率抽取法(DIF) 按“基数”分:基-2FFT算法;基-4FFT算法;混合基FFT算法;分裂基FFT算法 其它方法:线性调频Z变换(CZT法)

第三节 基--2按时间抽取的FFT算法Decimation-in-Time(DIT) (Coolkey-Tukey)

一、算法原理 设输入序列长度为N=2M(M为正整数,将该序列按时间顺序的奇偶分解为越来越短的子序列,称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。 其中基数2----N=2M,M为整数.若不满足这个条件,可以人为地加上若干零值(加零补长)使其达到 N=2M

例子 设一序列x(n)的长度为L=9,应加零补长为 N=24=16 应补7个零值。 x(n)

二、算法步骤 1.分组,变量置换 DFT变换: 先将x(n)按n的奇偶分为两 组,作变量置换: 前半部分: 后半部分: 当n=偶数时,令n=2r; 当n=奇数时,令n=2r+1; 得到:x(2r)=x1(r); x(2r+1)=x2(r);r=0…N/2-1; 则可得其DFT为两部分: 前半部分: 后半部分:

2.代入DFT中 x(0),x(2)…x(2r)偶数点 x(1),x(3)…x(2r+1)奇数点 代入DFT变换式: 生成两个子序列

3.求出子序列的DFT 上式得:

4.结论1 一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照: 再应用W系数的周期性,求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。

5.求出后半部的表示式 看出:后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。

6.结论2 频域中的N个点频率成分为: 结论:只要求出(0~N/2-1)区间内的各个整数k值所对应的X1(k),X2(k)值,即可以求出(0~N-1)整个区间内全部X(k)值,这就是FFT能大量节省计算的关键。

7.结论3 由于N=2M,因此N/2仍为偶数,可以依照上面方法进一步把每个N/2点子序列,再按输入n的奇偶分解为两个N/4点的子序列,按这种方法不断划分下去,直到最后剩下的是2点DFT,两点DFT实际上只是加减运算。

三、蝶形结 即蝶式计算结构也即为蝶式信号流图 上面频域中前/后半部分表示式可以用蝶形信号流图表示。 作图要素: (1)左边两路为输入 (2)右边两路为输出 (3)中间以一个小圆表示加、减运算(右上路为相加输出、右下路为相减输出) X1(k) X2(k) (4)如果在某一支路上信号需要进行相乘运算,则在该支路上标以箭头,将相乘的系数标在箭头旁。 (5)当支路上没有箭头及系数时,则该支路的传输比为1。

蝶形结描述的另一种方法 X1(k) X2(k)

例子:求 N=23=8点FFT变换 (1)先按N=8-->N/2=4,做4点的DFT: 先将N=8DFT分解成2个4点DFT: 可知:时域上:x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上:X(0)~X(3),由X(k)给出 X(4)~X(7),由X(k+N/2)给出

(a)比较N=8点直接DFT与分解2个4点DFT的FFT运算量 N=8点的直接DFT的计算量为:N2次(64次)复数相乘,N(N-1)次(8*(8-1)=56次)复数相加.共计120次。

(b)求 一个蝶形结需要的运算量 要运算一个蝶形结,需要一次乘法 , 两次加法。

(c)分解为两个N/2=4点的DFT的运算量 奇数 其复数相乘为 复数相加为 偶数 其复数相乘为 复数相加为

(d)用2个4点来求N=8点的FFT所需的运算量 再将N/2点(4点)合成N点(8点)DFT时,需要进行N/2个蝶形运算 还需N/2次(4次)乘法 及 次(8次)加法运算。

(e)将N=8点分解成2个4点的DFT的信号流图 x1(r) X1(0) x(0) x(2) x(4) x(6) 4点 DFT 偶数序列 X(0) X(1) X(2) X(3) X1(1) X1(2) X1(3) x2(r) X2(0) x(1) x(3) x(5) x(7) 奇数序列 4点 DFT X2(1) X(4) X(5) X(6) X(7) X2(2) X2(3) X(4)~X(7) 同学们自已写

(2)N/2(4点)-->N/4(2点)FFT (a)先将4点分解成2点的DFT: 若将N/2(4点)子序列按奇/偶分解成两个N/4点(2点)子序列。即将x1(r)和x2(r)分解成奇、偶两个N/4点(2点)点的子序列。

(b)求2点的DFT

(c)一个2点的DFT蝶形流图 X1(0) X1(1) X1(2) X1(3) x(0) x(4) X3(0) 2点DFT X3(1)

(d)另一个2点的DFT蝶形流图 同理: X2(0) X2(1) X2(2) X2(3) x(1) x(5) X5(0) 2点DFT

(3)将N/4(2点)DFT再分解成2个1点的DFT (a)求2个一点的DFT 最后剩下两点DFT,它可分解成两个一点DFT,但一点DFT就等于输入信号本身,所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。

(b)2个1点的DFT蝶形流图 X3(0) 1点DFT x(0) X3(1) 1点DFT x(4) 进一步简化为蝶形流图: X3(0)

(4)一个完整N=8的按时间抽取FFT的运算流图 m=0 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) m=1 m=2 x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7)

四、FFT算法中一些概念 (1)“级”概念 将N 点DFT先分成两个N/2点DFT,再是四个N/4点DFT…直至N/2个两点DFT.每分一次称为“一”级运算。 因为N=2M所以N点DFT可分成M级 如上图所示依次m=0,m=1….M-1共M级

(2)“组”概念 每一级都有N/2个蝶形单元,例如:N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组,每一组具有相同的结构,相同的 因子分布,第m级的组数为: 例:N=8=23,分3级。 m=0级,分成四组,每组系数为 m=1级,分成二组,每组系数为 m=2级,分成一组,每组系数为

(3) 因子的分布 结论:每级由后向前(m由M-1-->0级)推进一级,则此系数为后级系数中偶数序号的那一半。

(4)按时间抽取法 由于每一步分解都是基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列,所以称为“按时间抽取法”. 2点DFT 两个2点 DFT x(n) 两个 4点DFT 两个 N/2点 DFT X1(k) 2点DFT 两个2点 DFT 2点DFT X(k) 2点DFT …... 两个2点 DFT 2点DFT 两个 4点DFT 2点DFT X2(k) 2点DFT 两个2点 DFT 2点DFT

五、按时间抽取的FFT算法与直接计算DFT运算量的比较 每级都由N/2个蝶形单元构成,因此每一级运算都需要N/2次复乘和N次复加(每个结加减各一次)。这样(N=2M)M级运算共需要: 复乘次数: 复加次数: 可以得出如下结论: 按时间抽取法所需的复乘数和复加数都是与 成正比。而直接计算DFT时所需的复乘数与复加数则都是与N2成正比.(复乘数md=N2,复加数ad=N(N-1)≈N2)

例子 看N=8点和N=1024点时直接计算DFT与用基2-按时间抽取法FFT的运算量。

作业 1. P200,2及3中的DIT部分

六、按时间抽取FFT算法的特点 根据DIT基2-FFT算法原理,能得出任何N=2M点的FFT信号流图,并进而得出FFT计算程序流程图。最后总结出按时间抽取法解过程的规律。 1.原位运算(in-place) 2.码位倒读规则

1.原位运算(in-place) 原位运算的结构,可以节省存储单元,降低设备成本。 定义:当数据输入到存储器以后,每一组运算的结果,仍然存放在这同一组存储器中直到最后输出。 X3(0) X3(1) x(0) x(4)

例子 例:N=8 FFT运算,输入: A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0) A(1) A(0)=X(0) A(1)=X(1) A(2)=X(2) A(3)=X(3) A(4)=X(4) A(5)=X(5) A(6)=X(6) A(7)=X(7) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) R1 R1 R1 R2 R1 R2 R1 R3 R1 R4 R2 R1 看出:用原位运算结构运算后,A(0)…A(7)正好顺序存放X(0)…X(7),可以直接顺序输出。

2.码位倒读规则 我们从输入序列的序号及整序规律得到码位倒读规则。由N=8蝶形图看出:原位计算时,FFT输出的X(k)的次序正好是顺序排列的,即X(0)…X(7),但输入x(n)都不能按自然顺序存入到存储单元中,而是按x(0),x(4),x(2), x(6)….的顺序存入存储单元即为乱序输入,顺序输出。这种顺序看起来相当杂乱,然而它是有规律的。即码位倒读规则。

例子 以N=8为例: 自然顺序n 二进制码表示 码位倒读 码位倒置顺序n’ 1 2 3 4 5 6 7 000 001 010 011 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 000 100 010 110 001 101 011 111 4 2 6 1 5 3 7 看出:码位倒读后的顺序刚好是数据送入计算机内的顺序。

整序重排子程序 具体执行时,只须将1与4对调送入,3与6对调送入,而0,2,5,7不变,仅需要一个中间存储单元。 在实际运算时,先按自然顺序将输入序列存入存储单元,再通过变址运算将自然顺序变换成按时间抽取的FFT算法要求的顺序。变址的过程可以用程序安排加以实现--称为“整序”或“重排”(采用码位倒读)且注意: (1)当n=n’时,数据不必调换; (2)当n≠n’时,必须将原来存放数据x(n)送入暂存器R,再将x(n’)送入x(n),R中内容送x(n’).进行数据对调。 (3)为了避免再次考虑前面已调换过的数据,保证调换只进行一次,否则又变回原状。n’>n时,调换。 n 1 2 3 4 5 6 7 n’ 4 2 6 1 5 3 7

作业 编写N=128点的基2--按时间抽取的FFT算法。要求用C语言编写.

七、按时间抽取的FFT算法的若干变体 1.思路 对于任何流图,只要保持各节点所连续的支路及其传输系数不变,则不论节点位置怎么排列所得流图总是等效的,最后所得结果都是x(n)的离散付里叶变换的正确结果。只是数据的提取和存放的次序不同而已。

(2)输入是自然顺序而输出是乱序 将原先中与x(4)水平相邻的所有节点跟x(1)水平相邻的所有节点位置对调;将原先中与x(6)水平相邻的所有节点跟x(3)水平相邻的所有节点位置对调,其余诸节点保持不变,则可得: x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) X(0) X(4) X(2) X(6) X(1) X(3) X(5) X(7) 它与输入是乱序、输出顺序比较,看出:相同点:运算量一样;不同点:第一是数据存入方式不同;第二是取用系数的顺序不同。

(2)输入和输出都是自然顺序 对输入自然顺序,输出乱序的第二级,第三级节点作调整,可得输入输出都是顺序,无需数据重排: (1)它失掉了“原位运算”的性质。(2)为了变换N点数据,至少需要2N个复数单元。在内存比较紧张时,而对输入数据整序并不困难时一般不用。为了争取速度,才采取这种变体。 x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)