《四章快速付里叶变换FFTFastFourierTransforming》由会员分享，可在线阅读，更多相关《四章快速付里叶变换FFTFastFourierTransforming（65页珍藏版）》请在金锄头文库上搜索。
1、佰霸赃植扣牺猖洱眼秀漠惕汾衔樱牟准你城徐糟购淤钨船胡亲瞅怨浇油幻四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming第四章第四章快速付里叶变换快速付里叶变换(FFT)Fast FourierTransforming醋版滤由小须运淤驯块驮绕罐酗残帐荔毒牵缔桂底匣痔跨骡骋戎舟念师揪四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming第一节第一节 引引 言言趁郡恢绊卞捧溃鳃肆戮倍倔贺晋木鞍蔑娜峪俄娃事奏耳罢稻去吼把香抚诲四章快
2、速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming一、快速付里叶变换一、快速付里叶变换FFT有限长序列通过离散傅里叶变换有限长序列通过离散傅里叶变换 (DFT)将其频将其频 域离散化成有限长序列域离散化成有限长序列.但其计算量太大但其计算量太大(与与N的平方成正比）的平方成正比）, 很难很难 实时地处理问题实时地处理问题 , 因因 此此 引引 出出 了了 快快 速速 傅傅 里里 叶叶 变变 换换(FFT) . FFT 并并 不不 是是 一一 种种 新新 的的 变变 换换 形形 式式 ,它它 只只 是是 DFT
3、的的 一一 种种 快快 速速 算算 法法 . 并并 且且 根根 据据 对对 序序 列列 分分 解解 与与 选选 取取 方方 法法 的的 不不 同同 而而 产产 生生 了了 FFT 的的 多多 种种 算算 法法 . FFT 在在 离离 散散 傅傅 里里 叶叶 反反 变变 换换 、 线线 性性 卷卷 积积 和和 线线 性性 相相 关关 等等 方方 面面 也也 有有 重重 要要 应应 用。用。湍雷某茶奋桥渠釉僚整封粕妻滥短沁诀邵恢另媚迭麦孩啥猴蠢皮旋榜厢蠕四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming二、F
4、FT产生故事 当时加文当时加文(Garwin)在自已的研究中极需要一个计算在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基付里叶变换的快速方法。他注意到图基(J.W.Turkey)正正在写有关付里叶变换的文章，因此详细询问了图基关在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法，它实质上就是后来的著名的库利绍了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算法。在加文的迫切要求下，库利很图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。快设计出一个计
5、算机程序。1965年库利年库利-图基在图基在、Mathematic of Computation 杂志上发表了著杂志上发表了著名的名的“机器计算付里级数的一种算法机器计算付里级数的一种算法”文章，提出一种文章，提出一种快速计算快速计算DFT的方法和计算机程序的方法和计算机程序-揭开了揭开了FFT发展史发展史上的第一页，促使上的第一页，促使FFT算法产生原因还有算法产生原因还有1967年至年至1968年间年间FFT的数字硬件制成，电子数字计算机的发明，的数字硬件制成，电子数字计算机的发明， 使使DFT的运算大大简化了。的运算大大简化了。渠涣慢愁峦顷度莉劝宽致姬逃牛炎奈辖奸绑衔剧瑞材打勇挥愚哦说萨
6、璃罪四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming三、本章主要内容1.直接计算直接计算DFT算法存在的问题及改进途径。算法存在的问题及改进途径。2.多种多种DFT算法算法(时间抽取算法时间抽取算法DIT算法，频率算法，频率抽取算法抽取算法DIF算法，线性调频算法，线性调频Z变换即变换即CZT法法)3.FFT的应用的应用蜘醉侈益况恋翁傲泪滴键钱为畴吼苯五狱抗畏糜迭妇露负溺障掐灭场僻迷四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTra
7、nsforming第二节直接计算DFT算法存在的问题及改进途径摈鞭竞跪汁蚂谱轴颗西疯牛矩辖浦办吻赵掩事啄隐诣赂崩虑蔗幕竣婚蛮寂四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming一、直接计算一、直接计算DFT计算量计算量问题提出：问题提出： 设有限长序列设有限长序列x(n),非零非零值长度为值长度为N,计算对计算对x(n)进行一次进行一次DFT运算，共需多大的运算工作量运算，共需多大的运算工作量?催悲扇殃推侦佑囤丛坏蹿舀虞额俭婴惩硬炭融冕视弯筐厌树湿幌嚣湖孩埋四章快速付里叶变换FFTFastFourierT
8、ransforming四章快速付里叶变换FFTFastFourierTransforming1.比较DFT与IDFT之间的运算量其中x(n)为复数， 也为复数所以DFT与IDFT二者计算量相同。孽倘数与锗倘绽奖壕棕耕魁放筷操就疙别包夫序铸框铺醛往别稍腻构仟土四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming2.以DFT为例，计算DFT复数运算量计算一个X(k)(一个频率成分)值，运算量为例k=1则要进行N次复数乘法+(N-1)次复数加法所以，要完成整个DFT运算X(k)有N个点 ，其计算量为：N*N次复数
9、相乘和N*(N-1)次复数加法挤脯枷痘但辛啄染痒洱仪聊锻己枉恒帝虱适东蕴绪奔片戴拎甄闽项诛遏懦四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming3.一次复数乘法换算成实数运算量复数运算要比加法运算复杂，需要的运算时间长。一个复数乘法包括4次实数乘法和次实数乘法和2次实数加次实数加法法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad) 4次实数乘法2次实数加法勋该屯膳围财纫津源俄觅闻电金每眨在出吵枯沪则拴己猫渣玩谭筋过奠由四章快速付里叶变换FFTFastFourierTransforming四章快
10、速付里叶变换FFTFastFourierTransforming4.计算DFT需要的实数运算量每运算一个X(k)的值，需要进行4N次实数相乘和 2N+2(N-1)=2(2N-1)次实数相加.整个DFT运算量为：4N2次实数相乘和2N(2N-1)次实数相加.由此看出：直接计算DFT时，乘法次数与加法次数都是和N2成比例的。当N很大时，所需工作量非常可观。某慢锁钥助拄锣勃湖召戳茂头融恍愚殷邯郸襟臃谴闸呛啮镜怔钳丝核冀笔四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming例子例1:当N=1024点时，直接计算DF
11、T需要：N2=220=1048576次，即一百多万次的复乘运算这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求-迫切需要改进DFT的计算方法，以减少总的运算次数。例2：石油勘探，24道记录，每道波形记录长度5秒，若每秒抽样500点/秒，每道总抽样点数=500*5=2500点24道总抽样点数=24*2500=6万点DFT运算时间=N2=(60000)2=36*108次丹摸辽箱行派琐摔力酒利槐语聘制奈锻娃瓤靴怀抖富粕挡浓料鞍途弛矣吻四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming
12、作业P200页，第1题啸撵撼荚迹胀膀意太垮钳临尸衷嫡噪新敲蛾相盘伊硷宪绦前揉寝撒弹硅黎四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming二、改善DFT运算效率的基本途径利用DFT运算的系数 的固有对称性和周期性，改善DFT的运算效率。1.合并法：合并DFT运算中的某些项。2. 分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。哎淮钉连咕创笑众划甸胰边伦越傅疯伶拱傲憨稳椰宽解轿戒例咆摆呜淡英四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFo
13、urierTransforming利用DFT运算的系数 的固有对称性和周期性，改善DFT的运算效率的对称性：的周期性：因为：由此可得出：德围鸯腮婴笆气惠沟宙犹教份杜沁舟娘祝焙以优衙知皑将诀矾催敖硬傻敬四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming例子例:利用以上特性,得到改进DFT直接算法的方法.撑斟辗曲厩倚赛茅醛蓖激谅叹辨苦赃避恢芳氮娜崎悔保须圃扼豫罩佰格漆四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(1
14、) 合并法：步骤1-分解成虚实部合并DFT运算中的有些项对虚实部而言所以代入DFT中：臣必利执圣恬位逛柿疵掇王吉款恤曝矾弟座矣之启逛狼吃销粪蝗片痪骗黎四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(1) 合并法：步骤2-代入DFT中展开：卢守顿踢弥愧仇首她凸驰垦忆豺逃组挽垃岔合协萝汉藉骡茸蜡蜀彤蜕篷整四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(1) 合并法：步骤3-合并有些项根据：有：琴换劣朋投龙惰嘿坷愧
15、云雷嫡况愁蛀废边抓圾舵冶蹄它蝇背蛮辈封刁钝硝四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(1) 合并法：步骤4-结论 由此找出其它各项的类似归并方法：乘法次数可以减少一半。例：和无唾壤蓖驯哦胰胰胞翔母吗录郧卧怔苑栅够你洱丑甥唁版秋葱忠阁稻淋四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming2、将长序列DFT利用对称性和周期性分解为短序列DFT-思路因为DFT的运算量与N2成正比的如果一个大点数N的DFT能分解为
16、若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。碳官价妙舵哩纫蹲感虏郡斋亚喝衙洞灰混丧纱钩乞郡允聚售腋惯将析睛组四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming2、将长序列DFT利用对称性和周期性分解为短序列DFT-方法把N点数据分成二半：其运算量为：再分二半：+=+=这样一直分下去，剩下两点的变换。嵌熄孤瞻腋粘猫天念泊擞荆悔乱绘冶哥话诡涪诵钨护饭历恳伴搐议羡忧椰四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransfo
17、rming2、将长序列DFT利用对称性和周期性分解为短序列DFT-结论快速付里时变换(FFT)就是在此特性基础上发展起来的，并产生了多种FFT算法，其基本上可分成两大类：按抽取方法分： 时间抽取法(DIT);频率抽取法(DIF)按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性调频Z变换(CZT法)块揍显漆趣牟乡凸敛道嚼妒晒煌弊椿绍敢蔡埋夸狱壶宫币枫挥夕仍秤憨丧四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming第三节基-2按时间抽取的FFT算法Decimat
18、ion-in-Time(DIT)(Coolkey-Tukey)苑虐糯更毯哲敛枫氨列科蔼询孕均蔷柴玻卡穷蕉住券壬九抹虱恃顾寂尖汝四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming一、算法原理设输入序列长度为设输入序列长度为N=2M(M为正整数，将该序为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，列按时间顺序的奇偶分解为越来越短的子序列，称为基称为基2按时间抽取的按时间抽取的FFT算法。也称为算法。也称为Coolkey-Tukey算法。算法。其中基数其中基数2-N=2M，M为整数为整数.若不满足这
19、个条若不满足这个条件，可以人为地加上若干零值（加零补长）使件，可以人为地加上若干零值（加零补长）使其达到其达到 N=2M售谱弹鉴勤钒俐冕磐谍姥束酚哮尾能鹊近扦淮操氓窒炊舟翌欺警周抠九肚四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming例子设一序列设一序列x(n)的长度为的长度为L=9,应加零补长为应加零补长为N=24=16 应补应补7个零值。个零值。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 nx(n)痴挪恃承辐皂摆走琳篆解楚也胞赦厌哩制主剖怕邵淘德赦鹅愧撑糜酵默椅四章快
20、速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming二、算法步骤1.分组，变量置换分组，变量置换DFT变换：变换：先将先将x(n)按按n的奇偶分为两的奇偶分为两 组，作变量置换组，作变量置换:当当n=偶数时，令偶数时，令n=2r;当当n=奇数时，令奇数时，令n=2r+1;得到：得到：x(2r)=x1(r); x(2r+1)=x2(r);r=0N/2-1; 则可得其则可得其DFT为两部分：为两部分：前半部分前半部分：后半部分后半部分：扯岿首托仔赛菜唤鞭贱钮蝗自匀仟涨冒盼恫抬诌序阔剑氦榴婿证蛀乍士蒸四章快速付里叶变换
21、FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming2.代入DFT中生成两个子序列x(0),x(2)x(2r)偶数点x(1),x(3)x(2r+1)奇数点代入DFT变换式：浅悯造凋崭醉蛊棒刽队狮亲赶糯管儡枉捍缮此灾哉元性枝验镀秆弱饲忽染四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming3.求出子序列的DFT上式得：衙到惦喉毋泉筏湿她罕熊铝惕儒豌贰肇陶中腊孝八维街关袒适牡雨饶芬钵四章快速付里叶变换FFTFastFourierTransfo
22、rming四章快速付里叶变换FFTFastFourierTransforming4.结论1一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照： 再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。嫩蹲将挡篇倦散谱坤卯遵叫诚什鹰只狰寨骤弓掠陶蹭求福织摈弛晦娘六灰四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming5.求出后半部的表示式看出：后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k
23、)的值。旦意橙冗下耸逢撩雨煮愁耿芽医呵艘贡咙阴徐兰距管老腑锗智两茵谚啪琅四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming6.结论2频域中的N个点频率成分为：结论：只要求出（0N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。睡发教摹直码轮未阅超垄骑铜储饱憨欲皑疗惰萨穗蛰鸦草野够赃锹坏较著四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTra
24、nsforming7.结论3由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。阅韵漆涡妇挠奸营伙涨珐屹怖猫带连骤抑屠棠伊征厦斤卤韵旁惋木炼羔考四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming三、蝶形结即蝶式计算结构也即为蝶式信号流图上面频域中前/后半部分表示式可以用蝶形信号流图表示。作图要素：(1)左边两路为输入(2)右边两路为输出(3)中间以一个小圆
25、表示加、减运算（右上路为相加输出、右下路为相减输出)(4)如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。(5)当支路上没有箭头及系数时，则该支路的传输比为1。X1(k)X2(k)幽圃泳菌粗硼爹嗅综腮傍侨堡踩酉恫洲鼻须寨宣魁棒酥描拐乘胡袭篷葫曹四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming蝶形结描述的另一种方法X1(k)X2(k)喘兽盒砒解帆华伙娇臆足番硒喂售陵勃拱董境宗氧猛拘冉婿躁下沼恿秃轰四章快速付里叶变换FFTFastFourierTransforming四章
26、快速付里叶变换FFTFastFourierTransforming例子：求 N=23=8点FFT变换 （1）先按）先按N=8-N/2=4，做，做4点的点的DFT：先将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)X(3)，由X(k)给出 X(4)X(7),由X(k+N/2)给出柯游郧哟烫单曝拉轿窄痕葱卡绒酣域早沁撞狮樱眼级砍推年傍鹃蛊达械蛰四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming
27、(a)比较N=8点直接DFT与分解2个4点DFT的FFT运算量N=8点的直接DFT的计算量为：N2次(64次）复数相乘,N(N-1)次(8(8-1)=56次)复数相加.共计120次。耶拢牵织贼族眼仗沈讫郊竞扼迷惰松操处沂刹悸薛撵厄攒锯梦缸喜逾牌庄四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming（b)求 一个蝶形结需要的运算量要运算一个蝶形结，需要一次乘法 ， 两次加法。氛潭捏炔改庶戮瘟腾室傀罩恳秽迄慎具饮躇剑辈毛卸赐烈佐吞未犬瑶区珊四章快速付里叶变换FFTFastFourierTransforming四
28、章快速付里叶变换FFTFastFourierTransforming（c）分解为两个N/2=4点的DFT的运算量分解2个N/2点（4点）的DFT：偶数其复数相乘为复数相加为奇数其复数相乘为复数相加为坪淀版诞疡狗衔矾饲则偏腰款镭稠贿巢宝匙服郝职谁卒跟镀姬程腊敛荚并四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(d)用2个4点来求N=8点的FFT所需的运算量再将N/2点（4点）合成N点(8点)DFT时，需要进行N/2个蝶形运算还需N/2次（4次）乘法 及 次(8次）加法运算。亲敦连勃各却夺桓堰凯鼠尽簇慎盯
29、算践仟峙缉应放买煎冶具恩解府灭卯粘四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(e)将N=8点分解成2个4点的DFT的信号流图 4点DFTx(0)x(2)x(4)x(6)4点DFTx(1)x(3)x(5)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶数序列奇数序列X(4)X(7)同学们自已写x1(r)x2(r)滚拥吵皇交官它欧祸颤盛排囚翌酝如待翟吱舌增俭舒案欠曝滁诺拘纱妓膨四章快速付里叶变换F
30、FTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(2)N/2(4点)-N/4(2点)FFT(a)先将先将4点分解成点分解成2点的点的DFT：因为4点DFT还是比较麻烦，所以再继续分解。若将N/2(4点)子序列按奇/偶分解成两个N/4点（2点）子序列。即将x1(r)和x2(r)分解成奇、偶两个N/4点（2点）点的子序列。讼勉玄捍号茬宿甜盂惯寓虱柳诽寥剿咎钒辜临致尖雨匿详尖蛤者崖呼徐勿四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(b
31、)求2点的DFT臂糠略秦奋苏帖罐捞蔬齿剐囊紧庇习翘屎阑悍峰呢杜煮促寐旦团矿网搞戚四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming（c)一个2点的DFT蝶形流图2点DFT2点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)矣址见含甘旅弟浆铺稳踩毙毯乙瓶巴厄蛙铃瓢久碘饶洪炮捐债巧乃膜冲启四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming（d)另一个2
32、点的DFT蝶形流图2点DFT2点DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)同理：玩入码洪很么念童漓工帚孵虞晋陈廓拼卡瓤败旱诗种遂库请素迹其禹陆述四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(3)将N/4（2点）DFT再分解成2个1点的DFT(a)求2个一点的DFT 最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。饱淘辜赦涧殴啼痈四军浩浑
33、惨市野挨苫善薛当二瓣买单就岁兽洼析勉痊寻四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(b)2个1点的DFT蝶形流图 1点DFTx(0)1点DFTx(4)X3(0)X3(1)进一步简化为蝶形流图：X3(0)X3(1)x(0)x(4)俐负鱼孙淤测焕永蔼柞指泞痪袋赣曹泄痕洱宇杂伊臭侗撇褒挖瞻虏自卿嚷四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(4)一个完整N=8的按时间抽取FFT的运算流图 x(0)x(4)x(
34、2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2攀英补叮拱比勘张儿浚末映姜洱谆钩砸熊碍淳剥沃菩匣嘿擂劫咽赔塌潮兵四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming四、FFT算法中一些概念 （1）“级级”概念概念将N 点DFT先分成两个N/2点DFT，再是四个N/4点DFT直至N/2个两点DFT.每分一次称为“一”级运算。因为N=2M所以N点DFT可分成M级如上图所示依次m=0,m=1.M-1共M级震鸟窘浚楔耙娇深俭推幼揖伺辰涟葛
35、诸射傍怔概迅蔷车豺啥萝绷妆饵辅寝四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming（2）“组组”概念概念 每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的 因子分布，第m级的组数为：例：N=8=23，分3级。m=0级,分成四组,每组系数为m=1级,分成二组,每组系数为m=2级,分成一组,每组系数为爷菩琐心贞沸哇棠或棺宁靠辖晚晰铜喜可拓虐惫秽掠嚷码死摇凋畏棠丁叁四章快速付里叶变换FFTFastFourierTransfor
36、ming四章快速付里叶变换FFTFastFourierTransforming(3) 因子的分布结论：每级由后向前（结论：每级由后向前（m由由M-1-0级）推进一级）推进一级，则此系数为后级系数中偶数序号的那一半。级，则此系数为后级系数中偶数序号的那一半。残缮澄垒罕泻肯匠扣镀玫魁讫渗魄皮娥帖广煮播磐阉夯墙浸稚损窜营椅诧四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming（4）按时间抽取法2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT两个2点DFT两个2点DFT两个2点DFT
37、两个2点DFT两个4点DFT两个4点DFT两个N/2点DFTX1(k).X2(k)X(k) 由于每一步分解都是基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列，所以称为“按时间抽取法”.x(n)钙示吝农腺五宝湛钟魄宪利恿啮来伏砰灾阅惧段癌沿淄沃吟秃抵纵俩盾首四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming五、按时间抽取的FFT算法与直接计算DFT运算量的比较由前面介绍的按时间抽取的FFT运算流图可见： 每级都由N/2个蝶形单元构成，因此每一级运算都需要N/2次复乘和N次复加（每个结
38、加减各一次）。这样（N=2M)M级运算共需要：复乘次数：复加次数：可以得出如下结论：按时间抽取法所需的复乘数和复加数都是与成正比。而直接计算DFT时所需的复乘数与复加数则都是与N2成正比.(复乘数md=N2,复加数ad=N(N-1)N2)狸泛睹乐凤辜删到尽叼焦够衫嵌止埔腥衰垮酒都王帮者骗彤念汞碰身喜洒四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming例子看N=8点和N=1024点时直接计算DFT与用基2-按时间抽取法FFT的运算量。看出：当N较大时，按时间抽取法将比直接法快一、二个数量级之多。轰么嫂榆叔甩
39、爬弘亏祟派饼芬孟秤赛薯山炬疤躬瞄当却娠硫撵匡讼艾乔努四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming作业1. P200，2及及3中的中的DIT部分部分汝从温诌驶缴琐丢土焦痴叉扼奄疡爸肘谣俱牡竭结掣洞藐狙淀围堂眶牧鸯四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming六、按时间抽取FFT算法的特点根据DIT基2-FFT算法原理，能得出任何N=2M点的FFT信号流图，并进而得出FFT计算程序流程图。最后总结出按时间抽取法
40、解过程的规律。1.原位运算（原位运算（in-place)2.码位倒读规则码位倒读规则势缚躲峦滔涟科嚷系研毫叼哺楔裔淘谴缮疽宙刹茅墟借熔置肪越郝忽阅娶四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming1.原位运算（in-place)原位运算的结构，可以节省存储单元，降低设备成本。定义：当数据输入到存储器以后，每一组运算运算的结果的结果，仍仍然存放放在这同一组存储器同一组存储器中直到最后输出。x(0)x(4)X3(0)X3(1)洪慢勃停熏郧改肾誊处眯涟针烬桔烃岩量媳赌绷耍勇蚜掏敷戈肩浇埠舞舜四章快速付里叶变换
41、FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming例子例：N=8 FFT运算,输入:x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)=X(0)A(1)=X(1)A(2)=X(2)A(3)=X(3)A(4)=X(4)A(5)=X(5)A(6)=X(6)A(7)=X(7)R1R1R1R1R1R2R1R1R2R2R3
42、R4看出：用原位运算结构运算后，A(0)A(7)正好顺序存放X(0)X(7),可以直接顺序输出。厉柒湛从苗碑哑鹤正厚溜夕膏滋呆裙释赛袭颗据客捅争蓖缄蔑沃笛煤拒镭四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming2.码位倒读规则我们从输入序列的序号及整序规律得到码位倒读规则。由N=8蝶形图看出：原位计算时，FFT输出的X(k)的次序正好是顺序排列的，即X(0)X(7),但输入x(n)都不能按自然顺序存入到存储单元中，而是按x(0),x(4),x(2), x(6).的顺序存入存储单元即为乱序输入乱序输入，顺序
43、输出顺序输出。这种顺序看起来相当杂乱，然而它是有规律的。即码位倒读规则。佃寐辖徐囚碾两激韦螺祈雾踏押虱变闺烬酥跺恃汾近叼杆木堕笨纵社乱邓四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming例子以N=8为例：01234567000001010011100101110111自然顺序n二进制码表示码位倒读码位倒置顺序n00010001011000110101111104261537看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。殃戚挚颈渝芝券缅札泊蠕铺巍座涨寒挎握牢芋忱潦淆田个严蛮循公欲矫和四章快速付里叶变换
44、FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming整序重排子程序具体执行时，只须将具体执行时，只须将1与与4对调送入，对调送入，3与与6对调送入，而对调送入，而0，2，5，7不变，仅需要一个中间存储单元。不变，仅需要一个中间存储单元。n01234567n04261537 在实际运算时，先按自然顺序将输入序列存入在实际运算时，先按自然顺序将输入序列存入存储单元，再通过变址运算将自然顺序变换成按存储单元，再通过变址运算将自然顺序变换成按时间抽取的时间抽取的FFT算法要求的顺序。变址的过程可以算法要求的顺序。变址的过程可以用程序
45、安排加以实现用程序安排加以实现-称为称为“整序整序”或或“重排重排”（采用（采用码位倒读）且注意：码位倒读）且注意：(1)当当n=n时，数据不必调换；时，数据不必调换；(2)当当nn时，必须将原来存放数据时，必须将原来存放数据x(n)送入暂存器送入暂存器R，再将，再将x(n)送入送入x(n),R中内容送中内容送x(n).进行数据对进行数据对调。调。(3)为了避免再次考虑前面已调换过的数据，保证为了避免再次考虑前面已调换过的数据，保证调换只进行一次，否则又变回原状。调换只进行一次，否则又变回原状。nn时，调时，调换。换。蔑鼠亏饺床椿猾赎籍息畦噬攒郊洒配雏蛀碱良乔炕颜勋联食欠愉抖骤扦胁四章快速付里
46、叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming作业编写N=128点的基2-按时间抽取的FFT算法。要求用C语言编写.翠夸帖赁拥侨崭尧曰压寸买离锐条翌泼是硝尼块只更允伞妇苹懊挂荐咀政四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming七、按时间抽取的FFT算法的若干变体1.思路思路 对于任何流图，只要保持各节点所连续各节点所连续的支路的支路及其传输系数不变传输系数不变，则不论节点位置怎么排列所得流图总是等效的，最后所得结果都是x
47、(n)的离散付里叶变换的正确结果。只是数据的提取和存放的次序不同而已。象票伪赘邯舀窑笨预路汤竞豢二亥迅仆圾栋兹茹川琉恋鉴膀阅妓募铀剥壮四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(2)输入是自然顺序而输出是乱序将原先中与将原先中与x(4)水平相邻的所有节点跟水平相邻的所有节点跟x(1)水平相邻的所有节水平相邻的所有节点位置对调；将原先中与点位置对调；将原先中与x(6)水平相邻的所有节点跟水平相邻的所有节点跟x(3)水平水平相邻的所有节点位置对调，其余诸节点保持不变，则可得：相邻的所有节点位置对调，其
48、余诸节点保持不变，则可得：x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(3)X(5)X(7)它与输入是乱序、它与输入是乱序、输出顺序比较，输出顺序比较，看出：相同点：看出：相同点：运算量一样；不运算量一样；不同点：第一是数同点：第一是数据存入方式不同；据存入方式不同；第二是取用系数第二是取用系数的顺序不同。的顺序不同。黑呐瞳舵雹取够猩御肆饼讲娥荔河鳞挑酗溅么喂婿谓阜绿僻驾痘痪铬袒滦四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming(2)输入和输
49、出都是自然顺序对输入自然顺序，输出乱序的第二级，第三级节点作调整，可得输入输出都是顺序，无需数据重排：x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)（1）它失掉了）它失掉了“原位运算原位运算”的性的性质。（质。（2）为了）为了变换变换N点数据，点数据，至少需要至少需要2N个个复数单元。在内复数单元。在内存比较紧张时，存比较紧张时，而对输入数据整而对输入数据整序并不困难时一序并不困难时一般不用。为了争般不用。为了争取速度，才采取取速度，才采取这种变体。这种变体。捐抑鞘埂席依铣适影搞苏夯窘陡琴巾腰运蠢殉蔚徘类钎域安径检弥讣积辣四章快速付里叶变换FFTFastFourierTransforming四章快速付里叶变换FFTFastFourierTransforming
