第三版-04 快速傅里叶变换.ppt

数字信号处理第四章快速傅里叶变换(FFT)河北师范大学数信学院 张朝晖2012年11月22日 本章学习目标 (1) 基2FFT的算法原理 DIT-FFT和DIF-FFT的算法差异 基于FFT的DFT应用 主要内容 4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 DFT使计算机在频域处理信号成为可能。 DFT在实际应用中很重要: 可以计算信号的频谱、功率谱和线性卷积等。 当序列长度N很大时，直接按DFT变换进行计算，计算量非常大，所需时间会很长。 ----直接用DFT算法进行谱分析和信号的实时处理是不切实际的。 FFT并不是一种与DFT不同的变换，而是DFT的一种快速计算的算法。 例如：1965年发现的关于DFT的一种快速算法，使DFT的运算效率提高1－2个数量级，为数字信号处理技术应用于各种信号实时处理创造了条件，推动了数字处理技术的发展。1984年，提出了分裂基快速算法,使运算效率进一步提高。 更多FFT，可参见： /wiki/Fast_Fourier_transform 主要内容 4.1 引言 4.2 基2FFT算法 4.2.1 直接计算DFT特点及减少运算量的基本途径 4.2.2 时域抽取法基2FFT 基本原理(DIT-FFT) 4.2.3 DIT-FFT算法与直接DFT的运算量比较 4.2.4 DIT-FFT的运算规律及编程思想 4.2.5 频域抽取法FFT(DIF-FFT) 4.2.6 IDFT的高效算法 4.3 进一步减少运算量的措施 直接计算DFT的运算量 2. 减少运算量的基本途径 将N分解为较小值：不断把长序列分解为几个较短 的序列,分别计算其DFT值，可大大减少乘法次数 同时，利用旋转因子WNm的周期性、对称性进行合 并、归类处理，以减少DFT的运算次数。 周期性： 对称性： 2. 减少运算量的基本途径（续1） 其中，基2FFT( radix-2 Cooley–Tukey algorithm )只用到长序列分解及旋转因子WNk的对称性。 主要内容 4.1 引言 4.2 基2FFT算法 4.2.1 直接计算DFT特点及减少运算量的基本途径 4.2.2 时域抽取法基2FFT 基本原理(DIT-FFT) 4.2.3 DIT-FFT算法与直接DFT的运算量比较 4.2.4 DIT-FFT的运算规律及编程思想 4.2.5 频域抽取法FFT(DIF-FFT) 4.2.6 IDFT的高效算法 4.3 进一步减少运算量的措施 基2FFT算法要求DFT变换区间长度为： N=2M M为整数 基2FFT算法可分为两大类： 时域抽取法FFT (Decimation in Time FFT) 简称DIT-FFT 频域抽取法FFT (Decimation in Frequency FFT) 简称DIF-FFT 设序列x(n)的长度为N，且满足： 将序列x(n)按n的奇、偶，分为x1(n)、x2(n)两组短序列； 用2个短序列的N/2点DFT来完成一个长序列的N点DFT的计算。 (1) 按n的奇、偶，把N点长序列x(n)分解为两个N/2点的子序列 (2)用N/2点X1(k)和X2(k)表示序列x(n)的N点DFT X(k) 由于 X1(k)和X2(k)均以N/2为周期 所以， 可表示为: 上述运算用下图所示的流图符号来表示 (3)第二次分解： 将x1(l)按l取奇、偶可分解成2个长度为N/4的子序列 x3(r)= x1(2r) x4(r) = x1(2r+1) 根据上面推导可得：X1 (k)= X3(k)+ WN/2k?X4(k)， k=0,1,…,N/2-1 得N/4个蝶形运算： (3)第二次分解(续)： 将x2(l)按l取奇、偶可分解成2个长N/4的子序列 x5(r)= x2(2r) r=0,1