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

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

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

DFTN/4點(diǎn)

DFT2點(diǎn)

DFT

1個(gè)2個(gè)4個(gè)N/2個(gè)問題是如何分最有效？可以對時(shí)間變量分（DIT)，也可對頻率變量分(DIF）令：分解后的運(yùn)算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)N/2點(diǎn)DFT(N/2)2N/2(N/2–1)兩個(gè)N/2點(diǎn)DFTN2/2N(N/2–1)一個(gè)蝶形12N/2個(gè)蝶形N/2N總計(jì)運(yùn)算量減少了近一半

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

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

DFT則X(2r)和X(2r+1)分別是x1(n)和x2(n)的N/2點(diǎn)DFT，記為X1(k)和X2(k)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點(diǎn)DFTN/2點(diǎn)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仍為偶數(shù)，進(jìn)一步分解：N/2N/4x3(0)x3(1)-1-1x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X