《快速傅里叶变换课件》由会员分享，可在线阅读，更多相关《快速傅里叶变换课件（65页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 第四章 快速傅里叶变换 Fast Fourier Transform福建农林大学金山学院信息与机电工程系 ( )数字信号处理 Digital Signal Processing第 2 页 本章内容u介绍傅里叶变换的一些快速算法u快速算法的思想根据原始变换定义的运算规律，及其中某些算 子的特殊性，找出减少乘法和加法运算次数的有 效途径，实现原始变换的各种高效算法。第 3 页 u了解直接计算N点DFT的运算量u了解减少运算量的基本途径 u理解按时间抽取的基-2FFT算法的算法原理、运算 流图、所需计算量和算法特点 u了解按时间抽取的基-2FFT算法的编程思想u理解按频率抽取的基-2FF
2、T算法的算法原理、运算 流图、所需计算量和算法特点本章学习目标第 4 页 u 离散傅里叶变换不仅具有明确的物理意义，更便 于用计算机处理。但是，直至上个世纪六十年代 ，由于数字计算机的处理速度较低以及离散傅里 叶变换的计算量较大，离散傅里叶变换长期得不 到真正的应用，快速离散傅里叶变换算法的提出 ，才得以显现出离散傅里叶变换的强大功能，并 被广泛地应用于各种数字信号处理系统中。近年 来，计算机的处理速率有了惊人的发展，同时在 数字信号处理领域出现了许多新的方法，但在许 多应用中始终无法替代离散傅里叶变换及其快速 算法。 4.1 引言第 5 页 FFT产生故事虽然频谱分析和DFT运算很重要，但在
3、很长一段时间里，由于DFT运 算复杂，并没有得到真正的运用，而频谱分析仍大多采用模拟信号滤波 的方法解决。当时加文(Garwin)在自已的研究中极需要一个计算傅里叶变换的快速 方法。他注意到图基(J.W.Turkey)正在写有关傅里叶变换的文章，因此详 细询问了图基关于计算傅里叶变换的技术知识。图基概括地对加文介绍 了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算法。在 加文的迫切要求下，库利很快设计出一个计算机程序。1965年库利-图基 在、Mathematic of Computation 杂志上发表了著名的“机器 计算傅里级数的一种算法”文章，提出一种快速计算DFT
4、的方法和计算机 程序-揭开了FFT发展史上的第一页。促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成 ，电子数字计算机的条件， 使DFT的运算大简化了。1984年，法国的杜梅尔(P.Dohamel)和霍尔曼(H.Hollmann)将基2分解 和基4分解糅合在一起，提出了分裂基FFT算法。其运算量比前几种算法 都有所减少，运算流图却与基2FFT很接近，运算程序也很短。它是目前 一种实用的高效新算法。第 6 页 4.2 基2FFT算法u有限长序列通过离散傅里叶变换 (DFT)将其频域 离散化成有限长序列。但其计算量太大(与N的平 方成正比）,很难实时地处理问题，因此引出了快
5、速傅里叶变换(FFT)。 u FFT并不是一种新的变换形式，它只是DFT的一种 快速算法，并且根据对序列分解与选取方法的不 同而产生了FFT的多种算法。 u FFT在离散傅里叶反变换、线性卷积和线性相关 等方面也有重要应用。第 7 页 问题提出： 设有限长序列x(n)，非零值长度为N，计算对x(n)进行一次DFT运算，共需多大的运算工作量?4.2.1 直接计算DFT的特点及减少 运算量的基本途径第 8 页 其中x(n)为复数， 也为复数，所以DFT与IDFT二者计算量相同。1.比较DFT与IDFT的运算量4.2.1 直接计算DFT的特点及减少 运算量的基本途径第 9 页 计算一个X(k)(一个
6、频率成分)值，运算量为例k=1则要进行N次复数乘法，(N-1)次复数加法，所以， 要完成整个DFT运算，其计算量为：N*N次复数相乘和N*(N-1)次复数加法4.2.1 直接计算DFT的特点及减少 运算量的基本途径2.以DFT为例计算复数运算量第 10 页 一个复数乘法包括4个实数乘法和2个实数加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)所以所有X(k)就要4N2次实数乘法运算,2N22N(N- 1) N(4N-2)次实数加法运算。当N很大时,运算量 将是惊人的, 这样,难以做到实时处理。 4次实数乘法2次实数加法4.2.1 直接计算DFT的特点及减少 运算量的基本途径3.
7、一次复数乘法换算成实数运算量第 11 页 例1:当N=1024点时，直接计算DFT需要：N2=220=1048576次，即一百多万次的复乘运算，这 对实时性很强的信号处理(如雷达信号处理)来讲，它 对计算速度有十分苛刻的要求迫切需要改进DFT 的计算方法，以减少总的运算次数。例2：石油勘探，24道记录，每道波形记录长度5秒 ，若每秒抽样500点/秒，每道总抽样点数 =500*5=2500点，24道总抽样点数=24*2500=6万点 ，DFT运算时间=N2=(60000)2=36*108次4.2.1 直接计算DFT的特点及减少 运算量的基本途径3.一次复数乘法换算成实数运算量第 12 页 FFT
8、算法对于N点DFT,仅需(N/2)log2N 次复数乘法运算和Nlog2N 次复数加法。4.2.1 直接计算DFT的特点及减少 运算量的基本途径4、 FFT的计算工作量第 13 页 如果计算机的速度为平均每次复数乘需要510-6秒 ， 每次复加需要110-6秒，用来计算N=1024点DFT, 问1)直接计算需要多少时间？2）用FFT算法计算需要 多少时间？4.2.1 直接计算DFT的特点及减少 运算量的基本途径4、 FFT的计算工作量第 14 页 u 利用 的特性4.2.1 直接计算DFT的特点及减少 运算量的基本途径第 15 页 利用以上特性，得到改进DFT直接算法的方法。4.2.1 直接计
9、算DFT的特点及减少 运算量的基本途径u 例第 16 页 快速傅里叶变换( FFT ) 就是在此特性基础上发展起来的： （1）利用DFT系数的对称性和周期性,合并DFT运算中的某些项； （2）将长序列分解为短序列,从而减少其运算量。 因合并与分解方法的不同产生了多种DFT的快速 算法。4.2.1 直接计算DFT的特点及减少 运算量的基本途径5、DFT的基本思想第 17 页 1.按抽取方法分：时间抽取法(DIT Decimation-In-Time);频率抽取法(DIF Decimation-In-Frequency)2.按“基数”分： 基-2FFT算法；基-4FFT算法；混合基FFT算法 ；分
10、裂基FFT算法3.其它方法： 线性调频Z变换(Chrip-z法)4.2.1 直接计算DFT的特点及减少 运算量的基本途径6、FFT算法分类：第 18 页 1、时域抽取算法原理u设输入序列长度为N=2M(M为正整数），将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。u其中基数2-N=2M，M为整数。若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M。4.2.2 时域抽取法基2FFT基本原理 Decimation-in-Time(DIT)第 19 页 设一序列x(n)的长度为L=9，应加零补长为N=24=16 应补7个零值。0 1 2 3 4 5
11、 6 7 8 9 10 11 12 13 14 15 nx(n)1、时域抽取算法原理4.2.2 时域抽取法基2FFT基本原理 Decimation-in-Time(DIT)第 20 页 设序列点数 N = 2M，M为整数。若不满足，则补零2、算法步骤4.2.2 时域抽取法基2FFT基本原理 Decimation-in-Time(DIT)第 21 页 第 22 页 4.2.2 时域抽取法基2FFT基本原理 Decimation-in-Time(DIT)2、算法步骤第 23 页 4.2.2 时域抽取法基2FFT基本原理 Decimation-in-Time(DIT)3、蝶形运算1 1 1 1-1第
12、 24 页 (1)N/2点的DFT运算量:复乘次数: 复加次数: (2)两个N/2点的DFT运算量:复乘次数: 复加次数: (3)N/2个蝶形运算的运算量:复乘次数: 复加次数: 复乘 :复加:总共运算量:u 可见，N点DFT的复乘为N2，复加N(N-1)；与分解 后相比可知，计算工作点差不多减少 一半。4.2.2 时域抽取法基2FFT基本原理 Decimation-in-Time(DIT)第 25 页 例 8点FFT的算法首先可以分解为两个N/2=4点的DFT。具体方法如下:第 26 页 X(5)X(4)X(7)同学们自已写（1）N=8点分解成2个4点的DFT的信号流图x1(0)=x(0)
13、x1(1)=x(2) N/2点 x1(2)=x(4) DFT x1(3)=x(6) x2(0)=x(1) x2(1)=x(3) N/2点 x2(2)=x(5) DFT x2(3)=x(7)X1(0)X1(1) X1(2)X1(3)X2(0) X2(1)X2(2)X2(3)WN2NW1NW0-1-1-1X(0) X(1) X(2) X(3) X(4)X(6) X(7)WN3-1第 27 页 由于N=2 L ,所以 N/2仍为偶数,可以进一步把每 个N/2点的序列再按其奇偶部分分解为两个N/4的子 序列。(2) N/2(4点)N/4(2点)FFT第 28 页 (2) N/2(4点)N/4(2点)F
14、FT第 29 页 02NN02NN-1-1-1-1-1-1WWWWX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)N/4 DFTN/4 DFTN/4 DFTN/4 DFTx(0)x(2)x(6)x(1)x(5)x(3)x(7)x(4)WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)-1-1第 30 页 最后剩下两点DFT,它可分解成两个一点DFT，但一点 DFT就等于输入信号本身，所以两点DFT可用一个蝶形结 表示。取x(0)、x(4)为例。(3) N/4（2点）2个1点DFT第 31 页 1点DFTx(0)1点DFTx(4)X3(0)X3(1)2个1点的DFT蝶形流图-1(3) N/4（2点）2个1点DFT第 32 页 一个完整的按时间抽取的8点FFT第 33 页 u1）输入倒位序，输出自然序自然顺序n 二进制n2 n1 n0 倒位序二进制n0 n1 n2 倒位顺序n0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5
