【正文】 ble 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 puting unit design, storage unit design, block floatingpoint unit design, the address generation unit design, the 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。處理的任務(wù)大致分為三類 :卷積 —— 用于各種濾波器，對(duì)給定頻率范 圍的原始信號(hào)進(jìn)行加工（通過或?yàn)V出）來提高信噪比；相關(guān) —— 用于信號(hào)比較，分析隨機(jī)信號(hào)的功率譜密度；變換 —— 用于分析信號(hào)的頻率組成，對(duì)信號(hào)進(jìn)行識(shí)別。 目前， FFT 廣泛應(yīng)用在頻譜分析、匹配濾波、數(shù)字通信、圖像處理、語(yǔ)音識(shí)別、雷達(dá)處理、遙感遙測(cè)、地質(zhì)勘探和無線保密通訊等眾多領(lǐng)域。 此外，數(shù)字濾波在圖像處理、語(yǔ)音識(shí)別和模式識(shí)別等數(shù)字信號(hào)處理中占有重要地位。 FIR 濾波器被廣泛用于各類數(shù)字信號(hào)處理系統(tǒng)中實(shí)現(xiàn)卷積、相關(guān)、自適應(yīng)濾波、正交插值等處理 。 因此，自主研發(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)代信號(hào)處理的高速度、高可靠性要求，成為了現(xiàn)今我國(guó)數(shù)字信號(hào)處理的一個(gè)研究點(diǎn)。 通用型 DSP 芯片適合普通的 DSP 應(yīng)用， 通用 DSP 芯片具有接口靈活、編程方便、穩(wěn)定性好、運(yùn)算精度高等特點(diǎn)，同時(shí)也更適應(yīng)于大規(guī)模集成電路 如 TI 公司的一系列DSP 芯片屬于通用型 DSP 芯片 。但是，通用 DSP 處理器構(gòu)成的 FFT 處理器和 FIR 數(shù)字濾波器采用循環(huán)編碼算法，程序量小，但存在大量的冗余運(yùn)算，需要許多跳轉(zhuǎn)操作，處理速度較慢，難以滿足現(xiàn)代數(shù)字信號(hào)處理高速、大規(guī)模、理工大學(xué)學(xué)士學(xué)位論文 3 實(shí)時(shí)性的要求。 ASIC 在一些特殊功能的表現(xiàn)上相當(dāng)好，這種方案運(yùn)算速度快，可靠性高，非常適合實(shí)時(shí)和對(duì)可靠性要求較高的信號(hào)處理系統(tǒng)， 在批量生產(chǎn)時(shí)與通用集成電路相比具有體積更小、功耗更低、可靠性提高、性能提高、保密性增強(qiáng)、成本降低等優(yōu)點(diǎn) ，但是專用芯片不能重新組態(tài)，可編程能力有限， 在產(chǎn)品發(fā)展過程中，它的功 能無法任意修改或改進(jìn)。 使用可編程邏輯器件可以大大簡(jiǎn)化硬件系統(tǒng)，降低成本，提高系統(tǒng)的可靠性、靈活性和保密性。 其中，現(xiàn)場(chǎng)可編程門列陣（ FPGA）是最近幾年發(fā)展起來的新型高密度可編程邏輯器件。工 作時(shí)，這些配置數(shù)據(jù)存放在片內(nèi)的SRAM 或者熔絲圖上。國(guó)內(nèi)外已積極地開展了基于 FPGA 的數(shù)字信號(hào)處理算法應(yīng)用與研究，并且也取得了長(zhǎng)足的進(jìn)步。目前 Altera 公司提供的 FFT 模塊采用 4 引擎結(jié)構(gòu)，在實(shí)現(xiàn) 1024 點(diǎn) FFT 時(shí)所需時(shí)間己經(jīng)降至很低。目前不少大學(xué)及研究所都使用 FPGA 芯片設(shè)計(jì)開發(fā)具有自主知識(shí)產(chǎn)權(quán)的 FFT 和 FIR 數(shù)字濾波器，但是由于起步較晚，基礎(chǔ)薄弱，所設(shè)計(jì)的 FFT 和 FIR 數(shù)字濾波器無論是速度，還是可擴(kuò)展性上都與國(guó)外有一定差距。 20xx 年劉國(guó)棟等也使用基 2 算法設(shè)計(jì)了 FFT 單元，他使用了 ALTERA 高性能的Stratix 器件對(duì) 512 點(diǎn)、 1024 點(diǎn)、 2048 點(diǎn)、 4096 點(diǎn)和 8192 點(diǎn)都進(jìn)行了分析。本論文共5 章，各章的具體內(nèi)容如下： 第 1 章闡述了硬件實(shí)現(xiàn)的國(guó)內(nèi)外現(xiàn)狀及選題的意義和論文內(nèi)容。如果直接按 ()式計(jì)算 X(k)值，那么對(duì)于某一個(gè)k值而言需要 N次復(fù)數(shù)乘法和 m1次復(fù)數(shù)加法。當(dāng) N較大時(shí)，運(yùn)算量是十分龐大的。 在前面已經(jīng)講到， N點(diǎn) DFT的復(fù)乘次數(shù)等于 N2。其周期性表現(xiàn)為： mNmNjiNmNjlNmN WeeW ??? ???? ππ 2)(2 () 其對(duì)稱性表現(xiàn)為 mNNmN W ?? ? mNmNN WW ?? ]*[ 或者 wNm???2 （ ） 不斷的把長(zhǎng)序列的 DFT 分解成幾個(gè)短序列的 DFT，并且利用mN的周期性和對(duì)稱性來減少 DFT 的運(yùn)算次數(shù)，這就是 FFT 算法的基本思想。 基 2FFT算法基本原理 基 2FFT算法基本上分為時(shí)域抽取法 FFT(DITFFT)和頻域抽取法 FFT(DIFFFT)兩大類。式 ()和式 ()說明了原 N點(diǎn)的 DFT和這兩個(gè) N/2點(diǎn)的 DFT之間的關(guān)系。在圖 ， N=23=8，式 ()給出了 X(O)～ X(3)的計(jì)算方法，而式 ()給出了 X(4)～ X(7)的計(jì)算方法。 那 么 按 圖 計(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)算。式 ()和式 (2． 11)說明了原 N/2點(diǎn)的 DFT和這兩個(gè) N/4點(diǎn)的 DFT之間的關(guān)系。圖中的輸入序列不是順序的，但是后面會(huì)看到，其排列是有規(guī)律的。 N1時(shí)， N(N1)是約等于 N2的。 理工大學(xué)學(xué)士學(xué)位論文 12 圖 FFT算法與直接計(jì)算 DFT所需乘法次數(shù)的比較曲線 DITFFT的一些運(yùn)算規(guī)律 DITFFT運(yùn)算中是存在一些規(guī)律的，下面簡(jiǎn)單的介紹一下這些規(guī)律。這兩個(gè)輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在同一水平線上，并且它們只對(duì)本蝶形運(yùn)算有效，對(duì)其它的蝶形運(yùn)算是無效的。 (2)旋轉(zhuǎn)因子的變化規(guī)律 由 8點(diǎn) DITFFT的運(yùn)算流圖可以推得在 N點(diǎn) DITFFT運(yùn)算流圖中，每級(jí)都有 N/2個(gè)蝶形。 N=23=8時(shí)的各 級(jí)旋轉(zhuǎn)因子表示如下： 理工大學(xué)學(xué)士學(xué)位論文 13 3,2,1,0,31,0,20,1222/24/????????????JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL時(shí)，時(shí)，時(shí)， () 對(duì) N=2M的一半情況，第 L級(jí)的旋轉(zhuǎn)因子為 LMLJNJNpNMLMLMLLJpNJpJWWWNJLWWLMML??????????????????212,.. .,2,1,0,222212,.. .,2,1,0,12212 （ ） (3)蝶形運(yùn)算規(guī)律 設(shè)序列 x(n)經(jīng)時(shí)域抽選 (倒序 )后，存入數(shù)組 X中。由于 N=2M，所以順序數(shù)可用 M位二迸制數(shù) (0121 ... nnnn MM ??)表示。從圖中很容易看出它是一種順序輸入，倒序輸出的方式。 圖 DITFFT的順序輸入倒序輸出形式 理工大學(xué)學(xué)士學(xué)位論文 15 定點(diǎn)數(shù)的相關(guān)概念 定點(diǎn)數(shù)的定義 定點(diǎn)數(shù)指的是在二進(jìn)制數(shù)中小數(shù)點(diǎn)的位置是固定的數(shù)。 定點(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ā)生溢出。例如： x=+， y=+，那么 [x]補(bǔ) =， [y]補(bǔ) =，由補(bǔ)碼加法公式 [X]補(bǔ) +[Y]補(bǔ) =[X+Y]補(bǔ) 得： [x+y]補(bǔ) =，兩個(gè)正數(shù)相加的結(jié)果成為負(fù)數(shù)，這顯然是錯(cuò)誤的。兩個(gè)負(fù)數(shù)相加，結(jié)果小于機(jī)器所能表示的最小負(fù)數(shù)，稱為下溢。這是因?yàn)閮蓚€(gè)絕對(duì)值小于 l的數(shù)相加，其結(jié)果不會(huì)大于或等于 2，所以最高符號(hào)位永遠(yuǎn)表示結(jié)果的正確符號(hào)。這里討論的為有符號(hào)數(shù)。 當(dāng)利用 FPGA實(shí)現(xiàn)乘法計(jì)算的時(shí)候，例如計(jì)算兩個(gè) N位寬的二進(jìn)制數(shù)的乘積，乘積的理工大學(xué)學(xué)士學(xué)位論文 17 結(jié)果一般都會(huì)用 2N位寬的二進(jìn)制數(shù)表示，這個(gè)時(shí)候都會(huì)將結(jié)果進(jìn)行適當(dāng)?shù)纳嵛惶幚?，否則再進(jìn)行后面的運(yùn)算的話最終的結(jié)果的數(shù)據(jù)寬度將是難以想象的。 塊浮點(diǎn)數(shù) 浮點(diǎn)數(shù)具有很大的動(dòng)態(tài)范圍，可以非常精確地表示一個(gè)數(shù)值。這一方法的初始輸入數(shù)據(jù)限制為 |x(n)|l，計(jì)算方式按定點(diǎn)方式進(jìn)行?？偟膩碚f，塊浮點(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]。 蝶形運(yùn)算單元的設(shè)計(jì) 圖 給出了遞歸順序型 FFT 算法結(jié)構(gòu)框圖。如果輸入數(shù)據(jù)是連續(xù)的，那么一次 N 點(diǎn) FFT 運(yùn)算必須在下一組 N 點(diǎn)輸入數(shù)據(jù)輸入結(jié)束之前完成，這往往需要數(shù)倍于輸入數(shù)據(jù)時(shí)鐘的內(nèi)部運(yùn)算時(shí)鐘。 input clk。 理工大學(xué)學(xué)士學(xué)位論文 20 input [15:0] normal_im。 output [3:0] address_a。 output dataout_valid。 wire [15:0] d_im。 reg [4:0] datain_t。 reg [4:0] addra,addrb。 reg cf_address_gen_en。//cfft address wire blk_cf,rd_ram,wr_ram。 wire start_cfft。 wire read_twiddle。 wire last_butterfly。amp。b0。 assigndataout_cf1_t[24:0]={dataout_cf1[35],dataout_cf1[35],dataout_cf1[35],dataout_cf1[35],dataout_cf1[35],dataout_cf1[35],dataout_cf1[35],dataout_cf1[35:18]}number[3:0]。 assign dataout_a[13:0]=(dataout_valid)?{dataout_cf1[35],dataout_cf1_t2[12:0]}:1439。 assign address_a[3:0]=(dataout_valid)?addra[4:1]:439。 always(posedge clk or negedge rst_n) //input datain_valid sync。 if(!rst_n) datain[31:0]=0。 else if(valid) datain_t[4:0]=datain_t[4:0]+1。 datain_blk=0。 else case(state) st0 : begin //initial state if(d_valid) state = st1。 else state = st2。 end st4: begin // start the cfft ram1。 else state=st5。// ram signal blka=1。 blkb=1。 end st1 : begin