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