基于ModelSim的FFT算法的設(shè)計(jì)論文

1、基于ModelSim的FFT算法的設(shè)計(jì)學(xué)士學(xué)位論文摘 要快速傅立葉變換(FFT)作為時(shí)域和頻域轉(zhuǎn)換的基本運(yùn)算，是數(shù)字譜分析的必要前提。傳統(tǒng)的FFT使用軟件或DSP實(shí)現(xiàn)，高速處理時(shí)實(shí)時(shí)性較難滿足，因此專用集成電路(ASIC)和可編程邏輯器件(以現(xiàn)場可編程門陣列FPGA為代表)應(yīng)運(yùn)而生。速度上ASIC更占優(yōu)勢，但是隨著點(diǎn)數(shù)的增加，芯片面積將迅速擴(kuò)大，也就意味著成本的提高。而FPGA部含有硬件乘法器，大量的存儲單元和可編程I/O，十分適合于FFT處理器的實(shí)現(xiàn)，而且相對ASIC，成本低廉，可以反復(fù)編程，便于調(diào)試，也更具市場競爭力。本文應(yīng)用Verilog語言完成32點(diǎn)基-2復(fù)數(shù)的FFT處理系統(tǒng)設(shè)計(jì)，包括

2、蝶形運(yùn)算單元設(shè)計(jì)、存儲單元設(shè)計(jì)、塊浮點(diǎn)單元設(shè)計(jì)、地址產(chǎn)生單元設(shè)計(jì)、功能切換單元設(shè)計(jì)以與時(shí)序控制單元的設(shè)計(jì)工作。以選取的FPGA器件庫為基礎(chǔ)，使用modelsim軟件進(jìn)行仿真，并對結(jié)果進(jìn)行分析。關(guān)鍵詞：快速傅立葉變換；Verilog；單元設(shè)計(jì)；modelsim仿真57 / 62AbstractFast Fourier Transform is a necessary precondition of digital spectral analysis as the basic computing between the time domain and frequency domain. The t

3、raditional FFT uses software or DSP to realize, which is difficult to meet real-time in high speed processing. Application specific integrated circuit (ASIC) and programmable logic device (represented by field programmable gate array, FPGA) arises at the historic moment. ASIC has the advantage in th

4、e speed, but the chip area will expand rapidly with the processing points increasing, which means the improvement of costs. While FPGA contains hardware multipliers, massive memory cells and programmable I/O, so it is very suitable for implementation of FFT processor. Therefore, FPGA is low-cost, ea

5、sy to debug and can be repeatedly programmed. It has more market competitiveness.Use Verilog language completed 32 points 2 complex FFT processing system design, Including butterfly computing unit design, storage unit design, block floating-point unit design, the address generation unit design, the

6、function switch unit design and timing control unit design work . On the basis of the selected library as the FPGA device, use the modelsim simulation software, and analyze the results.Key Words:FFT;Verilog;Unit design;modelsim simulation目 錄1 緒論11.1課題的背景與意義11.2 FFT的國外發(fā)展研究現(xiàn)狀21.2.1 通用數(shù)字信號處理芯片21.2.2 專用

7、集成電路芯片ASIC31.2.3 可編程邏輯器件31.3 篇章結(jié)構(gòu)52 離散福利葉變換的快速算法的基本理論62.1 基-2FFT算法62.2 定點(diǎn)數(shù)的相關(guān)概念152.2.1 定點(diǎn)數(shù)的定義152.2.2 定點(diǎn)數(shù)加減法的溢出與檢測方法152.3 定點(diǎn)數(shù)的定標(biāo)162.4 有限字長效應(yīng)162.5 塊浮點(diǎn)數(shù)173 FFT的算法設(shè)計(jì)183.1 FFT處理器的實(shí)現(xiàn)框圖183.2 蝶形運(yùn)算單元的設(shè)計(jì)183.3 流水線結(jié)構(gòu)253.4 存儲單元的設(shè)計(jì)263.4.1 FFT數(shù)據(jù)存取規(guī)律分析263.4.2 雙口RAM與其地址發(fā)生器的設(shè)計(jì)273.4.3 ROM 與其地址發(fā)生器的設(shè)計(jì)303.5 浮點(diǎn)單元的設(shè)計(jì)333.6

8、時(shí)序控制單元的設(shè)計(jì)384 基于verilog語言的FFT的設(shè)計(jì)與仿真404.1 ModelSim介紹404.2 ModelSim仿真404.2.1 建立工程414.2.2 加載文件414.2.3 開始仿真424.3 結(jié)果分析44結(jié) 論46致 47參考文獻(xiàn)48附錄 A 英文原文50附錄 B 漢語翻譯551緒論1.1課題的背景與意義隨著數(shù)字技術(shù)與計(jì)算機(jī)技術(shù)的發(fā)展，數(shù)字信號處理（Digital Signal Processing，DSP）技術(shù)已深入到各個(gè)學(xué)科領(lǐng)域，其應(yīng)用又是多種多樣，但數(shù)字信號處理基本上從兩個(gè)方面來解決信號的處理問題：一個(gè)是時(shí)域方法，即數(shù)字濾波；另一個(gè)是頻域方法，即頻譜分析。處理的任

9、務(wù)大致分為三類:卷積用于各種濾波器，對給定頻率圍的原始信號進(jìn)行加工（通過或?yàn)V出）來提高信噪比；相關(guān)用于信號比較，分析隨機(jī)信號的功率譜密度；變換用于分析信號的頻率組成，對信號進(jìn)行識別。其中，離散傅立葉變換（Discrete-time Fourier Transform，DFT）和卷積是信號處理中兩個(gè)最基本也是最常用的運(yùn)算，它們涉與到信號與系統(tǒng)的分析與綜合這一廣泛的信號處理領(lǐng)域。由數(shù)字信號處理的基本理論可知，卷積可以轉(zhuǎn)化為DFT來實(shí)現(xiàn)，實(shí)際上其他許多算法，如相關(guān)、譜分析等也都可以轉(zhuǎn)化DFT來實(shí)現(xiàn)；此外，各種系統(tǒng)的分析、設(shè)計(jì)和實(shí)現(xiàn)中都會用到DFT的計(jì)算問題。所以，DFT在各種數(shù)字信號處理中起著核心作

10、用，而DFT的快速算法快速傅立葉變換(Fast Fourier Transform，F(xiàn)FT)就成為了數(shù)字信號處理的最基本技術(shù)之一，對FFT算法與其實(shí)現(xiàn)方式的研究是很有意義的。目前，F(xiàn)FT廣泛應(yīng)用在頻譜分析、匹配濾波、數(shù)字通信、圖像處理、語音識別、雷達(dá)處理、遙感遙測、地質(zhì)勘探和無線通訊等眾多領(lǐng)域。在不同應(yīng)用場合，需要不同性能要求的FFT處理器。在很多應(yīng)用領(lǐng)域都要求FFT處理器具有高速度、高精度、大容量和實(shí)時(shí)處理的性能。因此，如何更快速、更靈活地實(shí)現(xiàn)FFT變得越來越重要。此外，數(shù)字濾波在圖像處理、語音識別和模式識別等數(shù)字信號處理中占有重要地位。與模擬濾波器相比，數(shù)字濾波器可以滿足濾波器幅度和相位特

11、性的嚴(yán)格要求，可以克服模擬濾波器所無法克服的電壓漂移、溫度漂移和噪聲等問題。有限沖激響應(yīng)（FIR）濾波器可以保證嚴(yán)格的線性相位。同時(shí)由于其實(shí)現(xiàn)結(jié)構(gòu)主要是非遞歸的，因此FIR濾波器可以穩(wěn)定工作。FIR濾波器被廣泛用于各類數(shù)字信號處理系統(tǒng)中實(shí)現(xiàn)卷積、相關(guān)、自適應(yīng)濾波、正交插值等處理。隨著數(shù)字信號處理技術(shù)的發(fā)展，在消費(fèi)電子領(lǐng)域要求處理速度更快、功耗更低、集成度更高和產(chǎn)品開發(fā)周期更短，因此許多數(shù)字信號處理的實(shí)現(xiàn)方法被不斷提出，其中基于FPGA的數(shù)字信號處理實(shí)現(xiàn)技術(shù)就是其中的重要技術(shù)之一。近幾年，隨著現(xiàn)場可編程門陣列FPGA技術(shù)的迅速發(fā)展，采用并行度更大、速度更快的FPGA芯片來實(shí)現(xiàn)FFT和FIR數(shù)字濾

12、波器己成為必然趨勢。FPGA技術(shù)的關(guān)鍵就是利用強(qiáng)有力的設(shè)計(jì)工具來縮短開發(fā)周期，提供元器件的優(yōu)質(zhì)利用性，降低設(shè)計(jì)成本，并能夠并行處理數(shù)據(jù)，容易實(shí)現(xiàn)流水線結(jié)構(gòu)，且升級簡便，提高設(shè)計(jì)的靈活性，這些都非常適合實(shí)現(xiàn)FFT算法和FIR數(shù)字濾波器。因此，自主研發(fā)基于FPGA芯片的FFT和FIR數(shù)字濾波器，把FFT和FIR數(shù)字濾波器實(shí)時(shí)性的要求和FPGA芯片設(shè)計(jì)的靈活性結(jié)合起來，實(shí)現(xiàn)并行算法與硬件結(jié)構(gòu)的優(yōu)化配置，提高FFT和FIR數(shù)字濾波器處理速度，滿足現(xiàn)代信號處理的高速度、高可靠性要求，成為了現(xiàn)今我國數(shù)字信號處理的一個(gè)研究點(diǎn)。鑒于此種趨勢，作者將基于FPGA的FFT和FIR數(shù)字濾波器設(shè)計(jì)與實(shí)現(xiàn)作為了研究課題

13、。1.2 FFT的國外發(fā)展研究現(xiàn)狀針對FFT和FIR數(shù)字濾波器的硬件實(shí)現(xiàn)方案主要有三種途徑：DSP處理器、專用集成電路ASIC、可編程邏輯器件，其中可編程邏輯器件以FPGA為代表。1.2.1通用數(shù)字信號處理芯片通用數(shù)字信號處理芯片即DSP處理器，按照DSP的用途，可分為通用型DSP芯片和專用型DSP芯片。通用型DSP芯片適合普通的DSP應(yīng)用，通用DSP芯片具有接口靈活、編程方便、穩(wěn)定性好、運(yùn)算精度高等特點(diǎn)，同時(shí)也更適應(yīng)于大規(guī)模集成電路如TI公司的一系列DSP芯片屬于通用型DSP芯片。專用DSP芯片是為特定的DSP運(yùn)算而設(shè)計(jì)的，更適合特殊的運(yùn)算，如數(shù)字濾波、卷積和FFT，如Motorola公司的

14、DSP56200，Zoran公司的ZR34881，Inmos公司的IMSA100等就屬于專用型DSP芯片。針對一般數(shù)字信號處理算法的實(shí)現(xiàn)，采用通用可編程硬件處理器技術(shù)來實(shí)現(xiàn)FFT和FIR數(shù)字濾波器。這種實(shí)現(xiàn)方法具有軟件設(shè)計(jì)多用性的優(yōu)點(diǎn)，能夠適用于各種需要FFT運(yùn)算和FIR數(shù)字濾波器進(jìn)行信號處理的應(yīng)用場合，靈活方便。但是，通用DSP處理器構(gòu)成的FFT處理器和FIR數(shù)字濾波器采用循環(huán)編碼算法，程序量小，但存在大量的冗余運(yùn)算，需要許多跳轉(zhuǎn)操作，處理速度較慢，難以滿足現(xiàn)代數(shù)字信號處理高速、大規(guī)模、實(shí)時(shí)性的要求。在進(jìn)行大點(diǎn)數(shù)FFT計(jì)算和FIR數(shù)字濾波時(shí)，并行算法與DSP處理器的尋址能力不相適應(yīng)，不能有效

15、利用數(shù)據(jù)傳輸?shù)膸捄瓦\(yùn)算能力，造成硬件資源的浪費(fèi)。1.2.2專用集成電路芯片ASIC在集成電路界ASIC被認(rèn)為是一種為專門目的而設(shè)計(jì)的集成電路。是指應(yīng)特定用戶要求和特定電子系統(tǒng)的需要而設(shè)計(jì)、制造的集成電路。ASIC在一些特殊功能的表現(xiàn)上相當(dāng)好，這種方案運(yùn)算速度快，可靠性高，非常適合實(shí)時(shí)和對可靠性要求較高的信號處理系統(tǒng)，在批量生產(chǎn)時(shí)與通用集成電路相比具有體積更小、功耗更低、可靠性提高、性能提高、性增強(qiáng)、成本降低等優(yōu)點(diǎn)，但是專用芯片不能重新組態(tài)，可編程能力有限，在產(chǎn)品發(fā)展過程中，它的功能無法任意修改或改進(jìn)。因此，任何的線路改版都需要重新設(shè)計(jì)并且重新制造，這不僅增加開發(fā)成本，而且造成產(chǎn)品快速上市的障

16、礙，不太適合處理算法和參數(shù)經(jīng)常改變的場合。1.2.3可編程邏輯器件可編程邏輯器件以其獨(dú)特的優(yōu)越性能，一出現(xiàn)就受到大家的青睞。它不僅速度快、集成度高，并且?guī)缀跄茈S心所欲的完成定義的邏輯功能，還可以加密和重新編程，其編程次數(shù)可以達(dá)到1萬次以上。使用可編程邏輯器件可以大大簡化硬件系統(tǒng)，降低成本，提高系統(tǒng)的可靠性、靈活性和性。因此，可編程邏輯器件是設(shè)計(jì)數(shù)字系統(tǒng)的理想器件?，F(xiàn)在已廣泛用于計(jì)算機(jī)硬件、工業(yè)控制、智能儀表、通信設(shè)備和醫(yī)療電子儀器等多個(gè)領(lǐng)域?？删幊踢壿嬈骷膽?yīng)用不僅使電子產(chǎn)品性能有了很大改善，而且也使數(shù)字系統(tǒng)設(shè)計(jì)方法發(fā)生了根本性變革。其中，現(xiàn)場可編程門列陣（FPGA）是最近幾年發(fā)展起來的新型高

17、密度可編程邏輯器件?，F(xiàn)場可編程門陣列（FPGA）是20世紀(jì)80年代中期由美國Xilinx公司首先推出的大規(guī)模可編程邏輯器件。由于FPGA器件采用標(biāo)準(zhǔn)化結(jié)構(gòu)，并且具有體積小、集成度高、功耗低、速度快、可無限次反復(fù)編程等特點(diǎn)，已成為開發(fā)電子產(chǎn)品的首選器件。FPGA的功能由邏輯結(jié)構(gòu)的配置數(shù)據(jù)決定。工作時(shí)，這些配置數(shù)據(jù)存放在片的SRAM或者熔絲圖上。使用無SRAM的FPGA，在工作前需要從芯片外部加載配置數(shù)據(jù)。配置數(shù)據(jù)可以存儲在片外的EPROM或其他存儲體上，人們可以控制加載過程，在現(xiàn)場修改器件的邏輯功能，即所謂現(xiàn)場編程。世界上第一片F(xiàn)PGA由美國Xilinx公司于1985年發(fā)明，因而FPGA技術(shù)在國

18、外發(fā)展較早，隨著FPGA技術(shù)的普與，使用FPGA芯片設(shè)計(jì)正在世界圍興起。國外已積極地開展了基于FPGA的數(shù)字信號處理算法應(yīng)用與研究，并且也取得了長足的進(jìn)步。目前在國際上，兩大FPGA巨頭Xilinx和Altera除了FPGA的生產(chǎn)外還與其第三方合作伙伴致力于IP核的開發(fā)。這些IP核中包含了基本的數(shù)字信號處理模塊，如FFT、FIR等。由于FPGA芯片廠商對自己公司生產(chǎn)的芯片的性能非常了解，因此設(shè)計(jì)的模塊能最大限度的發(fā)揮芯片的性能。目前Altera公司提供的FFT模塊采用4引擎結(jié)構(gòu)，在實(shí)現(xiàn)1024點(diǎn)FFT時(shí)所需時(shí)間己經(jīng)降至很低。使用IP核構(gòu)建數(shù)字信號處理系統(tǒng)具有諸多優(yōu)點(diǎn)，如開發(fā)周期短、性能穩(wěn)定、可

19、靠、維護(hù)方便等。但也存在以下的缺點(diǎn)：IP核價(jià)格昂貴（Altera公司的FFTIP核售價(jià)為7995美元），且IP核源代碼不對外開放，不利于二次開發(fā)；IP核針對通用的設(shè)計(jì)，在某些特殊的應(yīng)用場合不一定最優(yōu)因此還難以在我國基層應(yīng)用領(lǐng)域普與。國方面，我國的FPGA技術(shù)起步較晚，但是進(jìn)入21世紀(jì)后，發(fā)展非常迅速。目前不少大學(xué)與研究所都使用FPGA芯片設(shè)計(jì)開發(fā)具有自主知識產(chǎn)權(quán)的FFT和FIR數(shù)字濾波器，但是由于起步較晚，基礎(chǔ)薄弱，所設(shè)計(jì)的FFT和FIR數(shù)字濾波器無論是速度，還是可擴(kuò)展性上都與國外有一定差距。2002年羅雪茍、詹陽分析了使用FPGA實(shí)現(xiàn)FFT的幾種方法，對這幾種方法的優(yōu)缺點(diǎn)進(jìn)行了討論。2003

20、年穎等采用Xilinx公司的FPGA設(shè)計(jì)了FFT處理器。采用流水方式對復(fù)數(shù)數(shù)據(jù)實(shí)現(xiàn)了加窗、FFT、求模平方三種運(yùn)算，整個(gè)設(shè)計(jì)使用雙基-2蝶形運(yùn)算單元，采用流水線方式盡量避免瓶頸的出現(xiàn)，提高了系統(tǒng)時(shí)鐘頻率。2004年國棟等也使用基2算法設(shè)計(jì)了FFT單元，他使用了ALTERA高性能的Stratix器件對512點(diǎn)、1024點(diǎn)、2048點(diǎn)、4096點(diǎn)和8192點(diǎn)都進(jìn)行了分析。2004年魯欣等也設(shè)計(jì)了4096點(diǎn)FFT，但是他使用了1024點(diǎn)的FFTIP核進(jìn)行了擴(kuò)展設(shè)計(jì)，如果系統(tǒng)輸入時(shí)鐘為50MHz，計(jì)算時(shí)間為0.577ms。2008年在爽、盧瑩瑩對FPGA實(shí)現(xiàn)FIR數(shù)字濾波器也進(jìn)行研究，討論了乘累加和基

21、于CSD（Canonic signed Digital，標(biāo)準(zhǔn)有符號數(shù)）編碼的數(shù)字濾波器的設(shè)計(jì)。1.3篇章結(jié)構(gòu)本文主要針對基-2順序處理的FFT處理器和FIR數(shù)字濾波器的FPGA實(shí)現(xiàn)進(jìn)行了研究，涉與算法選取、處理器結(jié)構(gòu)設(shè)計(jì)、系統(tǒng)仿真、FPGA實(shí)現(xiàn)和系統(tǒng)測試。本論文共5章，各章的具體容如下：第1章闡述了硬件實(shí)現(xiàn)的國外現(xiàn)狀與選題的意義和論文容。第2章為離散福利葉變換的快速算法的基本理論；第3章為基于modelsim的FFT算法的設(shè)計(jì)第4章為基于verilog語言的32點(diǎn)基-2復(fù)數(shù)的FFT的設(shè)計(jì)與仿真最后一章為結(jié)論最后對整篇論文進(jìn)行了總結(jié)和討論。2離散福利葉變換的快速算法的基本理論本章主要介紹了基-2

22、FFT算法和用硬件實(shí)現(xiàn)數(shù)字信號處理算法所涉與到的幾個(gè)基本問題。2.1 基-2FFT算法1、概述 長度為N的有限長序列x(n)的DFT的表達(dá)式為1：(2.1) x(n)在一般情況下是為復(fù)數(shù)序列的。如果直接按(2.1)式計(jì)算X(k)值，那么對于某一個(gè)k值而言需要N次復(fù)數(shù)乘法和m-1次復(fù)數(shù)加法。那么對于N個(gè)k值，一共需要N2次復(fù)數(shù)乘法以與N(N-1)次復(fù)數(shù)加法運(yùn)算。當(dāng)N>>1時(shí)，N(N-1)N2。從上面的說明中可以看出，N點(diǎn)DFT的乘法和加法運(yùn)算次數(shù)均與N2成正比。當(dāng)N較大時(shí)，運(yùn)算量是十分龐大的。如果N取1024，那么N2將達(dá)到1,048,576。如此巨大的計(jì)算量對于實(shí)時(shí)信號處理來說其運(yùn)

23、算速度是難以達(dá)到的。所以要想使得DFT在各種科學(xué)和工程計(jì)算中得到廣泛的應(yīng)用就必須想辦法減少其運(yùn)算量。在前面已經(jīng)講到，N點(diǎn)DFT的復(fù)乘次數(shù)等于N2。其實(shí)一個(gè)N點(diǎn)DFT可以看做是由幾個(gè)較短的DFT組成的。基于這一思想，可以將N點(diǎn)DFT分解為幾個(gè)較短的DFT，這樣一來乘法次數(shù)將大大減少，能夠非常明顯地降低DFT的運(yùn)算量。此外，旋轉(zhuǎn)因子wmN具有明顯的周期性和對稱性。其周期性表現(xiàn)為：(2.2)其對稱性表現(xiàn)為或者（2.3）不斷的把長序列的DFT分解成幾個(gè)短序列的DFT，并且利用的周期性和對稱性來減少DFT的運(yùn)算次數(shù)，這就是FFT算法的基本思想。比較常用的FFT算法有基-2FFT和基-4FFT兩種。基-2

24、FFT中的基2指的是N=2M，即有限長序列的長度N要到等于2的整數(shù)次冪；同理可得基-4FFT中的基4指的是有限長序列的長度N要到等于4的整數(shù)次冪。下面就以8點(diǎn)的FFT為例詳細(xì)分析基-2FFT算法。2、基-2FFT算法基本原理 基-2FFT算法基本上分為時(shí)域抽取法FFT(DIT-FFT)和頻域抽取法FFT(DIF-FFT)兩大類。由于這兩種算法的基本原理是一樣的，所以下面主要介紹DIT-FFT算法。本課題采用的就是DIT-FFT這一算法。 設(shè)序列x(n)的長度為N，并且有以下的條件成立N=2M，M為自然數(shù)(r)和(r)是x(n)按n的奇偶性分解成的兩個(gè)N/2點(diǎn)的子序列，如下式所示那么x(n)的D

25、FT為由于所以（2.4）其中和分別為和的N/2點(diǎn)DFT，即（2.5）（2.6）又由于和都是以N/2為周期，且所以X(k)又可以表示為如下所示的表達(dá)式（2.7）（2.8） 這樣一個(gè)N點(diǎn)的DFT就被拆分成為了兩個(gè)N/2點(diǎn)的DFT。式(2.7)和式(2.8)說明了原N點(diǎn)的DFT和這兩個(gè)N/2點(diǎn)的DFT之間的關(guān)系。通常為了后續(xù)說明的方便，和其它許多文獻(xiàn)一樣，在本文中也將式(2.7)和式(2.8)的運(yùn)算用圖2.1所示的一個(gè)流圖符號表示。因?yàn)檫@個(gè)流圖符號形狀酷似一只蝴蝶，所以稱其為蝶形運(yùn)算符號。圖2.1蝶形運(yùn)算符號 采用蝶形運(yùn)算符號的這種圖示方法，可以用圖22來表示前面所講到的運(yùn)算。在圖2.2中，N=23

26、=8，式(2.7)給出了X(O)X(3)的計(jì)算方法，而式(2.8)給出了X(4)X(7)的計(jì)算方法。由圖2.1可以看出，要完成一個(gè)蝶形運(yùn)算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法運(yùn)算。由圖2.2可以看出，經(jīng)過一次分解后，計(jì)算一個(gè)N點(diǎn)DFT共需要計(jì)算兩個(gè)N/2點(diǎn)DFT可和N/2個(gè)蝶形運(yùn)算。由前面的說明可以知道，計(jì)算一個(gè)N/2點(diǎn)DFT需要(N-2)2次復(fù)數(shù)乘法和N/2(N/2-1)次復(fù)數(shù)加法。那么按圖2.2計(jì)算N點(diǎn)DFT共需要2(N2)2+N/2=N(N+1)/2N2/2（N>>1）次復(fù)數(shù)乘法和N(N/2-1)+2N/2=N2/2次復(fù)數(shù)加法運(yùn)算。通過對比可以看出，只進(jìn)行過這樣的次分解就使得運(yùn)算

27、量減少了近一半，充分說明了這樣分解對減少DFT的運(yùn)算量是十分有效的。由這里N=2M，N/2仍然是偶數(shù)，為了使得計(jì)算量能夠得到進(jìn)一步的減少，可以仿效前面的做法對N/2點(diǎn)DFT再做進(jìn)一步分解。圖2.2N點(diǎn)DFT的一次時(shí)域抽取分解圖(NtiS)與第一次分解一樣，和為按奇偶分解成的兩個(gè)長為N/4的子序列，即 那么，又可表示為（2.9）其中同理，由和的周期性和Wm尼的對稱性最后得到：（2.10）同理可得（2.11）其中有 這樣，如圖2.3所示，經(jīng)過第二次的分解，一個(gè)N/2點(diǎn)的DFT就被拆分成為了兩個(gè)N/4點(diǎn)的DFT了。式(2.10)和式(211)說明了原N/2點(diǎn)的DFT和這兩個(gè)N/4點(diǎn)的DFT之間的關(guān)系

28、。依次類推，經(jīng)過M-1次分解，最后將N點(diǎn)DFT分解成N/2個(gè)2點(diǎn)DFT。將前面兩次分解的過程綜合起來，就得到了一個(gè)完整的8點(diǎn)DIT-FFT運(yùn)算流圖，如圖2.4所示。圖中用到關(guān)系式。圖中的輸入序列不是順序的，但是后面會看到，其排列是有規(guī)律的。圖2.3 N點(diǎn)DFT的第二次時(shí)域抽取分解圖(N_8)圖2.4N點(diǎn)DIT-FFT運(yùn)算流圖（N=8）3、DIT-FFT算法與直接計(jì)算DFT運(yùn)算量的比較由DIT-FFT算法的分解過程與圖2.4可見，N=2時(shí)，其運(yùn)算流圖應(yīng)該有M級蝶形，每一級都由N/2蝶形運(yùn)算構(gòu)成。每一級運(yùn)算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)an(每個(gè)蝶形需要兩次復(fù)數(shù)加法)。所以，M級運(yùn)算總共需要的復(fù)數(shù)

29、乘次數(shù)為復(fù)數(shù)加次數(shù)為而由前面的介紹，直接計(jì)算N點(diǎn)的DFT需要N2次復(fù)數(shù)乘法以與N(N-1)次復(fù)數(shù)加法運(yùn)算。N>>1時(shí)，N(N-1)是約等于N2的。當(dāng)N=210=1024時(shí)，可以求得直接計(jì)算N點(diǎn)的DFT和使用基-2DIT-FFT算法的所需乘法次數(shù)的比值為 這樣，運(yùn)算效率就提高了200多倍。圖2.5為FFT算法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線。由此圖更加直觀地看出FFT算法的優(yōu)越性，從圖2.5可以明顯的看出，N越大時(shí)，優(yōu)越性就越明顯。圖2.5 FFT算法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線4、DIT-FFT的一些運(yùn)算規(guī)律DIT-FFT運(yùn)算中是存在一些規(guī)律的，下面簡單的介紹一下這

30、些規(guī)律。(1)原址計(jì)算 由圖2.4可以看出，DIT-FFT的運(yùn)算過程是很有規(guī)律的。N=2M點(diǎn)的FFT共需要進(jìn)行進(jìn)行M級運(yùn)算，每級由N/2個(gè)蝶形運(yùn)算組成。在同一級運(yùn)算中，每一個(gè)蝶形運(yùn)算是有兩個(gè)輸入和兩個(gè)輸出的。這兩個(gè)輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在同一水平線上，并且它們只對本蝶形運(yùn)算有效，對其它的蝶形運(yùn)算是無效的。因?yàn)檫@樣，當(dāng)計(jì)算完一個(gè)蝶形以后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲單元i以此類推，當(dāng)M級運(yùn)算都計(jì)算完畢以后，原來存放輸入序列數(shù)據(jù)的N個(gè)存儲單元中便依次存放了X(k)的N個(gè)值。這種利用同一存儲單元存儲蝶形運(yùn)算計(jì)算輸入、輸出數(shù)據(jù)的方法就稱為原址計(jì)算。很明顯原址計(jì)算可以節(jié)省存儲資源，從而降低硬

31、件的成本。(2)旋轉(zhuǎn)因子的變化規(guī)律 由8點(diǎn)DIT-FFT的運(yùn)算流圖可以推得在N點(diǎn)DIT-FFT運(yùn)算流圖中，每級都有N/2個(gè)蝶形。每個(gè)蝶形都要乘以因子。被稱為旋轉(zhuǎn)因子，其中p為旋轉(zhuǎn)因子的指數(shù)。通過觀察圖2.4可以推得，第L級共有2L-1個(gè)不同的旋轉(zhuǎn)因子。N=23=8時(shí)的各級旋轉(zhuǎn)因子表示如下：(2.12)對N=2M的一半情況，第L級的旋轉(zhuǎn)因子為（2.13）(3)蝶形運(yùn)算規(guī)律設(shè)序列x(n)經(jīng)時(shí)域抽選(倒序)后，存入數(shù)組X中。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，則蝶形運(yùn)算可表示成如下形式：其中p=J2M-L；J=0,1,.,2L-1;L=1,2,.,M下標(biāo)L表示第L級運(yùn)算，XI，(J)

32、則表示第L級運(yùn)算后數(shù)組元素X(J)的值。(4)序列的倒序仔細(xì)分析可以發(fā)現(xiàn)看似毫無規(guī)律可循的DIT-FFT算法的輸入序列的排序其實(shí)是很有規(guī)律的。由于N=2M，所以順序數(shù)可用M位二迸制數(shù)()表示。當(dāng)N=8時(shí)，這種規(guī)律就可以用圖2.6和表2.1來表示。圖2.6形成倒序的樹狀圖(N-2)表2.1順序和倒序二進(jìn)制數(shù)對照表順序 倒敘十進(jìn)制數(shù)I二進(jìn)制數(shù) 二進(jìn)制數(shù) 十進(jìn)制數(shù)J0 000 000 01 001 100 42 010 010 23 011 110 64 100 001 15 101 101 56 110 011 37 111 111 75、DIT-FFT的輸入順序輸出倒序的信號流圖DIT-FFT的

33、信號流圖的形式不是唯一的，它還有多種表現(xiàn)形式。圖2.7是DIT-FFT的一種變形的運(yùn)算流圖，其中蝶形運(yùn)算的旋轉(zhuǎn)因子、運(yùn)算量與圖2.4一樣。從圖中很容易看出它是一種順序輸入，倒序輸出的方式。這種結(jié)構(gòu)的信號流圖有一個(gè)非常特別的優(yōu)點(diǎn)就是前一級的旋轉(zhuǎn)因子剛好是后一級上一半蝶形運(yùn)算的旋轉(zhuǎn)因子，且順序不變，如果旋轉(zhuǎn)因子的計(jì)算采用查表法，只要構(gòu)造出一個(gè)N/2點(diǎn)的，就可以用它來計(jì)算N、N/2、N/4、.長度的FFT。因此在大型數(shù)據(jù)處理系統(tǒng)的FFT算法中，較多采用的是圖2.7所示的流圖算法。本課題也是采用的圖2.7所示的流圖算法。圖2.7 DIT-FFT的順序輸入倒序輸出形式2.2 定點(diǎn)數(shù)的相關(guān)概念2.2.1

34、定點(diǎn)數(shù)的定義定點(diǎn)數(shù)指的是在二進(jìn)制數(shù)中小數(shù)點(diǎn)的位置是固定的數(shù)。浮點(diǎn)表示法所能表示的數(shù)值圍將遠(yuǎn)遠(yuǎn)大于定點(diǎn)表示法。對于字長一樣的定點(diǎn)數(shù)與浮點(diǎn)數(shù)來說，浮點(diǎn)數(shù)雖然擴(kuò)大了數(shù)的表示圍，但這是以降低精度為代價(jià)的，也就是數(shù)軸上各點(diǎn)的排列更稀疏了。浮點(diǎn)運(yùn)算要比定點(diǎn)運(yùn)算復(fù)雜。定點(diǎn)運(yùn)算時(shí)，當(dāng)運(yùn)算結(jié)果超出數(shù)的表示圍，就發(fā)生溢出；而在浮點(diǎn)運(yùn)算時(shí)，運(yùn)算結(jié)果超出尾數(shù)的表示圍卻并不一定溢出，只有當(dāng)階碼也超出所能表示的圍時(shí)，才發(fā)生溢出。2.2.2 定點(diǎn)數(shù)加減法的溢出與檢測方法 在定點(diǎn)小數(shù)機(jī)器中，數(shù)的表示圍為|X|<1。在運(yùn)算過程中如出現(xiàn)大于1的現(xiàn)象，稱為“溢出”。在定點(diǎn)機(jī)中，正常情況下是不允許出現(xiàn)溢出的。例如：x=+0.1

35、011，y=+0.1001，那么x補(bǔ)=0.1011，y補(bǔ)=0.1001，由補(bǔ)碼加法公式X補(bǔ)+Y補(bǔ)=X+Y補(bǔ) 得：x+y補(bǔ)=0.0100，兩個(gè)正數(shù)相加的結(jié)果成為負(fù)數(shù)，這顯然是錯(cuò)誤的。x=-0.1101，Y=-0.1011，那么x補(bǔ)=1.0011，y補(bǔ)=1.0101，同理可得：x+y補(bǔ)=0.1000，兩個(gè)負(fù)數(shù)相加的結(jié)果成為正數(shù)，這同樣是錯(cuò)誤的。 運(yùn)算結(jié)果產(chǎn)生了溢出是發(fā)生錯(cuò)誤的原因。兩個(gè)正數(shù)相加，結(jié)果大于機(jī)器所能表示的最大正數(shù)，稱為上溢。兩個(gè)負(fù)數(shù)相加，結(jié)果小于機(jī)器所能表示的最小負(fù)數(shù)，稱為下溢。為了判斷“溢出”是否發(fā)生，可以采用雙符號位法，也稱為“變形補(bǔ)碼”或“模4補(bǔ)碼”，從而可使模2補(bǔ)碼所能表示的數(shù)

36、的圍擴(kuò)大一倍。數(shù)的變形補(bǔ)碼定義為：x補(bǔ)=x當(dāng)2>xOx補(bǔ)=4+x當(dāng)0>x-2 或用同余式表示為：x補(bǔ)=4+X(mod 4) 下式也同樣成立：x補(bǔ)+y補(bǔ)=x+y補(bǔ) (mod 4) 為了得到兩數(shù)變形補(bǔ)碼之和等于兩數(shù)和的變形補(bǔ)碼，同樣必須：1、兩個(gè)符號位都看做數(shù)碼一樣參加運(yùn)算；2、兩數(shù)進(jìn)行以4為模的加法，即最高符號位上產(chǎn)生的進(jìn)位要丟掉。采用變形補(bǔ)碼后，任何小于l的正數(shù)，兩個(gè)符號位都是0，即00；任何大于-l的負(fù)數(shù)，兩個(gè)符號位都是“1”，即11；如果兩個(gè)數(shù)相加后，其結(jié)果的符號位出現(xiàn)“01”或“10”兩種組合時(shí)，表示發(fā)生溢出。這是因?yàn)閮蓚€(gè)絕對值小于l的數(shù)相加，其結(jié)果不會大于或等于2，所以最高

37、符號位永遠(yuǎn)表示結(jié)果的正確符號。2.3 定點(diǎn)數(shù)的定標(biāo) 數(shù)的定標(biāo)就是根據(jù)需要，人為地指定小數(shù)點(diǎn)的位置，這主要是由于在利用FPGA進(jìn)行數(shù)字系統(tǒng)設(shè)計(jì)的時(shí)候無法將小數(shù)直接表示出來。數(shù)的定標(biāo)有Q表示法和S表示法兩種表示方法?，F(xiàn)在以16位為例，通過表2.3來介紹這兩種表示法所能表示的十進(jìn)制數(shù)的圍和精度。這里討論的為有符號數(shù)。表2.3 16位有符號數(shù)的定標(biāo)表示法Q表示 S表示 十進(jìn)制數(shù)表示圍Q15S0.15-1<=x<=0.9999695Q14S1.14-2<=x<=1.9999390Q13S2.13-4<=x<=3.9998779Q12S3.12-8<=x<=

38、7.9997559Q11S4.11-16<=x<=15.9995117Q10S5.10-32<=x<=31.9990234Q9S6.9-64<=x<=63.9980469Q8S7.8-128<=x<=127.9960938Q7S8.7-256<=x<=255.9921875Q6S9.6-512<=x<=511.9804375Q5S10.5-1024<=x<=1023.96875Q4S11.4-2048<=x<=2047.9375Q3S12.3-4096<=x<=4095.875Q2S13

39、.2-8192<=x<=8191.75Q1S14.1-16384<=x<=16383.5Q0S15.0-32768<=x<=327672.4 有限字長效應(yīng)和單片機(jī)、DSP等器件一樣，F(xiàn)PGA也是不能直接處理模擬信號的。模擬信號必須利用A/D轉(zhuǎn)換成數(shù)字信號以后才能利用FPGA處理。由于A/D器件的精度是一定的，所以轉(zhuǎn)換之后的數(shù)值和真實(shí)值之間存在著偏差，這就是輸入的量化誤差。當(dāng)利用FPGA實(shí)現(xiàn)乘法計(jì)算的時(shí)候，例如計(jì)算兩個(gè)N位寬的二進(jìn)制數(shù)的乘積，乘積的結(jié)果一般都會用2N位寬的二進(jìn)制數(shù)表示，這個(gè)時(shí)候都會將結(jié)果進(jìn)行適當(dāng)?shù)纳嵛惶幚?，否則再進(jìn)行后面的運(yùn)算的話最終的結(jié)果的數(shù)

40、據(jù)寬度將是難以想象的。進(jìn)行舍位就會自然而然的引入誤差，這種誤差屬于運(yùn)算量化誤差，也稱為運(yùn)算噪聲。這些誤差就使得利用FPGA進(jìn)行數(shù)字信號處理的時(shí)候會產(chǎn)生有限字長效應(yīng)。為了得到精確結(jié)果，一方面可以選用合適的運(yùn)算結(jié)構(gòu)，盡量減少有限字長效應(yīng)，另一方面可以采用合適的字長以降低運(yùn)算噪聲3。2.5 塊浮點(diǎn)數(shù)浮點(diǎn)數(shù)具有很大的動態(tài)圍，可以非常精確地表示一個(gè)數(shù)值。由于在執(zhí)行算術(shù)運(yùn)算時(shí)需要大量的硬件資源，所以浮點(diǎn)數(shù)記數(shù)方法的使用成本很高。塊浮點(diǎn)數(shù)記數(shù)方法廣泛用于信號處理領(lǐng)域，如執(zhí)行FFT變換，它消耗的硬件資源要比浮點(diǎn)數(shù)少得多。在用FPGA實(shí)現(xiàn)FFT算法的時(shí)候，經(jīng)常會使用塊浮點(diǎn)的方式來進(jìn)行。這一方法的初始輸入數(shù)據(jù)限制

41、為|x(n)|<l，計(jì)算方式按定點(diǎn)方式進(jìn)行。塊浮點(diǎn)數(shù)可以跟蹤數(shù)值動態(tài)圍的變化，例如做256點(diǎn)FFT變換，數(shù)據(jù)寬度為16位，動態(tài)圍是-3276832767，經(jīng)過FFT的第一級運(yùn)算后，取值圍是-6553665535。為了保持?jǐn)?shù)據(jù)寬度不變，可以將所有256個(gè)點(diǎn)的數(shù)值均除以2，然后寄存器中置入一個(gè)“1”，這樣通過增加一位寄存器，達(dá)到了既增加了數(shù)據(jù)的動態(tài)圍，又未增加數(shù)據(jù)寬度的目的。這種記數(shù)方法就是塊浮點(diǎn)數(shù)記數(shù)方法。總的來說，塊浮點(diǎn)數(shù)具有定點(diǎn)數(shù)的運(yùn)算速度，同時(shí)又有浮點(diǎn)數(shù)的計(jì)數(shù)思想，鑒于塊浮點(diǎn)數(shù)的這種優(yōu)點(diǎn)，本課題選擇了塊浮點(diǎn)數(shù)的計(jì)數(shù)方式3。3 FFT的算法設(shè)計(jì)3.1 FFT處理器的實(shí)現(xiàn)框圖本論文主要研

42、究的是32點(diǎn)的按時(shí)間抽取的基-2FFT算法的FPGA實(shí)現(xiàn)，同時(shí)為了提高運(yùn)行速度還運(yùn)用了流水線結(jié)構(gòu)，為了兼顧高精度和復(fù)雜度的特點(diǎn)還引入了塊浮點(diǎn)結(jié)構(gòu)?；?2FFT模塊設(shè)計(jì)主要由6個(gè)部分組成：蝶形運(yùn)算單元、存儲單元、地址生成單元、功能切換單元、塊浮點(diǎn)單元和時(shí)序控制單元4，如圖3.1所示。圖3.1FFT處理器結(jié)構(gòu)框圖圖3.1中：蝶算單元采用DIT方式來完成基-2蝶形運(yùn)算，如果數(shù)據(jù)從雙口RAM1中讀出，則計(jì)算結(jié)果存入雙口RAM2中，反之亦然；存儲單元主要用來存儲輸入數(shù)據(jù)、中間結(jié)果(RAM)，預(yù)置旋轉(zhuǎn)因子(ROM)，以與最后的計(jì)算結(jié)果(RAM)；地址產(chǎn)生單元產(chǎn)生RAM的讀、寫地址和ROM的讀地址；功能切換

43、單元用來完成RAM1和RAM2間數(shù)據(jù)讀寫功能的切換；塊浮點(diǎn)單元記錄蝶算單元輸出數(shù)據(jù)的位信息，并完成蝶算單元輸入數(shù)據(jù)的截位；時(shí)序控制單元產(chǎn)生各個(gè)模塊的使能、控制信號，使整個(gè)流程正常工作。3.2 蝶形運(yùn)算單元的設(shè)計(jì) 圖3.2 給出了遞歸順序型FFT算法結(jié)構(gòu)框圖。這種形式的FFT只有一個(gè)蝶形運(yùn)算單元，蝶形運(yùn)算按遞歸的方式，根據(jù)蝶形圖從左向右、從上向下先計(jì)算第一級的每個(gè)蝶形，然后計(jì)算第二級、第三級，逐級地循環(huán)運(yùn)算，直至第N/2 log2N個(gè)蝶形，完成N點(diǎn)FFT的全部運(yùn)算。若執(zhí)行一次蝶形運(yùn)算的時(shí)間為T，則完成N點(diǎn)FFT計(jì)算，所需的時(shí)間為N/2 log2NT。在實(shí)際應(yīng)用中，輸入緩沖單元和輸出緩沖單元可以是

44、同一個(gè)存儲單元，完成N點(diǎn)FFT運(yùn)算最少只需要N個(gè)存儲單元來緩存輸入數(shù)據(jù)和中間計(jì)算結(jié)果。如果輸入數(shù)據(jù)是連續(xù)的，那么一次N點(diǎn)FFT運(yùn)算必須在下一組N點(diǎn)輸入數(shù)據(jù)輸入結(jié)束之前完成，這往往需要數(shù)倍于輸入數(shù)據(jù)時(shí)鐘的部運(yùn)算時(shí)鐘。這種結(jié)構(gòu)的優(yōu)點(diǎn)是只有一個(gè)蝶形運(yùn)算單元，所占的硬件資源少，結(jié)構(gòu)簡單，穩(wěn)定性能好，缺點(diǎn)是運(yùn)算速度緩慢，且時(shí)序控制較為復(fù)雜。其程序設(shè)計(jì)如下。圖3.2 遞歸順序型FFT結(jié)構(gòu)框圖module cfft32( clk, rst_n, slice_number, normal_re, normal_im, normal_valid, startfft, fft_finish, address_a,

45、 dataout_a, address_b, dataout_b, dataout_valid, number);input clk; input rst_n;input 4:0 slice_number; input 15:0 normal_re;input 15:0 normal_im;input normal_valid;input startfft;output fft_finish;output 3:0 address_a;output 13:0 dataout_a;output 3:0 address_b;output 13:0 dataout_b;output dataout_v

46、alid;output 3:0 number;wire d_valid;wire 15:0 d_re;wire 15:0 d_im;assign d_valid=normal_valid;assign d_re15:0=normal_re15:0;assign d_im15:0=normal_im15:0;reg 4:0 datain_cnt; /ram control signal and databus ,address busreg 35:0 dina,dinb;reg wrda,wrdb;reg blka,blkb;reg 4:0 addra,addrb;wire 35:0 douta

47、,doutb;parameter 4:0 st0=0, st1=1, st2=2, st3=3, st4=4, st5=5, st6=6, st7=7, st8=8,st9=9,st10=10,st11=11,st12=12,st13=13;reg 4:0 state;reg cf_address_gen_en;wire 31:0 datain_cf1,datain_cf2;wire 35:0 dataout_cf1,dataout_cf2;/cfft dataout output signalwire 4:0 addr_cf1,addr_cf2;/cfft addresswire blk_c

48、f,rd_ram,wr_ram;/cfft read write and blk_en signalwire finish_butterfly;reg 31:0 datain;reg valid;wire start_cfft;reg datain_wr,datain_blk;wire 3:0 address_w;wire 31:0 twiddle_dataout;wire read_twiddle;wire 15:0 d_im_conj;wire fft_finish;reg dataout_valid;wire last_butterfly;wire 1:0 shift;assign ff

49、t_finish=finish_butterfly;assign blk_cf=rd_ram&&wr_ram;assign d_im_conj15:0=d_im15:0;assigndatain_cf131:0=(shift1:0=0)?douta33:18,douta15:0:(shift1:0=1)?douta34:19,douta16:1:(shift1:0=2)?douta35:20,douta17:2:32'b0;assigndatain_cf231:0=(shift1:0=0)?doutb33:18,doutb15:0:(shift1:0=1)?doutb3

50、4:19,doutb16:1:(shift1:0=2)?doutb35:20,doutb17:2:32'b0;wire 24:0 dataout_cf1_t,dataout_cf2_t,dataout_cf1_t2,dataout_cf2_t2;assigndataout_cf1_t24:0=dataout_cf135,dataout_cf135,dataout_cf135,dataout_cf135,dataout_cf135,dataout_cf135,dataout_cf135,dataout_cf135:18<<number3:0;assigndataout_cf2

51、_t24:0=dataout_cf235,dataout_cf235,dataout_cf235,dataout_cf235,dataout_cf235,dataout_cf235,dataout_cf235,dataout_cf235:18<<number3:0;assign dataout_cf1_t224:0=dataout_cf1_t24:0>>slice_number4:0;assign dataout_cf2_t224:0=dataout_cf2_t24:0>>slice_number4:0;assign dataout_a13:0=(dataout_valid)?dataout_cf135,dataout_cf1_t212:0:14'b0;assign dataout_b13:0=(dataout_valid)?dataout_cf235,dataout_cf2_t212:0:14'b0;assign address_a3:0=(dataout_valid)?addra4:1:4'b0;assign address_b3:0=(dataout_val