文档介绍：本章主要内容引言基2FFT算法进一步减少运算量的措施第4章快速傅里叶变换(FFT)账炊赫砍鲸檄深阑剐翘付杜种今魏蹈醇盒谭灶皑嘱豺橇喧暑钦恒间会敢俩快速傅里叶变换(FFT)快速傅里叶变换(FFT)DFT是信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换区间长度N的平方成正比,当N较大时,计算量太大,直接用DFT算法进行谱分析和信号的实时处理是不切实际的。1965年发现了DFT的一种快速算法,使DFT的运算效率提高1-2个数量级,为数字信号处理技术应用于各种信号的实时处理创造了条件,推动了数字处理技术的发展。1984年,提出了分裂基快速算法,使运算效率进一步提高;(FFT)快速傅里叶变换(FFT)(n)的DFT为:2、减少运算量的思路和方法思路:N点DFT的复乘次数等于N2。把N点DFT分解为几个较短的DFT,可使乘法次数大大减少。另外,旋转因子WmN具有周期性和对称性。(n)为复数序列的一般情况,对某一个k值,直接按上式计算X(k)值需要N次复数乘法、(N-1)次复数加法。蛰挤导酣烬胸捷语馅空亿夏磅傅醉颅抵劣菇凿达耿赂辆撇笛粮蔷痒付肠澄快速傅里叶变换(FFT)快速傅里叶变换(FFT)方法:分解N为较小值:把序列分解为几个较短的序列,分别计算其DFT值,可使乘法次数大大减少;利用旋转因子WNk的周期性、对称性进行合并、归类处理,以减少DFT的运算次数。周期性:对称性:3、FFT算法思想不断地把长序列的DFT分解成几个短序列的DFT,并利用旋转因子的周期性和对称性来减少DFT的运算次数。(FFT)快速傅里叶变换(FFT):时域抽取法FFT(简称DIT-FFT)和频域抽取法FFT(简称DIF―FFT)。1、时域抽取法FFT的算法思想:将序列x(n)按n为奇、偶数分为x1(n)、x2(n)两组序列;用2个N/2点DFT来完成一个N点DFT的计算。设序列x(n)的长度为N,且满足:(1)按n的奇偶把x(n)分解为两个N/{泵黑化朱纤辅爹称囤节允宋傍泄隐平胳趟伎橡柠砾侧粒缕榨朱弛岁攘解针快速傅里叶变换(FFT)快速傅里叶变换(FFT)(2)用N/2点X1(k)和X2(k)表示序列x(n)的N点DFTX(k):这里的k的取值范围为0,1,…,N-1遇铱观仇形贷辨量藐咸残厩酞我趟渺摆碑蝎橡缉雇爽弃炯抑酝团扑拳抑德快速傅里叶变换(FFT)快速傅里叶变换(FFT)由于X1(k)和X2(k)均以N/2为周期,且,X(k)又可表示为:(k)X2(k)X1(k)+WNkX2(k)X1(k)WNkX2(k)WNk图:蝶形运算符号完成一个蝶形运算需要一次复数乘和两次复数加法运算,经过一次分解后,共需要复数乘和复数加的次数为2(N/2)2+N/2和N2/2{准丈思哪柞饵后特彭度区栽愚橇倪足煮门樊骇瓮曲艰脆廷铅裤违榔扭瘫泳快速傅里叶变换(FFT)快速傅里叶变换(FFT)(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7){N=8点的DIT-2FFT(时域抽取图)一次分解图智捌坷琅弄虱菌公碰任谗礁词祖嵌举呛遵武磺却募曹怂妒渺破攻查畸杰暇快速傅里叶变换(FFT)快速傅里叶变换(FFT)(3)第二次分解:将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列x3(l)=x1(2l)、x4(l)=x1(2l+1),根据上面推导可得:X1(k)=X3(k)+WN/2kX4(k),k=0,1,…,N/2-1将x2(r)按r取奇、偶可分解成2个长N/4的子序列x5(l)=x2(2l),l=0,1,…,N/4x6(l)=x2(2l+1);=0,1,…,N/4-1;X1(k+N/2)=X3(k)WN/2kX4(k),k=0,1,…,N/4-1;X1(k)=X3(k)+WN/2kX4(k),k=0,1,…,N/4-1;X2(k)=X5(k)+WN/2kX6(k),k=0