基于FPGA的FFT設(shè)計(jì)畢業(yè)論文

1、誠 信 承 諾 書本人承諾：所呈交的論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究成果。除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已發(fā)表或撰寫過的研究成果。參與同一工作的其他同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意。 簽 名： 日 期： 本論文使用授權(quán)說明本人完全了解南通大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留論文及送交論文復(fù)印件，允許論文被查閱和借閱；學(xué)?？梢怨颊撐牡娜炕虿糠謨?nèi)容。（保密的論文在解密后應(yīng)遵守此規(guī)定）學(xué)生簽名： 指導(dǎo)教師簽名： 日期： 摘 要快速傅里葉變換（fft）是一種為了改進(jìn)和提高離散傅里葉變換（dft）運(yùn)算速度而提出的算法。它是根據(jù)已有

2、的dft的運(yùn)算特性發(fā)展起來的dft快速算法?？焖俑道锶~變換的理論在信號處理、數(shù)字通信、語音處理和計(jì)算機(jī)等諸多領(lǐng)域有著廣泛的運(yùn)用。在不同的運(yùn)用場合，對fft電路的性能有著不同的要求，但是在很多領(lǐng)域都要求fft處理器能夠具有高速度、高精度和實(shí)時(shí)性的工作狀態(tài)?，F(xiàn)場可編程門陣列（fpga）是由許多獨(dú)立的可編程邏輯模塊組成一種新型可編程器件。fft運(yùn)算結(jié)構(gòu)相對比較簡單和固定，適合使用fpga進(jìn)行硬件實(shí)現(xiàn)，并且能兼顧速度及靈活性。本文介紹了一種基于fpga上實(shí)現(xiàn)32點(diǎn)fft變換的設(shè)計(jì)方案。整個fft模塊采用基-2時(shí)域抽取，順序輸入，逆序輸出的方法實(shí)現(xiàn)。將采集到的數(shù)據(jù)通過編寫串口程序輸入，再運(yùn)用復(fù)數(shù)乘法器為

3、核心設(shè)計(jì)了fft算法中的基-2蝶形運(yùn)算單元、溢出控制單元和地址與邏輯控制模塊等其它模塊，并以這些模塊和fpga內(nèi)部的雙口ram為基礎(chǔ)組成了基-2fft算法模塊，將經(jīng)過處理的數(shù)據(jù)由串口程序輸出，并且對運(yùn)算結(jié)果使用matlab軟件對比驗(yàn)證。關(guān)鍵詞：快速傅里葉變換，fpga，旋轉(zhuǎn)因子，基-2abstractfast fourier transform (fft) is a algorithm in order to improve and enhance the computing speed of the discrete fourier transform (dft). it is a dft

4、fast algorithm according to the development of the operational characteristics of the existing dft. the theory of fft is widely used in many fields such as signal processing, digital communications, voice processing, and computer. in different applications, the performances of the fft circuit have d

5、ifferent requirements, but in many areas fft processor is required with high speed, high accuracy and real-time work status.field programmable gate array (fpga) is a new type programmable device which is composed by a number of independent programmable logic module. the structure of fft computation

6、is relatively simple and fixed, suitable for the use of fpga hardware implementation, and also can take the speed and flexibility into account. this article introduces a 32-point fft transform design which is based on fpga. the entire module uses radix-2 time-domain extraction, the order of input, o

7、utput reverse method. input data using the serial interface program and using a complex multiplier as the core design of fft algorithm in the radix-2 butterfly unit, overflow control unit and address and logical control module and other modules, and within these modules and fpga-based dual-port ram

8、formed the radix-2 fft algorithm module, output the processed data from the serial interface program, and using matlab software for comparison and validation of calculation results. keywords: fft, fpga, rotation factor, radix-2目 錄摘 要iabstractii第一章 緒 論11.1數(shù)字信號處理概論11.2數(shù)字信號處理的發(fā)展趨勢11.3 所做的主要工作2第二章 fpga的

9、基礎(chǔ)知識32.1 fpga的簡介32.2 fpga較其他器件優(yōu)點(diǎn)32.3 開發(fā)軟件簡介42.3.1 quartus ii軟件介紹42.3.2 quartus ii軟件設(shè)計(jì)流程52.4 verilog hdl的簡介52.5 本章小結(jié)6第三章 fft算法原理73.1 快速傅里葉變換73.2 基-2fft算法73.2.1 基-2fft算法原理73.2.2 基-2fft算法特點(diǎn)113.3 本章小結(jié)13第四章 fft的fpga實(shí)現(xiàn)144.1 整體結(jié)構(gòu)設(shè)計(jì)144.2 蝶形運(yùn)算單元154.3 邏輯控制及其他輔助單元174.3.1 邏輯控制單元174.3.2 其他輔助模塊184.4 存儲單元204.5 串口通

10、信單元224.6 fft整體實(shí)現(xiàn)244.7 本章小結(jié)26第五章 系統(tǒng)的仿真與測試275.1 實(shí)驗(yàn)結(jié)果及分析275.2 本章小結(jié)29結(jié)束語30參考文獻(xiàn)31致 謝32第一章 緒 論1.1數(shù)字信號處理概論隨著現(xiàn)代計(jì)算機(jī)與信息技術(shù)的不斷飛速發(fā)展，對數(shù)字信號處理系統(tǒng)的運(yùn)行處理速度要求也越來越高。數(shù)字信號處理系統(tǒng)的研究人員一直在尋找各種優(yōu)化的算法來解決信號處理中遇到的棘手問題。其實(shí)質(zhì)就是通過相應(yīng)的軟件與硬件的結(jié)合，將模擬信號或者其他的一些信號轉(zhuǎn)換為數(shù)字信號并加以相應(yīng)的處理。在數(shù)字信號處理領(lǐng)域中部分?jǐn)?shù)據(jù)可以在完成所有采集之后再進(jìn)行處理，這些數(shù)據(jù)對系統(tǒng)的實(shí)時(shí)性處理要求較低，利用通用的計(jì)算機(jī)系統(tǒng)既可以完成處理。

11、這一類數(shù)字信號處理在計(jì)算機(jī)上編寫程序，修改和運(yùn)行，并對結(jié)果進(jìn)行分析就能滿足要求。還有一類數(shù)字信號處理必須在規(guī)定的時(shí)間內(nèi)完成，比如手機(jī)通話和雷達(dá)系統(tǒng)等。有的數(shù)字信號處理對時(shí)間的要求十分嚴(yán)格，甚至使用高速的通用微處理器芯片也無法滿足性能需要，因此在這種情況下就必須為這樣的運(yùn)算設(shè)計(jì)專用的硬線邏輯電路，通過fpga器件上實(shí)現(xiàn)或者制成高速專用集成電路。因此，對數(shù)字信號的實(shí)時(shí)處理一方面也是建立在高速大規(guī)模集成電路不斷發(fā)展的基礎(chǔ)上的。另一方面，對數(shù)字信號處理實(shí)時(shí)性的要求不斷提高，也推動了高速大規(guī)模集成電路制造技術(shù)的進(jìn)步1。經(jīng)過幾十年的發(fā)展，數(shù)字信號處理（dsp）作為一項(xiàng)成熟的技術(shù)，已經(jīng)在諸多領(lǐng)域取得了廣泛的

12、運(yùn)用，并且一些方面有逐步取代傳統(tǒng)的模擬信號處理系統(tǒng)的趨勢。dsp系統(tǒng)具有以下幾項(xiàng)優(yōu)點(diǎn)：如數(shù)字元器件對溫度變化老化及元件容差不敏感。相比較模擬信號，數(shù)字信號在精度、靈活性、線性相位、多維處理等方面具有明顯優(yōu)勢。有兩個事件加速了dsp技術(shù)的發(fā)展，其一是cooley和tuckey（1956年）揭示了一種計(jì)算離散傅里葉變換（discrete fourier transform ，dft）的有效算法。而另一個重大轉(zhuǎn)折就是在20世紀(jì)70年代后期可編程數(shù)字信號處理器（programmable digital signal processor，pdsp）引入。1.2數(shù)字信號處理的發(fā)展趨勢數(shù)字信號處理在很多領(lǐng)域

13、運(yùn)用廣泛，比如信號處理、數(shù)字通信、語音識別、雷達(dá)系統(tǒng)等。傳統(tǒng)的使用軟件處理來實(shí)現(xiàn)這些算法，缺點(diǎn)明顯：速度慢、效率低，已經(jīng)無法滿足現(xiàn)代通信中對于信號處理的實(shí)時(shí)性越來越高的要求。數(shù)字信號處理發(fā)展的一個明顯趨勢就是：高速和實(shí)時(shí)。在一些情況下，即使通用信號處理器（dsp）也無法滿足系統(tǒng)的性能要求。近年來，現(xiàn)場可編程門陣列（fpga）憑借著其更高的集成度、更強(qiáng)的邏輯實(shí)現(xiàn)能力和更好的設(shè)計(jì)靈活性，逐漸在數(shù)字信號處理領(lǐng)域獲得越來越廣泛的應(yīng)用。它作為專用集成電路（asic）中的一種半定制電路，相對于dsp有著成本、性能和靈活性等方面的優(yōu)點(diǎn)。fpga是一種直接由硬件實(shí)現(xiàn)的器件，它由邏輯功能塊排成陣列組成，內(nèi)部含有

14、很多相同的運(yùn)算單元，所以當(dāng)使用fpga在作數(shù)字信號處理時(shí)，速度會遠(yuǎn)遠(yuǎn)高于通用的dsp芯片。在實(shí)現(xiàn)實(shí)時(shí)處理方案時(shí)往往需要使用多個dsp芯片，從而提高了產(chǎn)品的價(jià)格、功耗和開發(fā)周期。特別是伴隨近年來fpga的集成規(guī)模、運(yùn)算速度不斷提高，系統(tǒng)設(shè)計(jì)和調(diào)試方法更加豐富，其在數(shù)字信號處理方面應(yīng)用會更加廣泛。1.3 所做的主要工作隨著fpga技術(shù)的不斷成熟和fft算法在諸多領(lǐng)域的廣泛應(yīng)用，所以利用fpga芯片進(jìn)行fft系統(tǒng)設(shè)計(jì)的方案越來越多。因?yàn)閒pga芯片的重復(fù)可編程特點(diǎn)和具有豐富的邏輯單元，所以非常適合于算法比較固定、運(yùn)算數(shù)據(jù)量大的實(shí)時(shí)數(shù)字信號處理。研究是在國內(nèi)外專家學(xué)者的研究基礎(chǔ)之上進(jìn)行的，本論文主要f

15、ft算法的fpga實(shí)現(xiàn)，重點(diǎn)是運(yùn)用quartus ii軟件模擬仿真。全文共分為五章，各章節(jié)的主要內(nèi)容安排如下：第一章為緒論，簡要介紹了數(shù)字信號處理技術(shù)的研究背景、意義和發(fā)展趨勢。第二章對fpga的基礎(chǔ)知識進(jìn)行了簡單的介紹，以及使用fpga進(jìn)行開發(fā)的優(yōu)點(diǎn)。然后對本次研究需要使用的quartus ii軟件和verilog hdl的使用予以介紹。第三章對fft算法的原理進(jìn)行介紹。了解快速傅里葉變換的主要內(nèi)容后，論文著重介紹了fft算法原理和特點(diǎn)。其中包括理論知識、算法實(shí)現(xiàn)和主要特點(diǎn)。第四章介紹fft的fpga的實(shí)現(xiàn)，首先描述整體的設(shè)計(jì)思路，再對使用硬件描述語言實(shí)現(xiàn)的各個模塊進(jìn)行介紹和分析。第五章為通

16、過使用quartus ii軟件對fft系統(tǒng)進(jìn)行編譯、仿真和測試，對輸入的數(shù)據(jù)進(jìn)行處理后再輸出，并且和理論值進(jìn)行比較驗(yàn)證設(shè)計(jì)的正確性。第二章 fpga的基礎(chǔ)知識2.1 fpga的簡介fpga（field programmable gate array，現(xiàn)場可編程門陣列）是在可編程邏輯陣列（pal）、通用邏輯陣列（gal）、復(fù)雜可編程邏輯器件（cpld）等可編程器件的基礎(chǔ)上進(jìn)一步發(fā)展的產(chǎn)物，相對于其他的可編程器件，fpga在系統(tǒng)集成度、邏輯實(shí)現(xiàn)和設(shè)計(jì)能力等諸多方面有著明顯的優(yōu)勢。它能夠根據(jù)用戶的編程實(shí)現(xiàn)某種邏輯功能，而不需要前期的大量硬件開發(fā)投入。這使得fpga在滿足專用的、個性化的設(shè)計(jì)要求方面無

17、疑將擁有更大的靈活性和競爭力2。近年來，隨著fpga的性能不斷快速發(fā)展，它的廣泛使用不僅簡化了電路的設(shè)計(jì)復(fù)雜程度，降低了設(shè)計(jì)成本，提高了系統(tǒng)的可靠性，而且給整個數(shù)字電路系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)帶來了革命性的變化，使更低成本、更短周期的復(fù)雜數(shù)字系統(tǒng)開發(fā)成為可能。正是由于fpga上述的優(yōu)點(diǎn)，使得其在在數(shù)字信號處理、工業(yè)控制、數(shù)據(jù)處理等諸多領(lǐng)域的運(yùn)用越來越廣泛。而隨著微電子制造技術(shù)的發(fā)展和市場的需要，各種大容量、高性能、低功耗的fpga不斷推出，新一代的fpga不僅包含可編程邏輯模塊，更集成了微處理器芯片（cpu）和其他各種外接端口，方便與外部設(shè)備的連接使用，從而能夠?qū)崿F(xiàn)軟硬件的協(xié)同工作，為數(shù)字系統(tǒng)設(shè)計(jì)提供

18、更為強(qiáng)大的硬件支持。所以fpga的發(fā)展前景必將十分的廣闊。2.2 fpga較其他器件優(yōu)點(diǎn)經(jīng)過二十多年的不斷發(fā)展，現(xiàn)在工程中使用的可編程邏輯器件主要包括兩大類：cpld和fpga。雖然fpga和cpld都是可編程的asic器件，它們之間有著很多的共同點(diǎn)，但是由于fpga和cpld在結(jié)構(gòu)上的差異，使得它們都具有各自的特點(diǎn)。通常cpld的特點(diǎn)有：（1） cpld不需要另外配置加載芯片。（2） cpld的運(yùn)算速度比fpga快，并且具有較大的時(shí)間上的可預(yù)測性。（3） 在編程存儲方式上，cpld使用e2prom或flash作為編程存儲器，即使系統(tǒng)斷電后存儲器內(nèi)容不會丟失。fpga則是使用sram的存儲，系

19、統(tǒng)斷電時(shí)存儲器中的編程信息丟失。（4） cpld的保密性比fpga好。（5） 通常情況下，cpld的功耗比fpga大，而且隨著集成度的提高而增大。fpga中包含數(shù)量豐富的可編程邏輯模塊，但是cpld通常情況下卻只能做到512個邏輯單元。除此之外，fpga的平均邏輯單元成本也大大低于cpld。所以，fpga和cpld相比較而言，具有一下的優(yōu)點(diǎn)：（1） i/o數(shù)量多。同cpld一樣，fpga同樣具有眾多的用戶可定義的i/o資源，支持多種i/o標(biāo)準(zhǔn)，且數(shù)據(jù)傳輸?shù)乃俾史浅８?。?） 時(shí)序更容易滿足要求。與cpld相比fpga的內(nèi)部布線資源更加豐富，更容易實(shí)現(xiàn)用戶的時(shí)序設(shè)計(jì)要求。（3） 細(xì)粒fpga結(jié)構(gòu)

20、的優(yōu)點(diǎn)。fpga是細(xì)粒結(jié)構(gòu)，這就意味著每個單元間存在細(xì)粒延遲。如果將少量的邏輯緊密排列在一起，fpga的速度會相當(dāng)?shù)目臁＃?） 內(nèi)部資源豐富。與cpld相比，fpga除了具有豐富的布線資源外，其內(nèi)部邏輯資源也要豐富的多。（5） 容量大、功能強(qiáng)。一般來說，fpga器件的容量比cpld器件更容易做大，其內(nèi)部資源更加的豐富，甚至可以把整個系統(tǒng)放在一塊fpga芯片上實(shí)現(xiàn)。（6） 可任意次數(shù)的編程。fpga器件的編程數(shù)據(jù)是存放在片外的ram上，當(dāng)系統(tǒng)上電時(shí)才將數(shù)據(jù)導(dǎo)入fpga芯片的內(nèi)部存儲單元中，理論上的編程次數(shù)是無限的，而cpld的穩(wěn)定可編程次數(shù)一般不超過1萬次。正是因?yàn)閒pga具有的以上特點(diǎn)，利用f

21、pga設(shè)計(jì)的fft系統(tǒng)相對于傳統(tǒng)軟件或者dsp實(shí)現(xiàn)fft具有以下優(yōu)點(diǎn)：（1） fpga芯片運(yùn)行速度快能夠很好的滿足實(shí)時(shí)處理的要求，而單純靠軟件或者dsp進(jìn)行處理速度通常比較慢。（2） fpga的可編程特性使得其靈活性很強(qiáng)，可以根據(jù)需要再次修改程序算法，而且降低了開發(fā)成本和設(shè)計(jì)周期，這是dsp無法比擬的。2.3 開發(fā)軟件簡介2.3.1 quartus ii軟件介紹quartus ii軟件是altera公司主推的fpga設(shè)計(jì)軟件，其前身是大家熟悉的maxplus ii軟件，quartus ii軟件集設(shè)計(jì)輸入、編譯、綜合、仿真、布線布局和下載等功能于一體，是一款功能非常強(qiáng)大的eda設(shè)計(jì)軟件，對于不是

22、很大的系統(tǒng)設(shè)計(jì)，完全可以在這個平臺上完成所有的設(shè)計(jì)任務(wù)。但是，由于altera公司畢竟是一家以fpga芯片為主營業(yè)務(wù)的公司，且quartus ii軟件功能過于龐雜，所以合理的利用fpga設(shè)計(jì)第三方軟件及其他數(shù)據(jù)處理軟件（如matlab軟件），將大大提高fpga的設(shè)計(jì)效率。2.3.2 quartus ii軟件設(shè)計(jì)流程基于quartus ii進(jìn)行的eda設(shè)計(jì)開發(fā)流程如圖2.1所示，包括以下步驟：（1）設(shè)計(jì)輸入：包括原理圖式設(shè)計(jì)輸入、硬件描述語言文本輸入、內(nèi)存編輯輸入及第三方工具輸入等幾種方式。（2）編譯：quartus ii可選的編譯方式有綜合并輸出網(wǎng)表和完全的編譯。第二種編譯包括，網(wǎng)表輸出、綜合

23、、器件配置等，并且編譯軟件根據(jù)器件配置設(shè)定延時(shí)時(shí)間。（3）仿真：quartus ii軟件支持多種輸入的仿真，如.vwf波形文件，.vec向量文件，.tbl列表文件。通過仿真驗(yàn)證設(shè)計(jì)的邏輯功能和時(shí)間延時(shí)是否滿足要求。（4）下載與檢驗(yàn)：當(dāng)設(shè)計(jì)經(jīng)過編譯和仿真測試后，如果滿足設(shè)計(jì)要求便可以下載到電路開發(fā)板上的fpga芯片中進(jìn)行在線測試。修改設(shè)計(jì)在線測試編程仿真與定時(shí)分析編譯輸入設(shè)計(jì)文件在設(shè)計(jì)過程中，如果出現(xiàn)錯誤，則需要重新回到設(shè)計(jì)輸入階段，改正錯誤或調(diào)整電路后重復(fù)上述過程3。圖2.1 quartus ii設(shè)計(jì)流程2.4 verilog hdl的簡介硬件描述語言（hdl,hardware descrip

24、tion language）是一種用形式化方法來描述數(shù)字電路和系統(tǒng)的語言。通過硬件描述語言，建立系統(tǒng)行為級的仿真模型，然后利用eda軟件對由硬件描述語言建立的的復(fù)雜數(shù)字邏輯電路模型進(jìn)行仿真，然后再進(jìn)行綜合編譯，以生成符合要求且在電路結(jié)構(gòu)上可以實(shí)現(xiàn)的數(shù)字電路邏輯網(wǎng)表（netlist）。再根據(jù)具體器件生成該器件工藝條件下的電路延時(shí)配置，經(jīng)測試驗(yàn)證后，寫入fpga或cpld的存儲器中。在20世紀(jì)80年代后期，硬件描述語言的發(fā)展趨勢就是逐漸實(shí)現(xiàn)標(biāo)準(zhǔn)化，經(jīng)過世界范圍內(nèi)的廣泛驗(yàn)證，verilog hdl和vhdl語言符合了這種趨勢的要求，得到越來越多的eda公司和設(shè)計(jì)人員的使用和認(rèn)可。本文采用的是veri

25、log hdl語言來設(shè)計(jì)邏輯電路4。verilog hdl是硬件描述語言的一種，用于數(shù)字電子系統(tǒng)的設(shè)計(jì)。該語言允許設(shè)計(jì)者進(jìn)行各種級別的邏輯功能設(shè)計(jì)和數(shù)字邏輯系統(tǒng)的仿真驗(yàn)證，更重要的是進(jìn)行時(shí)序分析和綜合測試。在美國、歐洲和我國臺灣地區(qū)都有大量的設(shè)計(jì)工程師在使用verilog hdl進(jìn)行數(shù)字電路設(shè)計(jì)。一般把功能經(jīng)過驗(yàn)證的、可綜合的、實(shí)現(xiàn)后電路結(jié)構(gòu)總門數(shù)在5000門以上的verilog hdl模型稱之為“軟核”（soft core），而把由軟核構(gòu)成的器件稱之為虛擬器件5。verilog hdl很適合系統(tǒng)級（system）、算法級（algorithem）、寄存器傳輸級（rtl）、邏輯級（logic）、

26、門級（gate）、電路開關(guān)級（switch）設(shè)計(jì)，而system verilog是verilog語言的延伸和擴(kuò)展，更適合于可重復(fù)使用的可綜合的ip核和可重用的驗(yàn)證用ip設(shè)計(jì)，以及特大型（千萬門級以上）基于ip的系統(tǒng)級設(shè)計(jì)和驗(yàn)證。概括的說，verilog hdl語言具有以下的一些特點(diǎn)：（1） 既用于可綜合的電路設(shè)計(jì)，也可以用于電路與系統(tǒng)的仿真。（2） 能在不同的層次上對所要設(shè)計(jì)的系統(tǒng)進(jìn)行描述，從開關(guān)級、門級、寄存器傳輸級行為級等。（3） 電路結(jié)構(gòu)描述方式靈活，不但可以使用行為級描述或者結(jié)構(gòu)級描述，還可以二者混合描述。（4）內(nèi)置各種邏輯門，如and、or和nand等，可以方便的進(jìn)行門級結(jié)構(gòu)描述；內(nèi)

27、置各種開關(guān)級器件，如pmos、nmos和cmos等，可以進(jìn)行開關(guān)級的建模。（5）用戶自定義原語（udp）的靈活性6。2.5 本章小結(jié)本章主要對fpga的相關(guān)知識進(jìn)行了介紹，包括含義、組成和相對于其他可編程器件的優(yōu)點(diǎn)，最重要的特點(diǎn)是大容量，可重復(fù)編程，實(shí)時(shí)處理能力強(qiáng)。然后對本文研究需要使用的quartus ii軟件進(jìn)行了簡單的介紹，著重介紹了其設(shè)計(jì)流程。最后對所使用的硬件描述語言語言verilog hdl予以介紹，包括其在世界范圍內(nèi)的發(fā)展情況和主要特點(diǎn)。第三章 fft算法原理3.1 快速傅里葉變換快速傅里葉變換（fft）是cooley和tukey于1956年提出的一種離散傅里葉變換的快速計(jì)算方法

28、，它在理論上并不是一種新的變換，而是一種快速有效地計(jì)算dft的方法。dft可以為連續(xù)信號頻譜分析，實(shí)現(xiàn)快速線性卷積，計(jì)算相關(guān)函數(shù)等。但是由于dft的計(jì)算量很大，所以其并沒有得到真正的運(yùn)用。直到fft算法的提出，這種情況才得到根本的改變。fft算法使得dft計(jì)算量大大降低，運(yùn)算時(shí)間比傳統(tǒng)的dft算法縮短了一到兩個數(shù)量級，從而有力地推動了數(shù)字信號處理技術(shù)的運(yùn)用和發(fā)展7。3.2 基-2fft算法3.2.1 基-2fft算法原理 基-2fft算法是最經(jīng)典而且也是運(yùn)用最廣泛的fft算法。該算法分按時(shí)間抽?。╠it）和按頻率抽?。╠if）兩種類型，它們兩者在原理上是基本相同的。本課題采用的是dit，下面著

29、重介紹這一算法。已知長度為n的有限長序列x(n)的dft表達(dá)式為： (3-1)當(dāng)x(n)為復(fù)數(shù)序列的一般情況時(shí)，k為0到n-1的某個整數(shù)，根據(jù)（3-1）式計(jì)算x(k)的dft值分別需要n次復(fù)數(shù)乘法和(n-1)次復(fù)數(shù)加法。 那么直接計(jì)算dft需要n2次復(fù)數(shù)乘法及n(n-1)次復(fù)數(shù)加法。因?yàn)?次復(fù)數(shù)乘法中包含4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法，1次復(fù)數(shù)加法中有2次實(shí)數(shù)加法，所以做1次離散傅里葉變換需要4n2次實(shí)數(shù)乘法和n(4n-2)次實(shí)數(shù)加法。當(dāng)序列的長度n不斷增大時(shí)，所需要的運(yùn)算次數(shù)也會隨著急劇的增加，所以直接用dft算法進(jìn)行譜分析和信號的實(shí)時(shí)處理是不切實(shí)際的8。通過以上分析，n點(diǎn)dft需要的復(fù)數(shù)乘法次

30、數(shù)為n2次。如果把整個序列分解成幾個有規(guī)律的短序列，再分別計(jì)算其各個短序列的dft值，就可以使整個運(yùn)算的乘法次數(shù)減少很多；利用旋轉(zhuǎn)因子的周期性、對稱性進(jìn)行合并和歸類處理，從而減少dft的運(yùn)算量。其對稱性為： (3-2)周期性為： (3-3)式中，m為非零整數(shù)。對于基-2fft，由于n=2m，因此可以通過m次的分解最后完全轉(zhuǎn)換成2點(diǎn)的dft，最終減少dft的運(yùn)算量。根據(jù)n的值為奇、偶數(shù)將序列x(n)分解為x1(n)、x2(n)兩組子序列；用2個n/2點(diǎn)的dft來實(shí)現(xiàn)一個n點(diǎn)dft的運(yùn)算。 設(shè)一個序列x(n)的長度為n，如下式所示， (3-4)， (3-5)所以 (3-6)偶數(shù)奇數(shù) 其中k的取值范

31、圍為0，1，n-1。因?yàn)?(3-7)所以這樣就將n點(diǎn)dft分解為兩個n/2點(diǎn)的dft。由于x1(k)和x2(k)均以n/2為周期，而且 (3-8)所以又可以將x(k)表示為如下所示的表達(dá)式 (3-9) (3-10)對上式的運(yùn)算用圖3.1所示的流圖符號來表示 a b a+bca-bcc圖3.1 蝶形運(yùn)算符號假設(shè)對于一個n=8點(diǎn)的dft運(yùn)算可以根據(jù)式（3-9）、（3-10）和圖3-1,表示成圖3.2的計(jì)算方式。其中式（3-9）和（3-10）分別給出了x(0)-x(3)和x(4）-x(7)的計(jì)算方法。圖3.2 n=8點(diǎn)dft一次時(shí)域分解圖由圖3.1和3.2知，在經(jīng)過一次時(shí)域分解后，計(jì)算一個n=2m點(diǎn)

32、的fft的流程圖共有m級蝶形運(yùn)算，每級由n/2個蝶形運(yùn)算組成，每個蝶形運(yùn)算需要1次復(fù)數(shù)乘法和2次復(fù)數(shù)加法。所以計(jì)算n=2m點(diǎn)fft的共需要2(n/2)2+n/2=n(n+1)/2n2/2(n1)次復(fù)數(shù)乘法，n(n/2)+2n/2=n2次復(fù)數(shù)加法運(yùn)算。與原dft運(yùn)算比較而言，復(fù)數(shù)乘法的運(yùn)算量減少了一半，這充分說明fft算法的有效性9。第二次分解：將x1(r)按r取奇、偶可分解成2個長度為n/4的子序列l(wèi)=0,1,n/4-1 （3-11） x3(l)= x1(2l) x4(l) = x1(2l+1)根據(jù)上面推導(dǎo)可得： ,k=0,1,n/2-1 （3-12）同理將x2(r)按r取奇、偶可分解成2個長

33、n/4的子序列l(wèi)=0,1,n/4-1 （3-13） x5(l)= x2(2l) x6(l) = x2(2l+1)推導(dǎo)可得： ,k=0,1,n/2-1 （3-14）經(jīng)過兩次分解，可以將一個n/2點(diǎn)的dft再被拆分成為了兩個n/4點(diǎn)的dft。依次拆分下去，由此可知，對于n=2m點(diǎn)需要經(jīng)過m-1次分解得到n/2個2點(diǎn)dft，如圖3.3所示。圖3.3 n=8點(diǎn)dft二次時(shí)域分解圖ditfft算法與直接計(jì)算dft運(yùn)算量的比較：整個運(yùn)算流圖中有m級蝶形，每一級運(yùn)算中包含n/2個蝶形，每個蝶形需一次復(fù)數(shù)乘和兩次復(fù)數(shù)加運(yùn)算。所以，直接dft作n點(diǎn)運(yùn)算： 復(fù)數(shù)乘次數(shù)：nn=n2 復(fù)數(shù)加次數(shù)：n(n-1) （3-

34、15）用dit-fft作n點(diǎn)運(yùn)算： 復(fù)數(shù)乘次數(shù)：mn/2=n/2log2n 復(fù)加次數(shù)：2n/2m= nlog2n （3-16）假設(shè)有n=210=1024點(diǎn)數(shù)據(jù)，按照上面的分析可知直接dft運(yùn)算和dit-fft運(yùn)算所需要的乘法次數(shù)的比值是 （3-17）很明顯運(yùn)算效率提高了204倍，而且隨著數(shù)據(jù)量越多，fft算法的優(yōu)越性越直觀。在常規(guī)的n數(shù)值下，fft的運(yùn)算量比dft降低了12個數(shù)量級，可見fft大大減少了運(yùn)算次數(shù)，提高了運(yùn)算速度10。3.2.2 基-2fft算法特點(diǎn)fft算法流程圖具有以下的規(guī)律：1. 蝶形運(yùn)算每一級運(yùn)算都由n/2個蝶形運(yùn)算單元組成。2. 原位計(jì)算根據(jù)旋轉(zhuǎn)因子的對稱性、周期性特點(diǎn)

35、，fft算法通過分解長序列減少了運(yùn)算時(shí)間，原位計(jì)算（in-place computation）的運(yùn)用，使算法的空間復(fù)雜度也因?yàn)檫\(yùn)算存儲單元的減少同時(shí)得到了降低。這也是fft算法的另一個大的優(yōu)點(diǎn)11。通過原位計(jì)算，把所有數(shù)據(jù)輸入到存儲器中，經(jīng)過每一級的蝶形運(yùn)算，把該級的運(yùn)算結(jié)果仍然保存到原來的存儲器中，直到所有的數(shù)據(jù)完成。fft采用迭代算法進(jìn)行運(yùn)算后再實(shí)行原位計(jì)算。所以，通過原位計(jì)算只需要n個復(fù)數(shù)的存儲單元，這些存儲單元不僅存放輸入的原始數(shù)據(jù)，而且運(yùn)算過程中也存儲了輸出數(shù)據(jù)，優(yōu)點(diǎn)是節(jié)省系統(tǒng)的了存儲資源，降低了整個系統(tǒng)的硬件開發(fā)成本12。3. 蝶形類型隨迭代次數(shù)成倍增加在第一級的蝶形運(yùn)算中，只需要

36、一個旋轉(zhuǎn)因子，參加蝶形運(yùn)算的兩個數(shù)據(jù)點(diǎn)之間間隔為1。在第二級蝶形運(yùn)算中，需要兩種旋轉(zhuǎn)因子和，參加蝶形運(yùn)算的兩個數(shù)據(jù)點(diǎn)之間間隔為2。在第三級蝶形運(yùn)算中，需要四個旋轉(zhuǎn)因子即，參加蝶形運(yùn)算的兩個數(shù)據(jù)點(diǎn)之間間隔為4。通過分析可以發(fā)現(xiàn)，每一級蝶形運(yùn)算單元所需要的旋轉(zhuǎn)因子個數(shù)增加一倍，參加運(yùn)算的數(shù)據(jù)點(diǎn)之間的間隔也同時(shí)增大一倍。最后一級需要的旋轉(zhuǎn)因子達(dá)到n/2個，參加蝶形運(yùn)算的兩個數(shù)據(jù)點(diǎn)的間隔也最大的等于n/2。x (5)圖3.4 n=8點(diǎn)dit-fft運(yùn)算流圖x(0)x(4)x(2)x(6)x(1)x(5)x(3)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x (0)x (1)x

37、 (2)x (3)x (4)x (6)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)x(7)l=1l=2l=3x (7)x3(0)x1(0)對于一個n=8點(diǎn)的dit-fft通過圖3.4可以發(fā)現(xiàn)，第l級共有個不同的旋轉(zhuǎn)因子，分別表示如下：第一級：l=1，有1個旋轉(zhuǎn)因子：，j=0 （3-18）第二級：l=2，有2個旋轉(zhuǎn)因子：，j=0,1 （3-19）第三級：l=3，有4個旋轉(zhuǎn)因子：，j=0,1,2,3 （3-20）對于n的一般情況，第l級共有個不同的旋轉(zhuǎn)因子： ，j=0,1,2,-1 （3-21） （3-22） ，j=0,1,2,-1 （3-23）4. 序數(shù)重排輸入數(shù)據(jù)x(

38、n)是按照新的次序重排的。將按照自然順序輸入的數(shù)據(jù)的次序用二進(jìn)制表示，從二進(jìn)制的最高位到最低位依次交換位置，即把一個二進(jìn)制數(shù)實(shí)現(xiàn)反轉(zhuǎn)。在實(shí)際運(yùn)算當(dāng)中，直接將輸入數(shù)據(jù)x(n)按照位反轉(zhuǎn)的順序排好輸入是很不方便的。所以通常情況下是先將數(shù)據(jù)按自然順序輸入，然后采用變址尋址算法去尋找相應(yīng)單元的x(n)，這叫做“順序輸入，逆序輸出”。現(xiàn)在設(shè)計(jì)很多fft的處理器均具有這種按位反轉(zhuǎn)的尋址功能13。表3.1順序和倒序二進(jìn)制數(shù)對照表順序倒序十進(jìn)制數(shù)i二進(jìn)制數(shù)二進(jìn)制數(shù)十進(jìn)制數(shù)j01234567000001010011100101110111000100010110001101011111042615373.3 本

39、章小結(jié)本章節(jié)主要介紹了基-2fft算法的原理方法。在稍微介紹快速傅里葉變換的概念和內(nèi)容之后，重點(diǎn)介紹了基-2fft算法，其中包括算法的原理、算法實(shí)現(xiàn)。基-2fft算法是最經(jīng)典且最簡單的fft算法。該算法分按時(shí)間抽?。╠it）和按頻率抽?。╠if）兩種類型，兩者的基本原理是等價(jià)的，可以相互轉(zhuǎn)化得到。本課題采用的是dit-fft。然后對fft算法的主要特點(diǎn)：蝶形運(yùn)算單元、原位計(jì)算、迭代次數(shù)和序數(shù)重排進(jìn)行了討論。通過分析驗(yàn)證fft算法相對于dft算法在計(jì)算量方面巨大的優(yōu)越性。fft算法使dft得計(jì)算量大為降低，有力地推動了傅里葉變換在數(shù)字信號處理技術(shù)的應(yīng)用和發(fā)展。第四章 fft的fpga實(shí)現(xiàn)4.1

40、整體結(jié)構(gòu)設(shè)計(jì)隨著集成電路制造工藝的不斷發(fā)展，fpga內(nèi)部的可編程邏輯資源越來越豐富。特別是ram和rom容量的增加，使得系統(tǒng)的可編程設(shè)計(jì)更加容易，也使得系統(tǒng)的實(shí)時(shí)處理性能得到了很大的提高。本文中采用的基-2fft設(shè)計(jì)主要由以下模塊組成：輸入輸出處理單元、邏輯控制單元、蝶形運(yùn)算單元、移位處理單元、溢出控制單元、旋轉(zhuǎn)因子存儲文件。如圖4.114。溢出控制單元fft運(yùn)算ram2蝶形運(yùn)算單元邏輯控制單元旋轉(zhuǎn)因子romfft運(yùn)算ram1輸出處理單元輸入處理單元圖4.1 fft工作流程圖根據(jù)fft的工作流程圖，先用硬件描述語言完成各個子模塊的功能，測試正確后再設(shè)計(jì)頂層模塊調(diào)用已完成的子模塊，從而實(shí)現(xiàn)整個系

41、統(tǒng)的功能。4.2 蝶形運(yùn)算單元從第三章fft算法原理中可以看到，蝶形運(yùn)算單元是整個fft算法的核心模塊。根據(jù)fft的算法原理公式可以得出圖4.2的蝶形單元示意圖15。z=a+bwz=a-bwabw圖4.2蝶形運(yùn)算單元示意圖圖中a和b表示兩個輸入的復(fù)數(shù)數(shù)據(jù)，表示旋轉(zhuǎn)因子，和表示蝶形輸出。 （4-1） （4-2） （4-3）所以對于兩點(diǎn)fft的計(jì)算過程根據(jù)復(fù)數(shù)運(yùn)算規(guī)則，可以得到： （4-4） （4-5）由式（4-4）和（4-5）可以發(fā)現(xiàn)，蝶形運(yùn)算單元將復(fù)數(shù)的運(yùn)算最終通過實(shí)數(shù)的運(yùn)算來完成。其中涉及到加法器和乘法器的協(xié)同工作，實(shí)數(shù)加法比較簡單，所以直接用硬件描述語言中的算術(shù)運(yùn)算符描述，而實(shí)數(shù)乘法相對比

42、較復(fù)雜，但是quartus ii軟件中提供了模塊化的乘法器可以直接調(diào)用，既保證了功能的正確性又提高了運(yùn)算效率，縮短了設(shè)計(jì)時(shí)間，這在eda設(shè)計(jì)中是經(jīng)常用到的。如圖4.3。圖4.3 quartus ii軟件中的乘法器模塊將蝶形運(yùn)算單元模塊的端口定義如下：module bfly_r2dit (rst, clk,din_av,out_enb,ar, ai,br,bi,wr,wi,xr, xi,yr,yi);其中：clk 外部輸入時(shí)鐘信號rst 復(fù)位信號din_av 輸入使能信號out_enb 輸出使能信號ar,ai,br,bi分別是兩個輸入的復(fù)數(shù)數(shù)據(jù)的實(shí)部和虛部，wr,wi是旋轉(zhuǎn)因子的實(shí)部和虛部xr,

43、xi,yr,yi 分別是蝶形運(yùn)算單元的兩個輸出的實(shí)部和虛部部分設(shè)計(jì)代碼如下：wire 19:0 cr, ci;assign cr =real_cos_reg - image_sin_reg;assign ci = image_cos_reg +real_sin_reg;wire 20:0 xr_c,xi_c,yr_c,yi_c;assign xr_c = ar_d1t9,ar_d1t9,ar_d1t,9b0_0000_0000 + cr19,cr ;assign xi_c = ai_d1t9,ai_d1t9,ai_d1t,9b0_0000_0000 + ci19,ci ;assign yr_c

44、 = ar_d1t9,ar_d1t9,ar_d1t,9b0_0000_0000 - cr19,cr ;assign yi_c = ai_d1t9,ai_d1t9,ai_d1t,9b0_0000_0000 - ci19,ci ;因?yàn)檫\(yùn)算過程中會出現(xiàn)數(shù)據(jù)溢出情況，所以在設(shè)計(jì)中充分考慮了這一點(diǎn)做了適當(dāng)?shù)奶幚?。最終完成的蝶形運(yùn)算單元模塊如圖4.4。圖4.4 蝶形運(yùn)算單元模塊圖4.5 蝶形運(yùn)算單元仿真波形圖4.5是蝶形運(yùn)算單元的仿真波形圖。其中real_sin，real_cos，image_sin，image_cos分別是四個實(shí)數(shù)乘法器的結(jié)果。當(dāng)a=1+2j，b=3+2j，w=8+3j時(shí)表示的復(fù)數(shù)乘法為

45、：(3+2j)(8+3j)=(24-6)+(16+9)j （4-6）所得的結(jié)果與仿真結(jié)果完全符合，可見設(shè)計(jì)的蝶形運(yùn)算單元是正確的。4.3 邏輯控制及其他輔助單元4.3.1 邏輯控制單元邏輯控制單元是整個系統(tǒng)的控制核心。它的主要功能是產(chǎn)生存儲器地址、溢出單元控制和其他各個模塊之間的邏輯控制。各個單元之間的協(xié)同工作主要就是邏輯控制單元完成的。因?yàn)楸疚脑O(shè)計(jì)中使用了雙端口ram，所以設(shè)計(jì)中在前一段時(shí)鐘信號讀取前一級ram中的數(shù)據(jù)，在后一段時(shí)鐘信號中讀取后一級ram中的數(shù)據(jù)，運(yùn)算的結(jié)果再被存入ram中供下一次讀取。設(shè)計(jì)中定義了10:0 frame_in_cnt來計(jì)數(shù)已經(jīng)輸入的數(shù)據(jù)個數(shù)。通過下一段語句：a

46、lways (posedge rst or posedge clk) begin if(rst) frame_in_cnt_enb = 1b0; else if(frame_in_eop) frame_in_cnt_enb = 1b0; else if(frame_in_enb & frame_in_sop) frame_in_cnt_enb = 1b1;end/ input switch controlassign frame_input_on = frame_in_sop | frame_in_cnt_enb;/ fram_in_cntalways (posedge rst or pose

47、dge clk) begin if(rst) frame_in_cnt = 11h0; / point=2048 else if(frame_in_enb & frame_input_on) frame_in_cnt = frame_in_cnt + 1b1;endassign frame_in_eop = (frame_in_cnt=11h7ff); / 211=2048完成全部的數(shù)據(jù)輸入。另外，邏輯控制單元還對每級蝶形運(yùn)算的輸出結(jié)果進(jìn)行判斷，根據(jù)輸出數(shù)據(jù)的高兩位，當(dāng)高兩位不相等時(shí)表示數(shù)據(jù)溢出，所以將數(shù)據(jù)進(jìn)行縮小處理，最終輸出數(shù)據(jù)時(shí)再做適當(dāng)?shù)姆糯蟊ＷC數(shù)據(jù)的準(zhǔn)確性。最終完成的邏輯控制單元模塊如

48、圖4.6。圖4.6 邏輯控制單元模塊4.3.2 其他輔助模塊在整個fft系統(tǒng)中，不僅需要蝶形運(yùn)算單元對數(shù)據(jù)進(jìn)行計(jì)算，還需要其他的模塊進(jìn)行進(jìn)一步的處理，這其中最重要的就是移位處理和溢出控制。移位處理模塊的端口定義如圖4.7。圖4.7 移位處理單元模塊其中，up_in_real, up_in_image, dn_in_real, dn_in_image分別是上一級和下一級ram中的復(fù)數(shù)的實(shí)部和虛部輸入。up_out_real, up_out_image, dn_out_real, dn_out_image分別是進(jìn)行移位操作后的復(fù)數(shù)實(shí)部和虛部輸出。溢出控制模塊的端口定義如圖4.8。圖4.8 溢出控制

49、單元模塊其中，xr_h3,xi_h3,yr_h3,yi_h3是輸入的需要判斷的數(shù)據(jù)，shift_ctrl是移位輸出控制信號。部分代碼如下：always (posedge rst or posedge clk) begin if(rst) shift_ctrl = 2b00; else if(shift_ctrl_clr) shift_ctrl = 2b00; else if(wr_stage_cmplt) shift_ctrl = of_flg1 ? 2b10 : of_flg;end4.4 存儲單元對于整個fft系統(tǒng)，存儲器是必不可少的組成部分。在蝶形運(yùn)算單元中，所有原始數(shù)據(jù)輸入、運(yùn)算的中間

50、結(jié)果和輸出結(jié)果都需要ram存儲，對存儲器的讀寫操作速度很大程度上決定了整個系統(tǒng)的運(yùn)行速度。所以本文設(shè)計(jì)的是雙端口ram調(diào)用。另外，旋轉(zhuǎn)因子的實(shí)部和虛部也需要rom存儲。在本文設(shè)計(jì)中共使用了兩組ram存儲器模塊交替讀寫數(shù)據(jù)。這樣設(shè)計(jì)的優(yōu)點(diǎn)是，先將所有數(shù)據(jù)存入第一個ram中，然后經(jīng)過第一級運(yùn)算后存入第二個ram中。在進(jìn)行第二級運(yùn)算時(shí)，先將數(shù)據(jù)從第二個ram中讀出，進(jìn)過計(jì)算后再存入第一個ram中，如此循環(huán)m次。這樣流水線式的處理可以很大的提高運(yùn)算速度。下面介紹雙端口ram的實(shí)現(xiàn)過程。在quartus ii軟件中為設(shè)計(jì)者提供了種類豐富的宏功能模塊，利用宏功能模塊可以極大地提高電路的設(shè)計(jì)可靠性和效率。這

51、里調(diào)用lpm_ram_dp模塊設(shè)計(jì)雙端口ram，如圖4.9所示。圖4.9 quartus ii中的lpm_ram_dp模塊數(shù)據(jù)線、地址線寬度設(shè)置如圖4.10所示。然后很據(jù)系統(tǒng)的設(shè)計(jì)要求，對ram其他參數(shù)進(jìn)行配置，最后完成雙端口ram的設(shè)計(jì)，如圖4.11所示。圖4.10 數(shù)據(jù)線和地址線寬度設(shè)置圖4.11 基于lpm_ram_dp的雙端口ram模塊旋轉(zhuǎn)因子是一個復(fù)數(shù)，在本設(shè)計(jì)中采用兩個rom分別存儲實(shí)部和虛部的方法，因?yàn)樗鼈兌际切∮?的小數(shù)，所以需要將數(shù)據(jù)定點(diǎn)化，處理的方式是擴(kuò)大512倍，而且根據(jù)旋轉(zhuǎn)因子的周期性可知，2048點(diǎn)數(shù)據(jù)只需要計(jì)算出512個旋轉(zhuǎn)因子就可以滿足計(jì)算要求，其余的旋轉(zhuǎn)因子可以

52、根據(jù)周期性由算法推導(dǎo)出。這樣的好處是可以降低存儲器的數(shù)量，降低開發(fā)成本。將已經(jīng)計(jì)算好的旋轉(zhuǎn)因子用quartus ii軟件中的.mif文件固化在其中如圖4.12，然后在設(shè)計(jì)rom的時(shí)候?qū)?mif文件載入，完成旋轉(zhuǎn)因子rom的設(shè)計(jì)，如圖4.13。圖4.12 旋轉(zhuǎn)因子rom的mif文件圖4.13 旋轉(zhuǎn)因子rom模塊4.5 串口通信單元在本文設(shè)計(jì)的fft系統(tǒng)中，通過串口程序?qū)崿F(xiàn)數(shù)據(jù)的輸入與輸出處理。串行輸入以每次輸入一位有效數(shù)據(jù)的方式傳輸，在數(shù)據(jù)傳輸之前需要對數(shù)據(jù)進(jìn)行“格式化”處理，即加上起始位（通常為低電平）、有效數(shù)據(jù)內(nèi)容、校驗(yàn)位、結(jié)束位（通常為高電平），形成一幀數(shù)據(jù)如圖4.14。發(fā)送數(shù)據(jù)時(shí)先發(fā)送幀數(shù)據(jù)的最低有效位，最后發(fā)送幀數(shù)據(jù)的最高有效位。在數(shù)據(jù)接受端，使用和發(fā)送端相同的采樣頻率對輸入內(nèi)容進(jìn)行采樣，然后轉(zhuǎn)換為發(fā)送端的原始數(shù)據(jù)。用波特率（baud r