【正文】 X=fft(x)。Input T:39。 圖 41 連續(xù)時(shí)間信號(hào) x(t) N=input(39。為了計(jì)算高效， fft 在負(fù)的頻率樣本之前先產(chǎn)生正頻率樣本。所用的近似式是根據(jù)積分的定義得到的，即 ?? ????????? ? ? n njtj enxdtetx ?? ???? )(lim)( 0 （ 46） 對(duì)于一般信號(hào)，在足夠小的τ下，上式右邊的和式是對(duì)于 CTFT 積分的一個(gè)好的近似。 將連續(xù)時(shí)間傅立葉變換進(jìn)行數(shù)字近似，用函數(shù) fft（快速傅立葉算法）高效地計(jì)算這個(gè)近似值。 應(yīng)該強(qiáng)調(diào)的是，式（ 43）只是一個(gè)近似表示，計(jì)算得到的 ()X? 只是一個(gè)近似值。 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說明書 13 在信號(hào)處理 中 的理論應(yīng)用 連續(xù)時(shí)間信號(hào)的快速傅里葉變換 設(shè) ()xt 是連續(xù)時(shí)間信號(hào)，并假設(shè) 0t? 時(shí) () 0xt? ，則其傅里葉變換由下式給出： 0( ) ( ) itX x t e d t?? ? ?? ? （ 41） 令 ? 是一固定的正實(shí)數(shù)， N 是一個(gè)固定的正整數(shù)。容易證明，圖 33的網(wǎng)絡(luò)形式在計(jì)算 )( kNX ? 時(shí)和計(jì)算 )(kX 時(shí)具有完全相同的極點(diǎn)，但前者的零點(diǎn)系數(shù)與后者的零點(diǎn)系數(shù)成復(fù)共軛關(guān)系。這種算法要求的乘法次數(shù)約為直接算法的一半。計(jì)算狀態(tài)變量 u 和 v 。作 N 次迭代所需的計(jì)算量是 N2 次實(shí)數(shù)乘法和 N4 次實(shí)數(shù)加法。由式（ 324)可見，濾波器是一個(gè)二階系統(tǒng)，有一對(duì)復(fù)數(shù)共軛極點(diǎn)和一個(gè)復(fù)數(shù)零點(diǎn)。按照上述 Goertzel 算法，所需的實(shí)數(shù)乘法和實(shí)數(shù)加法都是 24N 次。圖 32示出這個(gè)系統(tǒng)的信號(hào)流圖，相應(yīng)的差分方程為 )()1()( nxnyWny kkNk ??? ? ， 0)1( ??y (323) 按照此式進(jìn)行遞推運(yùn)算，到了 Nn? 時(shí)刻，即可依據(jù)式（ 321）得到 )(kX 。這種算法利用旋轉(zhuǎn)因子 kNW 的周期性，使 DFT 運(yùn)算化為線性濾波運(yùn)算 [9]。此法也是將 DFT 用折積來表示，此法與 Rader 算法相比，能運(yùn)用在更一般的轉(zhuǎn)換 上，其轉(zhuǎn)換的基礎(chǔ)為 Z 轉(zhuǎn)換 [8]。更精確地說，winograd 算法讓 DFT 可以用 2K點(diǎn)的 DFT 來簡化，但減少乘法量的同時(shí)，也增加了非常多的加法量。尤其是 Bruun 算法，把 FFT 看成是 1?zN ，并把它分解成 1?zM 與 12 ?? zz MM a 的形式。這方法之后被 splitradix variant of CooleyTukey 所取代，與 RaderBrenner 算法相比，有一樣多的乘法量，卻有較少的加法量，且不犧牲數(shù)值的準(zhǔn)確性 [7]。 3. 2 CooleyTukey FFT 算法 FFT 的核心是將一層運(yùn)算映射為二層運(yùn)算。因此，用上一組的兩個(gè)數(shù)據(jù)計(jì)算所得的兩個(gè)新數(shù)據(jù)仍可儲(chǔ)存在原來位置，計(jì)算過程中只需要 N個(gè)存儲(chǔ)器。 當(dāng) 2rN? 時(shí)， n 和 k 可用二進(jìn)制數(shù)表示： 121 2 0 1 2 022rrr r r rn n n n n n n??? ? ? ?? ? ? ? ?錯(cuò)誤 ! 未 找 到 引 用 源 。12,1,0。5. 著名的卷積定理指出 :傅立葉變換可以化復(fù)變換可以利用數(shù)字計(jì)算機(jī)快速的算出 (其算法稱為快速傅立葉變換算法 (FFT))。 任意 的函數(shù)通過一定的分解，都能夠表示為正弦函數(shù)的線性組合的形式，而正弦函數(shù)在物理上是被充分研究而相對(duì)簡單的函數(shù)類： 1. 傅立葉變換是線性算子 ,若賦予適當(dāng)?shù)姆稊?shù) ,它還是酉算子 。 從現(xiàn)代數(shù)學(xué)的眼光來看，傅里葉變換其實(shí)就是一種特殊的積分變換。 與傅立葉變換算法對(duì)應(yīng)的是反傅立葉變換算法。 2. 3 快速傅里葉變換的意義 傅立葉變換的物理意義：傅立葉變換是數(shù)字信號(hào)處理技術(shù)領(lǐng)域一項(xiàng)很重要的算法。在 FFT 中，利用 WN 的對(duì)稱性和周期性，把一個(gè) N 項(xiàng)序列（設(shè)k2?,k為正整數(shù)），分為兩個(gè) /項(xiàng)的子序列，而且每個(gè) 2/點(diǎn)的 DFT 變換需要? ?2/N次運(yùn)算，再運(yùn)用 N次運(yùn)算把兩個(gè) 2/N點(diǎn)的DFT 變換重新組合成一個(gè) N點(diǎn)的 DFT 變換。 2. 1 快速傅里葉變換原理 快速傅里葉變換原理： 1. 將長序列 DFT分解為短序列的 DFT 2. 利用旋轉(zhuǎn)因子的對(duì)稱性、周期性、可約性。 DFT 存在的缺點(diǎn)就是計(jì)算量太大 ,不易進(jìn)行實(shí)時(shí)處理。多數(shù)的 DSP芯片都能夠在一個(gè)指令周期內(nèi)完成一次乘法和加法，并且提供了專門的 FFT指令，完成一次指令的周期只需 10ns，使得 FFT算法在 DSP芯片上實(shí)現(xiàn)的速度更加快速。數(shù)字信號(hào)處理區(qū)別于普通的科學(xué)計(jì)算與分析，它強(qiáng)調(diào)運(yùn)算的實(shí)時(shí)性。 數(shù)字信號(hào)處理器（ DSP），是一種可編程的高性能處理器。繼庫利和圖基算法出來之后，桑德（ ）等快速算法也相繼出現(xiàn)，又經(jīng)過其他學(xué)者一步步改進(jìn)，很快就出現(xiàn)了通用型的快速傅里葉變換，簡稱 FFT。 傅里葉變換已經(jīng)有一百多年的歷史了，我們熟知頻域分析往往比時(shí)域分析更優(yōu)越，不僅簡單明了，而且易于分析較為復(fù)雜的信號(hào)。 1. 1 選題背景 近十多年來，數(shù)字信號(hào)處理技術(shù)同大規(guī)模集成電路、數(shù)字計(jì)算機(jī)等，都有了突飛猛進(jìn)的發(fā)展，日新月異，早已成為了一門具有強(qiáng)大生命力的技術(shù)科學(xué)?？焖俑凳献儞Q（ FFT），即離散傅氏變換的快速算法，它是根據(jù)離散傅氏變換的奇、偶、虛、實(shí)等特性，對(duì)離散傅立葉變換的算法進(jìn)行改進(jìn)獲得的 [1]。 widely used 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說明書 目 錄 摘要 …… ..……………………… .………………………………………………… .I Abstract ………… .…………… ………………………………………… ………… ……… II 選題背景 ................................................................................................................ 1 課題研究的意義 .................................................. 2 .............................................. 3 .......................................... 4 ............................................ 4 .............................................. 6 Cooley=Tukey FFT算法 ........................................... 8 RaderBrennr FFT 算法 ........................................... 9 Goertsel 算法 .................................................. 10 FFT 計(jì)算連續(xù)時(shí)間信號(hào)的傅里葉變換 ........................... 13 FFT 計(jì)算離散信號(hào)的線性卷積 ................................. 17 FFT 進(jìn)行離散信號(hào)壓縮 ....................................... 19 FFT 對(duì)離散信號(hào)進(jìn)行濾波 ..................................... 22 FFT 提取離散信號(hào)中的最強(qiáng)正弦分量 ........................... 24 ................... 29 ............................. 31 ........... 33 致謝 ................................................... 36 參考文獻(xiàn) ............................................... 37 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說明書 1 1 緒論 傅立葉變換在生產(chǎn)生活中的重要性非常突出，它將原本難以處理的時(shí)域信號(hào)相比比較容易地轉(zhuǎn)換成易于分析的頻域信號(hào)，我們可以利用一些專業(yè) 工具 對(duì)這些頻域信號(hào)進(jìn)行處理、加工，使信號(hào)轉(zhuǎn)化為可以對(duì)其進(jìn)行各種數(shù)學(xué)變換的數(shù)學(xué)公式，對(duì)其進(jìn)行處理。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。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準(zhǔn)用徒手畫 3）畢業(yè)論文須用 A4 單面打印，論文 50 頁以上的雙面打印 4）圖表應(yīng)繪制于無格子的頁面上 5）軟件工程類課題應(yīng)有程序清單，并提供電子文檔 1）設(shè)計(jì)（論文） 2）附件：按照任務(wù)書、開題報(bào)告、外文譯文、譯文原文（復(fù)印件）次序裝訂 3）其它 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說明書 摘 要 快速傅氏變換（ FFT），是離散傅氏 變換的快速算法，它是根據(jù)離散傅氏變換的奇、偶、虛、實(shí)等特性，對(duì)離散傅立葉變換的算法進(jìn)行改進(jìn)獲得 的。 涉密論文按學(xué)校規(guī)定處理。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。對(duì)本研究提供過幫助和做出過貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說明并表示了謝意。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu) 的學(xué)位或?qū)W歷而使用過的材料。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。本人授權(quán) 大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。 、圖表要求： 1）文字通順，語言流暢，書寫字跡 工整，打印字體及大小符合要求，無錯(cuò)別字，不準(zhǔn)請(qǐng)他人代寫 2）工程設(shè)計(jì)類題目的圖紙，要求部分用尺規(guī)繪制，部分用計(jì)算機(jī)繪制，所有圖紙應(yīng)符合國家技術(shù)標(biāo)準(zhǔn)規(guī)范。 關(guān)鍵詞： 快速傅氏變換；快速算法；簡化；廣泛應(yīng)用 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說明書 II Abstract Fast 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。 simplified。然而，它在運(yùn)算上過于復(fù)雜，過于宏大的運(yùn)