《數(shù)字信號處理題解及電子課件》-電子課件

第4章快速傅立葉變換（FFT）4.1概述4.2時間抽取基2算法4.3頻率抽取基2算法4.4減少運算量的措施4.5分裂基算法4.6線性調(diào)頻Z變換4.7其它算法4.1概述解決耗時的乘法問題是將數(shù)字信號處理理論用于實際的關(guān)鍵問題。特別是30年前，計算機(jī)的速度相當(dāng)慢。因此，很多學(xué)者對解決DFT的快速計算問題產(chǎn)生了極大的興趣。CooleyJW,TukeyJW.AnalgorithmforthemachinecomputationofcomplexFourierseries.MathematicsofComputation,1965,pp297~301DSP的正式開端！FFT的思路：如何充分利用這些關(guān)系？四點DFT幾個乘法？4.2時間抽取基2算法FFT的核心思想是：

N點DFTN/2點

DFTN/4點

DFT

2點

DFT

1個2個4個N/2個問題是如何分最有效？可以對時間變量分（DIT)，也可對頻率變量分(DIF）令：

都是N/2點的DFT，它們各自又可分成N/4點的DFT，如此繼續(xù)分下去，直至兩點DFT。兩點DFT不需要乘法運算：每一級有N/2個如下的“蝶形”單元：即:每一個蝶形單元僅需一個復(fù)數(shù)乘法，兩個復(fù)數(shù)加法。兩點構(gòu)成一個蝶形單元，并且這兩點不再參與別的蝶形單元的運算。同址運算。

所需運算量：注意：因子的位置；輸入序列的順序－－碼位倒置。00000000100001101001021100113001100410110150111106711111174.3頻率抽取基2算法令：各是N/2點的

DFT將分解：DecimationInTime,DIT時間抽取將分解：DecimationInFreq.,DIF頻率抽取各是N/2點的

DFT繼續(xù)分解，直到兩點DFT注意DIT和DIF的對偶性質(zhì)。輸入正序，輸出倒序。注意因子的位置4.4進(jìn)一步減少運算量的措施旋轉(zhuǎn)因子（twiddlefactor)FFT中乘法運算主要來自和復(fù)指數(shù)相乘：（1組）（2組）（4組）（N/2組）復(fù)數(shù)乘法數(shù)（N/4組）不需要乘法，無關(guān)緊要的旋轉(zhuǎn)因子（trivial~)M級，前兩級都是，去除之：后M-2級，含有個再去除之：（復(fù)乘）兩個復(fù)數(shù)相乘，需要四次實乘、兩次實加。實現(xiàn)和的相乘，需兩次實乘，兩次實加。

N點FFT中，有多少個虛部和實部相等，trivial~將所有無關(guān)緊要的旋轉(zhuǎn)因子去除，或單獨考慮，有：？個實乘實加各種算比較的基礎(chǔ)以上稱為多蝶形單元運算；單獨處理實數(shù)據(jù)的輸入；采用新的FFT算法。措施：多蝶形單元運算所需計算量的比較

基－2算法：1965年，DSP發(fā)展的里程碑；基－4算法:對基－2算法的改進(jìn)；

分裂基算法：1984年，接近最優(yōu)的FFT！4.5分裂基(Split-radix)算法Winograd

算法：1976年提出，是具有鮮明特色的FFT!用到較多的數(shù)論知識，可用于N不等于2的整次冪?；?DIF的基本單元：以4為基，分解時級數(shù)可減少1半，因此可減少乘法次數(shù)。不需要乘法！乘法數(shù)減少一半？所需計算量：基2基4分裂基要求:掌握導(dǎo)出方法極限：基2DIF:

旋轉(zhuǎn)因子都出現(xiàn)在奇序號項輸出，在求出偶序號項時不需要乘法。每一級都是如此?；?和基4算法的比較：基4？令則分析上述結(jié)果可知，在基－4算法中，N/4個偶序號輸出也要乘W因子。而基－2算法的偶序號項都不要乘W因子。如何將基－2和基－4的優(yōu)點都兼收？請思考：對偶序號項輸出用基－2算法，對奇序號項輸出用基－4算法。分裂基算法令則基2/4算法各種算法所需計算量的比較4.6輸入和輸出點數(shù)不相同的FFTDFT：輸入N點，輸出N點,輸入、輸出點數(shù)相同。輸出的N點均勻分布于單位圓上，頻域分辨率為

在實際應(yīng)用中：1.當(dāng)輸入點數(shù)極少時，若希望頻率分點較多，則需要補(bǔ)零，結(jié)果是增加了計算量;2.對于窄帶信號，我們只希望通帶內(nèi)分點密，帶外可以較疏，或根本不用計算。解決方案1.Pruning2.CZT如何解決？一、輸入端

Pruning（DIF）不需要的不計算！二、輸出端

Pruning

（窄帶情況）不需要的不計算！二、CZT

其中：

Z在其ROC內(nèi)取值，現(xiàn)為Z指定一離散的路徑：

Z變換：做DFT時，Z變換在單位圓上的等分的N個點上取值。CZT時，離散路徑可在單位圓內(nèi)、外，或圓上。CZT在Z平面上的變換路徑是一條螺旋線決定CZT的起點；決定變換路徑如何傾斜決定變換的步長。信號的點數(shù)N和變換路徑的點數(shù)M可以不相等。

CZT變成了DFT時，起點在單位圓外，反之，在圓內(nèi)；

時，內(nèi)旋，反之外旋；時,CZT變換路徑為單位園上一段弧，CZT的特點CZT可計算單位圓上任一段曲線上的Z變換，可任意給定起止頻率；作變換時輸入的點數(shù)N和輸出點數(shù)M可以不相等；可達(dá)到頻域“細(xì)化”的目的。CZT的計算：由定義：令：由于：所以：則：式中：CZT的實際計算方法：1.是點系列，由所決定：2.是雙邊無窮長序列，由定義所決定：3.是點序列，由需要所決定。

如何卷積？?點序列與本章有關(guān)的MATLAB文件與本章內(nèi)容有關(guān)的MATLAB文件主要是fft,ifft和czt.m。顧名思義，fft實現(xiàn)快速傅立葉變換，ifft實現(xiàn)快速傅立葉反變換，