《快速傅里葉變換算法原理綜述》1400字

快速傅里葉變換算法原理第9頁（共22頁）快速傅里葉變換算法原理綜述1.1傅里葉變換早在1822年，傅里葉（法國數(shù)學家）提出了具有深遠影響的傅里葉級數(shù)，其明確指出，所有處于連續(xù)狀態(tài)的周期信號，均能夠進行相應(yīng)分解，最終可以將若干正弦函數(shù)之和給求出來。在具體的頻域上，主要用其來對位離散非周期所對應(yīng)的相關(guān)信號進行表示。需要強調(diào)的是，傅里葉變換理論能夠借助數(shù)學公式的推導，將傅里葉級數(shù)逐一計算出來。在特定時域區(qū)間[t0，t0+T]上的一個可積函數(shù)，可用如下公式來表示傅里葉級數(shù)：ft=a02其中：an=2Ttbn=2Tt同時，需要說明的是，連續(xù)非周期連續(xù)時間信號f(t)傅里葉正/反變換可用如下公式來進行表示：F(jω)=-∞∞f(t)ft=12Π-∞最后，依據(jù)所輸入信號的差異，可將傅里葉變換劃分成多種類型：其一為周期性離散時間信號傅里葉變換，其二是周期性連續(xù)時間信號傅里葉變換，其三為非周期性連續(xù)時間信號傅里葉變換，其四則為非周期性離散時間信號傅里葉變換。各個變換所對應(yīng)的輸入信號如圖7所示。圖7.四種不同類型的輸入信號示意圖FPGA實現(xiàn)機械掃描成像聲吶的數(shù)據(jù)處理第10頁（共22頁）1.2離散傅里葉變換（DFT）針對離散傅里葉變換來考量，實際就是依據(jù)已知曉的傅里葉變換值，圍繞有限長序列傅里葉變換，以一種合理、高效且規(guī)范的方式再次實施有限次點采樣，將信號頻域進行離散化，因此，即便是在頻域中的信號，同樣能借助數(shù)字運算方法來實施處理，可以提高信號的處理效率和靈活度。在處理信號過程中，對于DFT的相關(guān)計算來講，同樣有著十分關(guān)鍵的地位，許多信號的頻譜，濾波以及相關(guān)性都可以使用這種方法來計算。其中，對離散時間信號f(n)的連續(xù)傅里葉變換可以由以下表示：F(ejω)=n=0由上式可以看出，頻域內(nèi)的變量為連續(xù)變量，無法在計算機中進行數(shù)字計算，所以必須對其進行頻譜離散化，最后就可以得到DFT的計算表示為：Fk=n=0N-1若將上式中的e-j2ΠN定義為WNFk=n=0N-1則離散傅里葉反變換的定義就為下式：fn=1N通常，可以將式(3-2-3)和式(3-2-4)稱為離散傅里葉變換對?？焖俑道锶~變換算法原理第11頁（共22頁）1.3快速傅里葉變換（FFT）對于FFT來考量，實際就是借助WN因子所對應(yīng)的周期性，結(jié)合DFT快速算法來進行各項工作。針對FFT算法來講，實際就是基于長序列的DFT，然后對其實施相應(yīng)分解，使其最終成為短序列的DFT；從物理層面來分析，其實際就是一個比較特殊的模擬信號，經(jīng)ADC采樣處理后，便會向數(shù)字信號轉(zhuǎn)換；需要強調(diào)的是，經(jīng)采樣而最終得到的數(shù)字信號，同樣可進行FFT變換。為了使FFT運算變得更加簡便，一般情況下，N需要取2的整數(shù)次方,這樣可以使計算量減小許多REF_Ref71530028\r\h[13]。此外，利用旋轉(zhuǎn)因子的特性即可以減少DFT的運算次數(shù)REF_Ref71530041\r\h[14]，使DFT在其所有的運算過程中進行簡化，形成一系列迭代運算的過程REF_Ref71530062\r\h[15]，使用的比較多的方法便是基2FFT算法。針對2FFT算法來分析，其能夠?qū)⒃缺容^長的序列進行分解，使之成為若干短序列，然后在逐一實施DFT運算；此外，通過對WkN的周期性、對稱性展開合理化、優(yōu)質(zhì)化的合并，便能實現(xiàn)DFT相應(yīng)運算次數(shù)的減少。其中，周期性與對稱性可以分別表示為：周期性：WNk還需指出的是，可將基2FFT算法劃分成兩種類型，一種是時域抽取法 FFT（簡稱為DIT-FFT），另外一種則為頻域抽取法FFT（DIF-FFT），本文根據(jù)總體設(shè)計需要，最終選擇的是時域抽取法FFTREF_Ref71530080\r\h[16]。首先，通過對n的奇、偶數(shù)進行準確區(qū)分，分解長序列，使之成為2個有著相同長度的子序列。f1k=f2kf2k=f(2k+1)然后分別對這兩個子序列進行DFT運算可以得到兩個離散的序列，F(xiàn)1K=n=0N/2fF2K=n=0N/2f利用旋轉(zhuǎn)因子的周期性和對稱性，進行多項式的轉(zhuǎn)換與求和。FK=F1KFK+N2=F最后便可以N點DFT分為N/2點的DFT，即蝶形運算REF_Ref71530111\r\h[17]，其有助于計算次數(shù)的大幅減少REF_Ref71530116\r\h[18]。但需強調(diào)的是，伴隨N的持續(xù)增大，F(xiàn)FT算法與DFT