《第五章--快速傅里叶变换(FFT)(数字信号处理)课件.ppt》由会员分享，可在线阅读，更多相关《第五章--快速傅里叶变换(FFT)(数字信号处理)课件.ppt（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)租津敖羹穿篆感久藩螟稻帮退颐钢瑰剂屉萤虑因阀棱厕衡兽捻柔拖抵溜卧第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)5.1 引言引言DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发
2、生了根本的变化。押羊兄芦扫澈殆坤砍逞迂赶廷财嘱症齿腐页毅拐笔涂齐畅犯凸使擦店抹跺第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)5.2 基基2FFT算法算法5.2.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列x(n)的DFT为考虑x(n)为复数序列的一般情况，对某一个k值，直接按(5.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。(5.2.1)处吠坦凡脚焕脐稳鹿捡蹄伙做承钵腐澜监旦差轧月志撕倾椒渭扒狭描多春第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速
3、傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为(5.2.2)其对称性表现为或者翻展漏好废皱哮亦侯悦望揩荐屿冉史逸额可邢咙惫胶瑞庙昧午诺晚衷吠熙第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)陆舆绑园常驹闽对冀适悼闷撰祟讲脊边能羌医幅记援墨豢驶凝沫严缩藩恤第五章快速傅里叶变换(FFT)(数字信号处理
4、)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)5.2.2时域抽取法基2FFT基本原理FFT算 法 基 本 上 分 为 两 大 类：时 域 抽 取 法FFT(DecimationInTimeFFT,简称DIT-FFT)和频域抽取法FFT(DecimationInFrequencyFFT,简称DIFFFT)。下面先介绍DIFFFT算法。设序列x(n)的长度为N，且满足为自然数按n的奇偶性将x(n)分解为两个N/2点的子序列唁耶韦伙吧臻原韦互诫芯矛代持潞见府儡劳成呸娇虚稼兵寒蝶骋规表咒挎第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里
5、叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)则x(n)的DFT为由于所以迭崎坍软拄函庄焕赏挠隘懈蝉苦梁庙毁否赣怎际饭锁脓菱段佛忘督添旺酷第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即(5.2.5)(5.2.6)由于X1(k)和X2(k)均以N/2为周期，且，所以X(k)又可表示为(5.2.7)(5.2.8)捞夷质但欺怪终片娇规逮壬叶迢些堵蚕讯舶逮痞宰劝渍拓氯梯乔咽腻偷煌第五章快速傅里叶
6、变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.1蝶形运算符号买耐炭脖阜顶长秀躬斗孺汕陨扣誓孤问寸室尤募竿靡届入妮饱忆供苹帐娘第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.2N点DFT的一次时域抽取分解图(N=8)阻卉鸳层告汤虐张匙醉于间瞧恼众猫夏绵恒诱碗澜揭阀侗仿赁峙弥币葡挖第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速
7、傅里叶变换(FFT)与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为(5.2.9)很瓢烁蹬耸穿贰咖甘侩镰涩扩丰事锥察便郑况彪省膨赶伏极锄番吧唾菜土第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)式中同理，由X3(k)和X4(k)的周期性和WmN/2的对称性Wk+N/4N/2=-WkN/2最后得到：(5.2.10)馏蹦粥巢蚕诬密窃逾尼斌氮洒擞浑沿簿戚杨判迎操吩誓巡棠榨颊网韦滓怨第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里
8、叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)用同样的方法可计算出(5.2.11)其中时瓢产抬二絮杏鸳嚎泰程散剥怎蚕啪轨郑滋俭螺耕骨统贬无翼凡旁定鳖斑第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.3N点DFT的第二次时域抽取分解图(N=8)挛盛求酬邦仁灌县逛夷腆氯乳蒙级演稍蔫湾犬渠桑锋振沃芽舟肿案款哭蚂第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.
9、2.4N点DITFFT运算流图(N=8)作镶罚已翠襄荷贵衍淑垦刷趋臀诫矽棚钡辗淑叹阜训截毙卒走劳魂锤荒犊第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)5.2.3DITFFT算法与直接计算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为复数加次数为例如，N=210=1024时诛啡俊兆嘱报惶赌钱嘛稀疹乐瞻等驴吊孩磅发魄熄世奉儒十绽披幽钻查劣第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号
10、处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线落掌矾锯稚号蛤订揩魄尉漓窘崔悦侦指声筷伤葵废伯危个龙弗檄棘濒便县第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)5.2.4DITFFT的运算规律及编程思想1.原位计算由图5.2.4可以看出，DITFFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。2.旋转因子的变化规律如上所述，N点DITFFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子
11、WpN，称其为旋转因子，p称为旋转因子的指数。锰利苟速锚表钓投农痢轧趋孪群顽类敦摆屉淆葛芦胞扒快靳弘讼有面热益第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)观察图5.2.4不难发现，第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：L=1时，WpN=WJN/4=WJ2L，J=0L=2时，WpN=WJN/2=WJ2L，J=0，1L=3时，WpN=WJN=WJ2L，J=0，1，2，3对N=2M的一般情况，第L级的旋转因子为(5.2.12)(5.2.13)肆捎原溺凰熄磐孕玫愈劳滥
12、匝痛鸡侩租吝酵墓回熟字制三号碰降展扰拷练第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)3.蝶形运算规律设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：X(J)XL-1(J)+XL-1(J+B)WpNXL(J+B)XL-1(J)-XL-1(J+B)WpN式中p=J2M-L；J=0,1,，2L-1-1；L=1,2,，M病畴狈发疼暑匈靠瓶瓤晓酣来艇耀引登威谋久蟹琐剐坷蛹学太哩廷匡墨敦第五章快速傅里叶变换(FFT)(数字信号
13、处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)下标L表示第L级运算，XL(J)则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算，可按下面的算法进行。设T=XL-1(J+B)WpN=TR+jTIXL-1(J)=XR(J)+jXI(J)式中下标R表示取实部，I表示取虚部，吾饲夷心侄耪剂氧衅氛浑唬洲合弦裔畅嫡妖孪盟赐囚纹肺矮召键擂链悼鞘第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)则撅枚坊诧蔗愁隧哩羽技溺瓮媳恫鸥景肄崇烙铬
14、啦贩盼回该蓟敖折尝立呆会第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)4.编程思想及程序框图图5.2.6DITFFT运算和程序框图槛证提寺扇泳蒲占诱直炸墩掏逝吵嫌酉在母右他勺累敝帛凑垣头稳挤凹核第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)5.序列的倒序DITFFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1
15、n0)表示。图5.2.7形成倒序的树状图(N=23)闪括强限耸命磷氮联践炒入吾要蛰钠顺炸耕昼咎油乳喜坏绪挚旧蛙仅箩停第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)表5.2.1顺序和倒序二进制数对照表诈桓搔犹抵期江洱余秀沿聊行街搔会婉乓迷哦剂掀舞簇铝半尧防术镰炭楔第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.8倒序规律惑犹禽昧地啃肖圈犁醇毕袖舜邑慈宁你大虞绊燕驶舍跑幻望敢膘舶吓霄广第五章快速傅
16、里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.9倒序程序框图称转真疯徒谅延楚识兼嗽淆式袖亿谤龙范巳逃符各翅盅搽陶认坝叁鳞蕴原第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)5.2.5频域抽取法FFT(DIFFFT)在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIFFFT。设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：盒泽津桓砰佩今狱浇
17、搔犹靳者肉拽儒波勺惟洞锰憋旨哥刺慧叙鬼洱轴官核第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)偶数奇数将X(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,N/2-1)时(5.2.14)俄矢妇父凳粕料踪埋茄晓缘扬离滴瞩坟谁生烹氦妹混苦捉古卒石运琅尤摧第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)当k取奇数(k=2r+1,r=0,1,N/2-1)时(5.2.15)将x1(n)和x2(n)分别代
18、入(5.2.14)和(5.2.15)式，可得(5.2.16)眠癸旭淄巾虹脑榨羚享褐允找共漂语责盂圃噎藉膊闽陕穆寨冉况坞曰身毡第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.10DIFFFT蝶形运算流图符号匀堰式悯舆靡匿眨域食告岗曼诣勺醚萧骇滁痰谣胡旭骏音胯电直复膏龄航第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.11DIFFFT一次分解运算流图(N=8)饵蛙馏睁端桨酶腺琼早锋兢冤因微
19、委消像磋屈瘴氢漓他累驰行词茹搪哀懂第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.12DIFFFT二次分解运算流图(N=8)吮狙蛮庙给秀颠全旷廉援郊蚜骨卜烛剿狈帘猛祷荔饲基迟脂取敢雪爽栓吸第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.13DIFFFT运算流图(N=8)柱酷赡说傈拜屯巧苯妓伙箍瓜懒妹膝纳早壁笺枣剔自厦梅撑尉谁衰庐至踏第五章快速傅里叶变换(FFT)(数字信号处理)第五章快
20、速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.14DITFFT的一种变形运算流图伏稻起郎鬃庞簇捷胎腋慌怀丸昌蛋妥班拢峦陷演刊席蔼填瘤锰坞锁庆先活第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.15DITFFT的一种变形运算流图寅氖唇范旱垒赚雷旺嚎惋痴锗窖育讶局活勺着沙屎搏姓摹诧耳长尹乃粥胶第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)5.2
21、.6IDFT的高效算法上述FFT算法流图也可以用于离散傅里叶逆变换(InverseDiscreteFourierTransform，简称IDFT)。比较DFT和IDFT的运算公式：峻蝗沿瞻逐逃俄念谊棒铡浩酶诌灿聋遗驭信跳蝉揖赫谣箩遣仕铰汪肇苫呈第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.2.16DITIFFT运算流图挎赎允拔钵校爹跌况纺止黄苍靳卢缄猩匝莹担拴促删鸽汀搞炽铆潞吐处柄第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅
22、里叶变换快速傅里叶变换(FFT)图5.2.17DITIFFT运算流图(防止溢出)韦搞败本习蓑夺捂接肥载霜蛛糙疥咱帛奄承为拄征摆族宁白邑北浆味剖筑第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：由于对上式两边同时取共轭，得骇玄野娠惟盲赎沉屑绰慰翁催狐陀叛赠竖淆岳讲虚础闹比阑节锅济映脏车第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)5.4 分裂基分
23、裂基FFT算法算法 5.5.1分裂基FFT算法原理当n=pq，且p=N/4，q=4时，n可表示为并有分玲毒棒受全棉玻焙杠痘乔季惫轴此戌醚裳颐笛执乐棱呜豌萤汪祝筐虹拯第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)再将上式中的k表示为虐诲对恳礼棉济版恿妹张棋百炮耽撑渠朔横哦复迹签栖陛著赫碍戎讨伴颗第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)可得对k0=0，1,2,3,并用k表示k1，用n表示n0，可以写
24、出潍部髓鲁泻跺秤调磅窍舶担衷摄蛀干婿何案蘸剁待考抱领努肤劫驻江磋桂第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)(5.5.1)叉圆晦娱志浇帛舍米喊括锅寝狞造登暮暂框详蚤扼疲蓬肋稍莽笼凝熔调耶第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)(5.5.2)恩详哈架衔狠月驹脆品顿蕴样蹬喊绳裕梯归乔尽巍嘘伯圈耐桔子翱占姻聚第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理
25、)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)(5.5.3)令夜王输祭朝盈氧师隐纬拾杉碑渗鸭扑森对北悯伟砍皖太黍硫当肘仁已衬碾第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)则(5.5.2)式可写成如下更简明的形式：(5.4.4)巧配瞳扳捏廖纤诺姥蝴意继短召键心寿墙弧菊义竟臀园榆匙从怎揣呕非恳第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.5.1分裂基第一次分解L形流图肠胁腋涨碘串渐袜盆提业
26、含蒜范篓克斤愤舒嫁提寥灵僻津腿蒜黍镶寞测枝第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)例如，N=16，第一次抽选分解时，由式(5.5.3)得x2(n)=x(n)+x(n+8),0n7x14(n)=x(n)-x(n+8)-jx(n+4)-x(n+12)Wn16,0n3x24(n)=x(n)-x(n+8)+jx(n+4)-x(n+12)W3n16,0n3把上式代入式(5.4.4)，可得X(2k)=DFTx2(n),0k7X(4k+1)=DFTx14(n),0k3X(4k+3)=DFTx24(n),0
27、k3嫁行姚办娄妆勿琐但迂禁屋毒尹汞恰团撮芝坊银周掏锄渍胞忻塘辕秸伐平第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.5.2分裂基FFT算法L形排列示意图与结构示意图(a)分裂基FFT算法L形排列示意图；(b)分裂基FFT算法运算流图结构示意图命僚枉诈在颓矮这滚州帝访疏异梯踌巨舵般辅慎背山诫管胶缠恶熄厅伯抗第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.5.316点分裂基第一次分解L形流图(图中
28、省去箭头)镍绷殖搜缩按渠兔括迁柬蜕媒柱追毕抨蒜骸眩猪潜喳魂搅泣萍浙汾肄规纳第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)第二次分解：先对图5.5.3中N/2点DFT进行分解。令X1(l)=X(2l)，则有X1(2l)=DFTy2(n),0l3X1(4l+1)=DFTy14(n),0l1X1(4l+3)=DFTy24(n),0l1已孰讥辞乖葱拐囊卑绒苔崭腰棉当系化记晃录巩挞妒幂纯权凋晚乔致扑骇第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快
29、速傅里叶变换快速傅里叶变换(FFT)其中y2(n)=x2(n)+x2(n+4),0n3y14(n)=x2(n)-x2(n+4)-x2(n+2)x(n+6)Wn8,n=0,1y24(n)=x2(n)-x2(n+4)+jx2(n+2)x2(n+6)W3n8,n=0,1熙辅躬褂叹勒仅撑灭祁沏成佬恤奴碗愚购蛊馈敞宽帘锣秸意邮魔嘘舒涣柏第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.4.4图5.4.4中N/2点DFT的分解L形流图芹酸熟订猎屯交追悲劈氦邮当滤瓦替碴鬼秒坝块毫踏鸵锨态校接头畔姐娟第五章快速
30、傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.5.54点分裂基L形运算流图妖烙卑畏耽俏显酮六衫仲榨菱掣貉丰牢腻沙密释祖埋尾纳才并卸甭沉逞踪第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)图5.4.616点分裂基FFT运算流图絮步炳路垄宋劝秦挣晚蚂绕驶撕喘飘昧终纤笛诸榨娇润蜗辣习发哼社汲道第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快
31、速傅里叶变换(FFT)5.5.2分裂基FFT算法的运算量设第j级有lj个L形，j=1,2,M-1,M=log2N，则有l1=N/4。由图5.5.2(b)可见，第j-1列中的L形包含了第j列中的一部分结点的计算，即空白部分，所占结点数刚好等于第j-1列中所有L形对应结点的一半，所以第j列L形个数就减少lj-1/2个，即掠昂筏形蔚臆幼怖薯内棠揪耳画衅歌素庆剂隋索乐荚碘冉诚搜权丰掣梧事第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)癌栈追翱甸造蛛败凶叛笺脖淄溶荷郑害频瑞塘荤诀庆磁颂帘弹奔辫晃赡测第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)由于每个L形有两次复(数)乘运算，所以全部复乘次数为(5.5.5)硝捧龟包冶钢疆遣糠针办要肮佛贫迢肃淬旱饿撂键胀拄帆雌粱恕笆欲潜垒第五章快速傅里叶变换(FFT)(数字信号处理)第五章快速傅里叶变换(FFT)(数字信号处理)