快速傅立葉變換FFT課件

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

1個2個4個N/2個問題是如何分最有效？可以對時間變量分（DIT)，也可對頻率變量分(DIF）4.2時間抽取基2算法FFT的核心思想是：N點(diǎn)N/7令：令：8快速傅立葉變換FFT課件9

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

所需運(yùn)算量：注意：因子的位置；輸入序列的順序－－碼位倒置。所需運(yùn)算量：注意：1200000000100001101001021100113001100410110150111106711111170000134.3頻率抽取基2算法令：4.3頻率抽取基2算法令：14各是N/2點(diǎn)的DFT各是N/2點(diǎn)的15快速傅立葉變換FFT課件16將分解：DecimationInTime,DIT時間抽取將分解：DecimationInFreq.,DIF頻率抽取各是N/2點(diǎn)的DFT繼續(xù)分解，直到兩點(diǎn)DFT注意DIT和DIF的對偶性質(zhì)。將分解：DecimationInTime,17輸入正序，輸出倒序。注意因子的位置輸入正序，輸出倒序。注意因子的位置184.4進(jìn)一步減少運(yùn)算量的措施旋轉(zhuǎn)因子（twiddlefactor)FFT中乘法運(yùn)算主要來自和復(fù)指數(shù)相乘：（1組）（2組）（4組）（N/2組）復(fù)數(shù)乘法數(shù)（N/4組）4.4進(jìn)一步減少運(yùn)算量的措施旋轉(zhuǎn)因子（twiddle19不需要乘法，無關(guān)緊要的旋轉(zhuǎn)因子（trivial~)不需要乘法，無關(guān)緊要的旋轉(zhuǎn)因子（trivial~)20M級，前兩級都是，去除之：后M-2級，含有個再去除之：（復(fù)乘）M級，前兩級都是，去除21兩個復(fù)數(shù)相乘，需要四次實(shí)乘、兩次實(shí)加。實(shí)現(xiàn)和的相乘，需兩次實(shí)乘，兩次實(shí)加。N點(diǎn)FFT中，有多少個虛部和實(shí)部相等，trivial~將所有無關(guān)緊要的旋轉(zhuǎn)因子去除，或單獨(dú)考慮，有：？個兩個復(fù)數(shù)相乘，需要四次實(shí)乘、兩次實(shí)加。實(shí)現(xiàn)22實(shí)乘實(shí)加各種算比較的基礎(chǔ)以上稱為多蝶形單元運(yùn)算；單獨(dú)處理實(shí)數(shù)據(jù)的輸入；采用新的FFT算法。措施：實(shí)乘實(shí)加各種算比較的基礎(chǔ)以上稱為多蝶形單元運(yùn)算；措施：23多蝶形單元運(yùn)算所需計(jì)算量的比較多蝶形單元運(yùn)算所需計(jì)算量的比較24基－2算法：1965年，DSP發(fā)展的里程碑；基－4算法:對基－2算法的改進(jìn)；分裂基算法：1984年，接近最優(yōu)的FFT！4.5分裂基(Split-radix)算法Winograd算法：1976年提出，是具有鮮明特色的FFT!用到較多的數(shù)論知識，可用于N不等于2的整次冪。基－2算法：1965年，DSP發(fā)展的里程碑25基4DIF的基本單元：以4為基，分解時級數(shù)可減少1半，因此可減少乘法次數(shù)。不需要乘法！乘法數(shù)減少一半？基4DIF的基本單元：以4為基，分解時級數(shù)可減少1半26所需計(jì)算量：基2基4分裂基要求:掌握導(dǎo)出方法極限：所需計(jì)算量：基2基4分裂基要求:掌握導(dǎo)出方法極限：27基2DIF:旋轉(zhuǎn)因子都出現(xiàn)在奇序號項(xiàng)輸出，在求出偶序號項(xiàng)時不需要乘法。每一級都是如此?；?和基4算法的比較：基4？基2DIF:基2和基4算法的比較：基4？28令則令則29分析上述結(jié)果可知，在基－4算法中，N/4個偶序號輸出也要乘W因子。而基－2算法的偶序號項(xiàng)都不要乘W因子。如何將基－2和基－4的優(yōu)點(diǎn)都兼收？請思考：對偶序號項(xiàng)輸出用基－2算法，對奇序號項(xiàng)輸出用基－4算法。分裂基算法分析上述結(jié)果可知，在基－4算法中，N/4個偶30令則基2/4算法令則基2/4算法31快速傅立葉變換FFT課件32各種算法所需計(jì)算量的比較各種算法所需計(jì)算量的比較334.6輸入和輸出點(diǎn)數(shù)不相同的FFTDFT：輸入N點(diǎn)，輸出N點(diǎn),輸入、輸出點(diǎn)數(shù)相同。輸出的N點(diǎn)均勻分布于單位圓上，頻域分辨率為

4.6輸入和輸出點(diǎn)數(shù)不相同的FFTDFT：輸入N點(diǎn)，34在實(shí)際應(yīng)用中：1.當(dāng)輸入點(diǎn)數(shù)極少時，若希望頻率分點(diǎn)較多，則需要補(bǔ)零，結(jié)果是增加了計(jì)算量;2.對于窄帶信號，我們只希望通帶內(nèi)分點(diǎn)密，帶外可以較疏，或根本不用計(jì)算。解決方案1.Pruning2.CZT如何解決？在實(shí)際應(yīng)用中：解決方案1.Pruning如何解決？35一、輸入端Pruning（DIF）不需要的不計(jì)算！一、輸入端不需要的不計(jì)算！36二、輸出端Pruning（窄帶情況）不需要的不計(jì)算！二、輸出端不需要的不計(jì)算！37二、CZT

其中：

Z在其ROC內(nèi)取值，現(xiàn)為Z指定一離散的路徑： Z變換：二、CZT 其中：Z在其ROC內(nèi)取值，現(xiàn)為Z指定一離散的38做DFT時，Z變換在單位圓上的等分的N個點(diǎn)上取值。CZT時，離散路徑可在單位圓內(nèi)、外，或圓上。做DFT時，Z變換在單位圓上的等分的N個點(diǎn)上取值。CZT時39CZT在Z平面上的變換路徑是一條螺旋線決定CZT的起點(diǎn)；決定變換路徑如何傾斜決定變換的步長。信號的點(diǎn)數(shù)N和變換路徑的點(diǎn)數(shù)M可以不相等。CZT在Z平面上的變換路徑是一條螺旋線決定CZT的40CZT變成了DFT時，起點(diǎn)在單位圓外，反之，在圓內(nèi)；

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

如何卷積？?3.是點(diǎn)序列，由需要46快速傅立葉變換FFT課件47點(diǎn)序列點(diǎn)序列48與本章有關(guān)的MATLAB文件與本章內(nèi)容有關(guān)的MATLAB文件主要是fft,ifft和czt.m。顧名思義，fft實(shí)現(xiàn)快速傅立葉變換，ifft實(shí)現(xiàn)快速傅立葉反變換，czt.m用來實(shí)現(xiàn)線性調(diào)頻Z變換。fft的調(diào)用格式是：X=fft(x),或X=fft(x，N)。czt.m調(diào)用格式是：X＝czt(x,M,W,A)。x是待變換的時域信號，其長度設(shè)為N，M是變換的長度，W確定變換的步長，A確定變換的起點(diǎn)。若M=N,A=1,則CZT變成DFT。與本章有關(guān)的MATLAB文件與本章內(nèi)容有關(guān)的MATLAB文件49第4章快速傅立葉變換（FFT）4.1概述4.2時間抽取基2算法4.3頻率抽取基2算法4.4減少運(yùn)算量的措施4.5分裂基算法4.6線性調(diào)頻Z變換4.7其它算法第4章快速傅立葉變換（FFT）4.1概述504.1概述4.1概述51解決耗時的乘法問題是將數(shù)字信號處理理論用于實(shí)際的關(guān)鍵問題。特別是30年前，計(jì)算機(jī)的速度相當(dāng)慢。因此，很多學(xué)者對解決DFT的快速計(jì)算問題產(chǎn)生了極大的興趣。CooleyJW,TukeyJW.AnalgorithmforthemachinecomputationofcomplexFourierseries.MathematicsofComputation,1965,pp297~301DSP的正式開端！解決耗時的乘法問題是將數(shù)字信號處理理論用于實(shí)際的關(guān)鍵52FFT的思路：如何充分利用這些關(guān)系？FFT的思路：如何充分利用這些關(guān)系？53四點(diǎn)DFT四點(diǎn)DFT54幾個乘法？幾個乘法？554.2時間抽取基2算法FFT的核心思想是：N點(diǎn)DFTN/2點(diǎn)DFTN/4點(diǎn)DFT2點(diǎn)DFT

1個2個4個N/2個問題是如何分最有效？可以對時間變量分（DIT)，也可對頻率變量分(DIF）4.2時間抽取基2算法FFT的核心思想是：N點(diǎn)N/56令：令：57快速傅立葉變換FFT課件58

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

所需運(yùn)算量：注意：因子的位置；輸入序列的順序－－碼位倒置。所需運(yùn)算量：注意：6100000000100001101001021100113001100410110150111106711111170000624.3頻率抽取基2算法令：4.3頻率抽取基2算法令：63各是N/2點(diǎn)的DFT各是N/2點(diǎn)的64快速傅立葉變換FFT課件65將分解：DecimationInTime,DIT時間抽取將分解：DecimationInFreq.,DIF頻率抽取各是N/2點(diǎn)的DFT繼續(xù)分解，直到兩點(diǎn)DFT注意DIT和DIF的對偶性質(zhì)。將分解：DecimationInTime,66輸入正序，輸出倒序。注意因子的位置輸入正序，輸出倒序。注意因子的位置674.4進(jìn)一步減少運(yùn)算量的措施旋轉(zhuǎn)因子（twiddlefactor)FFT中乘法運(yùn)算主要來自和復(fù)指數(shù)相乘：（1組）（2組）（4組）（N/2組）復(fù)數(shù)乘法數(shù)（N/4組）4.4進(jìn)一步減少運(yùn)算量的措施旋轉(zhuǎn)因子（twiddle68不需要乘法，無關(guān)緊要的旋轉(zhuǎn)因子（trivial~)不需要乘法，無關(guān)緊要的旋轉(zhuǎn)因子（trivial~)69M級，前兩級都是，去除之：后M-2級，含有個再去除之：（復(fù)乘）M級，前兩級都是，去除70兩個復(fù)數(shù)相乘，需要四次實(shí)乘、兩次實(shí)加。實(shí)現(xiàn)和的相乘，需兩次實(shí)乘，兩次實(shí)加。N點(diǎn)FFT中，有多少個虛部和實(shí)部相等，trivial~將所有無關(guān)緊要的旋轉(zhuǎn)因子去除，或單獨(dú)考慮，有：？個兩個復(fù)數(shù)相乘，需要四次實(shí)乘、兩次實(shí)加。實(shí)現(xiàn)71實(shí)乘實(shí)加各種算比較的基礎(chǔ)以上稱為多蝶形單元運(yùn)算；單獨(dú)處理實(shí)數(shù)據(jù)的輸入；采用新的FFT算法。措施：實(shí)乘實(shí)加各種算比較的基礎(chǔ)以上稱為多蝶形單元運(yùn)算；措施：72多蝶形單元運(yùn)算所需計(jì)算量的比較多蝶形單元運(yùn)算所需計(jì)算量的比較73基－2算法：1965年，DSP發(fā)展的里程碑；基－4算法:對基－2算法的改進(jìn)；分裂基算法：1984年，接近最優(yōu)的FFT！4.5分裂基(Split-radix)算法Winograd算法：1976年提出，是具有鮮明特色的FFT!用到較多的數(shù)論知識，可用于N不等于2的整次冪。基－2算法：1965年，DSP發(fā)展的里程碑74基4DIF的基本單元：以4為基，分解時級數(shù)可減少1半，因此可減少乘法次數(shù)。不需要乘法！乘法數(shù)減少一半？基4DIF的基本單元：以4為基，分解時級數(shù)可減少1半75所需計(jì)算量：基2基4分裂基要求:掌握導(dǎo)出方法極限：所需計(jì)算量：基2基4分裂基要求:掌握導(dǎo)出方法極限：76基2DIF:旋轉(zhuǎn)因子都出現(xiàn)在奇序號項(xiàng)輸出，在求出偶序號項(xiàng)時不需要乘法。每一級都是如此?；?和基4算法的比較：基4？基2DIF:基2和基4算法的比較：基4？77令則令則78分析上述結(jié)果可知，在基－4算法中，N/4個偶序號輸出也要乘W因子。而基－2算法的偶序號項(xiàng)都不要乘W因子。如何將基－2和基－4的優(yōu)點(diǎn)都兼收？請思考：對偶序號項(xiàng)輸出用基－2算法，對奇序號項(xiàng)輸出用基－4算法。分裂基算法分析上述結(jié)果可知，在基－4算法中，N/4個偶79令則基2/4算法令則基2/4算法80快速傅立葉變換FFT課件81各種算法所需計(jì)算量的比較各種算法所需計(jì)算量的比較824.6輸入和輸出點(diǎn)數(shù)不相同的FFTDFT：輸入N點(diǎn)，輸出N點(diǎn),輸入、輸出點(diǎn)數(shù)相同。輸出的N點(diǎn)均勻分布于單位圓上，頻域分辨率為

4.6輸入和輸出點(diǎn)數(shù)不相同的FFTDFT：輸入N點(diǎn)，83在實(shí)際應(yīng)用中：1.當(dāng)輸入點(diǎn)數(shù)極少時，若希望頻率分點(diǎn)較多，則需要補(bǔ)零，結(jié)果是增加了計(jì)算量;2.對于窄帶信號，我們只希望通帶內(nèi)分點(diǎn)密，帶外可以較疏，或根本不用計(jì)算。解決方案1.Pruning2.CZT如何解決？在實(shí)際應(yīng)用中：解決方案1.Pruning如何解決？84一、輸入端Pruning（DIF）不需要的不計(jì)算！一、輸入端不需要的不計(jì)算！85二、輸出端Pruning（窄帶情況）不需要的不計(jì)算！二、輸出端不需要的不計(jì)算！86二、CZT

其中：

Z在其ROC內(nèi)取值，現(xiàn)為Z指定一離散的路徑： Z變換：二、CZT 其中：Z在其ROC內(nèi)取值，現(xiàn)為Z指定一離散的87做DFT時，Z變換在單位圓上的等分的N個點(diǎn)上取值。CZT時，