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