《第4章快速傅里葉變換》由會員分享，可在線閱讀，更多相關(guān)《第4章快速傅里葉變換（108頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)FAST FOURIER TRANSFORM4.1 引言引言4.2 基基2FFT算法算法4.3 進一步減少運算量的措施進一步減少運算量的措施4.4 分裂基分裂基FFT算法算法4.5 離散哈特萊變換離散哈特萊變換(DHT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)本章主要內(nèi)容本章主要內(nèi)容1.直接計算DFT算法存在的問題及改進途徑。2.時間抽取算法DIT算法3.頻率抽取算法DIF算法4.FFT應(yīng)用（見第三章）4.1 引言引言第第4章章 快速傅里葉變換快速傅里葉變換(FFT)習(xí)題習(xí)題 1.3.
2、畫畫8點基點基2 DIT-FFT和和8點基點基2 DIF-FFT算法運算流圖算法運算流圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.1直接計算DFT的特點 及減少運算量的基本途徑4.2 4.2 基基2FFT2FFT算法算法(4.2.1)一.DFT的運算次數(shù)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)運算量運算量復(fù)數(shù)乘法復(fù)數(shù)加法一個X(k)NN 1N個X(k)(N點DFT)N 2N(N 1)實數(shù)乘法實數(shù)加法一次復(fù)乘42一次復(fù)加2一個X(k)4N2N+2(N 1)=2(2N 1)N個X(k)(N點DFT)4N 22N(2N 1)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)
3、例1:當N=1024點時，直接計算DFT需要：N2=220=1048576次，即一百多萬次的復(fù)乘運算例2：石油勘探，24道記錄，每道波形記錄長度5秒，若每秒抽樣500點/秒，每道總抽樣點數(shù)=500*5=2500點24道總抽樣點數(shù)=24*2500=6萬點DFT運算時間=N2=(60000)2=36*108次N點DFT的復(fù)乘次數(shù)等于N2。顯然，把N點DFT分解為幾個較短的DFT，可使乘法次數(shù)大大減少。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)(4.2.2)2.對稱性表現(xiàn)為或者二.旋轉(zhuǎn)因子的周期性和對稱性1.周期性表現(xiàn)為第第4章章 快速傅里葉變換快速傅里葉變換(FFT)FFT算法基本上分為兩
4、大類：算法基本上分為兩大類：時域抽取法DIT:Decimation-In-Time頻率抽取法DIF:Decimation-In-Frequency4.2.2時域抽取法基2FFT基本原理第第4章章 快速傅里葉變換快速傅里葉變換(FFT)一.基本算法設(shè)序列x(n)的長度為N，且滿足為自然數(shù)按n的奇偶把x(n)分解為兩個N/2點的子序列第第4章章 快速傅里葉變換快速傅里葉變換(FFT)則x(n)的DFT為由于所以第第4章章 快速傅里葉變換快速傅里葉變換(FFT)其中X1(k)和X2(k)分別為x1(r)和x2(r)的N/2點DFT，即(4.2.5)(4.2.6)再利用周期性求X(k)的后半部分第第4
5、章章 快速傅里葉變換快速傅里葉變換(FFT)作圖要素：作圖要素：(1)左邊兩路為輸入左邊兩路為輸入(2)右邊兩路為輸出右邊兩路為輸出(3)中間以一個小圓表示加、減運中間以一個小圓表示加、減運算（右上路為相加輸出、右下路算（右上路為相加輸出、右下路為相減輸出為相減輸出)(4)如果在某一支路上信號需要進如果在某一支路上信號需要進行相乘運算，則在該支路上標以行相乘運算，則在該支路上標以箭頭，將相乘的系數(shù)標在箭頭旁箭頭，將相乘的系數(shù)標在箭頭旁(5)當支路上沒有箭頭及系數(shù)時，當支路上沒有箭頭及系數(shù)時，則該支路的傳輸比為則該支路的傳輸比為1。圖4.2.1蝶形運算符號 X1(k)X2(k)(4.2.7)(4
6、.2.8)二.蝶形運算圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.2N點DFT的一次時域抽取分解圖(N=8)000010100110001011101111000001010011100101110111第第4章章 快速傅里葉變換快速傅里葉變換(FFT)三.進一步分解與第一次分解相同，將x1(r)按奇偶分解成兩個N/4長的子序列x3(l)和x4(l)，即那么，X1(k)又可表示為(4.2.9)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)式中(4.2.10)同理，由X3(k)和X4(k)的周期性和的對稱性最后得到：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)用同樣的
7、方法可計算出(4.2.11)其中第第4章章 快速傅里葉變換快速傅里葉變換(FFT)這樣逐級分解，直到2點DFT當N=8時，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.3N點DFT的第二次時域抽取分解圖(N=8)000100010110001101011111000001010011100101110111第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.4N點DITFFT運算流圖(N=8)p幻燈片幻燈片 22第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.3DITFFT算法與直接計算DFT運算
8、量的比較每一級運算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個蝶形需要兩次復(fù)數(shù)加法)。所以，M級運算總共需要的復(fù)數(shù)乘次數(shù)為復(fù)數(shù)加次數(shù)為例如，N=210=1024時第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.5FFT算法與直接計算DFT所需乘法次數(shù)的比較曲線第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.4DITFFT的運算規(guī)律及編程思想1.原位計算由圖4.2.4可以看出，DITFFT的運算過程很有規(guī)律。N=2M點的FFT共進行M級運算，每級由N/2個蝶形運算組成。2.旋轉(zhuǎn)因子的變化規(guī)律如上所述，N點DITFFT運算流圖中，每級都有N/2個蝶形。每個蝶形都要乘以因子，稱其為旋
9、轉(zhuǎn)因子，p稱為旋轉(zhuǎn)因子的指數(shù)。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)觀察圖4.2.4不難發(fā)現(xiàn)，第L級共有個不同的旋轉(zhuǎn)因子。N=23=8時的各級旋轉(zhuǎn)因子表示如下：(4.2.12)(4.2.13)對N=2M的一般情況，第L級的旋轉(zhuǎn)因子為第第4章章 快速傅里葉變換快速傅里葉變換(FFT)3.蝶形運算規(guī)律設(shè)序列x(n)經(jīng)時域抽選(倒序)后，存入數(shù)組X中。如果蝶形運算的兩個輸入數(shù)據(jù)相距B個點，應(yīng)用原位計算，則蝶形運算可表示成如下形式：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)如果要用實數(shù)運算完成上述蝶形運算，可按下面的算法進行。設(shè)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)則第
10、第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.編程思想及程序框圖圖4.2.6DITFFT運算和程序框圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)5.序列的倒序由于N=2M，所以順序數(shù)可用M位二進制數(shù)(nM-1nM-2n1n0)表示。圖4.2.7形成倒序的樹狀圖(N=23)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)表4.2.1順序和倒序二進制數(shù)對照表以此為鏡像以此為鏡像第第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也是一種常用的快速算法，簡稱DIFFFT。(Sander-Tukey算法)設(shè)序列x(n)長度為N=2M，首先將x(n)前后對半分開，得到兩個子序列，其DFT可表示為如下形式：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)偶數(shù)奇數(shù)(1)將X(k)分解成偶數(shù)組與奇數(shù)組，當k取偶數(shù)(k=2
12、r,r=0,1,N/2-1)時(4.2.14)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)當k取奇數(shù)(k=2r+1,r=0,1,N/2-1)時(4.2.15)將x1(n)和x2(n)分別代入(4.2.14)和(4.2.15)式，可得(4.2.16)例：N=8時，前半序列為：后半序列為：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.10DIFFFT蝶形運算流圖符號第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.11DIFFFT一次分解運算流圖(N=8)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.12DIFFFT二次分解運算流圖(N=8)第第4章章
13、快速傅里葉變換快速傅里葉變換(FFT)圖4.2.13DIFFFT運算流圖(N=8)000001010011100101110111000100010110001101011111第第4章章 快速傅里葉變換快速傅里葉變換(FFT)(5)DIF的特點的特點(a)輸入自然順序，輸出亂序且滿足碼位輸入自然順序，輸出亂序且滿足碼位倒置規(guī)則。倒置規(guī)則。(b)根據(jù)時域、頻域互換，可知：根據(jù)時域、頻域互換，可知：輸入亂序，輸出自然順序。輸入亂序，輸出自然順序。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)DIF與與DIT比較比較相同之處：（1）DIF與DIT兩種算法均為原位運算。（2）DIF與DIT運算量
14、相同。它們都需要第第4章章 快速傅里葉變換快速傅里葉變換(FFT)不同之處：（1）DIF與DIT兩種算法結(jié)構(gòu)倒過來。DIF為輸入順序，輸出亂序。運算完畢再運行“二進制倒讀”程序。DIT為輸入亂序，輸出順序。先運行“二進制倒讀”程序，再進行求DFT。（2）DIF與DIT根本區(qū)別：在于蝶形結(jié)不同。DIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。DIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.14DITFFT的一種變形運算流圖000001010011100101110111000100010110001101011111前一級旋轉(zhuǎn)因子剛好是前一級旋轉(zhuǎn)因子剛好是后一級上一半
15、后一級上一半蝶形運算的旋轉(zhuǎn)因子蝶形運算的旋轉(zhuǎn)因子 第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.15DITFFT的一種變形運算流圖不能原位計算，占用內(nèi)存較大不能原位計算，占用內(nèi)存較大第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.6IDFT的高效算法上述FFT算法流圖也可以用于離散傅里葉逆變換(InverseDiscreteFourierTransform，簡稱IDFT)。比較DFT和IDFT的運算公式：法一法一:第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.16DITIFFT運算流圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖4.2.17DITI
16、FFT運算流圖(防止溢出)在IFFT的運算中，常常把1/N分解為(1/2)M，并且在M級運算中每一級運算都分別乘以1/2因子，就可得到IFFT的兩種基本蝶形運算結(jié)構(gòu)。不常用不常用第第4章章 快速傅里葉變換快速傅里葉變換(FFT)如果希望直接調(diào)用FFT子程序計算IFFT，則可用下面的方法：由于對上式兩邊同時取共軛，得共用共用FFT程序程序只須將頻域成份一個求共軛變換，即（1）將X(k)的虛部乘以-1，即先取X(k)的共軛，得X*(k)。(2)將X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再對運算結(jié)果取一次共軛變換，并乘以常數(shù)1/N，即可以求出IFFT變換的x(n)的值。法二法二:
17、第第4章章 快速傅里葉變換快速傅里葉變換(FFT)直接利用直接利用FFT流圖方法的注意點流圖方法的注意點（1）FFT與IFFT連接應(yīng)用時，注意輸入輸出序列的排列順序，即應(yīng)注意是自然順序還是倒序。（2）FFT和IFFT共用同一個程序時，也應(yīng)注意利用FFT算法輸入輸出的排列順序，即應(yīng)注意自然順序還是倒位序（3）當把頻率抽取FFT流圖用于IDFT時，應(yīng)改稱時間抽取IFFT流圖。（4）當把時間抽取FFT流圖用于IDFT時，應(yīng)改稱頻率抽取IFFT流圖。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.3 進一步減少運算量的措施進一步減少運算量的措施4.3.1多類蝶形單元運算由DITFFT運算流圖已得
18、出結(jié)論，N=2M點FFT共需要MN/2次復(fù)數(shù)乘法。由(4.2.12)式，當L=1時，只有一種旋轉(zhuǎn)因子，所以，第一級不需要乘法運算。L=2時，有兩個旋轉(zhuǎn)因子：和，因此，第二級也不需要乘法運算。在DFT中，為無關(guān)緊要的旋轉(zhuǎn)因子，如第第4章章 快速傅里葉變換快速傅里葉變換(FFT)綜上所述，先除去第一、二兩級后，所需復(fù)數(shù)乘法次數(shù)應(yīng)是(4.3.1)(4.3.2)因此，DITFFT的復(fù)乘次數(shù)降至(4.3.3)同理，從L=3至L=M共減少復(fù)數(shù)乘法次數(shù)為第第4章章 快速傅里葉變換快速傅里葉變換(FFT)又又從實數(shù)運算考慮，計算N=2M點DITFFT所需實數(shù)乘法次數(shù)為第第4章章 快速傅里葉變換快速傅里葉變換(
19、FFT)包含所有旋轉(zhuǎn)因子的包含所有旋轉(zhuǎn)因子的FFT算法算法,稱為一類蝶形單元運算稱為一類蝶形單元運算;(4.3.4)一類蝶形單元運算中去掉一類蝶形單元運算中去掉 因子的因子的FFT算法算法,稱為二類蝶形單元運算稱為二類蝶形單元運算;去掉去掉 因子的因子的FFT算法算法,稱為三類蝶形單元運算稱為三類蝶形單元運算;去掉去掉 因子的因子的FFT算法算法,稱為四類蝶稱為四類蝶形單元運算形單元運算.第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.3.2旋轉(zhuǎn)因子的生成在FFT運算中，旋轉(zhuǎn)因子，求正弦和余弦函數(shù)值的計算量是很大的。提前算出，存在數(shù)組中，作為旋轉(zhuǎn)因子表。提前算出，存在數(shù)組中，作為旋轉(zhuǎn)因子
20、表。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.3.3實序列的FFT算法設(shè)x(n)為N點實序列，取x(n)的偶數(shù)點和奇數(shù)點分別作為新構(gòu)造序列y(n)的實部和虛部，即對y(n)進行N/2點FFT，輸出Y(k)，則根據(jù)DITFFT的思想及式(4.2.7)和(4.2.8)，可得到第第4章章 快速傅里葉變換快速傅里葉變換(FFT)由于x(n)為實序列，所以X(k)具有共軛對稱性，X(k)的另外N/2點的值為第第4章章 快速傅里葉變換快速傅里葉變換(FFT)%用用FFT對序列進行譜分析對序列進行譜分析%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:快速卷積快速卷積所需所需時間時間(假定假定H(k)已知已知)為為:T=2TFFT+5N=76.8ms處理處理1點所需時間點所需時間:76.8ms/1024,這這即是兩個采樣點間的間隔即是兩個采樣點間的間隔,因此采樣頻率為因此采樣頻率為:fs=1024000/76.8 信號的最高頻率信號的最高頻率fcmax=fs/2=6666.7Hz第第4章章 快速傅里葉變換快速傅里葉變換(FFT)3.解解:令令X(k)+jY(k)=F(k)利用利用DFT的對稱性的對稱性: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
第4章快速傅里葉變換
