快速傅里葉變換原理及其應(yīng)用快速入門

1、快速傅里葉變換的原理及其應(yīng)用摘要快速傅氏變換（FFT），是離散傅氏變換的快速算法，它是根據(jù)離散傅氏變換的奇、偶、虛、實(shí)等特性，對(duì)離散傅立葉變換的算法進(jìn)行改進(jìn)獲得的。它對(duì)傅氏變換的理論并沒有新的發(fā)現(xiàn)，但是對(duì)于在計(jì)算機(jī)系統(tǒng)或者說數(shù)字系統(tǒng)中應(yīng)用離散傅立葉變換，可以說是進(jìn)了一大步。傅里葉變換的理論與方法在“數(shù)理方程”、“線性系統(tǒng)分析”、“信號(hào)處理、仿真”等很多學(xué)科領(lǐng)域都有著廣泛應(yīng)用,由于計(jì)算機(jī)只能處理有限長度的離散的序列,所以真正在計(jì)算機(jī)上運(yùn)算的是一種離散傅里葉變換.雖然傅里葉運(yùn)算在各方面計(jì)算中有著重要的作用，但是它的計(jì)算過于復(fù)雜，大量的計(jì)算對(duì)于系統(tǒng)的運(yùn)算負(fù)擔(dān)過于龐大，使得一些對(duì)于耗電量少，運(yùn)算速度慢

2、的系統(tǒng)對(duì)其敬而遠(yuǎn)之，然而，快速傅里葉變換的產(chǎn)生，使得傅里葉變換大為簡(jiǎn)化，在不犧牲耗電量的條件下提高了系統(tǒng)的運(yùn)算速度，增強(qiáng)了系統(tǒng)的綜合能力，提高了運(yùn)算速度，因此快速傅里葉變換在生產(chǎn)和生活中都有著非常重要的作用，對(duì)于學(xué)習(xí)掌握都有著非常大的意義。關(guān)鍵詞快速傅氏變換；快速算法；簡(jiǎn)化；廣泛應(yīng)用AbstractFast Fourier Transform (FFT), is a discrete fast Fourier transform algorithm, which is based on the Discrete Fourier Transform of odd and even, false,

3、 false, and other characteristics of the Discrete Fourier Transform algorithms improvements obtained. Its Fourier transform theory has not found a new, but in the computer system or the application of digital systems Discrete Fourier Transform can be said to be a big step into. Fourier transform the

4、ory and methods in the mathematical equation and linear systems analysis and signal processing, simulation, and many other areas have a wide range of applications, as the computer can only handle a limited length of the sequence of discrete, so true On the computers operation is a discrete Fourier t

5、ransform. Fourier Although all aspects of computing in the calculation has an important role, but its calculation was too complicated, a lot of computing system for calculating the burden is too large for some Less power consumption, the slow speed of operation of its system at arms length, however,

6、 have the fast Fourier transform, Fourier transform greatly simplifying the making, not in power at the expense of the conditions to increase the speed of computing systems, and enhance the system The comprehensive ability to improve the speed of operation, the Fast Fourier Transform in the producti

7、on and life have a very important role in learning to master all have great significance. Key words Fast Fourier Transform; fast algorithm; simplified; widely used目錄摘要ABSTRACT 緒論快速傅里葉變換原理快速傅里葉的實(shí)際應(yīng)用快速傅里葉變換在喇曼光譜信號(hào)噪聲平滑中的應(yīng)用 引言實(shí)驗(yàn)原理及結(jié)果結(jié)論采用異步實(shí)現(xiàn)的快速傅里葉變換處理器 引言實(shí)驗(yàn)原理及結(jié)果結(jié)論快速傅里葉算法在哈特曼夏克傳感器波前重構(gòu)算法中的應(yīng)用引言實(shí)驗(yàn)原理及結(jié)果結(jié)論參考文

8、獻(xiàn) 緒論傅立葉變換在生產(chǎn)生活中的重要性非常突出，它將原來難以處理的時(shí)域信號(hào)相對(duì)比較容易地轉(zhuǎn)換成了易于分析的頻域信號(hào)，可以利用一些工具對(duì)這些頻域信號(hào)進(jìn)行處理、加工，把信號(hào)轉(zhuǎn)化為可以對(duì)其進(jìn)行各種數(shù)學(xué)變化的數(shù)學(xué)公式，對(duì)其進(jìn)行處理。最后還可以.利用傅立葉反變換將這些頻域信號(hào)轉(zhuǎn)換成時(shí)域信號(hào)，它是一種特殊的積分變換。它能將滿足一定條件的某個(gè)函數(shù)表示成正弦基函數(shù)的線性組合或者積分。然爾，它在運(yùn)算上過于復(fù)雜，過于宏大的運(yùn)算過程，對(duì)于一些相對(duì)簡(jiǎn)單的低功耗處理器來說，難以自如應(yīng)對(duì)，因此，快速傅里葉變換則顯出了它的優(yōu)越性?？焖俑凳献儞Q（FFT），是離散傅氏變換的快速算法，它是根據(jù)離散傅氏變換的奇、偶、虛、實(shí)等特性，

9、對(duì)離散傅立葉變換的算法進(jìn)行改進(jìn)獲得的。對(duì)于計(jì)算機(jī)處理信號(hào)方面上是一大進(jìn)步。系統(tǒng)的速度不但取決于本身的速度，而且還在相當(dāng)大的程度上取決于算法，算法運(yùn)算量的大小直接影響著對(duì)設(shè)備的控制質(zhì)量。通過傅立葉變換（DFT），運(yùn)用測(cè)試軟件進(jìn)行檢測(cè)，可以看出快速傅里葉變換大大的提高了運(yùn)算速度，它為各系統(tǒng)的設(shè)計(jì)提供了簡(jiǎn)單算法，有著十分重要的意義。.快速傅里葉變換原理數(shù)字信號(hào)的傅里葉變換,通常采用離散傅里葉變換(DFT)方法。DFT 存在的不足是計(jì)算量太大,很難進(jìn)行實(shí)時(shí)處理。計(jì)算一個(gè)N 點(diǎn)的DFT ,一般需要次復(fù)數(shù)乘法和N(N-1)次復(fù)數(shù)加法運(yùn)算.因此,當(dāng)N較大或要求對(duì)信號(hào)進(jìn)行實(shí)時(shí)處理時(shí),往往難以實(shí)現(xiàn)所需的運(yùn)算速度

10、。1965年,和發(fā)現(xiàn)了DFT的一種快速算法,經(jīng)其他學(xué)者進(jìn)一步改進(jìn), 很快形成了一套高效運(yùn)算方法,這就是現(xiàn)在通用的快速傅里葉變換, 簡(jiǎn)稱FFT( The Fast Fourier Transform)。快速傅里葉變換的實(shí)質(zhì)是利用式(1)中的權(quán)函數(shù)的對(duì)稱性和周期性,把N點(diǎn)DFT進(jìn)行一系列分解和組合,使整個(gè)DFT的計(jì)算過程變成一系列疊代運(yùn)算過程,使DFT的運(yùn)算量大大簡(jiǎn)化,為DFT及數(shù)字信號(hào)的實(shí)時(shí)處理和應(yīng)用創(chuàng)造了良好的條件。快速傅里葉變換算法如下：由(1)式可知，對(duì)每一個(gè)n，計(jì)算X()須作N次復(fù)數(shù)乘法及N-1次復(fù)數(shù)加法，要完成這組變換共需次乘法及N(N-1)次復(fù)數(shù)加法。但以下介紹的快速傅里葉變換的算法

11、，可大大減少運(yùn)算次數(shù)，提高工作效率。當(dāng)時(shí)，n和k可用二進(jìn)制數(shù)表示：又記,則（1）式可改寫為 （2）式中： (3)因?yàn)樗裕?）可改成 （4） (5)則式（）即為式（）的分解形式。將初始數(shù)據(jù)代入式（）的第一個(gè)等式，可得每一組計(jì)算數(shù)據(jù)，一般將痗L-1組計(jì)算數(shù)據(jù)代入式（）的第L個(gè)等式，計(jì)算后可得第L組計(jì)算數(shù)據(jù)（L，），計(jì)算公式也可表示為= （6）式中 （7） 根據(jù)式（），第L個(gè)數(shù)組中每個(gè) 的計(jì)算只依賴于上一個(gè)數(shù)組的兩個(gè)數(shù)據(jù)這兩個(gè)數(shù)據(jù)的標(biāo)號(hào)相差，即，而且這兩個(gè)數(shù)據(jù)只用于計(jì)算第L個(gè)數(shù)組中標(biāo)號(hào)的數(shù)據(jù)（等號(hào)右端為二進(jìn)制數(shù)）。當(dāng)分別取和時(shí)，分別有。因此，用上一組的兩個(gè)數(shù)據(jù)計(jì)算所得的兩個(gè)新數(shù)據(jù)仍可儲(chǔ)存在原來位置

12、，計(jì)算過程中只需要N個(gè)存儲(chǔ)器。將與稱為第L個(gè)數(shù)組中的對(duì)偶結(jié)點(diǎn)對(duì)。計(jì)算每個(gè)對(duì)偶結(jié)點(diǎn)對(duì)只需一次乘法，事實(shí)上由式（）可得式中： ；別為式（）中取，時(shí)對(duì)應(yīng)的P值。因，于是對(duì)偶結(jié)點(diǎn)的有如下關(guān)系：,因此式（）可表示為P的求法：在中，i寫成二進(jìn)制數(shù)右移位，就成為顛倒位序得式（）呂，前面的個(gè)等式，每個(gè)等式均對(duì)應(yīng)一組數(shù)據(jù)進(jìn)行計(jì)算，每組數(shù)據(jù)都有N/對(duì)結(jié)點(diǎn)，根據(jù)式（），每對(duì)結(jié)點(diǎn)只需作次乘法和次加法，因此，每組數(shù)據(jù)只需N/2次乘法和N次加法，因而完成組數(shù)據(jù)的計(jì)算共需N/2次乘法和N次加法。.快速傅里葉的實(shí)際應(yīng)用:一快速傅里葉變換在喇曼光譜信號(hào)噪聲平滑中的應(yīng)用引言電探測(cè)系統(tǒng)是光信號(hào)的轉(zhuǎn)換、傳輸及處理的系統(tǒng). 系統(tǒng)的各個(gè)

13、部分在工作時(shí)總會(huì)受到一些無用信號(hào)的干擾,給光譜峰的檢測(cè)判別及進(jìn)一步的數(shù)據(jù)處理帶來了不利因素.對(duì)光譜信號(hào)進(jìn)行數(shù)字濾波,以獲得更真實(shí)的光譜信息，顯得格外重要. 目前最為通用和有效的信號(hào)濾波處理方法是快速傅立葉變換方法.純水是一種較弱的喇曼散射介質(zhì),需要專用的喇曼散射光譜儀器才能獲得高信噪比的喇曼光譜.我們以增強(qiáng)型的CCD 探頭為探測(cè)器,結(jié)合普通的分光單色儀,在YAG 激光器532 nm 激光線的激勵(lì)下獲得低信噪比的純水的喇曼光譜. 信噪比較差的喇曼光譜經(jīng)過FFT 變換后,用FFT 的逆變換將濾除噪聲后的頻譜信號(hào)轉(zhuǎn)換成為光譜信號(hào),最終獲得信噪比較高的純水的喇曼光譜. 實(shí)驗(yàn)原理及結(jié)果傅里葉變換的基本表

14、達(dá)式為 （） （）式（1）中的x（n）(n=0,2,N-1)是列長為N的輸入序列，即實(shí)驗(yàn)采集到的時(shí)域上的切片數(shù)據(jù);x(k)(=0,1,N-1)是列長為N的輸出序列，即經(jīng)過傅里葉變換后的頻域上的數(shù)據(jù)。 對(duì)數(shù)字化后的光譜信號(hào)而言, x(n)是一組離散的實(shí)數(shù)信號(hào)；而X(k)分為實(shí)部x(v)和虛部y()2部分。x()和y()又可組成振幅譜A()和相位譜P()：（）（）通過對(duì)式(3)和式(4)性能的考察,發(fā)現(xiàn)A()和P()中既含有目標(biāo)信號(hào)的信息,也含有噪聲的信息,如果二者所在的區(qū)域不同, 則可以通過傅里葉變換分析出噪聲信息, 將之從捕獲的信號(hào)中去除,從而達(dá)到噪聲平滑的目的, 獲得高信噪比的目標(biāo)信號(hào).純水

15、普通喇曼散射的信號(hào)很弱,我們?cè)?32nm 脈沖激光泵浦液滴的條件下獲得其散射光譜.由于樣品信號(hào)極其微弱,在將CCD 的增益調(diào)至最大時(shí),獲得如圖1 所示的純水的喇曼光譜. 光譜的信噪比值用如下方式估算:設(shè) 為含噪聲圖像為消除噪聲后的圖像,圖像的均方根誤差為 (5)信噪比定義為除噪聲后的信號(hào)與均方根誤差之比 (6)計(jì)算出642. 86 643. 62 nm 光譜區(qū)的信噪比為SN R 17. 圖多通道光譜分析儀采集的含有噪聲的純水普通喇曼散射信號(hào)圖2 傅里葉變換后的頻譜圖對(duì)圖2 幅度譜縱軸取對(duì)數(shù)得圖噪聲幅度門限值低于2 105 ,經(jīng)門限濾波處理,在頻譜圖中將幅度譜低于該門限值的頻率成分去除,獲得的頻

16、譜用FFT 的逆變換返回得到門限濾波曲線如圖5 所示.計(jì)算出642. 86643. 62 nm 光譜區(qū)的信噪比為SN R484. 與圖1 相比,光譜的信噪比有了極大的改善.3 結(jié)論在光譜信號(hào)受到光子噪聲調(diào)制的條件下,如果光譜信號(hào)的變化頻率低于高頻光子噪聲的變化頻率,則可以通過快速傅里葉變換,獲得目標(biāo)信號(hào)和噪聲信號(hào)的頻譜,進(jìn)行低通濾波和門限濾波后,分別將具有高頻和不同振幅的噪聲信號(hào)去除,實(shí)現(xiàn)對(duì)弱光譜信號(hào)干擾噪聲的抑制,得到高信噪比的光譜信號(hào)?？焖俑道锶~變換在效果上，減輕了噪聲的干擾，同時(shí)計(jì)算也不會(huì)帶來過于復(fù)雜的計(jì)算。.采用異步實(shí)現(xiàn)的快速傅里葉變換處理器1.引言快速傅里葉變換(FFT)是數(shù)字信號(hào)處

17、理領(lǐng)域一個(gè)重要的分析工具,廣泛應(yīng)用于雷達(dá)、通訊、圖像處理、聲納和生物醫(yī)學(xué)領(lǐng)域。已經(jīng)開發(fā)出多種專用快速傅里葉變換處理器,大大提高了快速傅里葉變換的運(yùn)算速度。異步集成電路具有功率效率高、電磁兼容性(EMC)好、功耗低和沒有時(shí)鐘歪斜(Skew)的特性,同時(shí)又具有潛在的高性能,以及便于系統(tǒng)模塊化設(shè)計(jì)的優(yōu)勢(shì)1。異步集成電路運(yùn)算的性能是平均性能,而不是最差性能。這樣,當(dāng)平均性能與最差性能差別較大時(shí),異步集成電路有希望達(dá)到比同步電路更高的潛在性能。異步集成電路采用大量本地時(shí)序控制信號(hào)來取代整體時(shí)鐘,避免了當(dāng)前在超大規(guī)模集成電路設(shè)計(jì)中遇到的時(shí)鐘樹設(shè)計(jì)和代價(jià)問題。2.原理及結(jié)果異步實(shí)現(xiàn)的快速傅里葉變換處理器的結(jié)

18、構(gòu)如圖4所示。處理器的控制由本地的握手信號(hào)控制,每個(gè)單元獨(dú)立地工作,避免了同步電路中的時(shí)鐘分配問題。處理器在輸入數(shù)據(jù)準(zhǔn)備好后開始工作,整個(gè)運(yùn)算完成時(shí)產(chǎn)生一個(gè)完成信號(hào)。采用0.6m 標(biāo)準(zhǔn)CMOS工藝,設(shè)計(jì)一個(gè)8點(diǎn)的異步快速傅里葉變換處理器。該處理器具有28 比特的輸入,215 比特的輸出,220 比特的內(nèi)部運(yùn)算精度。在電路設(shè)計(jì)完成之后,采用華晶2上華的0.6m CMOS2P2M 混合電路工藝,建立了異步標(biāo)準(zhǔn)單元庫,然后對(duì)異步快速傅里葉變換處理器進(jìn)行了全定制設(shè)計(jì)。處理器的版圖如圖5 所示。圖4 異步快速傅里葉變換處理器結(jié)構(gòu)功能仿真：用晶體管構(gòu)成的電路網(wǎng)表描述每個(gè)單元(加法器、乘法器等) ,然后用H

19、spice 進(jìn)行功能仿真。根據(jù)電路Hspice 仿真結(jié)果,通過抽象模型,建立每個(gè)單元的功能和延遲的邏輯模型。異步邏輯和運(yùn)算模塊的抽象過程比同步模塊要復(fù)雜得多,因?yàn)橥侥K只要用功能加上一個(gè)最差延遲就可以描述模塊的功能性能模型。CMOS 的抽象過程就是用邏輯描述建立FFT的邏輯網(wǎng)表(帶延遲) ,再用Verilog 進(jìn)行邏輯仿真。性能仿真：響應(yīng)時(shí)間是異步集成電路性能分析時(shí)常用的度量標(biāo)準(zhǔn)5。響應(yīng)時(shí)間是指請(qǐng)求信號(hào)到完成信號(hào)之間的延遲,它主要有兩種類型:最差響應(yīng)時(shí)間和平均響應(yīng)時(shí)間。其中, 最差響應(yīng)時(shí)間主要依賴于電路的結(jié)構(gòu)和實(shí)現(xiàn),而平均響應(yīng)時(shí)間不僅與電路結(jié)構(gòu)有關(guān),還與輸入的數(shù)據(jù)相關(guān)。文中采用Star2Si

20、mXT ,對(duì)整個(gè)異步快速傅里葉變換處理器進(jìn)行了電路仿真,得到芯片完成一次變換的最差響應(yīng)時(shí)間為42.85 ns ,平均響應(yīng)時(shí)間為31.15 ns ,功耗約為350.7mW。3. 結(jié)論設(shè)計(jì)了一個(gè)異步的快速傅里葉變換處理器,該電路可以在異步邏輯控制下工作。性能分析表明,異步快速傅里葉變換處理器的平均性能較同步設(shè)計(jì)有優(yōu)勢(shì)。但是,異步集成電路完成信號(hào)的產(chǎn)生往往需要增加一部分電路。這不僅增加了芯片的面積,而且?guī)砹艘欢ǖ难舆t,異步集成電路性能的優(yōu)勢(shì)能否實(shí)現(xiàn),與這部分電路設(shè)計(jì)是否合理有很大的關(guān)系。另外,由于缺少成熟的EDA工具、算法和設(shè)計(jì)方法學(xué)的支撐,異步集成電路設(shè)計(jì)技術(shù)在超大規(guī)模集成方面還面臨很多挑戰(zhàn)，還

21、需繼續(xù)改進(jìn)。三. 快速傅里葉算法在哈特曼夏克傳感器波前重構(gòu)算法中的應(yīng)用1. 引言哈特曼夏克傳感器因其波前測(cè)量實(shí)時(shí)性好等特點(diǎn)而廣泛用于自適應(yīng)光學(xué)系統(tǒng)中,隨著應(yīng)用研究的發(fā)展,哈特曼夏克波前測(cè)量傳感器的空間分辨率也要相應(yīng)提高。哈特曼夏克傳感器測(cè)量的是波前相位斜率,需要經(jīng)過波前復(fù)原求出相位值,復(fù)原的方法主要有區(qū)域法和模式法兩類,為了滿足實(shí)時(shí)性的要求,哈特曼夏克傳感器的子孔徑較少,測(cè)量的空間分辯率因此比干涉儀低。當(dāng)增加哈特曼夏克傳感器的子孔徑數(shù)提高空間分辨率、提高測(cè)量精度時(shí),區(qū)域法和模式法的運(yùn)算量非常大,實(shí)時(shí)性降低,限制了高分辨率哈特曼夏克傳感器在自適應(yīng)光學(xué)系統(tǒng)等領(lǐng)域的進(jìn)一步應(yīng)用。針對(duì)實(shí)時(shí)性問題,提出了

22、分塊算法和迭代法進(jìn)行波前重構(gòu)。在區(qū)域法重構(gòu)波前的基礎(chǔ)上,應(yīng)用快速傅里葉變換(FFT) 算法,提高波前復(fù)原算法的實(shí)時(shí)性,為高分辨率哈特曼夏克傳感器在自適應(yīng)光學(xué)技術(shù)及其它領(lǐng)域的應(yīng)用作算法準(zhǔn)備。2. 實(shí)驗(yàn)原理及結(jié)果快速傅里葉變換算法以其運(yùn)算速度快、所需內(nèi)存小而被廣泛用于數(shù)字信號(hào)處理領(lǐng)域9。在求解由(1)式確定的線性方程組的過程中,需要實(shí)現(xiàn)方程系數(shù)矩陣的對(duì)角化,而這一過程可以通過快速傅里葉變換算法實(shí)現(xiàn),從而實(shí)現(xiàn)(1) 式的快速求解。首先,不考慮區(qū)域中邊界處的相位估計(jì)差分方程,在波前重構(gòu)的區(qū)域內(nèi),即1iM -1,1jN -1,(1)式嚴(yán)格成立,并由它導(dǎo)出波前估計(jì)的矩陣方程組表示為 (2)對(duì)(2)式的矩陣AO作正交變換,得: (4)其中（） 應(yīng)用快速傅里葉變換算法,乘法運(yùn)算量可由直接作線性變換的 次降為次,當(dāng)哈特曼夏克傳感器的子孔徑數(shù)比較大時(shí),運(yùn)算速度可大幅度提高,從而提高哈特曼夏克傳感器波前重構(gòu)算法的實(shí)時(shí)性。在波前估計(jì)的計(jì)算式(2)中,只考慮了哈特曼夏克傳感器區(qū)域內(nèi)的估計(jì)點(diǎn),需要知道區(qū)域邊界處的相位值,才能準(zhǔn)確求解式,而哈特曼夏克傳感器測(cè)量的是斜率值,給出的是諾依曼邊界條件,需要作邊界條件的近