DFT的快速算法FFT幻灯片.ppt

§4 DFT的快速算法——FFT 时域抽取基-2FFT算法（DIT-FFT） 频域抽取基-2FFT算法（DIF-FFT） 逆 DFT 的快速算法（IFFT） N为合数的 FFT 算法 （混合基） DFT的快速算法（FFT）综述 时域抽取基－2FFT算法（DIT-FFT） 算法的推导 典 型 例 题 运算量 FFT算法的特点 DIT-FFT算法其他形式的流图 N=8 时输入是正序、输出是倒码的DIT-FFT运算流图 频域抽取基－2FFT算法（DIF-FFT） 算法的推导 DIF-FFT的蝶式运算流图 DIF-FFT的一次分解运算流图 DIF-FFT的二次分解运算流图 有关说明 逆DFT的快速算法（IFFT） IFFT算法的推导 FFT（IFFT）算法的实现 N为合数的FFT算法（混合基） N为合数的FFT算法（混合基） 算法的推导 N为合数的FFT算法（混合基） 例： 算法的运算量 §5 DFT 与 FFT 的应用 利用 FFT 进行频谱分析 用FFT计算线性卷积 线性调频 Z 变换（Chirp-Z变换）及快速算法 利用 FFT 进行频谱分析 利用FFT进行频谱分析的基本方法 几个常用基本概念 典 型 例 题 用FFT进行频谱分析存在的两个问题 用FFT计算线性卷积 线性卷积 利用循环卷积计算线性卷积的条件 利用FFT进行线性卷积的步骤 长序列FFT卷积的计算方法 重叠相加法卷积示意图 线性调频Z变换(Chirp- Z 变换)算法 问题的引入 算法的基本原理 Chirp- Z 变换的方框图 说明 Chirp-Z变换的实现 Chirp- Z 变换算法具体步骤 N为合数的FFT算法（混合基） 经一次分解后的3个6点DFT，每个又可分解为3个2点的DFT ，如图： N为合数的FFT算法（混合基） 第一次抽取后的运算量： 第二次抽取后的运算量： 总运算量： 总乘法运算次数 设 为长为 N 的有限长序列，则： 利用 FFT 进行频谱分析的实现过程框图为： 利用 FFT 进行频谱分析 1、数字频率分辨率： 2、模拟频率分辨率： 3、用于FFT的采样点数： 4、频率刻度值： 5、模拟信号长度： 6、分辨率： 例：用FFT来分析信号的频谱，若已知信号的最高频率为 ，要求频率分辨率为 ，试确定： 1、采样间隔 T ； 2、采用基-2FFT的最小样点数 N ，以及与此相对应的最小记录长度； 3、按您确定的参数所获得的实际分辨率。 解： 1、据采样定理，采样间隔 2、基-2FFT的最小样点数N 当采用基-2FFT算法时，要求 典 型 例 题 与此相对应的最小记录长度为： 3、按确定的参数所获得的实际分辨率 利用 FFT 进行频谱分析 1、频谱泄漏 在实际应用中，通常将所观测与处理的信号限制在一定的时间间隔内，即在时域对信号进行 “ 截断操作 ” ，或 称作加时间窗（用时间窗函数乘以信号）。由卷积定理可知：时域相乘、频域卷积，这就造成 “ 拖尾现象 ” ，称之为频谱泄漏。 若序列 的长度为无限长，为了利用 FFT 进行频谱分析，首先必须将其截断为有限长序列 卷积定理 显然，两种频谱是有差别的，该现象就是频谱泄漏 解决办法：① 采用其它形式的窗函数（第六章详论） ② 对于周期序列，取其过零点截取 利用 FFT 进行频谱分析 2、栅栏效应 利用 FFT 进行频谱分析时，只知道离散频率点 的整数倍处的频谱。在两个谱线之间的情况就不知道，这如同通过一个栅栏观察景象一样，故称作栅栏效应。 解决办法：在序列后面补零点加大FFT点数 ，可使谱线间隔变小来提高分辨力，以减少栅栏效应。 注意：若需要加窗，则应先加窗再补零。 设 是 和 的线性卷积： 总运算量为： 可见，直接运算时运算量很大，必须寻找新思路。 思路：利用 FFT ,通过循环卷积来计算线性卷积 用FFT计算线性卷积 设 是x(n)和h(n)长为L的循环卷积： 其中 LMax[N,M], 用FFT计算线性卷积 用FFT计算线性卷积 上式表明： 是将 以L为周期进行延拓后再取主值区间所得的序列。∴利用循环卷积计算线性卷积的条件为： 利用循环卷积计算线性卷积如下图 用FFT计算线性卷积 ①、将已知序列 （长为N）和 （长为M）补零延长，使它们的长度