《浙大宁波理工学院 数字信号处理-第四章快速傅立叶变换(new)》由会员分享，可在线阅读，更多相关《浙大宁波理工学院 数字信号处理-第四章快速傅立叶变换(new)（54页珍藏版）》请在金锄头文库上搜索。
1、数字信号处理第四章 快速傅立叶变换 4.2 直接计算DFT的问题及改进的途径设 为N点有限长序列，其DFT为一般： 为复数，计算一个 需要N次复数乘法 及N-1次复数加法。由于 一共有N个点，因此完成整个DFT运算 需要 次复数乘法及 复数加法。（1）（2）数字信号处理第四章 快速傅立叶变换 由于所以数字信号处理第四章 快速傅立叶变换 一次复数乘法需用四次实数乘法，一次复数加法则需二次实数加法。每运算一个 需4N次实数乘法及4（N-1)+2=4N-2次实数加法。所以这 个DFT运算总共需要 次实数乘法和 N（4N-2)次实数加法。K一定：N-1 次加法K一定：N-1 次加法K一定：N-1 次加
2、法K一定：N-1 次加法数字信号处理第四章 快速傅立叶变换 W因子性质：N，k均以N为周期数字信号处理第四章 快速傅立叶变换 4.3 按时间抽选（DIT)的基2FFT算法（库利图基算法）一：算法原理基2FFT：序列点数N为2的整数幂的FFT。将 的序列 （n=0,1,N-1)先按n的奇偶分成以下 两组：蝶形运算令：数字信号处理第四章 快速傅立叶变换 N点 DFT.N/2点 DFT.蝶形 运算N/2点 DFT.数字信号处理第四章 快速傅立叶变换 蝶形运算数字信号处理第四章 快速傅立叶变换 N/2点 DFT.N/4点 DFT.蝶形 运算N/4点 DFT.数字信号处理第四章 快速傅立叶变换 N/2点
3、 DFT.N/4点 DFT.蝶形 运算N/4点 DFT.数字信号处理第四章 快速傅立叶变换 令(4)(3)如下K周期为N/2数字信号处理第四章 快速傅立叶变换 将式（3）、式（4）用蝶形信号流图符号表示。当支路未标出系数时，则该 支路的传输系数为1图4-1时间抽选法蝶形运算流图符号1数字信号处理第四章 快速傅立叶变换 如果N=2数字信号处理第四章 快速傅立叶变换 1N=2数字信号处理第四章 快速傅立叶变换 如果N=4数字信号处理第四章 快速傅立叶变换 1N=4111数字信号处理第四章 快速傅立叶变换 N=8点的DFT可以分解成两个4点的DFT及蝶形运算上半部分下半部分序号 为偶 次序号 为奇
4、次数字信号处理第四章 快速傅立叶变换 然后将 的DFT继续分解，分解成 的DFT及蝶形运算。上半部 分下半 部分序 号 为 偶 次序 号 为 奇 次数字信号处理第四章 快速傅立叶变换 数字信号处理第四章 快速傅立叶变换 数字信号处理第四章 快速傅立叶变换 DIT-FFT算法特点：（1）同址运算：每一级的每个蝶形的输入与输出数 据，在运算前后可以存储在同一内存单元上称为同址 运算。（2）倒位序规律（基2）：DIT的基2FFT运算，其输 出X(k)是自然顺序，但输入x(n)是码位倒置的顺序。 在实际运算中，先按自然顺序输入x(n)存入存储单位 ，再通过变址运算，将自然顺序的存储转换为码位倒 置顺序
5、的存储。（3）蝶距及W因子的变换规律：各类蝶形运算两个 点相距的“距离”称蝶距。数字信号处理第四章 快速傅立叶变换 蝶距规律：最后一级的蝶距为N/2,依次向左为N/4,N/8,W因子规律：最后一级有一组，每组有N/2种，顺序为向左一级有两组，每组N/4种，顺序为其余类推。m：蝶形运算的 第m级数字信号处理第四章 快速傅立叶变换 二、运算量按时间抽选法FFT的流图可见，当 ,共有 L级碟形运算 ，每级都有 个碟形运算组成，每个碟形有一次复乘（4次实乘）、二次复加（4次实加） ，这样FFT运算总共需要复乘数：运算总共需要实乘数：复加数：实加数：数字信号处理第四章 快速傅立叶变换 数字信号处理第四章
6、 快速傅立叶变换 数字信号处理第四章 快速傅立叶变换 1、如果一台通用计算机的速度为平均每次复乘 ，每次复加比较1024点DFTx(n)与FFTx(n)复乘次数，复加次数数字信号处理第四章 快速傅立叶变换 解: 直接DFT计计算:复乘所需时间时间 :复加所需时间时间 :用FFT计计算:复乘所需时间时间 :复加所需时间时间 :数字信号处理第四章 快速傅立叶变换 4.4 按频率抽选（DIF）的基2 FFT算法（桑德图基算法）按频率抽选（DIF）的基2 FFT算法：把输出序列 （也是N点序列）按 的其顺序的奇偶分解为越来越短的序列。IFFTIFFT蝶形运算数字信号处理第四章 快速傅立叶变换 N点 D
7、FT.N/2点 DFT.蝶形 运算N/2点 DFT.数字信号处理第四章 快速傅立叶变换 IFFTIFFT蝶形运算数字信号处理第四章 快速傅立叶变换 IFFTIFFT蝶形运算数字信号处理第四章 快速傅立叶变换 一、算法原理设序列点数为 为整数，在把输出 的奇偶分组之 前，先把输入按n的顺序分成前后两半：按令数字信号处理第四章 快速傅立叶变换 由于K取偶数K取奇数数字信号处理第四章 快速傅立叶变换 令则数字信号处理第四章 快速傅立叶变换 数字信号处理第四章 快速傅立叶变换 当N=2时，1数字信号处理第四章 快速傅立叶变换 当N=4时，12点DFT,一个蝶形运算1数字信号处理第四章 快速傅立叶变换
8、而 是一对蝶形运算输出而 是一对蝶形运算输出数字信号处理第四章 快速傅立叶变换 1111数字信号处理第四章 快速傅立叶变换 1111数字信号处理第四章 快速傅立叶变换 上半部 分下半 部分序 号 为 偶 次序 号 为 奇 次数字信号处理第四章 快速傅立叶变换 数字信号处理第四章 快速傅立叶变换 数字信号处理第四章 快速傅立叶变换 DIF-FFT算法特点：（1）同址运算：每一级的每个蝶形的输入与输出数 据，在运算前后可以存储在同一内存单元上称为同址 运算。（2）倒位序规律（基2）：DIF的基2-FFT运算，其输 出X(k)是码位倒置的，但输入x(n)是自然顺序。在实 际运算中，先计算X(k)，再
9、通过变址运算，将码位倒 置顺序的存储转换为自然顺序的存储。（3）蝶距及W因子的变换规律：各类蝶形运算两个 点相距的“距离”称蝶距。数字信号处理第四章 快速傅立叶变换 蝶距规律：最前一级的蝶距为N/2,依次向右为N/4,N/8,W因子规律：最前一级有一组，每组有N/2种，顺序为向右一级有两组，每组N/4种，顺序为其余类推。m：蝶形运算的 第m级数字信号处理第四章 快速傅立叶变换 二、运算量按频率抽选法FFT的流图可见，当 ,共有 L级碟形运算 ，每级都有 个碟形运算组成，每个碟形有一次复乘、二次复加，这样FFT运算总共需要复乘数：复加数：数字信号处理第四章 快速傅立叶变换 IDFT定义为比较可见
10、，只要:(1)将DFT运算中的每一个系数 改为（2）将输出结果乘以常数1/N。则以上的FFT运算都可以直接用来计算IFFT。IFFT与FFT在碟形运算上比较有3点不同：（1）W因子取反， k -n（2）碟形的每个输出都乘以1/2；（3）名称改变。4.5 离散傅立叶反变换（IDFT)的快速计算方法数字信号处理第四章 快速傅立叶变换 频率抽选（DIF）FFT变为IFFT数字信号处理第四章 快速傅立叶变换 IFFT数字信号处理第四章 快速傅立叶变换 例、已知 是两个N点实序列 的DFT值，今 需要从 求 值，为了提高运算效率，试用一 个N点IFFT运算一次完成。因为数字信号处理第四章 快速傅立叶变换
11、 例：对一个连续信号 采样1S得到一个4096个采样点序列，求（1）若采样后没有发生频谱混叠， 的最高频率是多少？（2）若计算采样信号的4096点DFT，DFT系数之间的频率间隔是多少？（3）假定仅仅对 频率范围所对应的DFT采样点感兴趣，若直接用DFT，要计算这些值需要多少次复乘？若用时间抽取FFT则需要多少次？（4）为了使FFT算法比直接计算DFT效率更高，需要多少个频率采样点？解（1）（2）（3） 频率范围所对应的DFT采样点为101点，计算一个点DFT的 复乘次数为N次，故101点DFT复乘次数为：4096点的FFT的复乘次数：（4）设需采M 点数字信号处理第四章 快速傅立叶变换 快速
12、FFT变换应用利用FFT求线性卷积线性卷积：设N数字信号处理第四章 快速傅立叶变换 数字信号处理第四章 快速傅立叶变换 例：已知一信号x(n)的最高频率成分不大于1.25kHz，现用基2FFT算法对x(n) 作频谱分析，因此点数N应为2的整数次幂，且频率分辨率 ，试 确定（1）信号的抽样频率 ；（2）信号的记录长度T；（3）信号的长 度N。解：（1）由抽样定理， ，取（2）信号记录长度（3）信号的长度数字信号处理第四章 快速傅立叶变换 例：令 已知x(n)和h(n)分别是8和5的实序列，可通过如下3种方法计算y(n):（1）直接计算线性卷积；（2）计算一次圆周卷积（3）基2FFT试说明三种方法分别所需要的乘法数。解（1）直接计算线性卷积，需要的实数乘法数是1+2+3+4+5+5+5+5+4+3+2+1=40次或85=40（2）由于y(n）的长度是8+5-1=12,因此，圆周卷积需要x(n)和h(n)后面分 别补零，构成长度为12点的序列，这样，所需要的实数乘法是（3）N=16,L=4，复数乘法
