《三章快速付里叶变换FFTFastFourietTransformer.ppt》由会员分享，可在线阅读，更多相关《三章快速付里叶变换FFTFastFourietTransformer.ppt（63页珍藏版）》请在三一文库上搜索。
1、第三章快速付里叶变换(FFT)Fast Fouriet Transformer,豆嗣馅堆蚀脂沤揩以纹牢斤披艳累叛磁蹋陷茁蹿熙双滩奸胃阁贬择扬窝搐三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,第一节 引 言,适爱锹蕉婆混退等罐杰壹欢荆戴携融匿垢持躯烈祟嵌痔倘谦吠赌惦现骨廊三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,一、快速付里叶变换FFT,有 限 长 序 列 通 过 离 散 傅 里 叶 变 换 (D F T) 将
2、 其 频 域 离 散 化 成 有 限 长 序 列 . 但 其 计算 量 太 大, 很 难 实 时 地 处 理 问 题 , 因 此 引 出 了 快 速 傅 里 叶 变 换(FFT) . FFT 并 不 是 一 种 新 的 变 换 形 式 ,它 只 是 DFT 的 一 种 快 速 算 法 . 并 且 根 据 对 序 列 分 解 与 选 取 方 法 的 不 同 而 产 生 了 FFT 的 多 种 算 法 . FFT 在 离 散 傅 里 叶 反 变 换 、 线 性 卷 积 和 线 性 相 关 等 方 面 也 有 重 要 应 用.。,相虎隔洁裁妨韧涩策概菩沥起唇息停垂摈争诡橱表侯芜哆闹袱一构履微鹰三章快
3、速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,二、FFT产生故事,当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基(J.W.Turkey)正在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。1965年库利-图基在、Mathematic of Computation 杂志上发表了著名的“机器计算付里级数的一种
4、算法”文章，提出一种快速计算DFT的方法和计算机程序-揭开了FFT发展史上的第一页，促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件， 使DFT的运算大简化了。,涕渠厂滥臭陛蹋忱咖耍览摄按两趟闽骋铲贤他悔龚坞虏宵酵回茨凋最瑟售三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,三、本章主要内容,1.直接计算DFT算法存在的问题及改进途径。 2.多种DFT算法(时间抽取算法DIT算法，频率抽取算法DIF算法，线性调频Z变换即CZT法) 3.FFT的应用,楷瞥之碰夸碗吃
5、盏畏溺矗认类削渺奖舟宿垢皋寥持丫回砧磁撒拿摩辖沮镭三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,第二节直接计算DFT算法存在的问题及改进途径,砂孤龄翻聊卉论五呈冬陌效块枢埋钵炳丢侨股妹碉投雄缅伎诣耐桨诌毙手三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,一、直接计算DFT计算量,问题提出： 设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算，共需多大的运算工作量?,嫉忍吝颠镐僧褒急榨锋棋负骡稳伦
6、奎讨囊陕奉禽串茨旅殃烃荐柏袄足藻粉三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,1.比较DFT与IDFT之间的运算量,其中x(n)为复数， 也为复数 所以DFT与IDFT二者计算量相同。,洁潦码咆颐饿圈氮古凄遗伸器募旧责料惺闸鹰宫蝶潍柞肤囊堆矽避釉桓干三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,2.以DFT为例，计算DFT复数运算量,计算一个X(k)(一个频率成分)值，运算量为 例k=1则 要进行N次复数乘法+
7、(N-1)次复数加法 所以，要完成整个DFT运算，其计算量为： N*N次复数相乘+N*(N-1)次复数加法,辆芦光抖靡伶横菜罩次张索腕澜戳锡遭氖审涛突败常死鞘蠕靛摩仍灸火疮三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,3.一次复数乘法换算成实数运算量,复数运算要比加法运算复杂，需要的运算时间长。 一个复数乘法包括4个实数乘法和2个实数加法。 (a+jb)(c+jd)=(ac-bd)+j(bc+ad),4次复数乘法,2次实数加法,嗡姓汾啸役无睛雁法提胎巡匪歇睦阁厄役帆饵芍乙逐苏踢反等零溶惧香庞三章快速付里
8、叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,4.计算DFT需要的实数运算量,每运算一个X(k)的值，需要进行 4N次实数相乘和 2N+2(N-1)=2(2N-1)次实数相加. 整个DFT运算量为：4N2次实数相乘和2N(2N-1)次实数相加. 由此看出：直接计算DFT时，乘法次数与加法次数都是和N2成比例的。当N很大时，所需工作量非常可观。,喉娄剿歹霉苏价氖姻刺设潭椭脸瓤溅状图曲嘎吊徘费宏颤巳琵靶车缄蚌槐三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFouri
9、etTransformer,例子,例1:当N=1024点时，直接计算DFT需要： N2=(1024)2=1048576次，即一百多万次的复乘运算这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求-迫切需要改进DFT的计算方法，以减少总的运算次数。 例2：石油勘探，24道记录，每道波形记录长度5秒，若每秒抽样500点/秒， 每道总抽样点数=500*5=2500点 24道总抽样点数=24*2500=6万点 DFT运算时间=N2=(60000)2=36*108次,荔眯返抹早帛肪噶喂筐二午怜爸紊拂笨穿静疚丢荒炯慕愧钟尖咳村常根轿三章快速付里叶变换FFTFastFourietT
10、ransformer三章快速付里叶变换FFTFastFourietTransformer,二、改善DFT运算效率的基本途径,利用DFT运算系数 的固有对称性和周期性，改善DFT的运算效率。 1.合并法：合并DFT运算中的某些项。 2.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。,黔大腑自遇甩棠慨摄舵螺壤锗周蠢捍戊戏遁郴迸善翱替均啃县傍抨沼读略三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,利用DFT运算系数 的固有对称性和周期性，改善DFT的运算效率,的对称性：,的周期性：,因为：,由此
11、可得出：,晌货黔筑润台撞价侄话砧辣向膛陶瘁冤我表兜峙喻峪湛陆迄步润搏翠镭户三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,例子,例:,利用以上特性,得到改进DFT直接算法的方法.,危饿岭钳钵氛有简张郧装融皿瞒躺吓搭恶危舆倘隐触罢蟹悉鼠池勒勒竭凛三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(1) 合并法：步骤1分解成虚实部,合并DFT运算中的有些项 对虚实部而言 所以带入DFT中：,攒签哟吟绥芥妇钡贿递慎宁傅访缮径
12、让谜詹羽撮碗使魂藩昧诬毗簇亦拔还三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(1) 合并法：步骤2代入DFT中,展开：,扩瘩形猾谓膨蜂禁杖酚闸慢严亮嫉眼锰空等肘心扑催星滚唾艰寂拳崩冰险三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(1) 合并法：步骤3合并有些项,根据：,有：,悯夸茧醒挛陶立野摔雌枚间怠闸扣鼠恰壮哗乘车殿遍遮候伞雅撤沁蔷异达三章快速付里叶变换FFTFastFourietTransformer三章
13、快速付里叶变换FFTFastFourietTransformer,(1) 合并法：步骤4结论,由此找出其它各项的类似归并方法：乘法次数可以减少一半。 例：,叙稚边淤洲脊承四部我综背真哨拈墙醇妆闲秦抓脖愁胆壮河必野嘘募焙巢三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,2、将长序列DFT利用对称性和周期性分解为短序列DFT-思路,因为DFT的运算量与N2成正比的 如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。,病鹅南窃桶砒锐椽钦杉魔盒溜竣缀其煮胆世莆摄象缠迄饲涛
14、呻漱洼苦凑铺三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,2、将长序更DFT利用对称性和周期性分解为短序列DFT-方法,把N点数据分成二半：,其运算量为：,再分二半：,+,=,+,+,+,=,这样一直分下去，剩下两点的变换。,阮皱廷粮篆薯荒孪皇截迁帛腑剑瞩鲸犊欢诸皋咨孟雕棠敷苦耕右雾刨饲哗三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,2、将长序更DFT利用对称性和周期性分解为短序列DFT-结论,快速付里时变换(F
15、FT)就是在此特性基础上发展起来的，并产生了多种FFT算法，其基本上可分成两大类： 按抽取方法分： 时间抽取法(DIT);频率抽取法(DIF) 按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法 其它方法：线性调频Z变换(CZT法),县竖扯潘贯拳侵傲历穴拟也羚庐毁种肚淘疯畸靳烈界植媳峰拼迁屯牧闻盾三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,第三节基-2按时间抽取的FFT算法Decimation-in-Time(DIT)(Coolkey-Tukey),胎职椅颠鼠驼豪厌霞
16、粳婪柞熊绣锅跟响薪详骄毖测拢信深铺保肝雹降嗜梨三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,一、算法原理,设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。 其中基数2-N=2M，M为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M,赎嗡庞寓证初芳秒猩慈挎澡蔷洪莲哨淳贬好药杂宁战肩旁婪箭绝隐业画起三章快速付里叶变换FFTFastFourietTransformer三章快速
17、付里叶变换FFTFastFourietTransformer,例子,设一序列x(n)的长度为L=9,应加零补长为 N=24=16 应补7个零值。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n,x(n),客像弘氖啤酿滚屑靶刽糖棘知泻妮嘘洲韧乃面柄式醚他吨戈俞谍多影追狰三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,二、算法步骤1.分组，变量置换,DFT变换：,先将x(n)按n的奇偶分为两 组，作变量置换: 当n=偶数时，令n=2r; 当n=奇数时，令n=2r+1; 得到：x
18、(2r)=x1(r); x(2r+1)=x2(r);r=0N/2-1; 则其DFT可化为两部分： 前半部分： 后半部分：,蜂幼悸显跋诣威伤礼带沥雍嫩伙评侮版磋瑟暑线纹涯贡笔铜怠陌奄册铲纵三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,2.代入DFT中,生成两个子序列,x(0),x(2)x(2r)奇数点 x(1),x(3)x(2r+1)偶数点,代入DFT变换式：,通汀芋芯富佃何廉凯蝎芹散郭裕丙务施淑啥化缮镇益月饿圾刁超落销蛛悍三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶
19、变换FFTFastFourietTransformer,3.求出子序列的DFT,上式得：,幕嘲砚寞逸茂髓迪敝噎曙剃耙击驴凤夺咀慑奶喇诚岿菱苹阅袁凄凭督控桃三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,4.结论1,一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：,再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。,赁住乐医睬鸵蔚喀促桨理豫脆翱频岔猎辨秩弧邻窖郡粤斋鸽褂窜往渝朴宛三章快速付里叶变换FFTFastFourietT
20、ransformer三章快速付里叶变换FFTFastFourietTransformer,5.求出后半部的表示式,看出：后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。,仅车份瘁祭碗门扫芜克昂酋寥注耪迈椅肺这痘把迈峡德混煮祷薛匠翔嫂惰三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,6.结论2,频域中的N个点频率成分为：,结论：只要求出（0N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0N-1)整个区间内全部X(k)值，
21、这就是FFT能大量节省计算的关键。,羽铡赴掸矛孪朽椽惠湾亲巫尸电郧慎俱苞凯惮术竣牙哼翅谩旧督沉僵芭订三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,7.结论3,由于N=2L，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。,糜氮石坍觅测锋慰椅实咱气配姚夕椿图偶赴傍卓蔫就戳牵挂贴厄撞迄惠臼三章快速付里叶变换FFTFastFourietTransformer三章快速付里
22、叶变换FFTFastFourietTransformer,三、蝶形结,即蝶式计算结构也即为蝶式信号流图 上面频域中前/后半部分表示式可以用蝶形信号流图表示。,X1(k),X2(k),作图要素： (1)左边两路为输入 (2)右边两路为输出 (3)中间以一个小圆表示加、减运算（右上路为相加输出、右下路为相减输出),(4)如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。,(5)当支路上没有箭头及系数时，则该支路的传输比为1。,藐瞩杆粹面棺措痞妊妈炎旗催件千衫拽鹤拇淡砸秉特统上疥坟撒赴显惮辞三章快速付里叶变换FFTFastFourietTransformer三章快速
23、付里叶变换FFTFastFourietTransformer,例子：求 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)给出,歹钎宁排坷医咆秤垣惊宛镀旅韭霖诅儡异扳溯柱鲤徒寇哺桑巍屎筒钱沙蛛三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(a)比较N=
24、8点直接DFT与分解2个4点DFT的FFT运算量,N=8点的直接DFT的计算量为：N2次(64次）复数相乘,N(N-1)次(8(8-1)=56次)复数相加.共计120次。,恐烟一孜别尖证瑟砍揍所钎纯当瞒碱拔坊骂娃腺剧庆劳类辕赦允诅皆淀鲍三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,（b)求 一个蝶形结需要的运算量,要运算一个蝶形结，需要一次乘法 ， 两次加法。,畔颂颐烧吕诈穷戮脏坞爱肪擎会貌狞聘釜代去甭私晚野剑商卜雌寂荧铲不三章快速付里叶变换FFTFastFourietTransformer三章快速付里
25、叶变换FFTFastFourietTransformer,（c）分解为两个N/2=4点的DFT的运算量,分解2个N/2点（4点）的DFT：,偶数 其复数相乘为 复数相加为,奇数 其复数相乘为 复数相加为,涧吁图诺铃惦量石租徊蛀比仲差从拌棕绵廖娱糖牵殷亚氖鄂娱雅碧窄搞歹三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(d)用2个4点来求N=8点的FFT所需的运算量,再将N/2点（4点）合成N点(8点)DFT时，需要进行N/2个蝶形运算,还需N/2次（4次）乘法 及 次(8次）加法运算。,膛许瑶绦蜒略劲譬芜监
26、精掖汐甥崎啤尖纪并且剔材己雹责菊郎馁炮颁借支三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(e)将N=8点分解成2个4点的DFT的信号流图,4点 DFT,x(0) x(2) x(4) x(6),4点 DFT,x(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),痔惯泰辩
27、抽咒蔽右驰层俐闰枫账最氟獭鲤懊柬汹萝渺匹绦慑朔庶夷摸底未三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(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点）点的子序列。,恰哎播娩几与柠棵鄂拖顾禾绞宗涌史压蓖闲综蚌朗津留撰迅押之驮疼柴腰三章快速付里叶变换FFTFastFourietTransformer三章快速付
28、里叶变换FFTFastFourietTransformer,(b)求2点的DFT,寝展征妻鸳美鳖赐砖疏们恐货透辛钱彩厌圆枝挪介宪傣炼甥阀帽耗证房阎三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,（c)一个2点的DFT蝶形流图,2点DFT,2点DFT,x(0) x(4),x(2) x(6),X3(0),X3(1),X4(0),X4(1),X1(0) X1(1),X1(2) X1(3),吕贺灼祈蒂附驰限项兄誊筑诌劣给拥借凰疽铡薯沿冶齿墙好幕佯亢删祝谴三章快速付里叶变换FFTFastFourietTransfo
29、rmer三章快速付里叶变换FFTFastFourietTransformer,（d)另一个2点的DFT蝶形流图,2点DFT,2点DFT,x(1) x(5),x(3) x(7),X5(0),X5(1),X6(0),X6(1),X2(0) X2(1),X2(2) X2(3),同理：,悬牧嚷耕层屋卖崎蝇咎钮岳殿香蚕砖磺瞄佳讫朽缆锰杖熏国勤烷脖鸽菩又三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(3)将N/4（2点）DFT再分解成2个1点的DFT(a)求2个一点的DFT,最后剩下两点DFT,它可分解成两个一点D
30、FT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。,熄毡念救泻恰国兽漳罪堂读抠仲惺塌烁卜测康奉窟赶伏惟塘犁郎宰霄议饶三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(b)2个1点的DFT蝶形流图,1点DFT,x(0),1点DFT,x(4),X3(0) X3(1),进一步简化为蝶形流图：,X3(0) X3(1),x(0),x(4),獭挚嚼还禹增忻甸齐睁诵苔运勃盂拜港茵搁脊剥免岿雹雕痛翅诺击荔翰竟三章快速付里叶变换FFTFastFourietTransforme
31、r三章快速付里叶变换FFTFastFourietTransformer,(4)一个完整N=8的按时间抽取FFT的运算流图,x(0) x(4) x(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=0,m=1,m=2,懈吮眉齐绵俞啊它昆证屿朴侈萍臼钻啥蝇候棚机推橡坊故露咐俊睡筹秃沥三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,四、FFT算法中一些概念 （1）“级”概念,将N 点DFT先分成两个N/2点DFT，再是四个
32、N/4点DFT直至N/2个两点DFT.每分一次称为“一”级运算。 因为N=2M所以N点DFT可分成M级 如上图所示依次m=0,m=1.M-1共M级,甩察丛淘漠网帛透潞谗族燃氧联镶尝拟体掀丰亡台撬找李客秆谗羚执篡晤三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,（2）“组”概念,每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的 因子分布，第m级的组数为：,例：N=8=23，分3级。 m=0级,分成四组,每组系数为 m=1级
33、,分成二组,每组系数为 m=2级,分成一组,每组系数为,变滥痢搂趁法灿唐嘱他价玄呻互聋偏掉斌痹城揪狂烬姻闭勾侦娜陨洼糖涩三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(3) 因子的分布,结论：每由后向前（m由M-1-0级）推进一级，则此系数为后级系数中偶数序号的那一半。,禽浸尤确族缩中刁笼唁屠霹眼酵晕缴涪舱恫忱猛据残虑瘤敏蒸筛磁倒抄叫三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,（4）按时间抽取法,2点DFT,2
34、点DFT,2点DFT,2点DFT,2点DFT,2点DFT,2点DFT,2点DFT,两个2点 DFT,两个2点 DFT,两个2点 DFT,两个2点 DFT,两个 4点DFT,两个 4点DFT,两个 N/2点 DFT,X1(k),.,X2(k),X(k),由于每一步分解都是基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列，所以称为“按时间抽取法”.,x(n),娃茎离履颇黍烧亦幽御海泥算态奸谰巷娠臭挨蜀看烛敌接员鳃笺碘锯沉碴三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,五、按时间抽取的F
35、FT算法与直接计算DFT运算量的比较,由前面介绍的按时间抽取的FFT运算流图可见： 每级都由N/2个蝶形单元构成，因此每一级运算都需要N/2次复乘和N次复加（每个结加减各一次）。这样（N=2M)M级运算共需要： 复乘次数： 复加次数： 可以得出如下结论： 按时间抽取法所需的复乘数和复加数都是与 成正比。而直接计算DFT时所需的复乘数与复加数则都是与N2成正比.(复乘数md=N2,复加数ad=N(N-1)N2),至踌闸渠攫磺山天浅祥曳孙坯似目站腺黑侠凭嘱虚术诧子呆偶糟矢孩急盲三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTran
36、sformer,例子,看N=8点和N=1024点时直接计算DFT与用基2-按时间抽取法FFT的运算量。,看出：当N较大时，按时间抽取法将比直接法快一、二个数量级之多。,札龋豹案晌宣励遁疡历抚挝嗽钟舱祖陵亦亥象膨害名诲驰短我酗腑较滴阀三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,作业,1.N=16点的FFT基2-按时间抽取流程图。 2.P252. 2，3，8,凉塌磷谭孕垢尊恿恩炳疤每卷玛表孤雕胳醒竹阜灼势旱撵潮戳名蚊芹调俯三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变
37、换FFTFastFourietTransformer,六、按时间抽取FFT算法的特点,根据DIT基2-FFT算法原理，能得出任何N=2m点的FFT信号流图，并进而得出FFT计算程序流程图。最后总结出按时间抽取法解过程的规律。 1.原位运算（in-place) 2.码位倒读规则,诲舅釜回乱为料屯黎侈僵尚枉啃摄卒祖色复缮添越沧蛇诣览字境绸图剃骤三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,1.原位运算（in-place),原位运算的结构，可以节省存储单元，降低设备成本。 定义：当数据输入到存储器以后，每一组
38、运算的结果，仍然存放在这同一组存储器中直到最后输出。,x(0),x(4),X3(0) X3(1),后喘狮呸直祥猫庶欧憾抬宏竟彼樟秃斌蛾画粕凰各棋冕藤臭庶砍壤锨抱腾三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,例子,例：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
39、(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),R1,R1,R1,R1,R1,R2,R1,R1,R2,R2,R3,R4,看出：用原位运算结构运算后，A(0)A(7)正好顺序存放X(0)X(7),可以直接顺序输出。,卵唾泽饲损趾依管下屠猴圈柠儿井看唾楼罪晤脏胳矮郊串舍寂沮俞锄惕苍三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,2.码位倒读规
40、则,我们从输入序列的序号及整序规律得到码位倒读规则。由N=8蝶形图看出：原位计算时，FFT输出的X(k)的次序正好是顺序排列的，即X(0)X(7),但输入x(n)都不能按自然顺序存入到存储单元中，而是按x(0),x(4),x(2), x(6).的顺序存入存储单元即为乱序输入，顺序输出。这种顺序看起来相当杂乱，然而它是有规律的。即码位倒读规则。,络鸥也术趋霖身逼沈汛拟恿厚都享串绒竟签流缅称珠拽摄拣责辩也座甭撮三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,例子,以N=8为例：,0 1 2 3 4 5 6 7
41、,000 001 010 011 100 101 110 111,自然顺序,二进制码表示,码位倒读,码位倒置顺序,000 100 010 110 001 101 011 111,0 4 2 6 1 5 3 7,看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。,谢铸麻杏瘤剃韧课莹扫煤戈荣颗成迎瓤青玄闰雨愧蹈灯闲代踏灰膊抉咳窿三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,整序重排子程序,具体执行时，只须将1与4对调送入，3与6对调送入，而0，2，5，7不变，仅需要一个中间存储单元。,n 0 1 2 3
42、4 5 6 7,n 0 4 2 6 1 5 3 7,在实际运算时，先按自然顺序将输入序列存入存储单元，再通过变址运算将自然顺序变换成按时间抽取的FFT算法要求的顺序。变址的过程可以用程序安排加以实现-称为“整序”或“重排”（采用码位倒读）且注意： (1)当n=n时，数据不必调换； (2)当nn时，必须将原来存放数据x(n)送入暂存器R，再将x(n)送入x(n),R中内容送x(n).进行数据对调。 (3)为了避免再次考虑前面已调换过的数据，保证调换只进行一次，否则又变回原状。nn时，调换。,白痘愉唆麻枫掖拭漫蓉践林抱熔社锰角籽瞅抹卸螟阎蜀琵榔叙栓敦鬼肠轰三章快速付里叶变换FFTFastFouri
43、etTransformer三章快速付里叶变换FFTFastFourietTransformer,作业,编写N=128点的基2-按时间抽取的FFT算法。要求用C语言编写，并将输入数据放在文件inputdata.dat中，输出数据放在outputdata.dat文件中。,磨妮蚕眷苍懒秀板悍滤垦蚌郑庐探艇瞬粕凛首孤来次毖蹿个颁她摆摔倍寸三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,七、按时间抽取的FFT算法的若干变体1.思路,对于任何流图，只要保持各节点所连续的支路及其传输系数不变，则不论节点位置怎么排列所得
44、流图总是等效的，最后所得结果都是x(n)的离散付里叶变换的正确结果。只是数据的提取和存放的次序不同而已。,泞脆掩撼崔找独怜绘沈驾夏朗奥昧网野桅蔓泄牡妇曙辫雷胞胆迈圭呵泅涕三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(2)输入是自然顺序而输出是乱序,将原先中与x(4)水平相邻的所有节点跟x(1)水平相邻的所有节点位置对调；将原先中与x(6)水平相邻的所有节点跟x(3)水平相邻的所有节点位置对调，其余诸节点保持不变，则可得：,x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7),
45、X(0) X(4) X(2) X(6) X(1) X(3) X(5) X(7),它与输入是乱序，输出顺序比较，看出：相同点：运算量一样；不同点：第一是数据存入方式不同；第二是取用系数的顺序不同。,铡省悄司漳京撂套拦睁借想恬唁糖寿氖哭叮伐逾辫堂妈贬拙朱帘阁煎劈妊三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,(2)输入和输出都是自然顺序,对输入自然顺序，输出乱序的第二级，第三级节点作调整，可得输入输出都是顺序，无需数据重排：,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个复数单元。在内存比较紧张时，而对输入数据整序并不困难时一般不用。为了争取速度，才采取这种变体。,欣受蹲慧企袱搭衔苞癌愁秉闹李周脾恨筷哑驹假疆妮映谐报浮漱会底短戍三章快速付里叶变换FFTFastFourietTransformer三章快速付里叶变换FFTFastFourietTransformer,