复旦大学:《数字信号处理》课程教学资源(课件讲稿)第六章 快速傅里叶变换FFT

2013年秋季学期 3教105 数字信号处理 第六章快速傅里叶变换FFT 身復g大 FUDAN UNIVERSITY
数字信号处理 第六章 快速傅里叶变换FFT 2013年秋季学期 3教105

第六章快速傅里叶变换FFT 60引言 ●6.1基2时间抽取法 62基2频率抽取法 6.3 FFT 64实序列FFT的高效算法 6.5*基4和混合基FFT算法(扩展部分) 6.6*线性调频Z变换算法
第六章 快速傅里叶变换FFT 6.0 引言 6.1 基2时间抽取法 6.2 基2频率抽取法 6.3 IFFT 6.4 实序列FFT的高效算法 6.5 *基4和混合基 FFT算法(扩展部分) 6.6 *线性调频Z变换算法 2

本章主要学习 1.掌握基2时间抽取和基2频率抽取FFT算法的基本思想和 方法。 2.了解基4时间抽取FFT算法的基本原理。 3.掌握实序列FFT计算,以及由N点序列FFT计算2N点序 列FFT的方法。 4.掌握利用FFT计算DFT的过程以及FT实现的原理 本章的重点是基2时间抽取FFT算法的基本原理, FFT蝶形运算流图 本章的难点是由短序列的DFT表达相应长序列的 DFT的基本原理及方法
1. 掌握基2时间抽取和基2频率抽取FFT算法的基本思想和 方法 。 2. 了解基4时间抽取FFT算法的基本原理 。 3. 掌握实序列FFT计算,以及由N点序列FFT计算2N点序 列FFT的方法 。 4. 掌握利用FFT计算IDFT的过程以及IFFT实现的原理 。 本章主要学习 3 本章的重点是基2时间抽取FFT算法的基本原理, FFT蝶形运算流图 本章的难点是由短序列的DFT表达相应长序列的 DFT的基本原理及方法

第六章快速傅里叶变换FFT 6.1基2时间抽取法 6.2基2频率抽取法 o6.3 FFT 6.4实序列FFT的高效算法 6.5基4和混合基FFT算法(扩展部分) 6.6*线性调频Z变换算法
第六章 快速傅里叶变换FFT 6.1 基2时间抽取法 6.2 基2频率抽取法 6.3 IFFT 6.4 实序列FFT的高效算法 6.5 *基4和混合基 FFT算法(扩展部分) 6.6 *线性调频Z变换算法 4

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

第六章快速傅里叶变换:引言 1669: Newton偶然发现了光谱但却没有意识到”频率”的概念( corpuscular theory of light, no waves) 1807: Fourier分析诞生 19h/20 th century:出现了两种 Fourier分析方法 Continuous& Discrete CONTINUOUS → Fourier将 Fourier分析推广至任意函数( Fourier Transform) Dirichlet等人研究了 Fourier级数的收敛问题 因不同的需要产生了不同形式的FTe.9. Short Time FT- speech analysis) DISCRETE: Fast calculation methods(FFT) →1965-| BM,s Cooley& Tukey发明了FFT算法(“ An algorithm for the machine calculation of complex Fourier series) 此后相继出现了各种用于计算机平台的改进FFT算法
第六章 快速傅里叶变换: 引言 6

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

FFT: Fast Fourier transform 1965年, James W. Cooley和 John W. Tukey在《计算数学》(《 Mathematics of Computation》)上发表了“一种用机器计算复序列傅 立叶级数的算法( An algorithm for the machine calculation of complex Fourier series)”论文。 自此之后,新的算法不断涌现。一种是对N等于2的整数次幂的算法 如基2算法,基4算法。另一种是N不等于2的整数次幂的算法,例如 Winagrad算法,素因子算法。 Calculation of B: Jena w Cadley and Joan W Tuley he as train untaa ata) M eagle a th prin=pal John W. Tukey A础计中h切 Dr James W. cooley Worked at IBM Watson Research Center in Yorktown Heights, (1915-2000) N.Y After his retirement from IBM x,1 in 1991, he joined the Electrica 出 Engineering Department at the University of Rhode islan
1965 年,James W. Cooley 和 John W. Tukey 在《计算数学》(《 Mathematics of Computation》)上发表了“ 一种用机器计算复序列傅 立叶级数的算法(An algorithm for the machine calculation of complex Fourier series)” 论文。 自此之后,新的算法不断涌现。一种是对N等于 2 的整数次幂的算法, 如基 2 算法,基 4 算法。另一种是N不等于 2 的整数次幂的算法,例如 Winagrad 算法,素因子算法。 FFT: Fast Fourier Transform Dr. James W. Cooley Worked at IBM Watson Research Center in Yorktown Heights, N.Y..After his retirement from IBM in 1991, he joined the Electrical Engineering Department at the University of Rhode Island. John W. Tukey (1915 – 2000)

●问题提出:设有限长序列x(n),非零值长度为N,计算对 x(m)进行一次DFT运算,共需多大的运算工作量? x(n)->X(k)=>x(n)WN k=0.1.N-1 X(k) IDFT )x(n)= ∑ X(kWN k n=0,1,…N-1 k=0 zTk 其中x(n)为复数,WM=eN也为复数 所以DFT与IDFT二者计算量相同
9 问题提出: 设有限长序列x(n),非零值长度为N,计算对 x(n)进行一次DFT运算,共需多大的运算工作量? 1 0 N n kn N DFT x(n) X (k) x(n)W k 0,1, N 1 1 0 N k kn N IDFT X (k) x(n) X (k)W n 0,1, N 1 其中x(n)为复数, 也为复数 所以DFT与IDFT二者计算量相同。kn N j kn N W e 2

6.0引言:直接计算DFT的运算量分析 k X(k)∑ 复数乘法复数加法 x(ne 每一个X(k) ∑ nk N个X(k) N(N-1) r(n N点DFT) (e+j)+(g+j)=(e+g)+j(f+h) a+ jb(c+ jd)=(ac-bd)+j(ad+cb) 实数乘法 实数加法 复加的加 次复乘 4 复乘的加 2 法次数 法次数 次复加 每一个X(k) AN 2N+2(N-1)=2(2N-1) N个X(k)N点DFT)4N2 2N(2N-1)
6.0 引言:直接计算 DFT 的运算量分析 10 复数乘法 复数加法 每一个X(k) N N – 1 N 个X(k) (N 点 DFT) N 2 N (N – 1) 实数乘法 实数加法 一次复乘 4 2 一次复加 2 每一个 X (k) 4N 2N+2 (N – 1)=2 (2N – 1) N个X (k) (N点DFT) 4N 2 2N (2N – 1) 1 0 1 0 2 X(k)= ( ) ( ) N n N nk N n j nk N x n n e W x a jb c jd ac bd j ad cb 复乘的加 法次数 复加的加 法次数 e jf g jh e g j f h
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 复旦大学:《数字信号处理》课程教学资源(课件讲稿)第五章 有限长离散变换.pdf
- 复旦大学:《数字信号处理》课程教学资源(课件讲稿)第四章 Z变换(定义、收敛域、基本性质、Z反变换、几种变换的对应关系、系统函数与频率特性).pdf
- 复旦大学:《数字信号处理》课程教学资源(课件讲稿)第三章 离散时间信号和系统的频域分析.pdf
- 复旦大学:《数字信号处理》课程教学资源(课件讲稿)第二章 离散时间信号和系统的时域分析.pdf
- 复旦大学:《数字信号处理》课程教学资源_第六章 习题解答.docx
- 复旦大学:《数字信号处理》课程教学资源_第六章 FFT习题解答.docx
- 复旦大学:《数字信号处理》课程教学资源_第八章 IIR滤波器 习题.docx
- 复旦大学:《数字信号处理》课程教学资源_第九章 FIR滤波器 习题.docx
- 复旦大学:《数字信号处理》课程教学资源_第三章习题.docx
- 复旦大学:《数字信号处理》课程教学资源_第七章 滤波器的网络结构 习题.docx
- 复旦大学:《数字信号处理》课程教学资源_IIR例题.pptx
- 复旦大学:《数字信号处理》课程教学资源_第四章 习题解答.docx
- 复旦大学:《数字信号处理》课程教学资源_第四章 习题解答.docx
- 复旦大学:《数字信号处理》课程教学资源_数字信号处理复习总结.docx
- 复旦大学:《数字信号处理》课程教学资源_课程各章重点.pdf
- 复旦大学:《光子学器件与工艺 Photonics Devices and Technology》教学课件_第十一章 光子学器件测试相关标准简介.pdf
- 复旦大学:《光子学器件与工艺 Photonics Devices and Technology》教学课件_第十章 光子学器件冷加工工艺简介.pdf
- 复旦大学:《光子学器件与工艺 Photonics Devices and Technology》教学课件_第九章 集成电路工艺简介——光子学器件中用到的微电子工艺(部分有源和无源器件用到的工艺).pdf
- 复旦大学:《光子学器件与工艺 Photonics Devices and Technology》教学课件_第八章 晶体硅太阳能电池.pdf
- 复旦大学:《光子学器件与工艺 Photonics Devices and Technology》教学课件_第七章 光子学薄膜、光学镀膜材料、光学薄膜制备的厚度监控.pdf
- 复旦大学:《数字信号处理》课程教学资源_数字信号处理习题和答案.docx
- 复旦大学:《数字信号处理》课程教学资源_数字信号处理第3讲习题课 - 第二次习题课.ppt
- 复旦大学:《数字信号处理》课程教学资源_第三次习题课.pptx
- 复旦大学:《数字信号处理》课程教学资源_时域离散信号和时域离散系统(习题).ppt
- 复旦大学:《数字信号处理》课程教学资源_时域离散信号和时域离散系统(习题和答案).ppt
- 复旦大学:《数字信号处理》课程教学资源_数字信号处理习题和答案.docx
- 复旦大学:《通信原理(A)》PPT教学课件_2015_02 第二章 概率论与随机过程.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2016_01 第一章 绪论.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2016_03 第三章 信道与噪声.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2016_04 第四章 连续波模拟调制.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2016_05 第五章 数字基带传输.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2016_06 第六章 模拟信号的数字传输.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2016_07 第七章 数字频带传输.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2016_08 第八章 数字信号的最佳接收.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2016_10 第十章 信道容量.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2018_02 第二章 概率论与随机过程.pptx
- 复旦大学:《通信原理(A)》PPT教学课件_2018_04 第四章 连续波模拟调制.pptx
- 延安大学:《电路分析基础》课程教学大纲 Fundamentals of Circuit Analysis.pdf
- 延安大学:《电路分析基础》课程教学资源(实验讲义)实验一 基本电工仪表的使用与典型电信号的观察.pdf
- 延安大学:《电路分析基础》课程教学资源(实验讲义)实验二 基尔霍夫定律的验证.pdf