《数字信号处理》课件12

1、第 4 2）,数字信号处理,第4章 快速傅里叶变换,引言 直接计算DFT的问题及改进途径 按时间抽选的基-2FFT算法（Cooley-Tukey算法） 按频率抽选的基-2FFT算法（Sande-Tukey算法） 离散傅里叶反变换的快速计算方法,4.3 按时间抽选（DIT）的基 -2 FFT算法,4.3.1 算法原理,步骤：将 x(n)按 n 先偶后奇分解为两个N/2点的子序列,基-2 FFT算法,且满足N=2L，L为正整数,时间抽选法蝶形运算流图符号,按时间抽选，将一个N点DFT分解为两个N/2点DFT（N=8）,复数乘法：,2个 点DFT,蝶形图部分,次复数乘法,复数加法：,2个 点DFT,

2、蝶形图部分,次复数乘法,次复数加法,将N点DFT，进行一次分解后，运算工作量节省了近一半,由于N=2L， 仍是偶数,可以进一步把每个 点子序列分解为两个 点的子序列,，,一 点DFT进一步分解为两个 点DFT,式中,按时间抽选，将一个N点DFT分解为两个N/2点DFT（N=8）,由两个N/4点DFT组合成一个N/2点DFT,按时间抽选，将一个N点DFT分解为四个N/4点DFT （N=8）,按时间抽选，将一个N点DFT分解为两个N/2点DFT（N=8）,X2(k)也可进行同样的分解：,式中,按时间抽选，将一个N点DFT分解为四个N/4点DFT （N=8）,N=8按时间抽选法FFT运算流图,按时间

3、抽选：N=2L时，共有L级蝶形，每级由N/2个蝶形组成,L 级蝶形运算需要： 复数乘法 复数加法,式中，数学符号lb=log2,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 ， 用

4、每秒可做10万次复数乘法的计算机，需要近3000小时。,例：对10241024点的二维图像做DFT变换，计算机每秒可做 10万次复数乘法，需要多少时间？ （忽略加法运算时间）,直接计算DFT与FFT计算量之比为,同样的计算机，应用FFT算法进行DFT变换需要0.2ms。,4.3.3 按时间抽选的FFT算法的特点,1分组的方法，每一步分解都是按输入序列在时域上是 属于偶数还是奇数分为两组，故称为“按时间抽选”法。,3. 原位运算（同址运算） 当数据输入到存储器后，每一级运算的结果仍然存储在这 同一组存储器中，直到最后输出，中间无需其他的存储器。,每一级运算均可在原位进行，这种原位运算的结构可以节

5、省存储单元，降低设备成本。,4. 倒位序规律,按时间抽选FFT 输出X(k) 按自然顺序排列在存储单元,输入 x(n) 不是按自然顺序排列,是由于x(n)按标号n先偶后奇不断分组造成的,倒位序的规律：,例如,自然顺序二进制数和相应的倒位序二进制数 （N=8）,第4章 快速傅里叶变换,引言 直接计算DFT的问题及改进途径 按时间抽选的基-2FFT算法（Cooley-Tukey算法） 按频率抽选的基-2FFT算法（Sande-Tukey算法） 离散傅里叶反变换的快速计算方法,4.4 按频率抽选（DIF）的基 -2 FFT算法,4.3.1 算法原理,步骤：将 x(n)按 n 前后对半分开为两个N/2

6、点的子序列,基-2 FFT算法,且满足N=2L，L为正整数,k=0, 1, , N-1,将DFT化为,k=0, 1, , N-1,按k的奇偶可将 X(k) 分为两部分:,下式：前一半输入与后一半输入之差再与WNn之积的N/2点DFT。,上式：前一半输入与后一半输入之和的N/2点DFT，,频率抽取法蝶形运算单元,按频率抽取的第一次分解,按频率抽取的第二次分解,按频率抽取的FFT（N=8）信号流图,4.4.2 按频率抽选的FFT算法的特点,1不断将序列分为前后两半，直到2点DFT,2分组的方法，从频率上看，每一次都是按输出在频域上是 属于偶数还是奇数分为两组，故称为“按频率抽选”法。,1按时间抽选

7、：输入是倒位序， 输出是自然顺序； 按频率抽选：输入是自然顺序， 输出是倒位序。,DIT法与DIF法比较：,二、相同点 运算量相同,一、不同点,2按时间抽选：复数乘法出现在加、减运算之前； 按频率抽选：复数乘法出现在减法运算之后。,第4章 快速傅里叶变换,引言 直接计算DFT的问题及改进途径 按时间抽选的基-2FFT算法（Cooley-Tukey算法） 按频率抽选的基-2FFT算法（Sande-Tukey算法） 离散傅里叶反变换的快速计算方法,4.5 离散傅里叶反变换的快速计算方法,1）DFT中的 IDFT中的,2）IDFT 中有常数,区别：,按频率抽取的FFT（N=8）信号流图,按时间抽选的