DSP第4章快速付里葉變換FFT

1、第四章快速付里葉變換(FFT)Fast FourierTransforming弟P引言、快速付里葉變換FFT有限反序列通過離散傅里葉變換(DFT)將其頻域離 散化成有限K序列但其計算量太大(與N的平方成 正比)，很難實時地處理問題，因 此引出了快速傅 里葉變換(FFT) FFT并不是一種新的變換形式，它只是DFT的一 種快速算法并且根據(jù)對序列分解與選取方法的不 同而產(chǎn)生了 FFT的多種算法. FFT在離散傅里葉反變換、線性卷積和線性相關(guān) 等方面也有重耍應(yīng)用。:、FFT產(chǎn)生故事當(dāng)時加文(Garwin)在自已的研究中極需要一個計算 付 里葉變換的快速方法。他注意到圖基(J.W.Turkey)iE在

2、寫有 關(guān)付里葉變換的文章，因此詳細詢問了圖基關(guān) 于計算付里 葉變換的技術(shù)知識。圖基概括地文寸加文介紹了一種方法， 它實質(zhì)上就是后來的著名的庫利(Cooley J.W)圖基算法。 在加文的迫切要求下，庫利很快設(shè)計出一個計算機程序。 1965年庫利-圖基在v計算 數(shù)學(xué)、Mathematic ofComputation雜志上發(fā)表了著乞的“機器計算付里級數(shù)的 一種算法”文章，提出一種快速計算DFT的方法和計算機 程序-揭開了 FFT發(fā)展 史上的第一頁，促使FFT算法產(chǎn)牛 原因還有1967年至1968年間FFT的數(shù)字硬件制成，電子 數(shù)字計算機的條 件，使DFT的運算大簡化了。、本章主要內(nèi)容 1 立接計算

3、DFT算法存在的問題及改進途徑。 2多種DFT算法（時間抽取算法DIT算法，頻 率抽取算法DIF算法，線性調(diào)頻Z變換即CZT 法） 3.FFT的應(yīng)用第二節(jié)直接計算6 FT算法存在的問題及改進逐徑'直接計算DFT計算量問題提出：設(shè)有限長序列x(n),非零值長度為 N,計算對x(n)進行一次DFT運算，共需多大的 運算工作量？1 比較DFT與IDFT之間的運算量N1x(n) dft>x 伙)二工上二0,1,N-1n=0N-X 伙)u)n>x(n)= VX 伙)A2 = 0,1, N -1 k=0其中x(n)為復(fù)數(shù)，W嚴(yán)之G”也為復(fù)數(shù)所以DFT與IDFT二者計算量相同。2以DFT

4、為例，計算DFT復(fù)數(shù)運算量計算一個X(k)(一個頻率成分)值，運算量為N-例“ *予)昭耍進行N次復(fù)數(shù)乘法+(N-1)次復(fù)數(shù)加法所以，要完成整個DFT運算，其計算量為：3一次復(fù)數(shù)乘法換算成實數(shù)運算量復(fù)數(shù)運算要比加法運算復(fù)雜，需要的運算時間長。一個復(fù)數(shù)乘法包括4個實數(shù)乘法和2個實數(shù)加 法。(a4-jb)(c+jd)=(ac-bd)+j(bc 丈 ad)2次實4次實數(shù)乘法4.計算DFT需要的實數(shù)運算量N-1X 伙)二工(Re x(«) Re Wf-Im x(«) Im Wf) /»=0+ j(Rex(/i) Im n7 + Im x(«) Re W? )每運

5、算一個X(k)的值，需耍進行4N次實數(shù)相乘和2N+2(N-1 )=2(2N-1)次實數(shù)相加.整個DFT運算量為：4N2次實數(shù)相乘和2N(2N1)次實數(shù)相加.由此看出：直接計算DFT時，乘法次數(shù)與加法次數(shù) 都 是和N2成比例的。當(dāng)N很大時，所需工作量非?？?觀。例子例1:當(dāng)N=1024點時，直接計算DFT需要:n2=220=i048576次，即一百多萬次的復(fù)乘運算 這文寸實時 性很強的信號處理(如雷達信號處理)來 講，它對計算速 度有十分苛刻的要求-迫切 需要改進DFT的計算方 法，以減少總的運算 次數(shù)。例2：石汕勘探，24道記錄，每道波形記錄長 度5秒，若每秒抽樣500點/秒， 每道總抽樣點數(shù)

6、=500*5=2500點24道總抽樣點數(shù)=24*2500=6萬點 DFT 運算時間=N2=(60000)2=36*108次:、改善DFT運算效率的基本途徑利用DFT運算的系數(shù)吟的固有對稱性和周期性，改 善DFT的運算效率。1 合并法：合并DFT運算中的某些項。3.分解法：將長序列DFT利用對稱性和周期性，分解 為短序列DFT0利用DFT運算的系數(shù)的固有對稱性和 周期性，改善DFT的運算效率的對稱性：=亞詠因為：()=©八)=/v 1弋=0,1, wy的周期性:=wa')a =wAk _.2£efJ2A = 1()=2 F'由此可得出:+l) = _w()=es=1 比1N(W； (A) = WJN一心二 W；族(w：）二幺 a/2 =cosA-jsin 7i-例子,例：w9=w(4 =