《快速傅里葉變換》由會員分享，可在線閱讀，更多相關(guān)《快速傅里葉變換（33頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,#,第,4,章 快速傅里葉變換,(FFT),4.1,引言,4.2,基,2FFT,算法,4.3,進(jìn)一步減少運(yùn)算量的措施,4.4,分裂基,FFT,算法,4.5,離散哈特萊變換,(DHT),4.1,引言,DFT,是信號分析與處理中的一種重要變換。因直接計算,DFT,的計算量與變換區(qū)間長度,N,的平方成正比，當(dāng),N,較大時，計算量太大，所以在快速傅里葉變換,(,簡稱,FFT),出現(xiàn)以前，直接用,DFT,算法進(jìn)行譜分析和信號的實(shí)時處理是不切實(shí)際的。直到,1965,年,Cooley,和,Tukey,發(fā)現(xiàn)了,DFT,的一種快

2、速算法以后，情況才發(fā)生了根本的變化。,4.2,基,2FFT,算法,4.2.1,直接計算,DFT,的特點(diǎn)及減少運(yùn)算量的基本途徑,長度為,N,的有限長序列,x,(,n,),的,DFT,為,考慮,x,(,n,),為復(fù)數(shù)序列的一般情況，對某一個,k,值，直接按,(4.2.1),式計算,X(,k,),值需要,N,次復(fù)數(shù)乘法、,(N-1),次復(fù)數(shù)加法。,因此，,N,點(diǎn),DFT,的復(fù)乘次數(shù)等于,N,2,加法次數(shù),N(N-1),.,當(dāng),N1,時，即,N,點(diǎn),DFT,的乘法和加法運(yùn)算次數(shù)均與,N,2,成正比，當(dāng),N,較大時，運(yùn)算量相等可觀。,(4.2.1),注意：,通常將算術(shù)乘法和算術(shù)加法的次數(shù)作為計算復(fù)雜性的

3、度量，因?yàn)檫@種方法使用起來很簡單。如果在計算機(jī)上用軟件實(shí)現(xiàn)這些算法，則乘法和加法的次數(shù)就直接與計算速度有關(guān)。,但是，在常用的,VLSI,實(shí)現(xiàn)時，芯片的面積和功率要求往往是最重要的考慮因素，而它們有可能與算法的運(yùn)算次數(shù)沒有直接的關(guān)系。,顯然，把,N,點(diǎn),DFT,分解為幾個較短的,DFT,，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子,W,m,N,具有明顯的周期性、對稱性和可約性。其,周期性,表現(xiàn)為,(4.2.2),其,對稱性,表現(xiàn)為,或者,可約性,表現(xiàn)在,：,4.2.2,時域抽取法基,2 FFT,基本原理,FFT,算法基本上分為兩大類：時域抽取法,FFT(Decimation In Time FFT,簡

4、稱,DIT-FFT,),和頻域抽取法,FFT(Decimation In Frequency FFT,簡稱,DIF-FFT,),。下面介紹,DIT-FFT,算法。,設(shè)序列,x,(,n,),的長度為,N,，且滿足,為自然數(shù),按,n,的奇偶把,x,(,n,),分解為兩個,N/2,點(diǎn)的子序列,則,x,(,n,),的,DFT,為,由于,所以,其中,X,1,(,k,),和,X,2,(,k,),分別為,x,1,(,r,),和,x,2,(,r,),的,N/2,點(diǎn),DFT,，即,(4.2.5),(4.2.6),由于,X,1,(,k,),和,X,2,(,k,),均以,N/2,為周期，且,，所以,X(,k,),又

5、可表示為,(4.2.7),(4.2.8),圖,4.2.1,蝶形運(yùn)算符號,X,1,(,k,),X,2,(,k,),W,N,K,X,1,(,k,)+W,N,K,X,2,(,k,),X,1,(,k,)-W,N,K,X,2,(,k,),經(jīng)過一次分解后，計算復(fù)數(shù)乘和復(fù)數(shù)加的次數(shù)：,復(fù)數(shù)乘：,復(fù)數(shù)加：,一次分解后，運(yùn)算量減少近一半，故可以對,N/2,點(diǎn),DFT,再作進(jìn)一步分解。,圖,4.2.2 N,點(diǎn),DFT,的一次時域抽取分解圖,(N=8),與第一次分解相同，將,x,1,(,r,),按奇偶分解成兩個,N/4,長的子序列,x,3,(,l,),和,x,4,(,l,),，即,那么，,X,1,(,k,),又可表

6、示為,(4.2.9),式中,同理，由,X,3,(,k,),和,X,4,(,k,),的周期性和 的對稱,性 ，最后得到：,(4.2.10),用同樣的方法可計算出,(4.2.11),其中,圖,4.2.3 N,點(diǎn),DFT,的第二次時域抽取分解圖,(N=8),圖,4.2.4 N,點(diǎn),DITFFT,運(yùn)算流圖,(N=8),4.2.3 DIT-FFT,算法與直接計算,DFT,運(yùn)算量的比較,運(yùn)算流圖有,M,級蝶型，每一級都有,N/2,個蝶型運(yùn)算。每一級運(yùn)算都需要,N/2,次復(fù)數(shù)乘和,N,次復(fù)數(shù)加,(,每個蝶形需要兩次復(fù)數(shù)加法,),。所以，,M,級運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為,復(fù)數(shù)加次數(shù)為,例如,，,N=2,10

7、,=1024,時,圖,4.2.5 FFT,算法與直接計算,DFT,所需乘法次數(shù)的比較曲線,MATLAB,提供了一個,fft,的函數(shù)用于計算一個向量,x,的,DFT,。調(diào)用,X=fft(x,N),就計算出,N,點(diǎn)的,DFT,。如果向量,x,的長度小于,N,，那么就將,x,補(bǔ),0,。如果略去,N,，則,DFT,的長度就是,x,的長度。如果,x,是一個矩陣，那么,fft(x,N),計算,x,中每一列的,N,點(diǎn)的,DFT,。,fft,由機(jī)器語言寫成的，執(zhí)行速度快。當(dāng),N,為,2,的冪次方，則使用基,2 FFT,算法，如果不是，那么將,N,分解為若干素因子并用一個較慢的混合基,FFT,算法。如果,N,為

8、某個素數(shù)，則,fft,算法就蛻化為原始的,DFT,算法。,4.2.4 DIT-FFT,的運(yùn)算規(guī)律及編程思想,1.,原位計算,1),由圖,4.2.4,可以看出，,DITFFT,的運(yùn)算過程很有規(guī)律。,N=2,M,點(diǎn)的,FFT,共進(jìn)行,M,級運(yùn)算，每級由,N/2,個蝶形運(yùn)算組成。,2),同一級，每個蝶形的兩個輸入數(shù)據(jù)只對計算本蝶形有用，而且每個蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)又同在一水平線上，即計算完一個蝶形后，所得的數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲單元。,3),經(jīng)過,M,級運(yùn)算后，原來存放輸入序列數(shù)據(jù)的,N,個存儲單元中依次存放,X(,k,),的,N,個值。,這種利用同一存儲單元存儲蝶形計算輸入、輸出

9、數(shù)據(jù)的方法稱為,原位計算,，可以大大節(jié)省內(nèi)存。,2.,旋轉(zhuǎn)因子的變化規(guī)律,如上所述，,N,點(diǎn),DIT-FFT,運(yùn)算流圖中，每級都有,N/2,個蝶形。每個蝶形都要乘以因子,W,p,N,，稱其為旋轉(zhuǎn)因子，,p,稱為旋轉(zhuǎn)因子的指數(shù),.,觀察圖,4.2.4,不難發(fā)現(xiàn)，第,L,級共有,2,L-1,個不同的旋轉(zhuǎn)因子。,N=2,3,=8,時的各級旋轉(zhuǎn)因子表示如下：,L=1,時，,L=2,時，,L=3,時，,對,N=2,M,的一般情況，第,L,級的旋轉(zhuǎn)因子為,(4.2.12),(4.2.13),3.,序列的倒序,DIT-FFT,算法的輸入序列的排序看起來似乎很亂，但仔細(xì)分析就會發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于,

10、N=2,M,，所以順序數(shù)可用,M,位二進(jìn)制數(shù),(,n,M-1,n,M-2,n,1,n,0,),表示。,圖,4.2.7,形成倒序的樹狀圖,(N=2,3,),表,4.2.1,順序和倒序二進(jìn)制數(shù)對照表,4.2.5,頻域抽取法,FFT(DIF-FFT),在基,2,快速算法中，頻域抽取法,FFT,也是一種常用的快速算法，簡稱,DIF-FFT,。,設(shè)序列,x,(,n,),長度為,N=2,M,，首先將,x,(,n,),前后對半分開，得到兩個子序列，其,DFT,可表示為如下形式：,將,X(,k,),分解成偶數(shù)組與奇數(shù)組，當(dāng),k,取偶數(shù),(,k,=2,r,r,=0,1,N/2-1),時,(4.2.14),x,1

11、,(,n,),當(dāng),k,取奇數(shù),(,k,=2,r,+1,r,=0,1,N/2-1),時,(4.2.15),將,x,1,(,n,),和,x,2,(,n,),分別代入,(4.2.14),和,(4.2.15),式，可得,(4.2.16),x,2,(,n,),圖,4.2.10 DIF-FFT,蝶形運(yùn)算流圖符號,4.2.6 IDFT,的高效算法,上述,FFT,算法流圖也可以用于離散傅里葉逆變換,(Inverse Discrete Fourier Transform,，簡稱,IDFT),。比較,DFT,和,IDFT,的運(yùn)算公式：,只要將,DFT,運(yùn)算式中的系數(shù) 改變?yōu)?，最后乘以 ，就是,IDFT,的運(yùn)算公

12、式。故只要將上述的,DIT-FFT,與,DIF-FFT,算法中的旋轉(zhuǎn)因子 改為,最后的輸出再乘以 就可以用來計算,IDFT.,如果希望直接調(diào)用,FFT,子程序計算,IFFT,，則可用下面的方法：,由于,對上式兩邊同時取共軛，得,4.3.2,實(shí)序列的,FFT,算法,1.,設(shè),x,(,n,),為,N,點(diǎn)實(shí)序列，取,x,(,n,),的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分別作為新構(gòu)造序列,y,(,n,),的實(shí)部和虛部，即,對,y,(,n,),進(jìn)行,N/2,點(diǎn),FFT,，輸出,Y(,k,),，則,根據(jù),DIT-FFT,的思想及式,(4.2.7),和,(4.2.8),，可得到,由于,x,(,n,),為實(shí)序列，所以,X(,k,),具有共軛對稱性，,X(,k,),的另外,N/2,點(diǎn)的值為,2.,一個,N,點(diǎn),FFT,計算兩個,N,點(diǎn)實(shí)序列的,FFT,，一個序列作為實(shí)部，一個序列作為虛部，計算完,FFT,后，根據(jù),DFT,的共軛對稱性，由輸出,X(,k,),分別得到兩個時序列的,N,點(diǎn),FFT.,