第4篇快速傅立叶变换(FFT).ppt

4.6 输入和输出点数不相同的FFT 二、CZT (线性调频Z变换)的定义 CZT的特点 CZT可计算单位圆上任一段曲线上的Z 变换，可任意给定起止频率； 作变换时输入的点数N和输出点数M可以不相等； 可达到频域“细化”的目的。 CZT的计算： 多蝶形单元运算所需计算量的比较 基－2 算法： 1965年， DSP 发展的里程碑； 基－4 算法 : 对基－2 算法的改进； 分裂基算法： 1984年， 接近最优的 FFT！ 4.5 分裂基 (Split-radix) 算法 Winograd 算法：1976年提出，是具有鲜明特色的FFT! 用到较多的数论知识，可用于N不等于2大整次幂。 基4 DIF 的基本单元： 基4 DIF 的基本单元： 以 4 为基，分解时级数可减少1半，因此可减少乘法次数。 不需要乘法！ 乘法数减少一半 所需计算量： 基2 基4 分裂基 要求:掌握导出方法 极限 基2 DIF: 旋转因子都出现在奇序号项输出，在求出偶序号项时不需要乘法。每一级都是如此。 基2 和基4 算法的比较： 基 4 令 则 分析上述结果可知，在基－4 算法中，N/4个偶序号输出也要乘W因子。而基－2 算法的偶序号项都不要乘W因子。 对偶序号项输出用基－2 算法，对奇序号项输出用基－4算法。 令 则 基 2 / 4 算法 各种算法所需计算量的比较 DFT： 输入N点，输出N点, 输入、输出点数 相同。输出的N点均匀分布于单位圆上，频域 分辨率为 在实际应用中： 1. 当输入点数极少时，若希望频率分点较多，则需要补零，结果是增加了计算量; 2. 对于窄带信号，我们只希望通带内分点密，带外可以较疏，或根本不用计算。 1.Pruning 2. CZT 一、输入端 Pruning （ DIF ） 不需要的不计算！ 二、输出端 Pruning （窄带情况） 不需要的不计算！ 其中： Z变换： Z在其 ROC 内取值，现为Z指定一离散的路径： 做DFT时，Z变换在单位圆上的等分的 N个点上取值。 CZT时，离散路径可在单位圆内、外，或圆上。 CZT在Z平面上的变换 路径是一条螺旋线 决定CZT的起点； 决定变换路径如何倾斜 决定变换的步长。 信号的点数 N 和变换路径的点数 M 可以不相等。 CZT变成了DFT 时，起点在单位圆外， 反之，在圆内； 时，内旋，反之外旋； 时, CZT变换路径 为单位园上一段弧， * * 第4章 快速傅立叶变换（FFT） 4.1 概述 4.2 时间抽取基 2 算法 4.3 频率抽取基 2 算法 4.4 减少运算量的措施 4.5 分裂基算法 4.6 线性调频 Z 变换 4.7 其它算法 4.1 概述 解决耗时的乘法问题是将数字信号处理理论用于实际的关键问题。特别是30年前，计算机的速度相当慢。因此，很多学者对解决DFT的快速计算问题产生了极大的兴趣。 Cooley J W, Tukey J W. An algorithm for the machine computation of complex Fourier series. Mathematics of Computation, 1965, pp297~301 Cooley 和 Tukey提出的解决DFT的快速傅立叶变换算法（Fast Fourier Transform, FFT），使计算量由 N2 降为 FFT 的思路： 如何充分利用这些关系 DFT： 四点 DFT 几个乘法？ 几个乘法？ 4.2 时间抽取基 2 算法 N点 DFT N/2点 DFT N/4点 DFT 2点 DFT 1个 2个 4个 N/2个 问题是如何分最有效？可以对时间变量分(DIT, decimation in time)，也可对频率变量分(DIF , decimation in frequency) 令： 将n按奇偶分开 2个N/2 点的DFT，分别 再分成2个N/4 点DFT 如此继续分下去，直至N/2个两点DFT。两点DFT不需要乘法运算： 每一级有 N / 2 个如下的“蝶形”单元： 即: 每一个蝶形单元仅需一个复数乘法，两个复数加法。两点构成一个蝶形单元，并且这两点不再参与别的蝶形单元的运算。同址运算。 p, q 的取值： 若每一级的数据自上而下都按自然顺序排列，则在第 m 级上下节点p