【正文】 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。它對傅氏變換的理論并沒有新的發(fā)現(xiàn)，但是對于在計算機(jī)系統(tǒng)或者說數(shù)字系統(tǒng)中應(yīng)用離散傅立葉變換，可以說是進(jìn)了一大步。 作者簽名： 日期： 年 月 日 導(dǎo)師簽名： 日期： 年 月 日 武漢工程大學(xué)畢業(yè)設(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）附錄（對論文支持必要時） ：理工類設(shè)計（論文）正文字?jǐn)?shù)不少于 1 萬字（不包括圖紙、程序清單等），文科類論文正文字?jǐn)?shù)不少于 萬字。本人完全意識到本聲明的法律后果由本人承擔(dān)。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)校可以采用影印、縮印、數(shù) 字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉績?nèi)容。 畢業(yè)設(shè)計 (論文 ) 題 目 快速傅里葉變換算法及其在信號處理中的應(yīng)用 專 業(yè) 班 級 學(xué) 號 姓 名 指 導(dǎo) 教 師 學(xué) 院 名 稱 武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。 作者簽名： 日 期： 武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。 ：任務(wù)書、開題報告、外文譯文、譯文原文（復(fù)印件）。 傅里葉變換的理論與方法在“數(shù)理方程”、“線性系統(tǒng)分析”、“信號處理、仿真”等很多學(xué)科領(lǐng)域都有著廣泛應(yīng)用 ,由于計算機(jī)只能處理有限長度的離散的序列 ,所以真正在計算機(jī)上運(yùn)算的是一種離散傅里葉變換 . 雖然傅里葉運(yùn)算在各方面計算中有著重要的作用，但是它的計算過于復(fù)雜，大量的計算對于系統(tǒng)的運(yùn)算負(fù)擔(dān)過于龐大，使得 一些對于耗電量少，運(yùn)算速度慢的系統(tǒng)對其敬而遠(yuǎn)之，然而，快速傅里葉變換的產(chǎn)生，使得傅里葉變換大為簡化，在不犧牲耗電量的條件下提高了系統(tǒng)的運(yùn)算速度，增強(qiáng)了系統(tǒng)的綜合能力，提高了運(yùn)算速度，因此快速傅里葉變換在生產(chǎn)和生活中都有著非常重要的作用，對于學(xué)習(xí)掌握都有著非常大的意義。 fast algorithm。它能夠?qū)M足一定條件的某個 函數(shù) 表示成為正弦基 函數(shù) 的線性組合或者積分。系統(tǒng)的速度不但取決于其本身的速度，而且還在相當(dāng)大的程度上取決于運(yùn)用的算法，算法運(yùn)算 量的大小直接影響到對設(shè)備的控制質(zhì)量。 在信號處理中，離散傅里葉變換（ Discrete Fourier Transform， DFT）是比較常用的變換方法之一，它在各種數(shù)字信號處理系統(tǒng)中扮演著及其重要的角色。武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 2 由于 DFT 的計算量太大，即使運(yùn)用計算機(jī)也很難對問題進(jìn)行實時的有效處理，所以 DFT 并沒有得到真正的應(yīng)用。應(yīng)當(dāng)指出的是，也是因為當(dāng)時電子數(shù)字計算機(jī)的“落后”條件也促成了這個算法的提出。之前通用的 微處理器在運(yùn)算速度上已經(jīng)很難適應(yīng)信號實時處理的高要求。 1. 2 課題研究的意義 如上所述，基于對 DSP的快速傅里葉變換算法的研究，從而使 FFT算法能夠有效地在 DSP芯片上實現(xiàn)。 FFT技術(shù)應(yīng)用 DSP芯片，從而可以提供使調(diào)制、解調(diào)、壓縮、解壓縮的數(shù)據(jù)傳輸更為高效的信號處理解決方案，因而廣泛應(yīng)用于雷達(dá)、圖像處理、通信、生物醫(yī)學(xué)和聲納領(lǐng)域。 1965 年 , 和 發(fā)現(xiàn)了 DFT 的一種快速算法 ,經(jīng)過后來學(xué)者的進(jìn)一步改進(jìn) , 很快便形成了一套高效的運(yùn)算方法 ,即現(xiàn)在通用的快速傅里葉變換 , 簡稱 FFT( The Fast Fourier Transform)。 其中：快速傅里葉變換分為兩種，分為基 2時間抽取算法和基 2 頻率抽取算法 基 2時間抽取 (Decimation in time)FFT 算法 ??? ?? ]12[ ]2[][ rx rxkx其中 :r=0,1,2? 12?N （ 21） 基 2頻率抽取 (Decimation in frequency)FFT 算法 ??? ?? ]12[ ]2[][ mX mXmX （ 22） 武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 4 2. 2 快速傅里葉變換的優(yōu)越性 設(shè)nx為N項的復(fù)數(shù)序列，依據(jù) DFT 變換，任一)(mx的計算都需要有N次復(fù)數(shù)乘法和（1?）次復(fù)數(shù)加法，而且一次復(fù)數(shù)乘法等同于四次實數(shù)乘法和兩次實數(shù)加法，同樣的，一次復(fù)數(shù)加法等同于兩次實數(shù)加法，即使我們把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運(yùn)算”（四次實數(shù)乘法和四次實數(shù)加法），那么求出N項復(fù)數(shù)序列的)(mx, 即 N 點(diǎn) DFT 變換大約就需要2N次運(yùn)算。承接上面的例子，當(dāng) 1024?時，總的運(yùn)算次數(shù)就變成了 525312 次，這樣看來，節(jié)省了大約 50%的運(yùn)算量。傅立葉變換原理表明：任何連續(xù)測量的時序或信號，都能夠表示成為不同頻率的正弦波信號的無限疊加。因此，也可以說，傅立葉變換將原來難以處理的時域信號轉(zhuǎn)換成了易于分析的頻域信號（信號的頻譜），我們可以利用一些專業(yè)工具對這些頻域信號進(jìn)行加工、處理。在不同的研究領(lǐng)域里，傅里葉變 換具有多種形式各異的變體形式，如連續(xù)傅里葉變換和離散傅里葉變換。3. 正弦基函數(shù)是微分運(yùn)算的本征函數(shù) ,從而使得線性微分方程的求解可以轉(zhuǎn)化為常系數(shù)的代數(shù)方程的求解 .在線性時不變雜的卷積運(yùn)算為簡單的乘積運(yùn)算 ,從而提供了計算卷積的一種簡單手段 。 武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 6 3. 快速傅里葉變換的算法 快速傅里 葉變換算法 快速傅里葉變換 FFT 是離散傅里葉變換 DFT 的一種快速算法，只有 FFT 才能在現(xiàn)實中有實際應(yīng)用的意義。 次乘法及 N(N1)次復(fù)數(shù)加法。將初始數(shù)據(jù)代入式（ 37）的第一個等式，可得每一組計算數(shù)據(jù)，一般將痗 L1 組計算數(shù)據(jù)代入式（ 37）的第 L個等式，計算后可得第 L 組計算數(shù)據(jù)（ L＝１，２，?，γ），計算公式也可表示為 1011 0 2 0 0 1 2 0( ) ( )rr r rkx n k k x k k k??? ? ?? ?121 2 0 0( 2 2 )rrrrn n n kW ????? ? ?= 1 0 1 2 1 2 0 1 0 1 2 1 2 0( 0 ) ( 0 ) Pl r r r l r r rx n n n k k k x n n n k k k W? ? ? ? ? ? ? ?? （ 38） 式中 1 2 11 2 02 2 2r r rllP n n n? ? ???? ? ? ? （ 39） 根據(jù)式（ 38），第 L 個數(shù)組中每個 1 2 0 1 2 0( ) ( )l l r r r rx k x n n n k k k? ? ? ?? 的計算只依賴于上一個數(shù)組的兩個數(shù)據(jù)這兩個數(shù) 據(jù)的標(biāo)號相差 12 / 2YlN? ? ，即/2lj i n?? ，而且這兩個數(shù)據(jù)只用于計算第 L個數(shù)組中標(biāo)號的數(shù)據(jù)（等號右端為二進(jìn)制數(shù)）。計算每個對偶結(jié)點(diǎn)對只需一次乘法，事實上由式（ 38）可得 11( ) ( ) [ ]2 pll lNx i x i i W?? ? ? 211( ) ( ) [ ]22 pl l lllNNx i x i x i W??? ? ? ? （ 310） 式中： lrlr nP ??? ??? 2...2 221 0n ； 0222 2...22 nnP lrlrlr ???? ???? 別為式（ 39）中 1?ln ?。?，１時對應(yīng)的 P值。 以 20 點(diǎn) FFT 為例， 1220, 5, 4N N N? ? ?，映射方式為： 124n n n??，125k k k?? ，則計算流圖如圖 31 所示。(RaderBrenner 以及 QFT 算法是為了 2 的指數(shù)所設(shè)計的算法，但依然可以適用在可分解的整數(shù)上。此算法把n1 k2 f[0] 0 W0 0 F[0] f[4] 1 W0 1 F[5] f[8] 2 W0 2 F[10] f[12] 3 W0 3 F[15] f[16] 4 W0 0 F[1] f[1] 0 W1 1 F[6] f[5] 1 W2 2 F[11] f[9] 2 W3 3 F[16] f[13] 3 f[17] 4 W0 0 F[2] W2 1 F[7] f[2] 0 W4 2 F[12] f[6] 1 W6 3 F[17] f[10] 2 f[14] 3 W0 0 F[3