复旦大学：《数字信号处理》课程教学资源（课件讲稿）第六章 快速傅里叶变换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              