快速傅里葉變換算法及其在信號處理中的應用畢業論文(已修改)

　

【正文】 武漢工程大學畢業設計(論文)說明書 畢業設計(論文) 題 目快速傅里葉變換算法及其在信號處理中的應用專 ?業? 班? 級學 ?? ? 號姓 ?名指 導 教 師學 院 名 稱畢業設計（論文）原創性聲明和使用授權說明原創性聲明本人鄭重承諾：所呈交的畢業設計（論文），是我個人在指導教師的指導下進行的研究工作及取得的成果。盡我所知，除文中特別加以標注和致謝的地方外，不包含其他人或組織已經發表或公布過的研究成果，也不包含我為獲得 及其它教育機構的學位或學歷而使用過的材料。對本研究提供過幫助和做出過貢獻的個人或集體，均已在文中作了明確的說明并表示了謝意。作 者 簽 名：　　 　 　　日　 期：　　 　 　　 指導教師簽名：　　 　 　　 日　　期：　　 　 　　 使用授權說明本人完全了解 大學關于收集、保存、使用畢業設計（論文）的規定，即：按照學校要求提交畢業設計（論文）的印刷本和電子版本；學校有權保存畢業設計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務；學?？梢圆捎糜坝?、縮印、數字化或其它復制手段保存論文；在不以贏利為目的前提下，學?？梢怨颊撐牡牟糠只蛉績热?。作者簽名：　　 　 　　 日　 期：　　 　 　　 學位論文原創性聲明本人鄭重聲明：所呈交的論文是本人在導師的指導下獨立進行研究所取得的研究成果。除了文中特別加以標注引用的內容外，本論文不包含任何其他個人或集體已經發表或撰寫的成果作品。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。本人完全意識到本聲明的法律后果由本人承擔。作者簽名： 日期： 年 月 日學位論文版權使用授權書本學位論文作者完全了解學校有關保留、使用學位論文的規定，同意學校保留并向國家有關部門或機構送交論文的復印件和電子版，允許論文被查閱和借閱。本人授權　　 　 　大學可以將本學位論文的全部或部分內容編入有關數據庫進行檢索，可以采用影印、縮印或掃描等復制手段保存和匯編本學位論文。涉密論文按學校規定處理。作者簽名： 日期： 年 月 日導師簽名： 日期： 年 月 日注 意 事 項（論文）的內容包括：1）封面（按教務處制定的標準封面格式制作）2）原創性聲明3）中文摘要（300字左右）、關鍵詞4）外文摘要、關鍵詞 5）目次頁（附件不統一編入）6）論文主體部分：引言（或緒論）、正文、結論7）參考文獻8）致謝9）附錄（對論文支持必要時）：理工類設計（論文）正文字數不少于1萬字（不包括圖紙、程序清單等）。：任務書、開題報告、外文譯文、譯文原文（復印件）。、圖表要求：1）文字通順，語言流暢，書寫字跡工整，打印字體及大小符合要求，無錯別字，不準請他人代寫2）工程設計類題目的圖紙，要求部分用尺規繪制，部分用計算機繪制，所有圖紙應符合國家技術標準規范。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準用徒手畫3）畢業論文須用A4單面打印，論文50頁以上的雙面打印4）圖表應繪制于無格子的頁面上5）軟件工程類課題應有程序清單，并提供電子文檔1）設計（論文）2）附件：按照任務書、開題報告、外文譯文、譯文原文（復印件）次序裝訂3）其它摘 要快速傅氏變換（FFT），是離散傅氏變換的快速算法，它是根據離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。它對傅氏變換的理論并沒有新的發現，但是對于在計算機系統或者說數字系統中應用離散傅立葉變換，可以說是進了一大步?！「道锶~變換的理論與方法在“數理方程”、“線性系統分析”、“信號處理、仿真”等很多學科領域都有著廣泛應用,由于計算機只能處理有限長度的離散的序列,所以真正在計算機上運算的是一種離散傅里葉變換.　雖然傅里葉運算在各方面計算中有著重要的作用，但是它的計算過于復雜，大量的計算對于系統的運算負擔過于龐大，使得一些對于耗電量少，運算速度慢的系統對其敬而遠之，然而，快速傅里葉變換的產生，使得傅里葉變換大為簡化，在不犧牲耗電量的條件下提高了系統的運算速度，增強了系統的綜合能力，提高了運算速度，因此快速傅里葉變換在生產和生活中都有著非常重要的作用，對于學習掌握都有著非常大的意義。 關鍵詞：快速傅氏變換；快速算法；簡化；廣泛應用AbstractFast Fourier Transform (FFT), is a discrete fast Fourier transform algorithm, which is based on the Discrete Fourier Transform of odd and even, false, false, and other characteristics of the Discrete Fourier Transform algorithms improvements obtained. Its Fourier transform theory has not found a new, but in the puter system or the application of digital systems Discrete Fourier Transform can be said to be a big step into. Fourier transform theory 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 puter can only handle a limited length of the sequence of discrete, so true On the puter39。s operation is a discrete Fourier transform. Fourier Although all aspects of puting in the calculation has an important role, but its calculation was too plicated, a lot of puting system for calculating the burden is too large for some Less power consumption, the slow speed of operation of its system at arm39。s length, however, 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 puting systems, and enhance the system The prehensive ability to improve the speed of operation, the Fast Fourier Transform in the production and life have a very important role in learning to master all have great significance.KeyWords：Fast Fourier Transform。 fast algorithm。 simplified。 widely usedII 目 錄摘要……..……………………….………………………………………………….IAbstract ………….…………… ……………………………………………………………II 選題背景 1 課題研究的意義 2 3 4 4 6 Cooley=Tukey FFT算法 8 RaderBrennr FFT算法 9 Goertsel 算法 10 13 17 19 22 24 29 31 33致謝 36參考文獻 37 1 緒論傅立葉變換在生產生活中的重要性非常突出，它將原本難以處理的時域信號相比比較容易地轉換成易于分析的頻域信號，我們可以利用一些專業工具對這些頻域信號進行處理、加工，使信號轉化為可以對其進行各種數學變換的數學公式，對其進行處理。最后還可以根據傅立葉反變換將這些頻域信號轉換成原來的時域信號，這是一種特殊的積分變換。它能夠將滿足一定條件的某個函數表示成為正弦基函數的線性組合或者積分。然而，它在運算上過于復雜，過于宏大的運算過程，對于一些相對簡單的低功耗處理器來說，難以自如應對，因此，快速傅里葉變換則顯出了它的優越性?？焖俑凳献儞Q（FFT），即離散傅氏變換的快速算法，它是根據離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的[1]。對于計算機處理信號方面上是一大進步。系統的速度不但取決于其本身的速度，而且還在相當大的程度上取決于運用的算法，算法運算量的大小直接影響到對設備的控制質量。通過傅立葉變換（DFT），運用測試軟件進行檢測，我們可以看出，快速傅里葉變換大大的提高了運算速度，它為各系統的設計方案提供了簡單算法，有著非常重要的意義。1. 1 選題背景近十多年來，數字信號處理技術同大規模集成電路、數字計算機等，都有了突飛猛進的發展，日新月異，早已成為了一門具有強大生命力的技術科學。因為它本身就具有一系列的優點，所以能夠有效地促進工程技術領域的技術改造和科學發展，應用領域也更加地廣泛、深入，越來越受到人們的重視。在信號處理中，離散傅里葉變換（Discrete Fourier Transform，DFT）是比較常用的變換方法之一，它在各種數字信號處理系統中扮演著及其重要的角色。由于離散傅里葉變換（DFT）而發現了頻率離散化，可以直接用它來分析信號的頻譜、計算濾波器的頻率響應、以及實現信號通過線系統的卷積運算等，因而在信號的譜分析等方面有著非常大的作用。傅里葉變換已經有一百多年的歷史了，我們熟知頻域分析往往比時域分析更優越，不僅簡單明了，而且易于分析較為復雜的信號。但需要用較為精準的數字方法，即DFT，進行譜分析，在快速傅氏變換（FFT）出現以前是不切實際的。由于DFT的計算量太大，即使運用計算機也很難對問題進行實時的有效處理，所以DFT并沒有得到真正的應用。直到1965年庫利（）和圖基（）首次發現DFT的一種快速算法，局面才發生根本性的變化。繼庫利和圖基算法出來之后，桑德（）等快速算法也相繼出現，又經過其他學者一步步改進，很快就出現了通用型的快速傅里葉變換，簡稱FFT?？焖俑道锶~變換（Fast Fourier Transform，FFT）并非與離散傅里葉變換完全不同的另一種變換，而是為了減少DFT計算次數而誕生的一種快速、有效的算法。應當指出的是，也是因為當時電子數字計算機的“落后”條件也促成了這個算法的提出。它使得DFT的運算量大大的縮小簡化，它推動了近30年來信號處理技術止步不前的前進發展，成為了數字信號處理應用領域里強有力的工具，為DFT乃至數字信號處理技術的實際應用創造了良好的條件，從而使DFT在實際使用中得以廣泛的應用[2]。數字信號處理器（DSP），是一種可編程的高性能處理器。近年來發展尤為迅速，它不僅應用于數字信號處理方面，而且在圖像處理、語音處理、通信等領域得到廣泛的應用。之前通用的微處理器在運算速度上已經很難適應信號實時處理的高要求。DSP處理器中集成了高速的乘法硬件，能快速、準確地