CHP4快速傅立叶变换.pptVIP

第二部分 傅立叶变换及其快速算法之第四章快速傅里叶变换 赵发勇 zfy_72@163.com 物电学院 目录 4.1概述 4.2时间抽取（DIT）基2FFT算法 4.3频率抽取（DIF）基2FFT算法4.5分裂基算法4.6线性调频Z变换4.7与本章有关节MATLAB文件 4.1 概述 4.1 概述 4.1 概述 4.1 概述 4.1 概述 算法分类： N为2的整次幂：按基数分为基-2FFT算法、基-4FFT算法、混合基FFT算法、分裂基FFT算法;当N不是2的整次幂:典型的有Winograd 算法. 按抽取方法分：时间抽取(Decimation－in－Time，简称DIT)；频率抽取(Decimation－in－Frequency，简称DIF) 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.2时间抽取（DIT）基2FFT算法 4.3 频率抽取（DIF）基2FFT算法 设输入序列长度为N=2M(M为正整数)，频率抽取法将输入序列不是按奇、偶分组，而是按前后对半分开，这样可将N点DFT写成前后两部分;将该序列的频域的输出序列X(k)(也是N点序列，按其频域顺序的奇偶分解为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。 4.3 频率抽取（DIF）基2FFT算法 4.3 频率抽取（DIF）基2FFT算法 4.3 频率抽取（DIF）基2FFT算法 4.3 频率抽取（DIF）基2FFT算法 4.3 频率抽取（DIF）基2FFT算法 4.3 频率抽取（DIF）基2FFT算法 4.5 分裂基算法 自从基2快速算法出现以来，人们仍在不断寻求更快的算法。1984年，法国的杜梅尔(P.Dohamel)和霍尔曼(H.Hollmann)将基2分解和基4分解糅合在一起，提出了分裂基FFT算法。其运算量比前几种算法都有所减少，运算流图却与基2FFT很接近，运算程序也很短。它是目前一种实用的高效新算法。 4.5 分裂基算法 4.5 分裂基算法 4.5 分裂基算法 4.5 分裂基算法 4.5 分裂基算法 4.5 分裂基算法 4.6线性调频Z变换 以上提出FFT算法，可以很快地求出全部DFT值。即求出有限长序列x(n)的z变换X(z)在单位园上N个等间隔抽样点zk处的抽样值。它要求N为高度复合数。即N可以分解成一些因子的乘积。例N=2L 实际上： （1）也许对其它围线上z变换取样发生兴趣。如语音处理中，常常需要知道某一围线z变换的极点所处的复频率。 （2）只需要计算单位圆上某一段的频谱,即M不等于N。如窄带信号，希望在窄带频率内频率抽样能够非常密集，提高分辨率，带外则不考虑。 （3）若N是大素数时，不能加以分解，又如何有效计算这种序列DFT。例N=311，若用基2则须补N=28=512点，要补211个零点。 4.6线性调频Z变换 问题提出 为了提高DFT的灵活性，须用新的方法。线性调频z变换(CZT)就是适用这种更为一般情况下，由x(n)求X(zk)的快速变换。 CZT 来自于雷达专业的专用词汇。Z 变换采用螺线抽样,可计算单位圆上任一段曲线的Z变换，适用于更一般情况下（M不等于N）由x(n)求X(zr)的快速算法, 达到频域细化的目的，这种变换称为线性调频Z变换(简称CZT )。 4.6线性调频Z变换 为适应z可以沿平面内更一般的路径取值，我们沿z平面上的一段螺线作等分角的抽样，则z的取样点Zr可表示为： 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 4.6线性调频Z变换 与标准FFT算法相比，CZT算法有以下特点： （1）输入序列长度N及输出序列长度M不需要相等，且N及M不必是高度合成数，二者均可为素数。