快速傅立葉變換(FFT)課件.ppt

《快速傅立葉變換(FFT)課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、快速傅立葉變換（FFT)理論及算法實(shí)現(xiàn)直接計(jì)算DFT的問題及改進(jìn)途徑設(shè)x(n)為N點(diǎn)有限長序列，其DFT為一般來說，x(n)和都是復(fù)數(shù)，X(k)也是復(fù)數(shù)，因此每計(jì)算一個(gè)X(k)值，需要N次復(fù)數(shù)乘法以及（N-1)次復(fù)數(shù)加法。而X(k)一共有N個(gè)點(diǎn)，所以完成整個(gè)DFT運(yùn)算總共需要次復(fù)數(shù)乘法及N(N-1)次復(fù)數(shù)加法。直接計(jì)算DFT的問題及改進(jìn)途徑由于一次復(fù)數(shù)乘法需用四次實(shí)數(shù)加法；一次復(fù)數(shù)加法則需二次實(shí)數(shù)加法。因此每運(yùn)算一個(gè)X(k)需要4N次實(shí)數(shù)乘法及2N+2(N-1)=2(2N-1)次實(shí)數(shù)加法。所以整個(gè)DFT運(yùn)算總共需要次實(shí)數(shù)乘法和次加法。例如：N=

2、1024時(shí)，DFT需要復(fù)乘1,048,576次。所以，直接計(jì)算DFT對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理來說，對(duì)計(jì)算速度要求是太高了。直接計(jì)算DFT的問題及改進(jìn)途徑仔細(xì)觀察DFT的運(yùn)算就可以看出，利用系數(shù)的以下固有特性，就可以減小DFT的運(yùn)算量：1、的對(duì)稱性2、的周期性由此可得出直接計(jì)算DFT的問題及改進(jìn)途徑這樣，(1)利用這些特性，使DFT運(yùn)算中有些項(xiàng)可以合并；(2)利用的對(duì)稱性和周期性，可以將長序列的DFT分解為短序列的DFT。前面已經(jīng)說過，DFT的運(yùn)算量與成正比，所以N越小越有利?？焖俑盗⑷~變換就是在這種思路下發(fā)展起來的。下面將詳細(xì)介紹。按時(shí)間抽取的F

3、FT算法先設(shè)序列長度為,L為整數(shù)。將的序列x(n)(n=0,1,..,N-1),先按n的奇偶分成兩組r=0,1,…,-1則將DFT化為按時(shí)間抽取的FFT算法可以得到由于則上式可表示成式中及分別是及的點(diǎn)DFT由上式可以看出，一個(gè)N點(diǎn)DFT已分解為兩個(gè)點(diǎn)DFT，它們又可以組合成一個(gè)N點(diǎn)DFT。按時(shí)間抽取的FFT算法按時(shí)間抽取的FFT算法但是，以及都是點(diǎn)的序列即r,k滿足r,k=0,…,-1。而卻有N點(diǎn)，而用上面的式子計(jì)算得到的只是的前一半項(xiàng)數(shù)的結(jié)果，要用來表達(dá)全部的值，還必須應(yīng)用系數(shù)的周期性，即這樣可得到按時(shí)間抽取的FFT算法同理可得：上兩式說明了

4、后半部分k值()所對(duì)應(yīng)的分別等于前半部分k值()所對(duì)應(yīng)的。再考慮到的對(duì)稱性這樣，就可以得到分為前后兩部分得表達(dá)：前半部分按時(shí)間抽取的FFT算法后半部分這樣，只要求出0到()區(qū)間得所有值，即可求出0到（N－1）區(qū)間內(nèi)的所有值，這就大大節(jié)省了運(yùn)算。按時(shí)間抽取的FFT算法上面的式子可以用下面的蝶形圖符號(hào)表示：可以看出，每個(gè)蝶性運(yùn)算，需要一次復(fù)數(shù)乘法及兩次復(fù)數(shù)加(減)法。據(jù)此，一個(gè)N點(diǎn)DFT分解為兩個(gè)點(diǎn)DFT只需要次復(fù)數(shù)乘法，次復(fù)數(shù)加法，兩個(gè)點(diǎn)DFT共需次復(fù)按時(shí)間抽取的FFT算法數(shù)乘法和次復(fù)數(shù)加法。此外把兩個(gè)點(diǎn)DFT合成N點(diǎn)DFT時(shí)，有個(gè)蝶性運(yùn)算，還需

5、要次復(fù)數(shù)乘法及次復(fù)數(shù)加法。因而通過這一步分解后，總共需要次復(fù)數(shù)乘法和次復(fù)數(shù)加法，可見通過這樣的分解后運(yùn)算工作量差不多減少到一半。FFT的軟件實(shí)現(xiàn)1.指數(shù)因子的確定每一蝶算得輸出都含有指數(shù)因子，因而如何根據(jù)不同蝶算確定具體的k值是編程過程需要考慮的重要問題。一般規(guī)律是隨著極數(shù)及節(jié)點(diǎn)數(shù)而變化，當(dāng)DIT輸入反序，則每級(jí)有個(gè)。第一級(jí)均為第二級(jí)為、共=組第三級(jí)為、、、共=組……FFT的軟件實(shí)現(xiàn)2.整序由于基2的FFT，若正序輸入則反序輸出，因此需要經(jīng)過整序才便于讀取和應(yīng)用處理后的數(shù)據(jù)。參見下圖。FFT的軟件實(shí)現(xiàn)m01234567FFT的軟件實(shí)現(xiàn)3.2個(gè)實(shí)

6、序列的DFT的計(jì)算從FFT的流圖可見，由第一級(jí)輸出開始，算法的所有變量都是復(fù)數(shù)，即此后蝶算的輸入和輸出均為復(fù)數(shù)。因而在考慮FFT算法時(shí)將輸入序列x(n)設(shè)置為復(fù)數(shù)，更具有普遍意義。且將兩個(gè)實(shí)數(shù)當(dāng)作一個(gè)復(fù)數(shù)來計(jì)算，可以減少運(yùn)算量。下面來說明如何由計(jì)算一個(gè)復(fù)數(shù)序列的FFT來等效得到兩個(gè)實(shí)數(shù)序列的FFT。FFT的軟件實(shí)現(xiàn)設(shè)有兩個(gè)待處理的實(shí)數(shù)序列,令復(fù)數(shù)序列，則按DFT線性性質(zhì)有由于又可以表示為根據(jù)DFT線性與復(fù)共軛性質(zhì)，故得