第第 4 4 章章 （2 2）数数字字信信号号处处理理哈尔滨工程大学哈尔滨工程大学哈尔滨工程大学哈尔滨工程大学 信息与通信工程学院信息与通信工程学院信息与通信工程学院信息与通信工程学院第第4 4章章 快速傅里叶变换快速傅里叶变换 v 引言引言v 直接计算直接计算DFT的问题及改进途径的问题及改进途径v 按时间抽选的基按时间抽选的基-2FFT算法（算法（Cooley-Tukey算法）算法）v 按频率抽选的基按频率抽选的基-2FFT算法（算法（Sande-Tukey算法）算法）v 离散傅里叶反变换的快速计算方法离散傅里叶反变换的快速计算方法4.3 4.3 按时间抽选（按时间抽选（DITDIT）的基的基 -2 FFT-2 FFT算法算法 4.3.1 4.3.1 算法原理算法原理设序列 x (n) 长度为N，步骤：将 x(n)按 n 先偶后奇分解为两个N/2点的子序列 基-2 FFT算法第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换且满足N=2L，L为正整数时间抽选法蝶形运算流图符号 按时间抽选，将一个N点DFT分解为两个N/2点DFT（N=8） 第第第第4 4章章章章 快速傅里叶快速傅里叶快速傅里叶快速傅里叶变换变换复数乘法：2个 点DFT蝶形图部分1个 点DFT次复数乘法第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换复数加法：2个 点DFT蝶形图部分1个 点DFT第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换N点DFT，一次分解后次复数乘法次复数加法将N点DFT，进行一次分解后，运算工作量节省了近一半N点DFT，不进行分解次复数加法次复数乘法第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换由于N=2L， 仍是偶数可以进一步把每个 点子序列分解为两个 点的子序列 ， 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换一 点DFT进一步分解为两个 点DFT 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换式中 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按时间抽选，将一个N点DFT分解为两个N/2点DFT（N=8） 由两个N/4点DFT组合成一个N/2点DFT 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按时间抽选，将一个N点DFT分解为四个N/4点DFT （N=8）第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按时间抽选，将一个N点DFT分解为两个N/2点DFT（N=8） X2(k)也可进行同样的分解：也可进行同样的分解： 式中式中 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按时间抽选，将一个N点DFT分解为四个N/4点DFT （N=8）第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换N=8按时间抽选法FFT运算流图按时间抽选：N=2L时，共有L级蝶形，每级由N/2个蝶形组成L 级蝶形运算需要： 复数乘法 复数加法式中，数学符号lb=log2第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换4.3.2 4.3.2 运算量运算量 每一级蝶形运算需要：复数乘法 N/2 次 复数加法 N 次当N=2048时，直接计算DFT的运算量是FFT运算量的372.4倍。当点数N越大时，FFT的优点更为明显。 直接计算DFT与FFT算法的计算量之比为 计算机乘法运算所需的时间比加法运算所需的时间多得多，故以乘法为例，比较 DFT和FFT的运算量。直接DFT复数乘法次数N 2，FFT复数乘法次数 解解: 直接计算直接计算DFT复乘次数（复乘次数（N )2=（10241024)2= 240 1012 ， 用每秒可做用每秒可做10万次复数乘法的计算机，需要近万次复数乘法的计算机，需要近3000小时小时。 例：对例：对10241024点的二维图像做点的二维图像做DFT变换，计算机每秒可做变换，计算机每秒可做 10万次复数乘法，需要多少时间？万次复数乘法，需要多少时间？ （忽略加法运算时间）（忽略加法运算时间） 直接计算直接计算DFT与与FFT计算量之比为计算量之比为 同样的计算机，应用同样的计算机，应用FFT算法进行算法进行DFT变换需要变换需要0.2ms。4.3.3 4.3.3 按时间抽选的按时间抽选的FFTFFT算法的特点算法的特点第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换1 1分组的方法，每一步分解都是按输入序列在时域上是分组的方法，每一步分解都是按输入序列在时域上是 属于偶数还是奇数分为两组，故称为属于偶数还是奇数分为两组，故称为“按时间抽选按时间抽选”法。法。2 2任何任何N= 2 2L点点DFT，通过，通过L次分解，完全成为次分解，完全成为2点点DFT，2点点DFT实际上只有加、减运算，为了方便比较和统一结实际上只有加、减运算，为了方便比较和统一结构，仍然用构，仍然用WN0做系数的蝶形运算来表示。做系数的蝶形运算来表示。 3. 3. 原位运算（同址运算）原位运算（同址运算） 当数据输入到存储器后，每一级运算的结果仍然存储在这当数据输入到存储器后，每一级运算的结果仍然存储在这 同一组存储器中，直到最后输出，中间无需其他的存储器。同一组存储器中，直到最后输出，中间无需其他的存储器。每每一一级级运运算算均均可可在在原原位位进进行行，这这种种原原位位运运算算的的结结构构可可以以节省存储单元，降低设备成本。节省存储单元，降低设备成本。第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换4. 4. 倒位序规律倒位序规律第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按时间抽选按时间抽选FFT FFT 输出输出X( (k) ) 按自然顺序排列在存储单元按自然顺序排列在存储单元 输入输入 x( (n) ) 不是按自然顺序排列不是按自然顺序排列是由于是由于x( (n) )按标号按标号n先偶后奇不断分组造成的先偶后奇不断分组造成的倒位序的规律：倒位序的规律：例如例如自然顺序二进制数和相应的倒位序二进制自然顺序二进制数和相应的倒位序二进制数数 （N=8）自然顺序（n） 二进制数 倒位序二进制数 倒位序（ ） 0123456700000101001110010111011100010001011000110101111104261537第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换第第4 4章章 快速傅里叶变换快速傅里叶变换 v 引言引言v 直接计算直接计算DFT的问题及改进途径的问题及改进途径v 按时间抽选的基按时间抽选的基-2FFT算法（算法（Cooley-Tukey算法）算法）v 按频率抽选的基按频率抽选的基-2FFT算法（算法（Sande-Tukey算法）算法）v 离散傅里叶反变换的快速计算方法离散傅里叶反变换的快速计算方法4.4 4.4 按频率抽选（按频率抽选（DIFDIF）的基）的基 -2 FFT-2 FFT算法算法 4.3.1 4.3.1 算法原理算法原理设序列 x (n) 长度为N，步骤：将 x(n)按 n 前后对半分开为两个N/2点的子序列 基-2 FFT算法第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换且满足N=2L，L为正整数k=0, 1, , N-1 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换将DFT化为 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换k=0, 1, , N-1 k为奇数时，( 1) k = 1第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按k的奇偶可将 X(k) 分为两部分: k为偶数时， ( 1) k = 1；第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换下式：前一半输入与后一半输入之差再与WNn之积的N/2点DFT。第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换上式：前一半输入与后一半输入之和的N/2点DFT，第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换频率抽取法蝶形运算单元 按频率抽取的第一次分解 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按频率抽取的第二次分解 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按频率抽取的FFT（N=8）信号流图 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换4.4.2 4.4.2 按频率抽选的按频率抽选的FFTFFT算法的特点算法的特点第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换1 1不断将序列分为前后两半，直到不断将序列分为前后两半，直到2 2点点DFT2 2分组的方法，从频率上看，每一次都是按输出在频域上是分组的方法，从频率上看，每一次都是按输出在频域上是 属于偶数还是奇数分为两组，故称为属于偶数还是奇数分为两组，故称为“按频率抽选按频率抽选”法。法。1按时间抽选：输入是倒位序， 输出是自然顺序； 按频率抽选：输入是自然顺序， 输出是倒位序。第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换DIT法与法与DIF法比较：法比较：二、相同点 运算量相同一、不同点2按时间抽选：复数乘法出现在加、减运算之前； 按频率抽选：复数乘法出现在减法运算之后。第第4 4章章 快速傅里叶变换快速傅里叶变换 v 引言引言v 直接计算直接计算DFT的问题及改进途径的问题及改进途径v 按时间抽选的基按时间抽选的基-2FFT算法（算法（Cooley-Tukey算法）算法）v 按频率抽选的基按频率抽选的基-2FFT算法（算法（Sande-Tukey算法）算法）v 离散傅里叶反变换的快速计算方法离散傅里叶反变换的快速计算方法第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换4.5 4.5 离散傅里叶反变换的快速计算方法离散傅里叶反变换的快速计算方法 1 1）DFT中的中的 IDFT中的中的 2 2）I IDFT 中有常数中有常数区别：区别：按频率抽取的FFT（N=8）信号流图 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按时间抽选的 IFFT （N =8）信号流图第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换按时间抽选的 FFT按频率抽选的 IFFT按频率抽选的 FFT按时间抽选的 IFFT稍作改动FFT程序，计算IFFT的方法第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换完全不改变FFT程序，计算IFFT的方法 第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换第4章 结束第第第第4 4 4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换