快速傅里葉變換算法及其在信號處理中的應(yīng)用畢業(yè)論文

1、 畢業(yè)設(shè)計(論文) 題 目快速傅里葉變換算法及其在信號處理中的應(yīng)用專 業(yè) 班 級學(xué) 號姓 名指 導(dǎo) 教 師學(xué) 院 名 稱畢業(yè)設(shè)計論文原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計論文，是我個人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機構(gòu)的學(xué)位或?qū)W歷而使用過的材料。對本研究提供過幫助和做出過奉獻(xiàn)的個人或集體，均已在文中作了明確的說明并表示了謝意。作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日期： 使用授權(quán)說明本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計論

2、文的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計論文的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計論文的印刷本和電子版，并提供目錄檢索與閱覽效勞；學(xué)校可以采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡木植炕蛉績?nèi)容。作者簽名： 日 期： 學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨立進(jìn)行研究所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。對本文的研究做出重要奉獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。本人完全意識到本聲明的法律后果由本人承當(dāng)。作者簽名： 日期： 年 月 日學(xué)位論文版權(quán)使用

3、授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保存、使用學(xué)位論文的規(guī)定，同意學(xué)校保存并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán) 大學(xué)可以將本學(xué)位論文的全部或局部內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。涉密論文按學(xué)校規(guī)定處理。作者簽名：日期： 年 月 日導(dǎo)師簽名： 日期： 年 月 日注 意 事 項1.設(shè)計論文的內(nèi)容包括：1封面按教務(wù)處制定的標(biāo)準(zhǔn)封面格式制作2原創(chuàng)性聲明3中文摘要300字左右、關(guān)鍵詞4外文摘要、關(guān)鍵詞 5目次頁附件不統(tǒng)一編入6論文主體局部：引言或緒論、正文、結(jié)論7參考文獻(xiàn)8致謝9附錄對論文支持必要時2.論文字?jǐn)?shù)要

4、求：理工類設(shè)計論文正文字?jǐn)?shù)不少于1萬字不包括圖紙、程序清單等，文科類論文正文字?jǐn)?shù)不少于1.2萬字。3.附件包括：任務(wù)書、開題報告、外文譯文、譯文原文復(fù)印件。4.文字、圖表要求：1文字通順，語言流暢，書寫字跡工整，打印字體及大小符合要求，無錯別字，不準(zhǔn)請他人代寫2工程設(shè)計類題目的圖紙，要求局部用尺規(guī)繪制，局部用計算機繪制，所有圖紙應(yīng)符合國家技術(shù)標(biāo)準(zhǔn)標(biāo)準(zhǔn)。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準(zhǔn)用徒手畫3畢業(yè)論文須用A4單面打印，論文50頁以上的雙面打印4圖表應(yīng)繪制于無格子的頁面上5軟件工程類課題應(yīng)有程序清單，并提供電子文檔5.裝訂順序1設(shè)計論文2附件：按照任務(wù)書、開題報告、外文譯文、

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

6、其敬而遠(yuǎn)之，然而，快速傅里葉變換的產(chǎn)生，使得傅里葉變換大為簡化，在不犧牲耗電量的條件下提高了系統(tǒng)的運算速度，增強了系統(tǒng)的綜合能力，提高了運算速度，因此快速傅里葉變換在生產(chǎn)和生活中都有著非常重要的作用，對于學(xué)習(xí)掌握都有著非常大的意義。 關(guā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, f

7、alse, 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 theor

8、y 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 tra

9、nsform. 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, h

10、ave 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 production

11、 and life have a very important role in learning to master all have great significance.KeyWords：Fast Fourier Transform; fast algorithm; simplified; widely used目 錄摘要.IAbstract . II TOC o 1-3 h z u HYPERLINK l _Toc385634561 1.緒論 HYPERLINK l _Toc385634562 1.1 選題背景1 HYPERLINK l _Toc385634563 1.2 課題研究的意義

12、2 HYPERLINK l _Toc385634567 HYPERLINK l _Toc31137 2.快速傅里葉變換原理及性質(zhì) HYPERLINK l _Toc385634568 2.1快速傅里葉變換原理3 HYPERLINK l _Toc385634569 2.2快速傅里葉變換的優(yōu)越性4 HYPERLINK l _Toc385634570 HYPERLINK l _Toc9754 2.3快速傅里葉變換的意義4 HYPERLINK l _Toc385634573 HYPERLINK l _Toc27753 3.快速傅里葉變換的算法 HYPERLINK l _Toc385634574 HYPE

13、RLINK l _Toc8124 3.1快速傅里葉變換算法6 HYPERLINK l _Toc385634575 3.2 Cooley=Tukey FFT算法8 HYPERLINK l _Toc385634576 3.3 Rader-Brennr FFT算法9 HYPERLINK l _Toc385634576 3.4 Goertsel 算法10 HYPERLINK l _Toc385634577 HYPERLINK l _Toc27753 4.快速傅里葉變換在信號處理中的理論應(yīng)用 HYPERLINK l _Toc385634578 HYPERLINK l _Toc8124 4.1利用FFT計

14、算連續(xù)時間信號的傅里葉變換13 HYPERLINK l _Toc385634579 4.2利用FFT計算離散信號的線性卷積17 HYPERLINK l _Toc385634580 4.3利用FFT進(jìn)行離散信號壓縮19 HYPERLINK l _Toc385634579 4.4利用FFT對離散信號進(jìn)行濾波22 HYPERLINK l _Toc385634579 4.5利用FFT提取離散信號中的最強正弦分量24 HYPERLINK l _Toc385634581 HYPERLINK l _Toc31137 5.快速傅里葉變換在數(shù)字信號分析與處理的實際應(yīng)用 HYPERLINK l _Toc38563

15、4582 5.1快速傅里葉變換在喇曼光譜信號噪聲平滑中的應(yīng)用29 HYPERLINK l _Toc385634583 5.2采用異步實現(xiàn)的快速傅里葉變換處理器31 HYPERLINK l _Toc385634584 HYPERLINK l _Toc9754 5.3快速傅里葉算法在哈特曼夏克傳感器波前重構(gòu)算法中的應(yīng)用33 HYPERLINK l _Toc385634587 致謝36 HYPERLINK l _Toc385634586 參考文獻(xiàn)371 緒論傅立葉變換在生產(chǎn)生活中的重要性非常突出，它將原本難以處理的時域信號相比比擬容易地轉(zhuǎn)換成易于分析的頻域信號，我們可以利用一些專業(yè)工具對這些頻域信號

16、進(jìn)行處理、加工，使信號轉(zhuǎn)化為可以對其進(jìn)行各種數(shù)學(xué)變換的數(shù)學(xué)公式，對其進(jìn)行處理。最后還可以根據(jù)傅立葉反變換將這些頻域信號轉(zhuǎn)換成原來的時域信號，這是一種特殊的積分變換。它能夠?qū)M足一定條件的某個函數(shù)表示成為正弦基函數(shù)的線性組合或者積分。然而，它在運算上過于復(fù)雜，過于宏大的運算過程，對于一些相對簡單的低功耗處理器來說，難以自如應(yīng)對，因此，快速傅里葉變換那么顯出了它的優(yōu)越性?？焖俑凳献儞QFFT，即離散傅氏變換的快速算法，它是根據(jù)離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進(jìn)行改良獲得的1。對于計算機處理信號方面上是一大進(jìn)步。系統(tǒng)的速度不但取決于其本身的速度，而且還在相當(dāng)大的程度上取決于運

17、用的算法，算法運算量的大小直接影響到對設(shè)備的控制質(zhì)量。通過傅立葉變換DFT，運用測試軟件進(jìn)行檢測，我們可以看出，快速傅里葉變換大大的提高了運算速度，它為各系統(tǒng)的設(shè)計方案提供了簡單算法，有著非常重要的意義。1. 1 選題背景近十多年來，數(shù)字信號處理技術(shù)同大規(guī)模集成電路、數(shù)字計算機等，都有了突飛猛進(jìn)的開展，日新月異，早已成為了一門具有強大生命力的技術(shù)科學(xué)。因為它本身就具有一系列的優(yōu)點，所以能夠有效地促進(jìn)工程技術(shù)領(lǐng)域的技術(shù)改造和科學(xué)開展，應(yīng)用領(lǐng)域也更加地廣泛、深入，越來越受到人們的重視。在信號處理中，離散傅里葉變換Discrete Fourier Transform，DFT是比擬常用的變換方法之一，

18、它在各種數(shù)字信號處理系統(tǒng)中扮演著及其重要的角色。由于離散傅里葉變換DFT而發(fā)現(xiàn)了頻率離散化，可以直接用它來分析信號的頻譜、計算濾波器的頻率響應(yīng)、以及實現(xiàn)信號通過線系統(tǒng)的卷積運算等，因而在信號的譜分析等方面有著非常大的作用。傅里葉變換已經(jīng)有一百多年的歷史了，我們熟知頻域分析往往比時域分析更優(yōu)越，不僅簡單明了，而且易于分析較為復(fù)雜的信號。但需要用較為精準(zhǔn)的數(shù)字方法，即DFT，進(jìn)行譜分析，在快速傅氏變換FFT出現(xiàn)以前是不切實際的。由于DFT的計算量太大，即使運用計算機也很難對問題進(jìn)行實時的有效處理，所以DFT并沒有得到真正的應(yīng)用。直到1965年庫利和圖基J.W.Tukey首次發(fā)現(xiàn)DFT的一種快速算法

19、，局面才發(fā)生根本性的變化。繼庫利和圖基算法出來之后，桑德G.Sander等快速算法也相繼出現(xiàn)，又經(jīng)過其他學(xué)者一步步改良，很快就出現(xiàn)了通用型的快速傅里葉變換，簡稱FFT?？焖俑道锶~變換Fast Fourier Transform，F(xiàn)FT并非與離散傅里葉變換完全不同的另一種變換，而是為了減少DFT計算次數(shù)而誕生的一種快速、有效的算法。應(yīng)當(dāng)指出的是，也是因為當(dāng)時電子數(shù)字計算機的“落后條件也促成了這個算法的提出。它使得DFT的運算量大大的縮小簡化，它推動了近30年來信號處理技術(shù)止步不前的前進(jìn)開展，成為了數(shù)字信號處理應(yīng)用領(lǐng)域里強有力的工具，為DFT乃至數(shù)字信號處理技術(shù)的實際應(yīng)用創(chuàng)造了良好的條件，從而使D

20、FT在實際使用中得以廣泛的應(yīng)用2。數(shù)字信號處理器DSP，是一種可編程的高性能處理器。近年來開展尤為迅速，它不僅應(yīng)用于數(shù)字信號處理方面，而且在圖像處理、語音處理、通信等領(lǐng)域得到廣泛的應(yīng)用。之前通用的微處理器在運算速度上已經(jīng)很難適應(yīng)信號實時處理的高要求。DSP處理器中集成了高速的乘法硬件，能快速、準(zhǔn)確地進(jìn)行大量數(shù)據(jù)的乘法以及加法的運算。數(shù)字信號處理區(qū)別于普通的科學(xué)計算與分析，它強調(diào)運算的實時性。除了需要普通微處理器所強調(diào)的高速運算和控制能力之外，鑒于實時數(shù)字信號處理的特點，在處理器結(jié)構(gòu)、指令系統(tǒng)、指令流程上做了很大程度上的改良。1. 2 課題研究的意義如上所述，基于對DSP的快速傅里葉變換算法的研

21、究，從而使FFT算法能夠有效地在DSP芯片上實現(xiàn)。DSP芯片的出現(xiàn)，使FFT的實現(xiàn)更加方便。多數(shù)的DSP芯片都能夠在一個指令周期內(nèi)完成一次乘法和加法，并且提供了專門的FFT指令，完成一次指令的周期只需10ns，使得FFT算法在DSP芯片上實現(xiàn)的速度更加快速。快速傅里葉變換為頻譜分析、卷積、相關(guān)數(shù)字濾波器設(shè)計與實現(xiàn)與功率譜計算、傳遞函數(shù)建模、圖像處理等，提供了快速有效的運算方法。FFT技術(shù)應(yīng)用DSP芯片，從而可以提供使調(diào)制、解調(diào)、壓縮、解壓縮的數(shù)據(jù)傳輸更為高效的信號處理解決方案，因而廣泛應(yīng)用于雷達(dá)、圖像處理、通信、生物醫(yī)學(xué)和聲納領(lǐng)域。2.快速傅里葉變換原理及性質(zhì) 數(shù)字信號中的傅里葉變換,通常是采

22、用離散型傅里葉變換(DFT)。DFT 存在的缺點就是計算量太大,不易進(jìn)行實時處理。比方，計算一個N 點的DFT ,一般需要次復(fù)數(shù)乘法和N(N-1)次復(fù)數(shù)加法運算.因此,當(dāng)N較大或要求對信號進(jìn)行實時處理時,往往很難實現(xiàn)到達(dá)所需的運算速度。1965年,J.W.Cooly和J.W.Tukey發(fā)現(xiàn)了DFT的一種快速算法,經(jīng)過后來學(xué)者的進(jìn)一步改良, 很快便形成了一套高效的運算方法,即現(xiàn)在通用的快速傅里葉變換, 簡稱FFT( The Fast Fourier Transform)。快速傅里葉變換的實質(zhì)是利用式(3-1)中的權(quán)函數(shù)的對稱性和周期性,把N點DFT進(jìn)行一系列分解和組合,使整個DFT的計算過程變成

23、一系列疊代運算過程,使DFT的運算量大大簡化,為DFT及數(shù)字信號的實時處理和應(yīng)用創(chuàng)造了非常良好的條件3。2. 1 快速傅里葉變換原理快速傅里葉變換原理：1. 將長序列DFT分解為短序列的DFT2. 利用旋轉(zhuǎn)因子的對稱性、周期性、可約性。將時域序列逐次分解為一組子序列，依據(jù)旋轉(zhuǎn)因子的特性，由子序列的DFT來實現(xiàn)整個序列的DFT4。其中：快速傅里葉變換分為兩種，分為基2時間抽取算法和基2頻率抽取算法基2-時間抽取(Decimation in time)FFT算法其中:r=0,1,2 2-1基2-頻率抽取(Decimation in frequency)FFT算法 2-22. 2 快速傅里葉變換的優(yōu)

24、越性設(shè)為項的復(fù)數(shù)序列，依據(jù)DFT變換，任一的計算都需要有次復(fù)數(shù)乘法和次復(fù)數(shù)加法，而且一次復(fù)數(shù)乘法等同于四次實數(shù)乘法和兩次實數(shù)加法，同樣的，一次復(fù)數(shù)加法等同于兩次實數(shù)加法，即使我們把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運算四次實數(shù)乘法和四次實數(shù)加法，那么求出項復(fù)數(shù)序列的, 即N點DFT變換大約就需要次運算。當(dāng)點甚至更多的時候，需要N2=1048576次運算。在FFT中，利用WN的對稱性和周期性，把一個N項序列設(shè),為正整數(shù)，分為兩個項的子序列，而且每個點的DFT變換需要次運算，再運用N次運算把兩個點的DFT 變換重新組合成一個N點的DFT變換。如此變換以后，總的運算次數(shù)就變成了。承接上面的例子，

25、當(dāng)時，總的運算次數(shù)就變成了525312次，這樣看來，節(jié)省了大約50%的運算量。而如果我們將這種“一分為二的思想不斷進(jìn)行下去，直到分成兩兩一組的DFT運算單元，那么N點的 DFT變換就只需要次的運算，在1024點時，運算量僅有10240次，是先前的直接算法的1%，點數(shù)越多，運算量的節(jié)約就越大，這就是 FFT的優(yōu)越性.當(dāng)然，F(xiàn)FT提高了運算速度,但是,也對參與運算的樣本序列作出了限制,即要求樣本數(shù)為2N點.離散傅里葉變換DFT那么無上述限制5。2. 3 快速傅里葉變換的意義 傅立葉變換的物理意義：傅立葉變換是數(shù)字信號處理技術(shù)領(lǐng)域一項很重要的算法。要知道傅立葉變換算法的意義，首先要了解傅立葉變換原理

26、的意義。傅立葉變換原理說明：任何連續(xù)測量的時序或信號，都能夠表示成為不同頻率的正弦波信號的無限疊加。而利用該原理而創(chuàng)立的傅立葉變換算法那么利用直接能測量到的原始信號，并以累加方式來計算該信號中不同正弦波信號的頻率、相位和振幅。與傅立葉變換算法對應(yīng)的是反傅立葉變換算法。該反變換從本質(zhì)上說也就是一種累加處理，這樣便可以將單獨改變的正弦波信號轉(zhuǎn)換成一個信號。因此，也可以說，傅立葉變換將原來難以處理的時域信號轉(zhuǎn)換成了易于分析的頻域信號信號的頻譜，我們可以利用一些專業(yè)工具對這些頻域信號進(jìn)行加工、處理。最后還可以利用傅立葉反變換將這些頻域信號轉(zhuǎn)換成原來的時域信號。從現(xiàn)代數(shù)學(xué)的眼光來看，傅里葉變換其實就是一

27、種特殊的積分變換。它能夠?qū)M足一定條件下的某個函數(shù)表示成為正弦基函數(shù)的線性組合或者積分形式。在不同的研究領(lǐng)域里，傅里葉變換具有多種形式各異的變體形式，如連續(xù)傅里葉變換和離散傅里葉變換。在數(shù)學(xué)領(lǐng)域，盡管最初傅立葉分析是作為熱過程的解析分析的工具，但是其思想方法仍然具有典型的復(fù)原論和分析主義的特征。任意的函數(shù)通過一定的分解，都能夠表示為正弦函數(shù)的線性組合的形式，而正弦函數(shù)在物理上是被充分研究而相對簡單的函數(shù)類：1. 傅立葉變換是線性算子,假設(shè)賦予適當(dāng)?shù)姆稊?shù),它還是酉算子;2. 傅立葉變換的逆變換容易求出,而且形式與正變換非常類似;3. 正弦基函數(shù)是微分運算的本征函數(shù),從而使得線性微分方程的求解可以

28、轉(zhuǎn)化為常系數(shù)的代數(shù)方程的求解.在線性時不變雜的卷積運算為簡單的乘積運算,從而提供了計算卷積的一種簡單手段;4. 離散形式的傅立葉的物理系統(tǒng)內(nèi),頻率是個不變的性質(zhì),從而系統(tǒng)對于復(fù)雜鼓勵的響應(yīng)可以通過組合其對不同頻率正弦信號的響應(yīng)來獲取;5. 著名的卷積定理指出:傅立葉變換可以化復(fù)變換可以利用數(shù)字計算機快速的算出(其算法稱為快速傅立葉變換算法(FFT)。正是由于上述的良好性質(zhì),傅里葉變換在物理學(xué)、數(shù)論、組合數(shù)學(xué)、信號處理、概率、統(tǒng)計、密碼學(xué)、聲學(xué)、光學(xué)等領(lǐng)域都有著廣泛的應(yīng)用6?？焖俑道锶~變換的算法3.1 快速傅里葉變換算法 快速傅里葉變換FFT 是離散傅里葉變換DFT 的一種快速算法，只有FFT

29、才能在現(xiàn)實中有實際應(yīng)用的意義。 QUOTE (3-1)由(3-1)式可知，對每一個n，計算X()須作N次復(fù)數(shù)乘法及N-1次復(fù)數(shù)加法，要完成這組變換共需 QUOTE 次乘法及N(N-1)次復(fù)數(shù)加法。但以下介紹的快速傅里葉變換的算法，可大大減少運算次數(shù)，提高工作效率。當(dāng)時，n和k可用二進(jìn)制數(shù)表示： QUOTE (3-2) 3-3又記,那么3-1式可改寫為 3-4式中： (3-5)因為所以3-2可改成 3-6 (3-7)那么式3-7即為式3-6的分解形式。將初始數(shù)據(jù)代入式3-7的第一個等式，可得每一組計算數(shù)據(jù)，一般將痗L-1組計算數(shù)據(jù)代入式3-7的第L個等式，計算后可得第L組計算數(shù)據(jù)L，計算公式也可

30、表示為 = 3-8式中 3-9 根據(jù)式3-8，第L個數(shù)組中每個 的計算只依賴于上一個數(shù)組的兩個數(shù)據(jù)這兩個數(shù)據(jù)的標(biāo)號相差，即，而且這兩個數(shù)據(jù)只用于計算第L個數(shù)組中標(biāo)號的數(shù)據(jù)等號右端為二進(jìn)制數(shù)。當(dāng)分別取和時，分別有。因此，用上一組的兩個數(shù)據(jù)計算所得的兩個新數(shù)據(jù)仍可儲存在原來位置，計算過程中只需要N個存儲器。將與稱為第L個數(shù)組中的對偶結(jié)點對。計算每個對偶結(jié)點對只需一次乘法，事實上由式3-8可得 3-10式中： ；別為式3-9中取，時對應(yīng)的P值。因，于是對偶結(jié)點的有如下關(guān)系： ,因此式3-8可表示為 3-11 P的求法：在中，i寫成二進(jìn)制數(shù)右移位，就成為顛倒位序得式3-7中，前面的r個等式，每個等式均

31、對應(yīng)一組數(shù)據(jù)進(jìn)行計算，每組數(shù)據(jù)都有N/對結(jié)點，根據(jù)式3-11，每對結(jié)點只需作次乘法和次加法，因此，每組數(shù)據(jù)只需N/2次乘法和N次加法，因而完成r組數(shù)據(jù)的計算共需Nr/2次乘法和Nr次加法。3. 2 Cooley-Tukey FFT算法的核心是將一層運算映射為二層運算。作點時，假設(shè)不是素數(shù)，那么可分解為，那么由的 3-12通過映射： 3-13可得到 而，可化簡為 3-14從而式3-12轉(zhuǎn)化為 3-15其中。以點為例，映射方式為：，那么計算流圖如圖3-1所示。 n1 k2f0 0 W0 0 F0f4 1 W0 1 F5f8 2 W0 2 F10f12 3 W0 3 F15f16 4 W0 0 F1

32、f1 0 W1 1 F6f5 1 W2 2 F11f9 2 W3 3 F16f13 3 f17 4 W0 0 F2 W2 1 F7f2 0 W4 2 F12f6 1 W6 3 F17f10 2f14 3 W0 0 F3f18 4 W3 1 F8 W6 2 F13f3 0 W9 3 F18f7 1f11 2 W0 0 F4f15 3 W4 1 F9f19 4 W8 2 F14 W12 3 F19k1=0n2=0n2=1n2=2n2=3k1=1k1=2k1=3k1=4圖3-1 Cooley-Tukey 20 點FFT算法3. 3 Rader-Brenner FFT算法Rader-Brenner 算

33、法是類似于 Cooley-Tukey 算法，但是采用的旋轉(zhuǎn)因子都是純虛數(shù)，以增加加法運算和降低了數(shù)值穩(wěn)定性為代價減少了乘法運算。這方法之后被split-radix variant of Cooley-Tukey所取代，與Rader-Brenner算法相比，有一樣多的乘法量，卻有較少的加法量，且不犧牲數(shù)值的準(zhǔn)確性7。 Bruun以及QFT算法是不斷的把DFT分成許多較小的DFT運算。(Rader-Brenner以及QFT算法是為了2的指數(shù)所設(shè)計的算法，但依然可以適用在可分解的整數(shù)上。Bruun算法那么可以運用在可被分成偶數(shù)個運算的數(shù)字)。尤其是Bruun算法，把FFT看成是 ，并把它分解成 與

34、的形式。 另一個從多項式觀點的快速傅立葉變換法是Winograd 算法。此算法把 分 解成cyclotomic多項式，而這些多項式的系數(shù)通常為1，0，-1。 這樣只需要很少的乘法量(如果有需要的話)，所以winograd是可以得到最少乘法量的快速傅立葉算法，對于較小的數(shù)字，可以找出有效率的算方式。更精確地說，winograd算法讓DFT可以用2K點的DFT來簡化，但減少乘法量的同時，也增加了非常多的加法量。Winograd也可以利用剩余值定理來簡化DFT。 Rader算法提出了利用點數(shù)為N(N為質(zhì)數(shù))的DFT進(jìn)行長度為N-1的盤旋折積來表示原本的DFT，如此就可利用折積用一對根本的FFT來計算

35、 DFT。另一個prime-size的FFT算法為chirp-Z算法。此法也是將DFT用折積來表示，此法與Rader算法相比，能運用在更一般的轉(zhuǎn)換 上，其轉(zhuǎn)換的根底為Z轉(zhuǎn)換8。3.4 Goertsel 算法如前所述, 點時域序列的離散付里葉變換式為， 3-16這點頻域序列是同時被算出的，不可能只計算其中某一個或幾個指定點。Goetzel 算法是為了解決這個問題而提出的。這個算法把離散付里葉變換看作一組濾波器，將輸入端的時域序列與其中一個濾波器的沖激響應(yīng)序列進(jìn)行卷積運算，求濾波器的輸出序列，即得序列的一點。這種算法利用旋轉(zhuǎn)因子的周期性，使DFT運算化為線性濾波運算9。 由于 故式3-16可化為

36、3-17定義序列為 3-18可見是由兩個序列卷積而得到的序列。 3-19其中，是輸入的點序列，另一個序列被看作濾波器的沖激響應(yīng)序列。 3-20比照式(3-17和式(3-18，可知：按式3-19進(jìn)行卷積運算，當(dāng)時，濾波器的輸出就是： 3-21對式(3-20)進(jìn)行Z變換，可得濾波器的系統(tǒng)函數(shù) 3-22這是一個一階系統(tǒng)。圖3-2示出這個系統(tǒng)的信號流圖，相應(yīng)的差分方程為 ， (3-23) 按照此式進(jìn)行遞推運算，到了 時刻，即可依據(jù)式3-21得到。 按照式(3-22)進(jìn)行運算時，可先算好旋轉(zhuǎn)因子，儲存起來。每次遞推包含一次復(fù)數(shù)乘法。按式(3-16)直接計算點離散付里葉變換,需要次實數(shù)乘法和次實數(shù)加法。按

37、照上述Goertzel算法，所需的實數(shù)乘法和實數(shù)加法都是次。所以當(dāng)不大時，上述算法的效率稍差10。下面介紹改良的Goertzel 算法，這種算法所需的實數(shù)乘法次數(shù)約為直接方法的一半。圖3-2 用一階系統(tǒng)實現(xiàn)Goertzel 算法 圖 3-3 用二階系統(tǒng)實現(xiàn)Goert算法把式3-22的分子和分母都乘上因子，就得到第個濾波器的系統(tǒng)函數(shù)為 3-24與此相應(yīng)的信號流圖示于圖3-3。由式3-24)可見，濾波器是一個二階系統(tǒng)，有一對復(fù)數(shù)共軛極點和一個復(fù)數(shù)零點。為了便于運算，在圖3-3所示的流圖中，設(shè)立狀態(tài)變量 和。按照圖3-3計算時，步驟有二，即： 1.實現(xiàn)一對復(fù)數(shù)極點輸入點依次取 ，進(jìn)行遞推運算。每次運

38、算中，更新狀態(tài)變量和。作次迭代所需的計算量是次實數(shù)乘法和次實數(shù)加法。 2.實現(xiàn)復(fù)數(shù)零點。是一個點序列， 。在點上。計算狀態(tài)變量和。這時，按照圖3-2算出濾波器的輸出，此即。所需的計算量是4次實數(shù)乘法和次實數(shù)加法11。 綜上所述，計算一點需要進(jìn)行次實數(shù)乘法和次實數(shù)加法。這種算法要求的乘法次數(shù)約為直接算法的一半。在這種較為有效的方案中，仍具有這樣的優(yōu)點，即必須計算和存儲的系數(shù)只有和。還要說明圖3-3所示的算法的另一個優(yōu)點。當(dāng)輸入序列為實序列時，離散付里葉變換序列是對稱的，即。容易證明，圖3-3的網(wǎng)絡(luò)形式在計算時和計算時具有完全相同的極點，但前者的零點系數(shù)與后者的零點系數(shù)成復(fù)共軛關(guān)系。由于零點僅在最

39、后的迭代中實現(xiàn)，所以諸極點要求的次乘法和 次加法可以用來計算離散付里葉變換的兩個值。因此，假設(shè)用Goertzel 算法計算離散付里葉變換的所有個點的值，需要的乘法次數(shù)近似為，加法次數(shù)近似為。然而，它同直接計算離散付里葉變換一樣，計算量仍然正比于。4.快速傅里葉變換在信號處理中的理論應(yīng)用4.1 連續(xù)時間信號的快速傅里葉變換設(shè)是連續(xù)時間信號，并假設(shè)時，那么其傅里葉變換由下式給出： 4-1 令是一固定的正實數(shù)，是一個固定的正整數(shù)。當(dāng)時，利用FFT算法可計算。一個固定的時間間隔，選擇讓T足夠小，使得每一個T秒的間隔內(nèi)，的變化很小，那么式中積分可近似為 4-2假設(shè)足夠大，對于所有的整數(shù)，幅值很小，那么式

40、4-2變?yōu)?4-3當(dāng)時，式4-2兩邊的值為 4-4其中代表抽樣信號的點。最后令，那么上式變?yōu)?4-5首先用FFT算法求出，然后可用上式求出時的。應(yīng)該強調(diào)的是，式4-3只是一個近似表示，計算得到的只是一個近似值。通過取更小的抽樣間隔，或者增加點數(shù)，可以得到更精確的值。如果時，幅度譜很小，對應(yīng)于奈奎斯特抽樣頻率，抽樣間隔選擇比擬適宜。如果信號只在時間區(qū)間內(nèi)存在，可以通過對時的抽樣信號補零，使足夠大12。將連續(xù)時間傅立葉變換進(jìn)行數(shù)字近似，用函數(shù)fft快速傅立葉算法高效地計算這個近似值。很多信號都能用4-1式連續(xù)時間傅立葉變換CTFT來表示。利用MATLAB可以計算CTFT積分的數(shù)值近似。利用在密集的

41、等間隔t的樣本上的求和來近似這個積分，就可以用函數(shù)fft高效地計算這個近似值。所用的近似式是根據(jù)積分的定義得到的，即 4-6對于一般信號，在足夠小的下，上式右邊的和式是對于CTFT積分的一個好的近似。假設(shè)信號對于和為零，那么這個近似式就能寫成 4-7式中，N為一整數(shù)?？梢岳煤瘮?shù)fft對一組離散的頻率計算上式中的和式。如果N個樣本是存在向量x內(nèi)的話，那么調(diào)用函數(shù)X=tau*fft(x)就可以計算出 4-8式中 以及N假設(shè)為偶數(shù)。為了計算高效，fft在負(fù)的頻率樣本之前先產(chǎn)生正頻率樣本。為了將頻率樣本置于上升的順序，能用函數(shù)fftshift。為了將存入X中的的樣本排列成使就是對于，在上求得的CTF

42、T,可用X=fftshift(tau*fft(x)。例4-1 利用FFT計算傅里葉變換如圖4-1所示的信號其傅里葉變換為：利用下面的命令，可得到的近似值和準(zhǔn)確值。 圖4-1 連續(xù)時間信號x(t)N=input(Input N:);T=input(Input T:);%計算X(w)近似值t=0:T:2;x=t-1 zeros(1,N-length(t);X=fft(x);gamma=2*pi/(N*T);k=0:10/gamma;Xapp=(1-exp(-i*k*gamma*T)/(i*k*gamma)*X;%計算真實值X(w)w=0.05:0.05:10;Xact=exp(-i*w)*2*i.

43、*(w.*cos(w)-sin(w)./(w.*w);plot(k*gamma,abs(Xapp(1:length(k),o,w,abs(Xact);legend(近似值,真實值);xlabel(頻率(rad/s);ylabel(|X|)運行程序后輸入N=128，T=0.1，此時，得到實際的和近似的傅里葉變換的幅度譜如圖4-2所示，此時近似值已經(jīng)相當(dāng)準(zhǔn)確。通過增加NT可以增加更多的細(xì)節(jié)，減少T使得到的值更精確。再次運行程序后輸入N=512，T=0.05，此時，得到實際的和近似的傅里葉變換的幅度譜如圖4-3所示。圖4-2 N=128，T=0.1時的幅度譜 圖4-3 N=512，T=0.05時的幅

44、度譜4.2 FFT計算離散信號的線性卷積兩個離散時間信號與，取，對和右端補零，使得 4-9利用FFT算法可以求得和的L點DFT，分別是和，利用DTFT卷積性質(zhì)，卷積等于乘積的L點DFT反變換，這也可以通過FFT算法得到。例4-2 利用FFT計算線性卷積，其中為單位階躍序列，信號如圖4-4所示。由于當(dāng)時，很小，故可以取為17；N取10，。利用下面的Matlab命令，可得到、的卷積圖形如圖4-4所示。subplot(3,1,1);n=0:16;x=0.8.n;stem(n,x);xlabel(n);ylabel(xn);subplot(3,1,2);n=0:15;y=ones(1,10) zero

45、s(1,6); stem(n,y);xlabel(n);ylabel(yn)subplot(3,1,3);L=26;n=0:L-1;X=fft(x,L);Y=fft(y,L);Z=X.*Y;z=ifft(Z,L);stem(n,z);xlabel(n);ylabel(zn)圖4-4 信號xn、yn及其卷積zn=xn*yn利用下面的Matlab命令，可得到信號xn、yn的幅度譜與相位譜如圖4-5所示。subplot(2,2,1);L=26;k=0:L-1;n=0:16;x=0.8.n;X=fft(x,L);stem(k,abs(X);axis(0 25 0 5);xlabel(k);ylabel

46、(|Xk|)subplot(2,2,2);stem(k,angle(X);axis(0 25 -1 1);xlabel(k);ylabel(Angle(Xk)(弧度)subplot(2,2,3);y=ones(1,10);Y=fft(y,L);stem(k,abs(Y);axis(0 25 0 10);xlabel(k);ylabel(|Yk|)subplot(2,2,4);stem(k,angle(Y);axis(0 25 -3 3);xlabel(k);ylabel(Angle(Yk)(弧度)圖4-5 信號xn、yn的幅度譜與相位譜4.3 FFT進(jìn)行離散信號壓縮利用FFT算法對離散信號進(jìn)行

47、壓縮的步驟如下：1通過采樣將信號離散化；2對離散化信號進(jìn)行傅里葉變換；3對變換后的系數(shù)進(jìn)行處理，將絕對值小于某一閾值的系數(shù)置為0，保存剩余的系數(shù)；4利用IFFT算法對處理后的信號進(jìn)行逆傅里葉變換13。 例4-3 對單位區(qū)間上的以下連續(xù)信號以采樣頻率進(jìn)行采樣，將其離散化為個采樣值用FFT分解信號，對信號進(jìn)行小波壓縮，然后重構(gòu)信號。令絕對值最小的80%系數(shù)為0，得到重構(gòu)信號圖形如圖4-6a)所示，均方差為0.0429，相對誤差為0.0449；令絕對值最小的90%系數(shù)為0，得到重構(gòu)信號圖形如圖4-6b)所示，均方差為0.0610，相對誤差為0.0638。 a) 絕對值最小的80%系數(shù)為0的重構(gòu)信號F

48、FT b) 絕對值最小的90%系數(shù)為0的重構(gòu)信號FFT圖4-6 用FFT壓縮后的重構(gòu)信號相關(guān)Matlab程序如下:function wc=compress(w,r)%壓縮函數(shù)compress.m%輸入信號數(shù)據(jù)w,壓縮率r%輸出壓縮后的信號數(shù)據(jù)if(r1) error(r 應(yīng)該介于0和1之間!);end;N=length(w);Nr=floor(N*r);ww=sort(abs(w);tol=abs(ww(Nr+1);wc=(abs(w)=tol).*w; function unbiased_variance,error=fftcomp(t,y,r)%利用FFT做離散信號壓縮%輸入時間t,原信號

49、y,以及壓縮率rif(r1) error(r 應(yīng)該介于0和1之間!);end;fy=fft(y);fyc=compress(fy,r); %調(diào)用壓縮函數(shù)compress.myc=ifft(fyc);plot(t,y,r,t,yc,b);legend(原信號,重構(gòu)信號);unbiased_variance=norm(y-yc)/sqrt(length(t);error=norm(y-yc)/norm(y);輸入以下Matlab命令：t=(0:255)/256;f=t+cos(4*pi*t)+1/2*sin(8*pi*t);unbiased_variance,error=fftcomp(t,f,0

50、.8) unbiased_variance = 0.0429error =0.0449如果用Harr尺度函數(shù)和Harr小波分解信號，對信號進(jìn)行小波壓縮，然后重構(gòu)信號。令絕對值最小的80%系數(shù)為0，得到重構(gòu)信號圖形如圖4-7a)所示，均方差為0.0584，相對誤差為0.0611；令絕對值最小的90%系數(shù)為0，得到重構(gòu)信號圖形如圖4-7b)所示，均方差為0.1136，相對誤差為0.1190。 a) 絕對值最小的80%系數(shù)為0的重構(gòu)信號Harr b) 絕對值最小的90%系數(shù)為0的重構(gòu)信號Harr圖4-7 用Harr小波壓縮后的重構(gòu)信號相關(guān)Matlab程序如下function unbiased_var

51、iance,error=daubcomp(t,y,n,r)%利用Daubechies系列小波做離散信號壓縮%輸入時間t,原信號y,分解層數(shù)n,以及壓縮率r%輸出原信號和壓縮后重構(gòu)信號的圖像,以及重構(gòu)均方差和相對l2誤差if(r1) error(r應(yīng)該介于0和1之間!);end;c,l=wavedec(y,n,db1);cc=compress(c,r); %調(diào)用壓縮函數(shù)compress.myc=waverec(cc,l,db1);plot(t,y,r,t,yc,b);legend(原信號,重構(gòu)信號);unbiased_variance=norm(y-yc)/sqrt(length(t);erro

52、r=norm(y-yc)/norm(y);輸入以下Matlab命令：=(0:255)/256;f=t+cos(4*pi*t)+1/2*sin(8*pi*t);unbiased_variance,error=daubcomp(t,f,8,0.8) unbiased_variance = 0.0584error = 0.0611結(jié)論：在信號沒有突變、快變化或者大致上具有周期性的信號，用FFT可以處理得很好甚至比小波還要好。4. 4 利用FFT對離散信號進(jìn)行濾波利用FFT算法對信號進(jìn)行濾波的步驟如下：1通過采樣將信號離散化；2對離散化信號進(jìn)行傅里葉變換；3對變換后的系數(shù)進(jìn)行處理，將絕對值大于某一閾值

53、的系數(shù)置為0，保存剩余的系數(shù)；4利用IFFT算法對處理后的信號進(jìn)行逆傅里葉變換14。例4-4 對被白噪聲污染的信進(jìn)行頻譜分析，從中鑒別出有用的信號。要求：將信號的幅度換算成實際的幅度，信號的頻率換算成實際的頻率。相關(guān)Matlab程序如下fs=1000;%采樣頻率N=512;%數(shù)據(jù)點數(shù)n=0:N-1;randn(1,N);t=0:1/fs:(N-1)/fs;%采樣時間序列f0=100;%信號頻率x=2+3*cos(100*pi*t-pi/6)+(3/2)*cos(150*pi*t+pi/2);subplot(3,1,1);plot(t,x);xlabel(t);ylabel(sin(2+3*co

54、s(100*pi*t-pi/6)+(3/2)*cos(150*pi*t+pi/2);title(時域信號);Y=fft(x,N);%對信號進(jìn)行FFT變換magY=abs(Y);%求得FFT變換后的幅度angY=angle(Y)*180/pi;%求得FFT變換后的相位f=n*fs/N;%頻率序列subplot(3,1,2);plot(f,magY);%畫出幅頻響應(yīng)xlabel(f);ylabel(幅度);title(N=512);grid;subplot(3,1,3);plot(f,angY);%畫出相頻響應(yīng)xlabel(f);ylabel(相位)title(N=512);grid;圖4-8 濾

55、波信號的相位，幅度4.5 利用FFT提取離散信號中的最強正弦分量這里最強是指在信號中某個正弦分量的振幅遠(yuǎn)大于其它正弦分量的振幅。可以對求點來確定信號中是否有最強的正弦分量。如果信號是連續(xù)時間形式的，首先還要對其進(jìn)行抽樣，得到離散時間形式的信號，根據(jù)Nyquist定理，抽樣間隔應(yīng)滿，其中是中的最大頻率分量。要判斷信號中是否包含最強正弦分量，采樣數(shù)據(jù)至少要包含該分量一個完整周期的數(shù)據(jù)15。例4-5 太陽耀斑數(shù)據(jù)的分析太陽耀斑活動的周期是11年，這個事實可以通過提取耀斑數(shù)據(jù)的最強正弦下載后的數(shù)據(jù)存放在文件“monthssn.dat中，里面有四列數(shù)據(jù)，第一年是日期，第三列是太陽耀斑的平均數(shù)，第四列平滑

56、后太陽耀斑的平均數(shù)，可以得到從1749年到當(dāng)前年月2006年4月的耀斑數(shù)據(jù)。本次分析選擇第三列1981年1月作為開始日期，2005年12月作為結(jié)束日期，共25年300個月份的數(shù)據(jù)。為此先把相關(guān)數(shù)據(jù)復(fù)制到Excel表格的第一列中，然后保存到Matlab所在目錄下，并命名為“sunspotdata.csv。然后輸入以下命令，得到耀斑曲線如圖9所示16。spd=csvread(sunspotdata.csv,0,0,0 0 299 0);plot(spd);grid;xlabel(月數(shù));ylabel(耀斑平均數(shù));axis(0 300 0 200)圖4-9 1981年1月至2005年12月太陽耀斑

57、的平均數(shù)由上圖可見，太陽耀斑的活動確實具有周期性，但周期的準(zhǔn)確值不明顯?？梢酝ㄟ^數(shù)第一個峰值和第二個峰值之間的月份來估計周期的值。查驗表中的數(shù)據(jù)得，第一個峰值為200.3，出現(xiàn)在第116個月1990年8月，第二個峰值為170.1，出現(xiàn)在第235個月2000年7月，所以周期是235-116=119月，和實際值132月比擬接近。下面利用來分析。首先，從圖4-9中可以看出從到整個區(qū)間的平均值不為0，為了更方便地分析，需要減去該均值，得到結(jié)果如下： 4-12然后對進(jìn)行傅里葉變換，得到。在Matlab中輸入以下命令，得到的幅度譜的圖形如圖10所示。x=spd-sum(spd)/300;X=fft(x);

58、k=0:299;plot(k,abs(X);grid;xlabel(k);ylabel(|Xk|)圖4-10 的幅度譜由圖4-10可見，的幅度譜中有一個清晰的尖峰，這就證實中確實包含一個最強正弦分量。為了確定尖峰所對應(yīng)的頻率，用火柴棒圖重畫當(dāng)時的圖形，在Matlab中輸入以下命令，得到圖形如圖4-11所示。k=0:10;X=X(1:11);stem(k,abs(X);xlabel(k);ylabel(|Xk|)圖4-11 當(dāng)時的火柴棒圖可以看出上圖中有兩個強譜分量，頻率分別為弧度/月和，周期分別為150月和100月。由于的數(shù)據(jù)長度不是其中強正弦分量的整數(shù)倍，譜分量在出現(xiàn)了泄露。要消除泄露，需要

59、使數(shù)據(jù)的長度正好是其中強正弦分量的周期太陽耀斑活動的周期，也即的整數(shù)倍。為此，重新取中從1至264之間的數(shù)據(jù)進(jìn)行分析，令 4-13然后對進(jìn)行傅里葉變換，得到。輸入以下命令，得到時的火柴棒圖如圖4-12所示。y=spd(1:264);z=y-sum(y)/264;Z=fft(z);k=0:10;Z=Z(1:11);stem(k,abs(Z);xlabel(k);ylabel(|Zk|)圖4-12 當(dāng)時的火柴棒圖注意到的峰值仍然在，但此時比其附近的值大得多，這說明沒有出現(xiàn)泄露，頻率為弧度/月的正弦分量就是或者中唯一的最強正弦分量。該頻率對應(yīng)周期月，正好等于11年。時的值主要是由于太陽耀斑數(shù)據(jù)中的噪

60、聲引起的。然而和其它值相比，、和的值相對較大，這說明除了周期為11年的最強分量，還包括其它正弦分量，此時太陽耀斑的活動并不是一個只包含單一頻率的純粹弦運動。5. 快速傅里葉變換在數(shù)字信號分析與處理的實際應(yīng)用5.1 快速傅里葉變換在喇曼光譜信號噪聲平滑中的應(yīng)用電探測系統(tǒng)是光信號的轉(zhuǎn)換、傳輸及處理的系統(tǒng). 系統(tǒng)的各個局部在工作時總會受到一些無用信號的干擾,給光譜峰的檢測判別及進(jìn)一步的數(shù)據(jù)處理帶來了不利因素.對光譜信號進(jìn)行數(shù)字濾波,以獲得更真實的光譜信息，顯得格外重要. 目前最為通用和有效的信號濾波處理方法是快速傅立葉變換方法.純水是一種較弱的喇曼散射介質(zhì),需要專用的喇曼散射光譜儀器才能獲得高信噪比