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

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