数字信号处理程佩青第三课件第四章快速傅里叶变换FF

第四章

快速傅里叶变换

（FFT）主要内容DIT-FFT算法DIF-FFT算法IFFT算法Chirp-FFT算法线性卷积的FFT算法§4.1引言FFT:

FastFourierTransform1965年，Cooley-Turky发表文章《机器计算傅里叶级数的一种算法》，提出FFT算法，解决DFT运算量太大，在实际使用中受限制的问题。FFT的应用：频谱分析、滤波器实现、实时信号处理等。TI芯片TMS320系列

DSP芯片实现。TI公司的TMS320c30，10MHz时钟，基2-FFT1024点FFT时间15ms。典型应用：信号频谱计算、系统分析等系统分析频谱分析与功率谱计算§4.2直接计算DFT的问题及改进途径1、DFT与IDFT2、DFT与IDFT运算特点复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)同理：IDFT运算量与DFT相同。实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)3、降低DFT运算量的考虑FFT算法分类:时间抽选法 DIT:Decimation-In-Time频率抽选法 DIF:Decimation-In-Frequency§4.3按时间抽取（DIT）的FFT算法（DecimationInTime）1、算法原理 设序列点数N=2L，L为整数。若不满足，则补零将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。将N点DFT定义式分解为两个长度为N/2的DFT记：………（1）（这一步利用：）再利用周期性求X(k)的后半部分将上式表达的运算用一个专用“蝶形”信流图表示。注：a.上支路为加法，下支路为减法；b.乘法运算的支路标箭头和系数。用“蝶形结”表示上面运算的分解： 分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计运算量减少了近一半进一纵步分法解由于，仍为偶数，因此，两个点DFT又可同样进一步分解为4个点的DFT。“蝶蛾形”嫂信流非图表默示N点DF锈T分解鹿为四示个N/4点的DF慌T类似勾的分碎解一调直继穷续下臣去，颜直到女分解耐为最闷后的刷两类翁蝶形酷运算川为止(2点DF蔽T)苍.如上产述N=8桶=23，N/4恰=2点中驾：类似澡进一截步分惧解1点DFTx(0)1点DFTx(4)X3(0)X3(1)进一定步简告化为渗蝶形音流图杠：X3(0)X3(1)x(0)x(4)因此8点FF样T时间肠抽取码方法侦的信锁流图域如下——FF抹T运算席量与饿运算支特点1．N=2L时，呀共有L=l倦og2N级运州算；讽每一解级有N/2个蝶棉形结堡。2．每淋一级携有N个数报据中前间数育据，凭且每壁级只仰用到乎本级掘的转伟入中炸间数颈据，待适合归于迭赔代运本算。3．计锤算量着：每级N/2次复云乘法开，N次复查加(每蝶搜形只折乘一搂次，悄加减郊各一扔次)共有L*枪N/姥2=情N/席2l爪og2N次复口乘法;复加过法L*稠N=景Nl秆og2N次与直骂接DF吉T定义械式运烧算量促相比(倍数)原N2/(牢Nl秧og2N)挽,当N大时歇，此秤倍数慨很大凡。比较DF算T参考P1机50表4-前1图4-汤6可以替直观照看出胖，当络点数N越大菠时，FF臂T的优扮点更魔突出任。按时企间抽矮取FF份T蝶形倒运算浅特点1、关肥于FF泼T运算兔的混齿序与迎顺序状处理岂（位锋倒序耍处理切）由于料输入静序列济按时尊间序丈位的略奇偶刑抽取疾，故交输入计序列滨是混郊序的两，为侦此需辈要先驻进行昌混序许处理涨。混序厚规律恩：x(n)按n位置银进行啦码位翼（二镰进制殊）倒祸置规窗律输铅入，浴而非票自然游排序联，即烈得到唱混序棕排列食。所厨以称锻为位倒脾序处皂理。位倒玻序实拐现：（1）DS踏P实现滋采用者位倒踏序寻伟址（2）通搏用计数算机晶实现最可以本有两姐个方鲁法：追一是计严格隐按照絮位倒索序含尤义进霉行；胆二是鸡倒进满位的者加N/融2。倒位序自然序0000000010041001010220101106301100114100101551010113611011177111倒位逃序例巨计算眯，妙。计遵算虎点FF做T。用时贴间抽印取输潮入倒戏序算疫法，啦问倒锦序前橡寄存飞器的晕数口和滑倒序页后仁的渐数据棒值？解：嘴倒序岸前倒序倒序阿为倒序忽后DI考T辅FF答T中最浸主要巴的蝶拉形运亡算实港现（1）参孔与蝶旅形运映算的劣两类幕结点稿（信锹号）做间“涌距离棍”（床码地取址）忧与其怪所处右的第书几级兆蝶形落有关正；第m级的岔“结牺距离桐”为(即原圆位计脊算迭魄代）（2）每训级迭王形结镜构为蝶形隐运算艺两节袋点的陶第一妨个节盯点为k值，叠表示输成L位二胁进制轰数，谊左移L龟–格m位，对把右隔边空勺出的浅位置限补零鸟，结纲果为r的二奸进制语数。（3）煮的确见定：第m级的r取值模：四、FF思T算法雅中一拖些概献念（1）“队级”浴概念将N点DF码T先分则成两捎个N/2点DF猫T，再是绳四个N/4删点D孩FT脏…直芬至N/2想个两乱点D日FT设.每分胸一次肚称为胃“一砖”级托运算早。因为N=2M所以N点D传FT政可分丸成M级如上里图所捕示依语次m=0,m=1….M-1摆共M级（2）“肺组”办概念每一熊级都索有N/悔2个蝶慌形单欠元，上例如串：N昨=8筹,则乔每级蜓都有笑4个修蝶形惩单元掌。每一准级的N/蜡2个蝶侍形单漂元可凳以分售成若策干组权，每搭一组福具有法相同辜的结园构，姐相同珠的妨因熄子分同布，番第m级的坛组数箭为：例：N=凶8=辫23，分3僻级。m=复0级,分成涝四组,每组售系数继为m=房诚1级,爹分成炉二组寒,每柄组系竭数为m=雪2级,毯分成救一组街,每陆组系野数为(3闯)因子猪的分舱布结论博：每布由后跃向前吼（m由M-1皱--丘>0板级）慢推进唱一级声，则早此系司数为化后级碰系数钓中偶绸数序施号的堆那一请半。DI睁T算法勉的其唉他形钟式流谊图输入如倒位痕序输饺出自损然序输入招自然孔序输百出倒雁位序输入馋输出仙均自核然序相同工几何辛形状输入钓倒位本序输登出自叛然序输入馅自然屠序输膝出倒累位序参考P1次54畅-1令55时间勉抽取划、龙输入司自然锦顺序膜、估输出雹倒位燥序的FF仪T流图例用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为 次，仅为直接计算DFT所需时间的10万分之一。即原需要3000小时，现在只需要2分钟。§4辩.4按频饰率抽驴取（DI触F）的FF进T算法与DI斧T-决FF宅T算法剧类似准分解汗，但准是抽累取的简是X(k)。即分捎解X(k)成奇脆数与幸偶数牙序号时的两金个序打列。设：N=榴2L，L为整芹数。站将X(k)按k的奇鹅偶分决组前眠，先掌将输壶入x(n)按n的顺哪序分调成前借后两集半：（D绑ec心im翼at怎io存n阳In估F岩re产qu朵en沟cy背)一、称算法究原理下面却讨论按k的奇冶偶将X(k)分成慕两部轿分：显然劈燕：令：用蝶意型结田构图芬表示越为：x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2点DFTN/2点DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)N/浪2仍为片偶数浸，进讽一步粘分解损：N/腥2→N/行4x3(0)x3(1)-1-1x4(0)x4(1)N/4点DFTN/4点DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)按照该以上延思路治继续业分解营，即刘一个N/尝2的DF展T分解抵成两虽个N/妥4点DF汗T，直到笑只计者算2点的DF筑T，这就容是DI荡F-速FF齐T算法码。2个1点的DF嘱T蝶形靠流图进一暴步简豪化为稀蝶形株流图芒：1点DFTx3(0)1点DFTx3(1)X(0)X(4)X(0)X(4)x3(0)x3(1)二、匪按频耗率抽锐取FF揉T蝶形祸运算毯特点1）原吃位计永算-1L级蝶迁形运穿算，仓每级N/2个蝶惜形，驻每个稳蝶形冠结构始：m表示种第m级迭暂代，k，j表示项数据怒所在络的行测数2）蝶垂形运法算对N=2L点FF午T，输入汉自然摆序，牧输出西倒位潜序，两节族点距寨离：2L-处m=N/悉2m第m级运殊算：蝶形卷运算驻两节丑点的呼第一弃个节让点为k值，逆表示辩成L位二毯进制贩数，绿左移m-1位，帅把右宏边空福出的郑位置妹补零拨，结眨果为r的二脱进制宗数。存储粘单元输入产序列x(n)侧:N个存乱储单芝元系数：N/2个存储单元三、DI适T与DI猛F的异下同基本纱蝶形随不同DI谁T:先复历乘后县加减DI贱F:先减诊后复似乘运算妄量相窗同都可呀原位稠运算DI查T和DI洋F的基携本蝶拾形互促为转匙置§4姥.5真ID桃FT的FF看T算法疯（FF句T应用环一）一、姿从定六义比胃较分明析与DF顽T的比波较：1）旋羡转因殊子WN-kn的不徒同；2）结篮果还枣要乘1/罢N。二、混实现许算法——直接承使用FF法T程序踢的算智法共轭FFT共轭乘1/N直接灿调用FF团T子程刺序计戴算IF叙FT的方据法：§4添.6线性娘调频Z变换成（Ch浇ir弄p-银Z变换丘）算娇法（FF卧T应用稼二）单位钉圆与土非单葛位圆呼采样（a）沿单音位圆闸采样;梦(庙b)沿AB弧采街样螺线稍采样zk=AW-kk=0尖,甚1,墓…搂,M-1Ch菌ir遭p-触Z变换饥的线爬性系灭统表格示由于系统的单位脉冲响应可以想象为频率随时间(n)呈线性增长的复指数序列。在雷达系统中,这种信号称为线性调频信号（ChirpSignal），因此，这里的变换称为线性调频Z变换。一、猎基本种算法急思路§4甘.7线性骑卷积只的FF案T算法活（FF倦T应用劈燕三）若L点x(n)，M点h(n)，则直剪接计羽算其纽奉线性临卷积y(n)需运社算量丘：若系驶统满捐足线呼性相佳位，每即：则需卸运算口量：FF罢T法：具以圆电周卷译积代欠替线松性卷银积N总运算量：次乘法比较得直接膝计算容和FF街T法计欺算的培运算泉量讨论捐：1）当2）当x(只n)长度盾很长垂时，泉将x(可n)分为L长的亭若干认小的涌片段停，L与M可比抢拟。1、重悲叠相财加法则：输出岔：其中顽：可以用圆筒周卷桐积计颈算：选，上面圆周卷积可用FFT计算。N由于yi(n)长度凭为N，而xi(n)长度L，必有M-1点重启叠，yi(n)应相愚加才鹿能构碰成最怨后y(n)的。重叠诸相加颂法图虫形和上面的讨论一样，用FFT法实现重叠相加法的步骤如下:

①计算N点FFT，H(k)=DFT［h(n)］；②计算N点FFT，Xi(k)=DFT［xi(n)］；③相乘，Yi(k)=Xi(k)H(k)；④计算N点IFFT，yi(n)=IDFT［Yi(k)］；⑤将各段yi(n)（包括重叠部分）相加， 。重叠相加的名称是由于各输出段的重叠部分相加而得名的。例鉴已贤知序匪列x[敌n]仙=n占+2姑,0n12舟,艘h[皆n]该={永1,规2,尘1}试利用拴重叠贤相加驶法计甲算线钓性卷亏积,取L=与5。y[姿n]凝={猾2,咽7配,府12翻,他16黑,露20娇,拳2灶4,崇2退8,农3旺2,趣3党6,辞4晓0,拒4末4,针4虑8,枯5袍2,渠4倚1,境1裁4}解:重叠健相加泻法x1[n粘]=挠{2榆,伴3,种4村,叫5,橡6苹}x2[n虽]=也{7百,领8,贝9延,的10靠,搁11腾}x3[n哗]=暑{1论2,板13冷,捉14龟}y1[n泻]=倡{2哑,施7傅,仇12火,接16屡,凭2匪0,躁17挺,贯6等}y2[n液]=荐{库7,沃22含,析32踪蝶,绩36劣,环40拣,派32赏,邮11袍}y3[n渔]=雷{1采2,馋3闭7,颠5存2,鱼4裁1,弦1炕4}2、重寒叠保这存法此方赚法与糕上述谜方法徐稍有闷不同假。先将x(n)分段铲，每壤段L=N-M+1个点辩，这杏是相宣同的字。不同插之处杏是，南序列缠中补聪零处俩不补蛮零，黑而在败每一监段的益前边嫩补上及前一前段保叉留下明来的蝇（M-1）个输宪入序赢列值肿，制组成L+M-1点序判列xi(n)。如果L+M-1片<2m，则可痛在每努段序待列末虹端补述零值斗点，吗补到借长度情为2m，这时虚如果笔用DF克T实现h(n)和xi(n)圆周滥卷积单，则韵其每仓段圆挤周卷您积结驳果的兼前（M-1）个点询的值剂不等和于线棕性卷来积