【正文】 比較常用的變換方法之一，它在各種數(shù)字信號處理系統(tǒng)中扮演著及其重要的角色。由于離散傅里葉變換（ DFT）而發(fā)現(xiàn)了頻率離散化，可以直接用它來分析信號的頻譜、計算濾波器的頻率響應、以及實現(xiàn)信號通過線系統(tǒng)的卷積運算等，因而在信號的譜分析等方面有著非常大的作用。 傅里葉變換已經(jīng)有一百多年的歷史了，我們熟知頻域分析往往比時域分析更優(yōu)越，不僅簡單明了，而且易于分析較為復雜的信號。但需要用較為精準的數(shù)字方法，即 DFT，進行譜分析，在 快速傅氏變換（ FFT）出現(xiàn)以前是不 切實際的。武漢工程大學畢業(yè)設計 (論文 )說明書 2 由于 DFT 的計算量太大，即使運用計算機也很難對問題進行實時的有效處理，所以 DFT 并沒有得到真正的應用。直到 1965 年庫利（ ）和圖基（ ）首次發(fā)現(xiàn) DFT 的一種快速算法，局面才發(fā)生根本性的變化。繼庫利和圖基算法出來之后，桑德（ ）等快速算法也相繼出現(xiàn)，又經(jīng)過其他學者一步步改進，很快就出現(xiàn)了通用型的快速傅里葉變換，簡稱 FFT?？焖俑道锶~變換（ Fast Fourier Transform， FFT）并非與離散傅里葉變換完全不同的另一種變換，而是為了減少 DFT 計 算次數(shù)而誕生的一種快速、有效的算法。應當指出的是，也是因為當時電子數(shù)字計算機的“落后”條件也促成了這個算法的提出。它使得 DFT 的運算量大大的縮小簡化，它推動了近 30 年來信號處理技術(shù)止步不前的前進發(fā)展，成為了數(shù)字信號處理應用領域里強有力的工具，為 DFT 乃至數(shù)字信號處理技術(shù)的實際應用創(chuàng)造了良好的條件，從而使 DFT 在實際使用中得以廣泛的應用 [2]。 數(shù)字信號處理器（ DSP），是一種可編程的高性能處理器。近年來發(fā)展尤為迅速，它不僅應用于數(shù)字信號處理方面，而且在圖像處理、語音處理、通信等領域得到廣泛的應用。之前通用的 微處理器在運算速度上已經(jīng)很難適應信號實時處理的高要求。 DSP 處理器中集成了高速的乘法硬件，能快速、準確地進行大量數(shù)據(jù)的乘法以及加法的運算。數(shù)字信號處理區(qū)別于普通的科學計算與分析，它強調(diào)運算的實時性。除了需要普通微處理器所強調(diào)的高速運算和控制能力之外，鑒于實時數(shù)字信號處理的特點，在處理器結(jié)構(gòu)、指令系統(tǒng)、指令流程上做了很大程度上的改進。 1. 2 課題研究的意義 如上所述，基于對 DSP的快速傅里葉變換算法的研究，從而使 FFT算法能夠有效地在 DSP芯片上實現(xiàn)。 DSP芯片的出現(xiàn)，使 FFT的實現(xiàn)更加方便。多數(shù)的 DSP芯片都能夠在一個指令周期內(nèi)完成一次乘法和加法，并且提供了專門的 FFT指令，完成一次指令的周期只需 10ns，使得 FFT算法在 DSP芯片上實現(xiàn)的速度更加快速。 快速傅里葉變換為頻譜分析、卷積、相關(guān)數(shù)字濾波器設計與實現(xiàn)與功率譜計算、傳遞函數(shù)建模、圖像處理等，提供了快速有效的運算方法。 FFT技術(shù)應用 DSP芯片，從而可以提供使調(diào)制、解調(diào)、壓縮、解壓縮的數(shù)據(jù)傳輸更為高效的信號處理解決方案，因而廣泛應用于雷達、圖像處理、通信、生物醫(yī)學和聲納領域。 武漢工程大學畢業(yè)設計 (論文 )說明書 3 數(shù) 字信號中的傅里葉變換 ,通常是采用離散 型傅里葉變換 (DFT)。 DFT 存在的缺點就是計算量太大 ,不易進行實時處理。比如，計算一個 N 點的 DFT ,一般需要2N次復數(shù)乘法和 N(N1)次復數(shù)加法運算 .因此 ,當 N較大或要求對信號進行實時處理時 ,往往很難實現(xiàn)達到所需的運算速度。 1965 年 , 和 發(fā)現(xiàn)了 DFT 的一種快速算法 ,經(jīng)過后來學者的進一步改進 , 很快便形成了一套高效的運算方法 ,即現(xiàn)在通用的快速傅里葉變換 , 簡稱 FFT( The Fast Fourier Transform)。快速 傅里葉變換的實質(zhì)是利用式 (31)中的權(quán)函數(shù)nkNW的對稱性和周期性 ,把 N點 DFT進行一系列分解和組合 ,使整個 DFT的計算過程變成一系列疊代運算過程 ,使 DFT的運算量大大簡化 ,為 DFT及數(shù)字信號的實時處理和應用創(chuàng)造了非常良好的條件 [3]。 2. 1 快速傅里葉變換原理 快速傅里葉變換原理： 1. 將長序列 DFT分解為短序列的 DFT 2. 利用旋轉(zhuǎn)因子的對稱性、周期性、可約性。將時域序列逐次分解為一組子序列，依據(jù)旋轉(zhuǎn)因子的特性，由子序列的 DFT 來實現(xiàn)整個序列的 DFT[4]。 其中：快速傅里葉變換分為兩種，分為基 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） 武漢工程大學畢業(yè)設計 (論文 )說明書 4 2. 2 快速傅里葉變換的優(yōu)越性 設nx為N項的復數(shù)序列，依據(jù) DFT 變換，任一)(mx的計算都需要有N次復數(shù)乘法和（1?）次復數(shù)加法，而且一次復數(shù)乘法等同于四次實數(shù)乘法和兩次實數(shù)加法，同樣的，一次復數(shù)加法等同于兩次實數(shù)加法，即使我們把一次復數(shù)乘法和一次復數(shù)加法定義成一次“運算”（四次實數(shù)乘法和四次實數(shù)加法），那么求出N項復數(shù)序列的)(mx, 即 N 點 DFT 變換大約就需要2N次運算。當1024?N點甚至更多的時候，需要 N2=1048576 次運算。在 FFT 中，利用 WN 的對稱性和周期性，把一個 N 項序列（設k2?,k為正整數(shù)），分為兩個 /項的子序列，而且每個 2/點的 DFT 變換需要? ?2/N次運算，再運用 N次運算把兩個 2/N點的DFT 變換重新組合成一個 N點的 DFT 變換。如此變換以后，總的運算次數(shù)就變成了2/)2/(2 22 NNN ???。承接上面的例子，當 1024?時，總的運算次數(shù)就變成了 525312 次，這樣看來，節(jié)省了大約 50%的運算量。而如果我們將這種“一分為二”的思想不斷進行下去，直到分成兩兩一組的 DFT運算單元，那么 N點的 DFT 變換就只需要nN 2log次的運算，N在 1024 點時，運算量僅有 10240 次，是先前的直接算法的 1%，點數(shù)越多，運算量的節(jié)約就越大，這就是 FFT 的優(yōu)越性 .當然， FFT 提高了運算速度 ,但是 ,也對參與運算的樣本序列作出了限制 ,即要求樣本數(shù)為 2^N點 .離散傅里葉變換 DFT則無上述限制 [5]。 2. 3 快速傅里葉變換的意義 傅立葉變換的物理意義：傅立葉變換是數(shù)字信號處理技術(shù)領域一項很重要的算法。要知道傅立葉變換算法的意義，首先要了解傅立葉變換原理的意義。傅立葉變換原理表明：任何連續(xù)測量的時序或信號，都能夠表示成為不同頻率的正弦波信號的無限疊加。而利用該原理而創(chuàng)立的傅立葉變換算法則利用直接能測量到的原始信號，并以累加方式來計算該信號中不同正弦波信號的頻率、相 位和振幅。 與傅立葉變換算法對應的是反傅立葉變換算法。該反變換從本質(zhì)上說也就是一種累加處理，這樣便可以將單獨改變的正弦波信號轉(zhuǎn)換成一個信號。因此，也可以說，傅立葉變換將原來難以處理的時域信號轉(zhuǎn)換成了易于分析的頻域信號（信號的頻譜），我們可以利用一些專業(yè)工具對這些頻域信號進行加工、處理。武漢工程大學畢業(yè)設計 (論文 )說明書 5 最后還可以利用傅立葉反變換將這些頻域信號轉(zhuǎn)換成原來的時域信號。 從現(xiàn)代數(shù)學的眼光來看，傅里葉變換其實就是一種特殊的積分變換。它能夠?qū)M足一定條件下的某個函數(shù)表示成為正弦基函數(shù)的線性組合或者積分形式。在不同的研究領域里，傅里葉變 換具有多種形式各異的變體形式，如連續(xù)傅里葉變換和離散傅里葉變換。 在數(shù)學領域，盡管最初傅立葉分析是作為熱過程的解析分析的工具，但是其思想方法仍然具有典型的還原論和分析主義的特征。 任意 的函數(shù)通過一定的分解，都能夠表示為正弦函數(shù)的線性組合的形式，而正弦函數(shù)在物理上是被充分研究而相對簡單的函數(shù)類： 1. 傅立葉變換是線性算子 ,若賦予適當?shù)姆稊?shù) ,它還是酉算子 。2. 傅立葉變換的逆變換容易求出 ,而且形式與正變換非常類似 。3. 正弦基函數(shù)是微分運算的本征函數(shù) ,從而使得線性微分方程的求解可以轉(zhuǎn)化為常系數(shù)的代數(shù)方程的求解 .在線性時不變雜的卷積運算為簡單的乘積運算 ,從而提供了計算卷積的一種簡單手段 。4. 離散形式的傅立葉的物理系統(tǒng)內(nèi) ,頻率是個不變的性質(zhì) ,從而系統(tǒng)對于復雜激勵的響應可以通過組合其對不同頻率正弦信號的響應來獲取 。5. 著名的卷積定理指出 :傅立葉變換可以化復變換可以利用數(shù)字計算機快速的算出 (其算法稱為快速傅立葉變換算法 (FFT))。 正是由于上述的良好性質(zhì) ,傅里葉變換在物理學、數(shù)論、組合數(shù)學、信號處理、概率、統(tǒng)計、密碼學、聲學、光學等領域都有著廣泛的應用 [6]。 武漢工程大學畢業(yè)設計 (論文 )說明書 6 3. 快速傅里葉變換的算法 快速傅里 葉變換算法 快速傅里葉變換 FFT 是離散傅里葉變換 DFT 的一種快速算法，只有 FFT 才能在現(xiàn)實中有實際應用的意義。 錯誤 !未找到引用源。12,1,0。10)( )(0 ??? ??? Nne NnkxX NKn k ?? (31) 由 (31)式可知，對每一個 n，計算 X(ｎ )須作 N次復數(shù)乘法及 N1次復數(shù)加法，要完成這組變換共需 N2 錯誤 !未找到引用源。 次乘法及 N(N1)次復數(shù)加法。但以下介紹的快速 傅里葉變換的算法，可大大減少運算次數(shù)，提高工作效率。 當 2rN? 時， n 和 k 可用二進制數(shù)表示： 121 2 0 1 2 022rrr r r rn n n n n n n??? ? ? ?? ? ? ? ?錯誤 ! 未 找 到 引 用 源 。 (32) 121 2 0 1 2 022rrr r r rk k k k k k k??? ? ? ?? ? ? ? ? （ 33） 又記 NWe???? ,則（ 31）式可改寫為 0 0 1 1 01 1 11 2 0 0 1 2 00( ) ( )r pr r r rk k kX n n n x k k k W? ? ?? ? ? ??? ? ? ? （ 34） 式中： 1 2 1 21 2 0 1 2 0( 2 2 ) ( 2 2 )r r r rr r r rP n k k k k n n n? ? ? ?? ? ? ?? ? ? ? ? ? ? ? ? 1 2 1 1 2 21 2 0 1 1 2 0 2( 2 2 ) 2 ( 2 2 ) 2r r r r r rr r r r r rn n n k n n n kPW W W? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? 120 1 2 0( 2 2 )rrrrK n n nW ????? ? ? (35) 因為 22 [ ] 1r r NNW W e ??? ? ?所以（ 32）可改成 Z 0 0 1 1 01 1 11 2 0 0 1 2 00( ) ( )rr r r rk k kX n n n x k k k? ? ?? ? ? ??? ? ?1 2 1 1 2 2 1 21 2 0 1 1 2 0 2 0 1 2 0( 2 2 ) 2 ( 2 2 ) 2 ( 2 2 )r r r r r r r rr r r r r r r rn n n k n n n k K n n nW W W? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? （ 36） 2012 0 1 3 0 0 0 2 0( ) ( )rrrkx n n k k x n k k????? ?1 0 2(2 )2 2 rn n r kW ??? (37) 1 2 0 0 1 1( ) ( )r r r rX n n n x n n n? ? ?? 武漢工程大學畢業(yè)設計 (論文 )說明書 7 則式（ 37）即為式（ 36）的分解形式。將初始數(shù)據(jù)代入式（ 37）的第一個等式，可得每一組計算數(shù)據(jù)，一般將痗 L1 組計算數(shù)據(jù)代入式（ 37）的第 L個等式，計算后可得第 L 組計算數(shù)據(jù)（ L＝１，２，?，γ），計算公式也可表示為 1011 0 2 0 0 1 2 0( ) (