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

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

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

3、DFT算法存在的問題及改進(jìn)途徑。 2多種DFT算法（時(shí)間抽取算法DIT算法，頻 率抽取算法DIF算法，線性調(diào)頻Z變換即CZT 法） 3.FFT的應(yīng)用第二節(jié)直接計(jì)算6 FT算法存在的問題及改進(jìn)逐徑'直接計(jì)算DFT計(jì)算量問題提出：設(shè)有限長(zhǎng)序列x(n),非零值長(zhǎng)度為 N,計(jì)算對(duì)x(n)進(jìn)行一次DFT運(yùn)算，共需多大的 運(yùn)算工作量？1 比較DFT與IDFT之間的運(yùn)算量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二者計(jì)算量相同。2以DFT

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

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

6、=500*5=2500點(diǎn)24道總抽樣點(diǎn)數(shù)=24*2500=6萬點(diǎn) DFT 運(yùn)算時(shí)間=N2=(60000)2=36*108次:、改善DFT運(yùn)算效率的基本途徑利用DFT運(yùn)算的系數(shù)吟的固有對(duì)稱性和周期性，改 善DFT的運(yùn)算效率。1 合并法：合并DFT運(yùn)算中的某些項(xiàng)。3.分解法：將長(zhǎng)序列DFT利用對(duì)稱性和周期性，分解 為短序列DFT0利用DFT運(yùn)算的系數(shù)的固有對(duì)稱性和 周期性，改善DFT的運(yùn)算效率的對(duì)稱性：=亞詠因?yàn)椋?)=©八)=/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 =