【正文】 更高的計算效率。以計算l024點的序列為例，F(xiàn)FT將計算時間縮短為原來的1/100，從而使數(shù)字信號處理從一個計算數(shù)學的分支變?yōu)橐婚T應用科學，逐步走向?qū)嵱眉夹g。1965年，Cooley和Tukey在《計算數(shù)學》上發(fā)表了著名的論文，并立即引起了廣泛注意。因為DFT的運算量與成比例，所以如果將一個大點數(shù)的DFT分解為若干個小點數(shù)的DFT的組合，將有效地減少運算量。在FFT算法中，Tukey主要利用了旋轉(zhuǎn)因子的周期性和對稱性。當時Garwin在自己的研究中極需要一個計算傅里葉變換的快速方法，Tukey概括地對Garwin介紹了一種方法，它實質(zhì)上就是后來著名的CooleyTukey算法。但其計算量太大，很難實時地處理問題。它把數(shù)字計算機的應用和信號分析理論結(jié)合在一起，使得譜分析、卷積、相關等運算都可以通過DFT在計算機上實現(xiàn)。它是分析有限長序列的有用工具。但還有一種方法更能反映序列的有限長這個特點，即離散傅里葉變換。通過學習和討論算法，編寫程序，討論仿真結(jié)果。熟悉CCS（Code Composer Studio）開發(fā)環(huán)境，CCS是TI公司的DSP集成開發(fā)環(huán)境。掌握旋轉(zhuǎn)因子的生成和序列的倒序。這些離散值通過快速傅立葉變換轉(zhuǎn)變?yōu)轭l域信號，用以進行下一步的分析研究。本文要解決的問題就是如何對數(shù)據(jù)進行分析研究，得到一個能快速進行離散傅里葉變換的方法，降低對計算機內(nèi)存的要求，使FFT能更加廣泛的應用于科學研究。快速傅里葉變換和離散傅里葉變換的基本理論是一樣的，它根據(jù)離散傅氏變換的奇、偶、虛、實等特性，對離散傅里葉變換的算法進行了改進。 本文主要研究內(nèi)容本文主要介紹基于DSP的快速傅里葉變換的算法的實現(xiàn)?？焖俑道锶~變換為頻譜分析、卷積與相關數(shù)字濾波器設計與實現(xiàn)、功率譜計算、傳遞函數(shù)建模、圖像處理等，提供了快速運算方法。由于多數(shù)的DSP芯片都能在一個指令周期內(nèi)完成一次乘法和加法，而且提供了專門的FFT指令。 課題研究的意義綜上所述，基于DSP的快速傅里葉變換算法的研究使FFT算法能夠有效地在DSP芯片上實現(xiàn)。數(shù)字信號處理不同于普通的科學計算與分析，它強調(diào)運算的實時性。通用的微處理器在運算速度上很難適應信號實時處理的要求。數(shù)字信號處理器（DSP）是一種可編程的高性能處理器，近年來發(fā)展很快。應當指出，當時電子數(shù)字計算機的條件也促成了這個算法的提出。繼庫利和圖基算法之后，桑德（）等快速算法相繼出現(xiàn)，又經(jīng)過其他學者進一步改進，很快出現(xiàn)了通用的快速傅里葉變換，簡稱FFT。由于DFT的計算量太大，即使采用計算機也很難對問題進行實時處理，至此DFT并沒有得到真正的應用。傅里葉變換已有一百多年的歷史了，我們知道頻域分析常常比時域分析更優(yōu)越，不僅簡單，而且易于分析復雜信號。在信號處理中，離散傅里葉變換（Discrete Fourier Transform，DFT）是常用的變換方法，它在各種數(shù)字信號處理系統(tǒng)中扮演著重要的角色。 Rotation東北石油大學本科生畢業(yè)設計（論文）目 錄第1章 概 述 1 課題研究的背景及意義 1 本文主要研究內(nèi)容 2第2章 快速傅里葉變換及其算法 4 快速傅里葉變換的原理 4 快速傅里葉算法及其應用 7 本章小結(jié) 14第3章 軟件設計 15 算法設計和程序編寫 15 CCS開發(fā)環(huán)境的使用及軟件仿真 20 本章小結(jié) 24第4章 DSP芯片的原理和FFT在DSP上的實現(xiàn) 26 DSP芯片的原理、特點和結(jié)構(gòu) 26 FFT算法在DSP上的實現(xiàn) 31 本章小結(jié) 32結(jié) 論 33參考文獻 34致 謝 35附錄 36I東北石油大學本科生畢業(yè)設計（論文）第1章 概 述 課題研究的背景及意義 課題背景近十多年來數(shù)字信號處理技術同數(shù)字計算機、大規(guī)模集成電路等，有了突飛猛進的發(fā)展，日新月異，已經(jīng)成為一門具有強大生命力的技術科學。關鍵詞：DSP；FFT；旋轉(zhuǎn)因子AbstractUsing advanced C language to realize FFT algorithm. Using digital signal processor (DSP) endemic harvard structure and special FFT instructions. In more quickly on DSP can realize FFT. In order to promote the development of digital signal processor (DSP) based on DSP, accelerate the speed of digital signal processing.Base on the study of FFT, from basic research and study, the key to mastering FFT algorithm. Research on how to accelerate DSP and wing how effectively yards of a output upside down. Familiar with the rotation factor production. Through studying the working principle of DSP, analyzes the algorithm, realized the design of FFT algorithm in DSP. Based on studying DSP development environment, CCS simple missioning and software simulation. CCS development environment in observing sine wave, the output waveform input, PC FFT calculation of wave graph with simulation. Comparative simulation diagram, verify the correctness of design and program. Use DSP controller that peculiar sequence indirect addressing the realization of FFT make more convenient.Key words：DSP。比較仿真圖，驗證設計和程序的正確性。通過對DSP開發(fā)環(huán)境的學習，掌握CCS的簡單調(diào)試和軟件仿真。熟悉旋轉(zhuǎn)因子的生成。通過對FFT的算法進行研究，從基礎深入研究和學習，掌握FFT算法的關鍵。在DSP上能夠更快速的實現(xiàn)FFT。東北石油大學本科生畢業(yè)設計（論文）摘 要采用高級C語言實現(xiàn)FFT算法。利用DSP芯片特有的哈佛結(jié)構(gòu)和專門的FFT指令。從而促進DSP芯片的發(fā)展，同時加快基于DSP數(shù)字信號處理的速度。研究DSP芯片如何加快蝶形計算以及如何有效地碼位倒置的輸出顛倒過來。通過學習DSP芯片的工作原理，分析DSP控制的算法，在DSP芯片上實現(xiàn)快速傅里葉變換算法的設計。在CCS開發(fā)環(huán)境中觀察正弦波輸入波形、輸出波形、PC機FFT計算處理后的仿真波形圖。表明利用DSP控制器特有的反序間接尋址使FFT的實現(xiàn)更加方便。 FFT。由于它本身具有一系列的優(yōu)點，所以能有效地促進個工程技術領域的技術改造和學科發(fā)展，應用領域也更加廣泛、深入，越來越受到人們的重視。由離散傅里葉變換（DFT）發(fā)現(xiàn)了頻率離散化，可以直接用來分析信號的頻譜、計算濾波器的頻率響應，以及實現(xiàn)信號通過線系統(tǒng)的卷積運算等，因而在信號的譜分析等方面有很大的作用。但需要用較精準的數(shù)字方法，即DFT進行譜分析，在FFT出現(xiàn)以前是不切實際的。直到1965年庫利（）和圖基（）首次發(fā)現(xiàn)DFT的一種快速算法，情況才發(fā)生根本性的變化?？焖俑道锶~變換（Fast Fourier Transform，F(xiàn)FT）并不是與離散傅里葉變換不同的另一種變換，而是為了減少DFT計算次數(shù)的一種快速有效的算法。它使DFT的運算量大大的簡化，它推動了近30年的信號處理技術的發(fā)展，成為數(shù)字信號處理應用領域強有力的工具，為DFT乃至數(shù)字信號處理技術的實際應用創(chuàng)造了良好的條件，從而使DFT在實際使用中得以廣泛的應用。它不僅適用于數(shù)字信號處理，而且在圖像處理、語音處理、通信等領域得到廣泛的應用。DSP處理器中集成有高速的乘法硬件，能快速地進行大量數(shù)據(jù)的乘法和加法運算。除了具備普通微處理器所強調(diào)的高速運算和控制能力外，針對實施數(shù)字信號處理的特點，在處理器結(jié)構(gòu)、指令系統(tǒng)、指令流程上做了很大的改進。DSP芯片的出現(xiàn)使FFT的實現(xiàn)更為方便。完成一次指令的周期只需10ns，使得FFT算法在DSP芯片上實現(xiàn)的速度更快。FFT技術應用DSP芯片，從而可以提供使調(diào)制、解調(diào)、壓縮、解壓縮和數(shù)據(jù)傳輸更為高效的信號處理解決方案，因而廣泛應用于雷達、通信、圖像處理、聲納和生物醫(yī)學領域。研究快速傅里葉變換原理。在計算機系統(tǒng)或者數(shù)字系統(tǒng)中廣泛應用快速傅里葉變換，這是一個巨大的進步?？焖俑道锶~變換是離散傅里葉變換的改進方法，因此對連續(xù)的周期信號和連續(xù)的非周期信號，均需進行加窗與取樣，從而得到一系列離散值。掌握在DSP上實現(xiàn)快速傅里葉變換算法。學習DSP芯片TMS320C5416的性能和結(jié)構(gòu)。利用CCS軟件的仿真環(huán)境來模擬TMS320C5416芯片，并對信號處理。35東北石油大學本科生畢業(yè)設計（論文）第2章 快速傅里葉變換及其算法 快速傅里葉變換的原理 離散傅里葉變換的介紹及FFT的發(fā)展在數(shù)字信號處理中，對于有限長序列，也可以用序列的傅里葉變換和Z變換來分析和表示。離散傅里葉變換（Discrete Fourier Transform，DFT）是常用的變換方法，它在各種數(shù)字信號處理系統(tǒng)中扮演著重要的角色。離散傅里葉變換除了作為有限長序列的一種傅里葉表示法，在理論上相當重要之外，而且由于存在著計算離散傅里葉變換的有效快速算法，因而離散傅里葉變換在各種數(shù)字信號處理的算法中起著核心的作用[1]。有限長序列可以通過離散傅里葉變換（DFT）將其頻域也離散化成有限長序列。直到1965年出現(xiàn)了DFT運算的一種快速方法以后，情況才發(fā)生了根本的變化。在Garwin的迫切要求下，1963年，IBM公司的Cooley根據(jù)Tukey的想法編寫了第一個FFT算法程序。這兩個性質(zhì)使DFT運算中的某些項可以合并，使DFT運算盡量分解為更少點數(shù)的DFT運算。Cooley在計算機上實現(xiàn)該算法時，為節(jié)省存儲空間和減少尋址時間，采用了三維標號映射方法和在算法內(nèi)部的循環(huán)結(jié)構(gòu)，這些結(jié)構(gòu)和技巧對后來的FFT算法研究及實現(xiàn)同樣產(chǎn)生了很大影響。FFT算法將運算時間減少12個數(shù)量級，從理論上解決了數(shù)字信號處理運算量大的問題，是數(shù)字信號處理發(fā)展史上的—塊里程碑。在CooleyTukey算法提出之后，Sande提出了按照頻率抽取的FFT算法，它可以作為按照時間抽取的CooleyTukey算法的對偶形式。增大基數(shù)雖然可以減少計算量，但同時每個計算單元的結(jié)構(gòu)也更復雜。當采用高于4的基數(shù)r時，雖然總的乘法次數(shù)更少，但比基4算法中所需的復乘次數(shù)減少得并不顯著，并且r點的DFT中將包含乘法運算，因此實際應用中多采用基4算法。對于輸入數(shù)據(jù)是實數(shù)情況，可以將N點的DFT運算轉(zhuǎn)換為N/2點的DFT運算，或者同時計算兩個實序列的DFT，都可以采用FFT算法。事實上，在CooleyTukey算法提出之前，Good就提出用點數(shù)互素的短點數(shù)DFT運算組合來實現(xiàn)長點數(shù)DFT運算，并且這種實現(xiàn)方式不會引入附加的乘旋轉(zhuǎn)因子的運算。在素因子算法中，由于避免了乘旋轉(zhuǎn)因子的運算