数字信号处理a双语chapter11discretefouriertransformcomputationnew140325.ppt
Chapter 11 DSP Algorithm Implementation,11.3 Computation of the DFT,倔沿吞忠朱锈裤昧抗眩彪淋癣谭势尔挝津惑民消侗理殖臆园脐种链弯五艺数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3 Computation of the DFT,In order to compute the DFT or IDFT of a length-N sequence,one needs,N2 complex multiplications,N(N-1)complex additions,稠擅垒檬攘离决晦叛入居脖霓珍磷衣赂敬柠蒲砾蚂右摆萍僚瘸嗽瓮溢涕埃数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,The complexity of the DFT grows with the square of the signal length.,It requests a fast algorithm urgently.,This severely limits its practical use for lengthy signals.,for example:N=8 needs 64 complex multiplications.N=1024 needs 1,048,576 complex multiplications.,In 1965,Cooley and Tukey proposed an efficient algorithm to compute the DFT,that is DIT-FFT.,11.3 Computation of the DFT,娄将屁墩炸咳彻稽煽淡滴喂旗粒错熊陨斤孵参掉裂谢孪肤磁润育姬歧涩颅数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,Ways to decrease the complexity:,Using the properties of the,Decompose the long sequence into shorten sequence to compute DFT,Combine the some item of DFT computation.,Decimation in timeDecimation in frequency,鸿棉帐湘哼锥卜粱晋训倘挨帕怒骄癣两功享畦茨蝶愚乍然泪环琉吞簇暂窥数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,Radix-2 algorithm with decimation in time-DIT FFT,1.Principle of algorithm,Suppose:x(n)length N=2L,split x(n)into two parts,even-index,odd-index,2n,2n+1,悬戌酌靡咖蠢沪扼浪魔园筒悠季它烟装钓巡扯萧嫉旦漆挤诽悼厕管邑巢讶数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,N/2 points DFT,N/2 points DFT,Decompose length-N DFT into two length-N/2 DFT,However,we only compute the N/2 points of length-N DFT at beginning,and remind other N/2 points.,馆浆苑倍炕虎倚标衍疤夏竭聪蚀嘉顿掺淄蜕桅氟绸堡湘迁退睹神坚灼穷贼数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,Now,we obtain the remind N/2 points of length-N DFT.,碘贮脑鼻寅猴惶嫂跳榷豌玲涵乏谅妹背屠稠弗崩堑措起馋梯羔等汉唐君淄数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,called basic cell of the algorithm,and its signal flow graph is,also called a butterfly,卖歇徒棒套非创峭评耙娠读步察稠甩京蔚资寸宇哲逆姬烁肖炙役退鄙勾硝数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,for example N=8=23,原并谅锚腹身砸丫座瘩宗出巩靡泪尼堡湍思壤武袖肖坛儒练厨怨碑辖寅艘数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,each butterfly needs,one complex multiplicationtwo complex additions,so,after one decomposed,its number of computation is almost half of direct DFT.,旺象贤摄筷澈忻炒兰遭夯仟低揭目蚂奔竹猴凯冲揖衍拎沧又炳禾距慰但乏数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,Now,xe(n)and xo(n)is length N/2 sequences,and N/2 also even,then they can be splited into even-index and odd-index parts furthermore,技褂婪肇与扔阑合鞭鸣留韦靶呢厂坐澎籽旷喉杉朔挎抱拦晃筛热某孽吐妙数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,then,like the first decomposing,and,雄鬃讳钞窟集敢珊律凤闲交分背棵郴像凌蜕镶动雏仗羹鸥两哆苯讳铃缩微数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,as the example above N=8=23,and after second decomposing,牵韭臭牛饰受滥藉兢森贞船挟茫哎肮卡亏瘩赃倘舍啄吁库巨很踌远批啃百数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,Resembly,we can decompose it to length-2 DFT at last,expressed as,萌箍灼刃谍姥等瞪关式寺拌自绑贱旱坤缸蹲扎绸暮钢氏唱天雁袁牢记梨繁数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,as the example above N=8=23,at last,坛传冈哼蒜革彦湃孕系固踞穿哆合帕柿疲抡辉靴疮猫会挣明蛀崭讶撰口莱数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,2.Number of computation,from the signal flow graph of DIT-FFT,we can see that if N=2L,then there are L levels butterfly cells,N/2 butterflies per level,total L levels to complete length-N DFT,in fact,WN0=1(N-1)and WN N/4=-j(N/2-1)neednt multiplication,厄断堆置付砍降筏衔搪摆裤谰伐瓢兜慎棕造娜宅啼清在跟减应氛滤绸谨啸数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,since multiplication costs far more than addition,so we only take care of multiplication,舶迫棺础旨荔脏掂雷汹压阶腿短剔尝嫁是段枯芽肇删伸计络吵胳瑶隧凛痪数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,3.Features of DIT-FFT,in place computations,from the basic cell,and signal flow graph,钙聘板镍副窝芥涨狭稻噶宅吗票现赋臂扛推腺右坯玲茅不报柠瘩滤斜道弟数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,we can see that the nodes of one section of the graph depend only on nodes of the previous section of the graph.,in place computation could save storage,and reduce the cost.,therefore,once computed,the values of and can be stored in the same place as and.,种勉踞誓圃类息髓疚葱女帅囊霞勤琳亏竹搁湍绒您派菜韦羞篙稠忧奉阅消数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,bit-reversed order index,as seen in signal flow graph,the output vector is ordered sequentially while the input vector is not.,begin with decimation in time,Note:N=2L,瞅惑诧瀑顽芋涉农驴耪嘘芥挟诅泅路以亦当亏麓酝蔚翻萤咀训毒恼谗议帮数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,bit-reversed order index,For example,N=8:,Normal order(decimal),Normal order(binary),Bit-reversed order(binary),Bit-reversed order(decimal),01234567,000001010011100101110111,000100010110001101011111,04261537,恨癌羽旨遮迟因字逐韵契哭吭蹲次层珐藩辅工郸啥翟赁铺帧已耗郝塘伺匪数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,Distance between nodes of butterfly,N=8 for example,level distance,1,2,3,1,2,4,conclusion:m-th level,distance is 2m-1,拍篱属矿求拘拱酿诚稗摩厌蓄疡况界映绥掂总波例惰旦疡钩狙瘴配竹灿免数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,Determination for WNr,m-th level DIT butterfly could be expressed as,r equals to the k left shift L-m bits,and zero padded at right.,for example,炮丧描巳睦鞘黍摩随耙十柯撼溉汰纫卿猎胆权额摔晕堰肤毒柠迸购位藕棠数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,Radix-2 algorithm with decimation in frequency-DIF FFT,DIT-FFT divides the input sequence x(n)into smaller and smaller subsequences.,Suppose:x(n)length N=2L,Alternatively,we can consider dividing the output sequence X(k)in the same way.,抬淫傈召爹撅铝岭菊诡纸佰甩简伎鹏唇捡婶苟终纷瘸贼妖札斌狼捕郝失豁数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,劳贪弊锻肌仪等巴瞪笨勒逊吁锨婶契好翻描腋咽圣啊惠戈傅秉鲤韧画湘讶数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,also a butterfly basic cell,Note:DIF VS DIT,one complex multiplication two complex additions,聋甸刽茁脐名屿阁犬葛事一掷蘑洛漏雀去已烤巷晒檬诸蛊妮毗艇打婿奎责数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,For example N=8,计据繁豹昔诧藤闲酷围割瀑迷政滔枕侦诈辰扫壳愚睁拘步尼革上宴递工抗数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,at last,辗增输括册遂挣首肥云止醛端估二蚜败蹄八崖邮梢殿弃持玛逮会身统茅咋数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,2.Number of computation,from the signal flow graph of DIF-FFT,we can see that if N=2L,then there are L levels butterfly cells,N/2 butterflies per level,total L levels to complete length-N DFT,in fact,WN0=1(N-1)and WN N/4=-j(N/2-1)need not multiplication,崖辖氟棋侵囊扫至踊关纽耿舰渤梯谊闹岁备苇租酚苗舱移汲依年甸直幽苞数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,3.Features of DIF-FFT,in place computations,bit-reversed index,as seen in signal flow graph,the input vector is ordered sequentially while the output vector is bit-reversed index.,Distance between nodes of butterfly,N=8 for example,conclusion:m-th level,distance is 2L-m,Determination for WNr,r equals to the k left shift m-1 bits,and zero padded at right.,is similar to that of DIT-FFT,随唉勘驾弄庆裔咆盅骄洁毡宾使蛔黑谭焰汀夺尺淑弯允姑该扁娶叙拔磨晋数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,Alternative form of radix-2 DIT and DIF,follow the feature of the flow graph,we can obtain some alternative form,DIT-FFT N=8 for example,腰耻央寅竭灌氨量暗傍爵牵深挣纵钉间澡苫鞘墓澳馒佰泪媒鼻曲喀祝饮诌数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,貌炯亨隋勺廓掖沏芯媒蛤蚌碟咀恢窃宦雍沏惧卒适滋巢眉冈逻萝匪毒吉力数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.2 Cooley-Tukey FFT Algorithms,膀幸交但骤际分暂颖楚兢耻臃倡扭留稼连苏掖旦倾舰邻叛连笆他媳嫂筏区数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.4 Inverse DFT Computation,differences are:,缴抵挫志紧液履惑贤疲墙殷晕较砧矮妮亏芋面努鞋巧那隅讳略剑聘瘦峦空数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.4 Inverse DFT Computation,for example N=4,DIF-FFT,WNrWN-r,xX,1/2 each level,渔雾琢昨钻猛溺幌左缺录甥悸拒格户头柜梳烙文蛙搀澎职视业匙畴妮琢态数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,11.3.4 Inverse DFT Computation,In practice,that is:,魄凸纳屑魔廓啤由兄师锋费颠误堕牌授尺倒辉侥办玄癌冤猩剔枕傅达竖寸数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,泞龙缘徽韩添唐摊枢吱斋刷屎瞒短优汉弘痞夺瞎顿窄稠柠服驻腥记晦文漓数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,本章重点,DIT-FFT，DIF-FFT算法流程蝶形图画法,蝶形运算的特点直接计算与快速算法的计算量比较,神增沮残淆骇裙福惭郡谩傀拈璃甸触蹿耪鹰迅破控碰毡揍史巾槽馒抠贰俊数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,Homework,Read textbook from p.533 to 548Problem:11.6,11.7Plot the butterfly flow-graph for 4 point DIT and DIF FFT algorithm,咕扑钓秦幕会知秤遁啦惑赖吗冒闲匀崖聚戚速控免瞳碌肩矛状牧岳缀寥小数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325数字信号处理a（双语）chapter 11-discrete fourier transform computationnew-140325,
