【正文】 5 6 110 011 3 7 111 111 7 DITFFT的輸入順序輸出倒序的信號流圖 DITFFT的信號流圖的形式不是唯一的，它還有多種表現(xiàn)形式。由于 N=2M，所以順序數(shù)可用 M位二迸制數(shù) (0121 ... nnnn MM ??)表示。L=1,2,...,M 下標(biāo) L表示第 L級運(yùn)算， XI， (J)則表示第 L級運(yùn)算后數(shù)組元素 X(J)的值。 N=23=8時(shí)的各 級旋轉(zhuǎn)因子表示如下： 理工大學(xué)學(xué)士學(xué)位論文 13 3,2,1,0,31,0,20,1222/24/????????????JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL時(shí)，時(shí)，時(shí)， () 對 N=2M的一半情況，第 L級的旋轉(zhuǎn)因子為 LMLJNJNpNMLMLMLLJpNJpJWWWNJLWWLMML??????????????????212,.. .,2,1,0,222212,.. .,2,1,0,12212 （ ） (3)蝶形運(yùn)算規(guī)律 設(shè)序列 x(n)經(jīng)時(shí)域抽選 (倒序 )后，存入數(shù)組 X中。p被稱為旋轉(zhuǎn)因子，其中 p為旋轉(zhuǎn)因子的指數(shù)。 (2)旋轉(zhuǎn)因子的變化規(guī)律 由 8點(diǎn) DITFFT的運(yùn)算流圖可以推得在 N點(diǎn) DITFFT運(yùn)算流圖中，每級都有 N/2個(gè)蝶形。這種利用同一存儲單元存儲蝶形運(yùn)算計(jì)算輸入、輸出數(shù)據(jù)的 方法就稱為原址計(jì)算。這兩個(gè)輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在同一水平線上，并且它們只對本蝶形運(yùn)算有效，對其它的蝶形運(yùn)算是無效的。 N=2M點(diǎn)的 FFT共需要進(jìn)行進(jìn)行 M級運(yùn)算，每級由 N/2個(gè)蝶形運(yùn)算組成。 理工大學(xué)學(xué)士學(xué)位論文 12 圖 FFT算法與直接計(jì)算 DFT所需乘法次數(shù)的比較曲線 DITFFT的一些運(yùn)算規(guī)律 DITFFT運(yùn)算中是存在一些規(guī)律的，下面簡單的介紹一下這些規(guī)律。圖 FFT算法與直接計(jì)算 DFT所需乘法次數(shù)的比較曲線。 N1時(shí)， N(N1)是約等于 N2的。每一級運(yùn)算都需要 N/2次復(fù)數(shù)乘和 N次復(fù)數(shù) an(每個(gè)蝶形需要兩次復(fù)數(shù)加法 )。圖中的輸入序列不是順序的，但是后面會看到，其排列是有規(guī)律的。將前面兩次分解的過程綜合起來，就得到了一個(gè)完整的 8點(diǎn) DITFFT運(yùn)算流圖，如圖 。式 ()和式 (2． 11)說明了原 N/2點(diǎn)的 DFT和這兩個(gè) N/4點(diǎn)的 DFT之間的關(guān)系。由這里 N=2M， N/2仍然是偶數(shù)，為了使得計(jì)算理工大學(xué)學(xué)士學(xué)位論文 9 量能夠得到進(jìn)一步的減少，可以仿效前面的做法對 N/2點(diǎn) DFT再做進(jìn)一步分解。 那 么 按 圖 計(jì)算 N 點(diǎn) DFT 共需要 2(N ／2)2+N/2=N(N+1)/2≈N2/2（ N1） 次復(fù)數(shù)乘法和 N(N/21)+2N/2=N2/2次復(fù)數(shù)加法運(yùn)算。由圖 ，經(jīng)過一次分解后，計(jì)算一個(gè) N點(diǎn) DFT共需要計(jì)算兩個(gè) N/2點(diǎn)DFT可和 N/2個(gè)蝶形運(yùn)算。在圖 ， N=23=8，式 ()給出了 X(O)～ X(3)的計(jì)算方法，而式 ()給出了 X(4)～ X(7)的計(jì)算方法。因?yàn)檫@個(gè)流圖符號形狀酷似一只蝴蝶，所以稱其為蝶形運(yùn)算符號。式 ()和式 ()說明了原 N點(diǎn)的 DFT和這兩個(gè) N/2點(diǎn)的 DFT之間的關(guān)系。本課題采用的就是 DITFFT這一算法。 基 2FFT算法基本原理 基 2FFT算法基本上分為時(shí)域抽取法 FFT(DITFFT)和頻域抽取法 FFT(DIFFFT)兩大類?；?2FFT 中的基 2 指的是 N=2M，即有限長序列的長度 N 要到等于 2理工大學(xué)學(xué)士學(xué)位論文 7 的整數(shù)次冪；同理可得基 4FFT 中的基 4 指的是有限長序列的長度 N 要到等于 4 的整數(shù)次冪。其周期性表現(xiàn)為： mNmNjiNmNjlNmN WeeW ??? ???? ππ 2)(2 () 其對稱性表現(xiàn)為 mNNmN W ?? ? mNmNN WW ?? ]*[ 或者 wNm???2 （ ） 不斷的把長序列的 DFT 分解成幾個(gè)短序列的 DFT，并且利用mN的周期性和對稱性來減少 DFT 的運(yùn)算次數(shù)，這就是 FFT 算法的基本思想?；谶@一思想，可以將 N點(diǎn) DFT分解為幾個(gè)較短的 DFT，這樣一來乘法次數(shù)將大大減少，能夠非常明顯地降低 DFT的運(yùn)算量。 在前面已經(jīng)講到， N點(diǎn) DFT的復(fù)乘次數(shù)等于 N2。如此巨大的計(jì)算量對于實(shí)時(shí)信號處理來說其運(yùn)算速度是難以達(dá)到的。當(dāng) N較大時(shí)，運(yùn)算量是十分龐大的。當(dāng) N1時(shí)， N(N1)≈N2。如果直接按 ()式計(jì)算 X(k)值，那么對于某一個(gè)k值而言需要 N次復(fù)數(shù)乘法和 m1次復(fù)數(shù)加法。 理工大學(xué)學(xué)士學(xué)位論文 6 2 離散福利葉變換的快速算法的基本理論 本章主要介紹了基 2FFT算法和用硬件實(shí)現(xiàn)數(shù)字信號處理算法所涉及到的幾個(gè)基本問題。本論文共5 章，各章的具體內(nèi)容如下： 第 1 章闡述了硬件實(shí)現(xiàn)的國內(nèi)外現(xiàn)狀及選題的意義和論文內(nèi)容。 20xx 年劉在爽、盧瑩瑩對 FPGA 實(shí)現(xiàn) FIR 數(shù)字濾波器也進(jìn)行研究，討論了乘累加和基于 CSD（ Canonic signed Digital，標(biāo)準(zhǔn)有符號數(shù)）編碼的數(shù)字濾波器的設(shè)計(jì)。 20xx 年劉國棟等也使用基 2 算法設(shè)計(jì)了 FFT 單元，他使用了 ALTERA 高性能的Stratix 器件對 512 點(diǎn)、 1024 點(diǎn)、 2048 點(diǎn)、 4096 點(diǎn)和 8192 點(diǎn)都進(jìn)行了分析。 20xx 年韓穎等 采用 Xilinx 公司的 FPGA 設(shè)計(jì)了 FFT 處理器。目前不少大學(xué)及研究所都使用 FPGA 芯片設(shè)計(jì)開發(fā)具有自主知識產(chǎn)權(quán)的 FFT 和 FIR 數(shù)字濾波器，但是由于起步較晚，基礎(chǔ)薄弱，所設(shè)計(jì)的 FFT 和 FIR 數(shù)字濾波器無論是速度，還是可擴(kuò)展性上都與國外有一定差距。但也存在以下的缺點(diǎn)： IP 核價(jià)格昂貴（ Altera 公司的 FFT IP 核售價(jià)為 7995 美元）， 且 IP 核源代碼不對外開放，不利于二次開發(fā)； IP 核針對通用的設(shè)計(jì)，在某些特殊的應(yīng)用場合不一定最優(yōu)因此還難以在我國基層應(yīng)用領(lǐng)域普及。目前 Altera 公司提供的 FFT 模塊采用 4 引擎結(jié)構(gòu)，在實(shí)現(xiàn) 1024 點(diǎn) FFT 時(shí)所需時(shí)間己經(jīng)降至很低。這些 IP 核中包含了基本的數(shù)字信號處理模塊，如 FFT、FIR 等。國內(nèi)外已積極地開展了基于 FPGA 的數(shù)字信號處理算法應(yīng)用與研究，并且也取得了長足的進(jìn)步。配置數(shù)據(jù)可以存儲在片外的 EPROM 或其他存儲體上，人們可以控制加載過程，在現(xiàn)場修改器件的邏輯功能，即所謂現(xiàn)場編程。工 作時(shí)，這些配置數(shù)據(jù)存放在片內(nèi)的SRAM 或者熔絲圖上。由于 FPGA 器件采用標(biāo)準(zhǔn)化結(jié)構(gòu)，并且具有體積小、集成度高、功耗低、速度快、可無限次反復(fù)編程等特點(diǎn)，已成為開發(fā)電子產(chǎn)品的首選器件。 其中，現(xiàn)場可編程門列陣（ FPGA）是最近幾年發(fā)展起來的新型高密度可編程邏輯器件。現(xiàn)在已廣泛用于計(jì)算機(jī) 硬件、工業(yè)控制、智能儀表、通信設(shè)備和醫(yī)療電子儀器等多個(gè)領(lǐng)域。 使用可編程邏輯器件可以大大簡化硬件系統(tǒng)，降低成本，提高系統(tǒng)的可靠性、靈活性和保密性。 可編程邏輯器件 可編程邏輯器件以其獨(dú)特的優(yōu)越性能，一出現(xiàn)就受到大家的青睞。 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)。 專用集成電路芯片 ASIC 在集成電路界 ASIC 被認(rèn)為是一種為專門目的而設(shè)計(jì)的集成電路。但是，通用 DSP 處理器構(gòu)成的 FFT 處理器和 FIR 數(shù)字濾波器采用循環(huán)編碼算法，程序量小，但存在大量的冗余運(yùn)算，需要許多跳轉(zhuǎn)操作，處理速度較慢，難以滿足現(xiàn)代數(shù)字信號處理高速、大規(guī)模、理工大學(xué)學(xué)士學(xué)位論文 3 實(shí)時(shí)性的要求。 針對一般數(shù)字信號處理算法的實(shí)現(xiàn)，采用通用可編程硬件處理器技術(shù)來實(shí)現(xiàn) FFT 和FIR 數(shù)字濾波器。 通用型 DSP 芯片適合普通的 DSP 應(yīng)用， 通用 DSP 芯片具有接口靈活、編程方便、穩(wěn)定性好、運(yùn)算精度高等特點(diǎn)，同時(shí)也更適應(yīng)于大規(guī)模集成電路 如 TI 公司的一系列DSP 芯片屬于通用型 DSP 芯片 。 FFT 的國內(nèi)外發(fā)展研究現(xiàn)狀 針對 FFT 和 FIR 數(shù)字濾波器的硬件實(shí)現(xiàn)方案主要有三種途徑： DSP 處理器、專用集成電路 ASIC、可編程邏輯器件，其中可編程邏輯器件以 FPGA 為代 表 。 因此，自主研發(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)。 理工大學(xué)學(xué)士學(xué)位論文 2 近幾年，隨著現(xiàn)場可編程門陣列 FPGA 技術(shù)的迅速發(fā)展，采用并行度更大、速度更快的 FPGA 芯片來實(shí)現(xiàn) FFT 和 FIR 數(shù)字濾波器己成為必然趨勢。 FIR 濾波器被廣泛用于各類數(shù)字信號處理系統(tǒng)中實(shí)現(xiàn)卷積、相關(guān)、自適應(yīng)濾波、正交插值等處理 。有限沖激響應(yīng)（ FIR）濾波器可以保證嚴(yán)格的線性相位。 此外，數(shù)字濾波在圖像處理、語音識別和模式識別等數(shù)字信號處理中占有重要地位。在很多應(yīng)用領(lǐng)域都要求 FFT 處理器具有高速度、高精度、大容量和實(shí)時(shí)處理的性能。 目前， FFT 廣泛應(yīng)用在頻譜分析、匹配濾波、數(shù)字通信、圖像處理、語音識別、雷達(dá)處理、遙感遙測、地質(zhì)勘探和無線保密通訊等眾多領(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ì) 算問題。處理的任務(wù)大致分為三類 :卷積 —— 用于各種濾波器，對給定頻率范 圍的原始信號進(jìn)行加工（通過或?yàn)V出）來提高信噪比；相關(guān) —— 用于信號比較，分析隨機(jī)信號的功率譜密度；變換 —— 用于分析信號的頻率組成，對信號進(jìn)行識別。Unit design。 關(guān)鍵詞：快速傅立葉變換； Verilog；單元設(shè)計(jì)； modelsim 仿真 理工大學(xué)學(xué)士學(xué)位論文 II Abstract Fast Fourier Transform is a necessary precondition of digital spectral analysis as the basic puting between the time domain and frequency domain. The traditional FFT uses software or DSP to realize, which is difficult to meet realtime 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 the 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 lowcost, easy to debug and can be repeatedly programmed. It has more market petitiveness. Use Verilog language pleted 32 points 2 plex FFT processing system design, Including butterfly putin