第4章快速傅里葉變換

《第4章快速傅里葉變換》由會(huì)員分享，可在線閱讀，更多相關(guān)《第4章快速傅里葉變換（108頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)FAST FOURIER TRANSFORM4.1 引言引言4.2 基基2FFT算法算法4.3 進(jìn)一步減少運(yùn)算量的措施進(jìn)一步減少運(yùn)算量的措施4.4 分裂基分裂基FFT算法算法4.5 離散哈特萊變換離散哈特萊變換(DHT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)本章主要內(nèi)容本章主要內(nèi)容1.直接計(jì)算DFT算法存在的問(wèn)題及改進(jìn)途徑。2.時(shí)間抽取算法DIT算法3.頻率抽取算法DIF算法4.FFT應(yīng)用（見(jiàn)第三章）4.1 引言引言第第4章章 快速傅里葉變換快速傅里葉變換(FFT)習(xí)題習(xí)題 1.3.

2、畫(huà)畫(huà)8點(diǎn)基點(diǎn)基2 DIT-FFT和和8點(diǎn)基點(diǎn)基2 DIF-FFT算法運(yùn)算流圖算法運(yùn)算流圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.1直接計(jì)算DFT的特點(diǎn) 及減少運(yùn)算量的基本途徑4.2 4.2 基基2FFT2FFT算法算法(4.2.1)一.DFT的運(yùn)算次數(shù)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)運(yùn)算量運(yùn)算量復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)X(k)NN 1N個(gè)X(k)(N點(diǎn)DFT)N 2N(N 1)實(shí)數(shù)乘法實(shí)數(shù)加法一次復(fù)乘42一次復(fù)加2一個(gè)X(k)4N2N+2(N 1)=2(2N 1)N個(gè)X(k)(N點(diǎn)DFT)4N 22N(2N 1)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)

3、例1:當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算DFT需要：N2=220=1048576次，即一百多萬(wàn)次的復(fù)乘運(yùn)算例2：石油勘探，24道記錄，每道波形記錄長(zhǎng)度5秒，若每秒抽樣500點(diǎn)/秒，每道總抽樣點(diǎn)數(shù)=500*5=2500點(diǎn)24道總抽樣點(diǎn)數(shù)=24*2500=6萬(wàn)點(diǎn)DFT運(yùn)算時(shí)間=N2=(60000)2=36*108次N點(diǎn)DFT的復(fù)乘次數(shù)等于N2。顯然，把N點(diǎn)DFT分解為幾個(gè)較短的DFT，可使乘法次數(shù)大大減少。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)(4.2.2)2.對(duì)稱性表現(xiàn)為或者二.旋轉(zhuǎn)因子的周期性和對(duì)稱性1.周期性表現(xiàn)為第第4章章 快速傅里葉變換快速傅里葉變換(FFT)FFT算法基本上分為兩

4、大類：算法基本上分為兩大類：時(shí)域抽取法DIT:Decimation-In-Time頻率抽取法DIF:Decimation-In-Frequency4.2.2時(shí)域抽取法基2FFT基本原理第第4章章 快速傅里葉變換快速傅里葉變換(FFT)一.基本算法設(shè)序列x(n)的長(zhǎng)度為N，且滿足為自然數(shù)按n的奇偶把x(n)分解為兩個(gè)N/2點(diǎn)的子序列第第4章章 快速傅里葉變換快速傅里葉變換(FFT)則x(n)的DFT為由于所以第第4章章 快速傅里葉變換快速傅里葉變換(FFT)其中X1(k)和X2(k)分別為x1(r)和x2(r)的N/2點(diǎn)DFT，即(4.2.5)(4.2.6)再利用周期性求X(k)的后半部分第第4

5、章章 快速傅里葉變換快速傅里葉變換(FFT)作圖要素：作圖要素：(1)左邊兩路為輸入左邊兩路為輸入(2)右邊兩路為輸出右邊兩路為輸出(3)中間以一個(gè)小圓表示加、減運(yùn)中間以一個(gè)小圓表示加、減運(yùn)算（右上路為相加輸出、右下路算（右上路為相加輸出、右下路為相減輸出為相減輸出)(4)如果在某一支路上信號(hào)需要進(jìn)如果在某一支路上信號(hào)需要進(jìn)行相乘運(yùn)算，則在該支路上標(biāo)以行相乘運(yùn)算，則在該支路上標(biāo)以箭頭，將相乘的系數(shù)標(biāo)在箭頭旁箭頭，將相乘的系數(shù)標(biāo)在箭頭旁(5)當(dāng)支路上沒(méi)有箭頭及系數(shù)時(shí)，當(dāng)支路上沒(méi)有箭頭及系數(shù)時(shí)，則該支路的傳輸比為則該支路的傳輸比為1。圖4.2.1蝶形運(yùn)算符號(hào) X1(k)X2(k)(4.2.7)(4

6、.2.8)二.蝶形運(yùn)算圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.2N點(diǎn)DFT的一次時(shí)域抽取分解圖(N=8)000010100110001011101111000001010011100101110111第第4章章 快速傅里葉變換快速傅里葉變換(FFT)三.進(jìn)一步分解與第一次分解相同，將x1(r)按奇偶分解成兩個(gè)N/4長(zhǎng)的子序列x3(l)和x4(l)，即那么，X1(k)又可表示為(4.2.9)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)式中(4.2.10)同理，由X3(k)和X4(k)的周期性和的對(duì)稱性最后得到：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)用同樣的

7、方法可計(jì)算出(4.2.11)其中第第4章章 快速傅里葉變換快速傅里葉變換(FFT)這樣逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.3N點(diǎn)DFT的第二次時(shí)域抽取分解圖(N=8)000100010110001101011111000001010011100101110111第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.4N點(diǎn)DITFFT運(yùn)算流圖(N=8)p幻燈片幻燈片 22第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.3DITFFT算法與直接計(jì)算DFT運(yùn)算

8、量的比較每一級(jí)運(yùn)算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個(gè)蝶形需要兩次復(fù)數(shù)加法)。所以，M級(jí)運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為復(fù)數(shù)加次數(shù)為例如，N=210=1024時(shí)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.5FFT算法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.4DITFFT的運(yùn)算規(guī)律及編程思想1.原位計(jì)算由圖4.2.4可以看出，DITFFT的運(yùn)算過(guò)程很有規(guī)律。N=2M點(diǎn)的FFT共進(jìn)行M級(jí)運(yùn)算，每級(jí)由N/2個(gè)蝶形運(yùn)算組成。2.旋轉(zhuǎn)因子的變化規(guī)律如上所述，N點(diǎn)DITFFT運(yùn)算流圖中，每級(jí)都有N/2個(gè)蝶形。每個(gè)蝶形都要乘以因子，稱其為旋

9、轉(zhuǎn)因子，p稱為旋轉(zhuǎn)因子的指數(shù)。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)觀察圖4.2.4不難發(fā)現(xiàn)，第L級(jí)共有個(gè)不同的旋轉(zhuǎn)因子。N=23=8時(shí)的各級(jí)旋轉(zhuǎn)因子表示如下：(4.2.12)(4.2.13)對(duì)N=2M的一般情況，第L級(jí)的旋轉(zhuǎn)因子為第第4章章 快速傅里葉變換快速傅里葉變換(FFT)3.蝶形運(yùn)算規(guī)律設(shè)序列x(n)經(jīng)時(shí)域抽選(倒序)后，存入數(shù)組X中。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，則蝶形運(yùn)算可表示成如下形式：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)如果要用實(shí)數(shù)運(yùn)算完成上述蝶形運(yùn)算，可按下面的算法進(jìn)行。設(shè)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)則第

10、第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.編程思想及程序框圖圖4.2.6DITFFT運(yùn)算和程序框圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)5.序列的倒序由于N=2M，所以順序數(shù)可用M位二進(jìn)制數(shù)(nM-1nM-2n1n0)表示。圖4.2.7形成倒序的樹(shù)狀圖(N=23)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)表4.2.1順序和倒序二進(jìn)制數(shù)對(duì)照表以此為鏡像以此為鏡像第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.8倒序規(guī)律第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.9倒序程序框圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第第4章章 快

11、速傅里葉變換快速傅里葉變換(FFT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.5頻域抽取法FFT(DIFFFT)在基2快速算法中，頻域抽取法FFT也是一種常用的快速算法，簡(jiǎn)稱DIFFFT。(Sander-Tukey算法)設(shè)序列x(n)長(zhǎng)度為N=2M，首先將x(n)前后對(duì)半分開(kāi)，得到兩個(gè)子序列，其DFT可表示為如下形式：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)偶數(shù)奇數(shù)(1)將X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)(k=2

12、r,r=0,1,N/2-1)時(shí)(4.2.14)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)當(dāng)k取奇數(shù)(k=2r+1,r=0,1,N/2-1)時(shí)(4.2.15)將x1(n)和x2(n)分別代入(4.2.14)和(4.2.15)式，可得(4.2.16)例：N=8時(shí)，前半序列為：后半序列為：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.10DIFFFT蝶形運(yùn)算流圖符號(hào)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.11DIFFFT一次分解運(yùn)算流圖(N=8)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.12DIFFFT二次分解運(yùn)算流圖(N=8)第第4章章

13、快速傅里葉變換快速傅里葉變換(FFT)圖4.2.13DIFFFT運(yùn)算流圖(N=8)000001010011100101110111000100010110001101011111第第4章章 快速傅里葉變換快速傅里葉變換(FFT)(5)DIF的特點(diǎn)的特點(diǎn)(a)輸入自然順序，輸出亂序且滿足碼位輸入自然順序，輸出亂序且滿足碼位倒置規(guī)則。倒置規(guī)則。(b)根據(jù)時(shí)域、頻域互換，可知：根據(jù)時(shí)域、頻域互換，可知：輸入亂序，輸出自然順序。輸入亂序，輸出自然順序。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)DIF與與DIT比較比較相同之處：（1）DIF與DIT兩種算法均為原位運(yùn)算。（2）DIF與DIT運(yùn)算量

14、相同。它們都需要第第4章章 快速傅里葉變換快速傅里葉變換(FFT)不同之處：（1）DIF與DIT兩種算法結(jié)構(gòu)倒過(guò)來(lái)。DIF為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行“二進(jìn)制倒讀”程序。DIT為輸入亂序，輸出順序。先運(yùn)行“二進(jìn)制倒讀”程序，再進(jìn)行求DFT。（2）DIF與DIT根本區(qū)別：在于蝶形結(jié)不同。DIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。DIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.14DITFFT的一種變形運(yùn)算流圖000001010011100101110111000100010110001101011111前一級(jí)旋轉(zhuǎn)因子剛好是前一級(jí)旋轉(zhuǎn)因子剛好是后一級(jí)上一半

15、后一級(jí)上一半蝶形運(yùn)算的旋轉(zhuǎn)因子蝶形運(yùn)算的旋轉(zhuǎn)因子 第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.15DITFFT的一種變形運(yùn)算流圖不能原位計(jì)算，占用內(nèi)存較大不能原位計(jì)算，占用內(nèi)存較大第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.6IDFT的高效算法上述FFT算法流圖也可以用于離散傅里葉逆變換(InverseDiscreteFourierTransform，簡(jiǎn)稱IDFT)。比較DFT和IDFT的運(yùn)算公式：法一法一:第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.16DITIFFT運(yùn)算流圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.17DITI

16、FFT運(yùn)算流圖(防止溢出)在IFFT的運(yùn)算中，常常把1/N分解為(1/2)M，并且在M級(jí)運(yùn)算中每一級(jí)運(yùn)算都分別乘以1/2因子，就可得到IFFT的兩種基本蝶形運(yùn)算結(jié)構(gòu)。不常用不常用第第4章章 快速傅里葉變換快速傅里葉變換(FFT)如果希望直接調(diào)用FFT子程序計(jì)算IFFT，則可用下面的方法：由于對(duì)上式兩邊同時(shí)取共軛，得共用共用FFT程序程序只須將頻域成份一個(gè)求共軛變換，即（1）將X(k)的虛部乘以-1，即先取X(k)的共軛，得X*(k)。(2)將X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再對(duì)運(yùn)算結(jié)果取一次共軛變換，并乘以常數(shù)1/N，即可以求出IFFT變換的x(n)的值。法二法二:

17、第第4章章 快速傅里葉變換快速傅里葉變換(FFT)直接利用直接利用FFT流圖方法的注意點(diǎn)流圖方法的注意點(diǎn)（1）FFT與IFFT連接應(yīng)用時(shí)，注意輸入輸出序列的排列順序，即應(yīng)注意是自然順序還是倒序。（2）FFT和IFFT共用同一個(gè)程序時(shí)，也應(yīng)注意利用FFT算法輸入輸出的排列順序，即應(yīng)注意自然順序還是倒位序（3）當(dāng)把頻率抽取FFT流圖用于IDFT時(shí)，應(yīng)改稱時(shí)間抽取IFFT流圖。（4）當(dāng)把時(shí)間抽取FFT流圖用于IDFT時(shí)，應(yīng)改稱頻率抽取IFFT流圖。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.3 進(jìn)一步減少運(yùn)算量的措施進(jìn)一步減少運(yùn)算量的措施4.3.1多類蝶形單元運(yùn)算由DITFFT運(yùn)算流圖已得

18、出結(jié)論，N=2M點(diǎn)FFT共需要MN/2次復(fù)數(shù)乘法。由(4.2.12)式，當(dāng)L=1時(shí)，只有一種旋轉(zhuǎn)因子，所以，第一級(jí)不需要乘法運(yùn)算。L=2時(shí)，有兩個(gè)旋轉(zhuǎn)因子：和，因此，第二級(jí)也不需要乘法運(yùn)算。在DFT中，為無(wú)關(guān)緊要的旋轉(zhuǎn)因子，如第第4章章 快速傅里葉變換快速傅里葉變換(FFT)綜上所述，先除去第一、二兩級(jí)后，所需復(fù)數(shù)乘法次數(shù)應(yīng)是(4.3.1)(4.3.2)因此，DITFFT的復(fù)乘次數(shù)降至(4.3.3)同理，從L=3至L=M共減少?gòu)?fù)數(shù)乘法次數(shù)為第第4章章 快速傅里葉變換快速傅里葉變換(FFT)又又從實(shí)數(shù)運(yùn)算考慮，計(jì)算N=2M點(diǎn)DITFFT所需實(shí)數(shù)乘法次數(shù)為第第4章章 快速傅里葉變換快速傅里葉變換(

19、FFT)包含所有旋轉(zhuǎn)因子的包含所有旋轉(zhuǎn)因子的FFT算法算法,稱為一類蝶形單元運(yùn)算稱為一類蝶形單元運(yùn)算;(4.3.4)一類蝶形單元運(yùn)算中去掉一類蝶形單元運(yùn)算中去掉 因子的因子的FFT算法算法,稱為二類蝶形單元運(yùn)算稱為二類蝶形單元運(yùn)算;去掉去掉 因子的因子的FFT算法算法,稱為三類蝶形單元運(yùn)算稱為三類蝶形單元運(yùn)算;去掉去掉 因子的因子的FFT算法算法,稱為四類蝶稱為四類蝶形單元運(yùn)算形單元運(yùn)算.第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.3.2旋轉(zhuǎn)因子的生成在FFT運(yùn)算中，旋轉(zhuǎn)因子，求正弦和余弦函數(shù)值的計(jì)算量是很大的。提前算出，存在數(shù)組中，作為旋轉(zhuǎn)因子表。提前算出，存在數(shù)組中，作為旋轉(zhuǎn)因子

20、表。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.3.3實(shí)序列的FFT算法設(shè)x(n)為N點(diǎn)實(shí)序列，取x(n)的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分別作為新構(gòu)造序列y(n)的實(shí)部和虛部，即對(duì)y(n)進(jìn)行N/2點(diǎn)FFT，輸出Y(k)，則根據(jù)DITFFT的思想及式(4.2.7)和(4.2.8)，可得到第第4章章 快速傅里葉變換快速傅里葉變換(FFT)由于x(n)為實(shí)序列，所以X(k)具有共軛對(duì)稱性，X(k)的另外N/2點(diǎn)的值為第第4章章 快速傅里葉變換快速傅里葉變換(FFT)%用用FFT對(duì)序列進(jìn)行譜分析對(duì)序列進(jìn)行譜分析%x1(n)=R4(n);x2(n)=cos(0.25n*pi)+cos(0.125n*pi)

21、;x1=1,1,1,1,0,0,0,0;i=0:7;subplot(3,2,1);stem(i,x1,.);xlabel(n);ylabel(x1(n);axis(0,10,0,2);y1=fft(x1,8);subplot(3,2,3),stem(i,abs(y1),.);xlabel(N=8)k);ylabel(X1(k);axis(0,10,0,6);j=0:63;y2=fft(x1,64);subplot(3,2,5);stem(j,abs(y2),.);xlabel(N=64)k);ylabel(X1(k);axis(0,70,0,5);第第4章章 快速傅里葉變換快速傅里葉變換(FF

22、T)n=0:15;x2=cos(0.375*n*pi)+cos(0.125*n*pi);subplot(3,2,2);stem(n,x2,.);xlabel(n);ylabel(x2(n);axis(0,15,-2,3);l=0:63;y3=fft(x2,16);y4=fft(x2,64);subplot(3,2,4),stem(n,abs(y3),.);xlabel(N=16)k);ylabel(X2(k);axis(0,15,0,10);subplot(3,2,6),stem(l,abs(y4),.);xlabel(N=64)k);ylabel(X2(k);axis(0,63,0,10);

23、第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)P127 習(xí)題習(xí)題1.解解:DFT:FFT:快速卷積快速卷積所需所需時(shí)間時(shí)間(假定假定H(k)已知已知)為為:T=2TFFT+5N=76.8ms處理處理1點(diǎn)所需時(shí)間點(diǎn)所需時(shí)間:76.8ms/1024,這這即是兩個(gè)采樣點(diǎn)間的間隔即是兩個(gè)采樣點(diǎn)間的間隔,因此采樣頻率為因此采樣頻率為:fs=1024000/76.8 信號(hào)的最高頻率信號(hào)的最高頻率fcmax=fs/2=6666.7Hz第第4章章 快速傅里葉變換快速傅里葉變換(FFT)3.解解:令令X(k)+jY(k)=F(k)利用利用DFT的對(duì)稱性的對(duì)稱性:F(k)=FR(k)+jFI(k)f(n)=fep(n)+fop(n)IDFTIDFTIDFT可以得到可以得到 x(n)=IDFTX(k)=fep(n)=f(n)+f*(N-n)/2y(n)=IDFTY(k)=-jfop(n)=-jf(n)-f*(N-n)/2