《离散时间信号处理英文版chap9第1讲.ppt》由会员分享，可在线阅读，更多相关《离散时间信号处理英文版chap9第1讲.ppt（32页珍藏版）》请在三一办公上搜索。
1、Ch9.Computation of the Discrete Fourier Transform,遥垮早注忌惧霖竣憎活节娠滴围瑚栓肩慷激络蔡阀枷食炙廖漠确吭侨昨文离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,Main contents,Decimation-In-Time FFT algorithm(DIT-FFT),Decimation-In-Frequency FFT algorithm(DIF-FFT),IFFT,咏乌劲席康蜂啮寅茂敬韩沤琼暖貌甲苟谱镐纤吭铡撕永歧榨篮介嗡霸螺蚀离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文
2、版）chap9-第1讲,9.0 Introduction,The Fast Fourier Transform(FFT)is not a new algorithm which is different from the DFT,but an efficient algorithm for fast computation of the DFT.,在眉交烷旷袖队煽沾清构尔与谚硕足益揣县缀鞍恃论鹊砚群铲州裂涝慢帛离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,9.1 Efficient Computation of the DFT,The direct
3、computation of DFT,N,N-1,N(N-1),4N,2N+2(N-1)=4N-2,懈碌宪庭盐达滁铂汽秩爹袭弃所播弦秉裁诉敬监范昼樟燎绷疽敷戮深贞诅离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,e.g.,N:,Complex Mul:,8,1024,64,1048576,The amount of computation(the computation time)required to compute the DFT by the direct method becomes very large for large N.,For th
4、is reason,we are interested in computational procedures that reduce the number of multiplications and additions.,钨钝剐球评谗纷夏浸陀谅剧皂豁葵灵蹲戈遣妊戒阉欲疆虏肆蛤啄股倘歌泌离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,(i)complex conjugate symmetry:,(ii)periodicity in n and k:,(iii)可约性:,Approaches to reduce the computation of D
5、FT by using the Properties of,(iv),勉拽铂摸堰铱竖腆鲤亥除郑啄榜澎襟导貉渣挑拭芭付湃戈屁蔼氏旺尺耻拢离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,FFT算法的基本思路,Decimation-In-Time FFT(DIT-FFT),Decimation-In-Frequency FFT(DIF-FFT),利用 的周期性、对称性、可约性，使DFT运算中某些项合并,将长序列的DFT分解为若干短序列的DFT,鸳焉琳爬附通寝墓汾铡蠕锁翁珊匪癣骋桥喜虾痘茬隔标爱攫钵懦诀庶蘸佃离散时间信号处理（英文版）chap9-第1讲离散时间
6、信号处理（英文版）chap9-第1讲,9.3.Decimation-In-Time FFT algorithms,The decomposition is based on decomposing the sequence xn into successively smaller subsequences.,鲍攀俘拟栈园赦坑汉纯烽烧叉币媳达熊监唇暑汽音摧授付贡他鸦漫刻政蚤离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,Principle of the DIT-FFT Algorithm,Let,radix-2 FFT,Decompose xn into
7、 two sequences according n is even or odd,亨窘甥瞩胚蛇恋宁拉篆滩引藏遣桂口丝代炎骡甲字俗纂清师儡法心工鹃殊离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,Then,Another half of Xk:,秘瘟帮影枣蓑苏川猖捍提鼓杉赞溺左衡错贞蛹辙试慎企贩申线巾狡体远砂离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,So,Butterfly Computation:,A N-point DFT is decomposed into two N/2-point DFTs,o
8、ne complex multiplication+two complex addition,速歇俞刘氰赐握奉奥倪笆堆铣阅庇阂饲怕震凌篆钨楞钓错凶豢细良尖膝姚离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,e.g.,complex mul:,complex add:,Computation=two N/2-point DFTs+N/2 butterflies,计算量减少大约一半,脱仿踌线弹穷妆葵崔墒愿霄宴泻涕兵僻消赠裴筛虱颊永唉闪缴椅秃帕孜置离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,(ii)The 2nd
9、 decomposition:,键访顺质的夸种戌屹社构谣乳嘻应悉轧卜卑廷鞋哲铁虐道闲奏夕喘析痢僻离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,Similarly,Then,a N-point DFT is decomposed into four N/4-point DFTs.,崔瑚廊北贷修禽裙彝狠瘁钱附罐莱爽患稗见肇疤鼓纱萤屎醚壕股搏泰菲析离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,计算量进一步减少大约一半,e.g.,Computation=Four N/4-point DFTs+2 stages bu
10、tterflies,舞渠良导袋骇扳弯庭禄创第窘略舶裤靶象秸栗戳暑亢休省醉蚊苍牲僧胸根离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,(iii)Further decomposition until 2-point DFTs are left,e.g.,侵蚕则勘烧烽沤供妙缨芬蛰路沽曰逞靛诡附完软勾坊袄握绳摊围扇编嗓毫离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,So,the 8-point DIT-FFT:,眠身睬映唱旅诲卤辊嚷嫂悬职逢害蹲朋脱沙毫仕淤似硝竹铃瘤唐疫氧斧预离散时间信号处理（英文版）chap9-第
11、1讲离散时间信号处理（英文版）chap9-第1讲,Computation of DIT-FFT,当 时，共有 级蝶形；每级都由N/2个蝶形运算组成，每个蝶形有1次复乘、2次复加，因此每级运算需N/2次复乘和N次复加。,v级运算总共需要 复乘和 复加。,煮星谤牛筛吮反徽炕星热弟犊墅久嫡篷薯泼裕既巢褂皋炕镍谎烈统灌蛔屎离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,(i)The DIT-FFT,complex mul:,complex add:,(ii)The direct DFT,complex mul:,complex add:,(iii)Ratio,
12、Comparison of the computation of DFT and DIT-FFT,船士铺祝侩巢晋儡础千页孩连材炊湾皖勃芋橱晃畔栏逢羡坪摆励演陨口辕离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,Comparison of the computation of DFT and DIT-FFT,裁裂咏头赞文赎遣栈窍送铜拉悍总尼婆力朽酉揖玖绚骇变毛叭米山撮毙悍离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,Characteristics of DIT-FFT,(i)In-Place Computati
13、ons(原位运算、同址运算),迭代运算：,啦峨采辞胳歪鹃时上躯心亦核挫买淄腐注霖诗妖减犬盈绚蹋台牵夹炮季绽离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,(i)In-Place Computations(原位运算、同址运算),第m级的两个节点p,q的值只与第(m-1)级的p,q两个节点有关，与其他节点均无关。因此，蝶形的两个输出值Xmp 和Xmq可以存放在蝶形的两个输入Xmp-1 和Xmq-1所在的存储器中(这种运算就称为原位运算)。每一级的蝶形运算全部完成后，再开始下一级的蝶形运算，直到最后输出，中间无需其他存储器。这样存储数据只需要N个存储单元。,
14、芝绊昼狗坐始惰戎蜡秉顽饶音巧桅摄邪森栋王枢医稽嘲匈弟掉蚀凛吱俄瞒离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,(ii)Bit-reversed order(倒位序),input:,bit-reversed order,胆泄接扛开让茨幻页腹肚睡择佬乾聊爆歌耿绦椒迢汐赂板责弧蹭擂轿大撕离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,The reason for bit-reversed order,锹悬淖题臆宅挤竭冠言夯辈涪钓里琼企甭翟试瑟陕线婉烯薯盯薪价蜗岭虎离散时间信号处理（英文版）chap9-第1讲离散时间
15、信号处理（英文版）chap9-第1讲,The realization of bit-reversed order,矢件队叼骡曾涕眷勘灭纲菠毙局史刻剖涸贤惩千举钞败荚躇匡播泛辙分抖离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,(iii)Distance between two source nodes of one butterfly,第一级(第一列)每个蝶形的两个节点间距离为1第二级(第二列)每个蝶形的两个节点间距离为2第三级(第三列)每个蝶形的两个节点间距离为4,依次类推，对于 点DIT-FFT，当输入为倒位序，输出为正常序时，其第m级运算每个蝶形
16、的两节点间距离为,旨给蛰渔闭绽摘憨敦勒揍倦闻意虞酋辑笛养热逾期凡走甚责机焊郧对喜移离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,(iv)Determine,最后一级有N/2种：,倒数第二级有N/4种:,依次类推，第一级有1种：,孩脂粗叼思循负嘉辱茄独甫丹低饺皆栈竭锐蹋骑揩膝以查临董镍婿拽拎母离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,(v)存储单元,存储输入序列 的N个存储单元单元，以及存储系数 的N/2个存储单元。,晋隆赐糠喇鸡泳丑猩砂浴气蒙艘高宛根挚抹笨铬羹瀑棘浓轰肪傲坑泥向辫离散时间信号处理（英文版
17、）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,Alternative Forms,只要保持各节点所连的支路及其传输系数不变，则不论节点位置怎么排列，所得流图总是等效的，所得结果都是xn的DFT的正确结果，只是数据的提取和存放顺序不同而已。,头供芳存汝屈棋堤哭废吼甜踩划翌抱系闪叔扭陨岩陋卉蒙噪惑矿牌拌褒谊离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,input in normal order,output in bit-reserved order,阀健垮聋燃蔚予氯采辉狰恶希脯源又豹蹋贿瓜泄婆港裤披啃嗣迅韵嘎慕鼻离散时间信号处理（英
18、文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,both input and output in normal order,突棱钒舔掠悟林呸阎挫么瓢弹谚陇委天剑阐瓣椭褒跨酗傍乔销右谈皮禁郎离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,input in bit-reserved order,output in normal order,with the same geometry for each stage,际竟捻蚌常寒雇挣缅含妒冲看疽派虎赢晦乡次疟衣趋秀饯端讥丑拒咏镣哭离散时间信号处理（英文版）chap9-第1讲离散时间信号处理（英文版）chap9-第1讲,
