《數(shù)字信號處理導(dǎo)論-第4章》課件

第4章快速傅立葉變換（FFT）4.1概述4.2時間抽取基2算法-DIT4.3頻率抽取基2算法-DIF4.1概述

解決耗時的乘法問題是將數(shù)字信號處理理論用于實際的關(guān)鍵問題。特別是30年前，計算機的速度相當(dāng)慢。因此，很多學(xué)者對解決DFT的快速計算問題產(chǎn)生了極大的興趣。CooleyJW,TukeyJW.AnalgorithmforthemachinecomputationofcomplexFourierseries.MathematicsofComputation,1965,pp297~301DSP的正式開端！FFT的思路：如何充分利用這些關(guān)系？四點DFT4.2時間抽取基2FFT的算法——DIT(DecimationInTime)FFT的核心思想是：N點DFTN/2點

DFTN/4點

DFT2點

DFT

1個2個4個N/2個問題是如何分最有效？可以對時間變量分（DIT)，也可對頻率變量分(DIF）令：分解后的運算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個N/2點DFT(N/2)2N/2(N/2–1)兩個N/2點DFTN2/2N(N/2–1)一個蝶形12N/2個蝶形N/2N總計運算量減少了近一半即:每一個蝶形單元僅需一個復(fù)數(shù)乘法，兩個復(fù)數(shù)加法。兩點構(gòu)成一個蝶形單元，并且這兩點不再參與別的蝶形單元的運算。同址運算。

所需運算量：注意：因子的位置；輸入序列的順序－－碼位倒置。0000000010000110100102110011300110041011015011110671111117運算量比較當(dāng)N=2M時，共有M級蝶形，每級N/2個蝶形，每個蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：比較DFT4.3頻率抽取基2FFT的算法——DIF(DecimationInFrequency)令：各是N/2點的

DFT則X(2r)和X(2r+1)分別是x1(n)和x2(n)的N/2點DFT，記為X1(k)和X2(k)N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/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)逐級分解，直到2點DFT當(dāng)N=8時，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,1輸入正序，輸出倒序。注意因子的位置DIT與DIF的異同基本蝶形不同DIT:先復(fù)乘后加減DIF:先減后復(fù)乘運算量相同都可原位運算DIT和DIF的基本蝶形互為轉(zhuǎn)置將分解：DecimationInTime,DIT時間抽取將分解：DecimationInFreq.,DIF頻率抽取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算法。措施：多蝶形單元運算所需計算量的比較4.7與本章有關(guān)的MATLAB文件與本章內(nèi)容有關(guān)的MATLAB文件主要是fft,ifft和czt.m。顧名思義，fft