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