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

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

N點(diǎn)DFTN/2點(diǎn)

DFTN/4點(diǎn)

DFT

2點(diǎn)

DFT

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

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

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

DFT將分解：DecimationInTime,DIT時(shí)間抽取將分解：DecimationInFreq.,DIF頻率抽取各是N/2點(diǎn)的

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

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

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

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

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

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

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

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

Pruning

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

其中：

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

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

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

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

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