【正文】 dataout_valid=~wr_ram。 dina[35:0]=dataout_cf1[35:0]。 dinb[35:0]=0。 理工大學(xué)學(xué)士學(xué)位論文 23 end default:state=st0。 理工大學(xué)學(xué)士學(xué)位論文 22 end else begin datain_wr=1。b0。wr_ram。//cfft read write and blk_en signal wire finish_butterfly。 assign d_valid=normal_valid。 input rst_n。塊浮點(diǎn)數(shù)可以跟蹤數(shù)值動(dòng)態(tài)范圍的變化，例 如做 256點(diǎn) FFT變換，數(shù)據(jù)寬度為 16位，動(dòng)態(tài)范圍是 32768～ 32767，經(jīng)過 FFT的第一級(jí)運(yùn)算后，取值范圍是 65536～ 65535。 定點(diǎn)數(shù)的定標(biāo) 數(shù)的定標(biāo)就是根據(jù)需要，人為地指定小數(shù)點(diǎn)的位置，這 主要是由于在利用 FPGA進(jìn)行數(shù)字系統(tǒng)設(shè)計(jì)的時(shí)候無(wú)法將小數(shù)直接表示出來。 浮點(diǎn)表示法所能表示的數(shù)值范圍將遠(yuǎn)遠(yuǎn)大于定點(diǎn)表示法。每個(gè)蝶形都要乘以因子pW。 圖 N點(diǎn) DFT的第二次時(shí)域抽取分解圖 (N_8) 理工大學(xué)學(xué)士學(xué)位論文 11 圖 N點(diǎn) DITFFT運(yùn)算流圖 （ N=8） DITFFT算法與直接計(jì)算 DFT運(yùn)算量的比較 由 DITFFT算法的分解過程及圖 ， N=2M時(shí)，其運(yùn)算流圖應(yīng)該有 M級(jí)蝶形，每一級(jí)都由 N/2蝶形 運(yùn)算構(gòu)成。通常為了后續(xù)說明的方便，和其它許多文獻(xiàn)一樣，在本文中也將式 ()和式 ()的運(yùn)算用圖 。如果 N取 1024，那么 N2將達(dá)到 1,048,576。 20xx 年羅雪茍、詹陽(yáng)分析了使用 FPGA 實(shí)現(xiàn) FFT 的幾種方法，對(duì)這幾種方法的優(yōu)缺點(diǎn)進(jìn)行了討論。現(xiàn)場(chǎng)可編程門陣列（ FPGA）是 20 世紀(jì) 80 年代中期由美國(guó) Xilinx 公司首先推出的大規(guī)?？删幊踢壿嬈骷? 專用 DSP 芯片是為特定的 DSP 運(yùn)算而設(shè)計(jì)的，更適合特殊的運(yùn)算，如數(shù)字濾波、卷積和 FFT，如 Motorola 公司的 DSP56200， Zoran 公司的 ZR34881， Inmos公司的 IMSA100 等就屬于專用型 DSP 芯片 。在不同應(yīng)用場(chǎng)合，需要不同性能要求的 FFT 處理器。理工大學(xué)學(xué)士學(xué)位論文 I 基于 ModelSim 的 FFT 算法的設(shè)計(jì)學(xué)士學(xué)位論文 理工大學(xué)學(xué)士學(xué)位論文 II 摘 要 快速傅立葉變換 (FFT)作為時(shí)域和頻域轉(zhuǎn)換的基本運(yùn)算，是數(shù)字譜分析的必要前提。在很多應(yīng)用領(lǐng)域都要求 FFT 處理器具有高速度、高精度、大容量和實(shí)時(shí)處理的性能。 針對(duì)一般數(shù)字信號(hào)處理算法的實(shí)現(xiàn)，采用通用可編程硬件處理器技術(shù)來實(shí)現(xiàn) FFT 和FIR 數(shù)字濾波器。由于 FPGA 器件采用標(biāo)準(zhǔn)化結(jié)構(gòu)，并且具有體積小、集成度高、功耗低、速度快、可無(wú)限次反復(fù)編程等特點(diǎn)，已成為開發(fā)電子產(chǎn)品的首選器件。 20xx 年韓穎等 采用 Xilinx 公司的 FPGA 設(shè)計(jì)了 FFT 處理器。如此巨大的計(jì)算量對(duì)于實(shí)時(shí)信號(hào)處理來說其運(yùn)算速度是難以達(dá)到的。因?yàn)檫@個(gè)流圖符號(hào)形狀酷似一只蝴蝶，所以稱其為蝶形運(yùn)算符號(hào)。每一級(jí)運(yùn)算都需要 N/2次復(fù)數(shù)乘和 N次復(fù)數(shù) an(每個(gè)蝶形需要兩次復(fù)數(shù)加法 )。p被稱為旋轉(zhuǎn)因子，其中 p為旋轉(zhuǎn)因子的指數(shù)。對(duì)于字長(zhǎng)相同的定點(diǎn)數(shù)與浮點(diǎn)數(shù)來說，浮點(diǎn)數(shù)雖然擴(kuò)大了數(shù)的表示范圍，但這是以降低精度為代價(jià)的，也就是數(shù)軸上各點(diǎn)的排列更稀疏了。數(shù)的定標(biāo)有 Q表示法和 S表示法兩種表示方法。為了保持?jǐn)?shù)據(jù)寬度不變，可以將所有 256個(gè)點(diǎn)的數(shù)值均除以 2， 然后寄存器中置入一個(gè)“ 1”，這樣通過增加一位寄存器，達(dá)到了既增加了數(shù)據(jù)的動(dòng)態(tài)范圍，又未增加數(shù)據(jù)寬度的目的。 input [4:0] slice_number。 assign d_re[15:0]=normal_re[15:0]。 reg [31:0] datain。 assign d_im_conj[15:0]=d_im[15:0]。 assign address_b[3:0]=(dataout_valid)?addrb[4:1]:439。 datain_blk=1。 endcase end always(posedge clk) begin case(state) st0 : begin //start state cf_address_gen_en=0。 blkb=1。 //join the ram to cfft blka=blk_cf。 end st5 : begin //finish the cfft process to ram1,start to output the result cf_address_gen_en=0。 addrb[4:0]=addr_cf2[4:0]。 end st3 : begin // start cfft to process the ram cf_address_gen_en=1。 wrda=datain_wr。 else state=st5。 datain_blk=0。 assign address_a[3:0]=(dataout_valid)?addra[4:1]:439。amp。//cfft address wire blk_cf,rd_ram,wr_ram。 wire [15:0] d_im。 input clk。這一方法的初始輸入數(shù)據(jù)限制為 |x(n)|l，計(jì)算方式按定點(diǎn)方式進(jìn)行。這是因?yàn)閮蓚€(gè)絕對(duì)值小于 l的數(shù)相加，其結(jié)果不會(huì)大于或等于 2，所以最高符號(hào)位永遠(yuǎn)表示結(jié)果的正確符號(hào)。 圖 DITFFT的順序輸入倒序輸出形式 理工大學(xué)學(xué)士學(xué)位論文 15 定點(diǎn)數(shù)的相關(guān)概念 定點(diǎn)數(shù)的定義 定點(diǎn)數(shù)指的是在二進(jìn)制數(shù)中小數(shù)點(diǎn)的位置是固定的數(shù)。 (2)旋轉(zhuǎn)因子的變化規(guī)律 由 8點(diǎn) DITFFT的運(yùn)算流圖可以推得在 N點(diǎn) DITFFT運(yùn)算流圖中，每級(jí)都有 N/2個(gè)蝶形。圖中的輸入序列不是順序的，但是后面會(huì)看到，其排列是有規(guī)律的。式 ()和式 ()說明了原 N點(diǎn)的 DFT和這兩個(gè) N/2點(diǎn)的 DFT之間的關(guān)系。當(dāng) N較大時(shí)，運(yùn)算量是十分龐大的。目前不少大學(xué)及研究所都使用 FPGA 芯片設(shè)計(jì)開發(fā)具有自主知識(shí)產(chǎn)權(quán)的 FFT 和 FIR 數(shù)字濾波器，但是由于起步較晚，基礎(chǔ)薄弱，所設(shè)計(jì)的 FFT 和 FIR 數(shù)字濾波器無(wú)論是速度，還是可擴(kuò)展性上都與國(guó)外有一定差距。 其中，現(xiàn)場(chǎng)可編程門列陣（ FPGA）是最近幾年發(fā)展起來的新型高密度可編程邏輯器件。 通用型 DSP 芯片適合普通的 DSP 應(yīng)用， 通用 DSP 芯片具有接口靈活、編程方便、穩(wěn)定性好、運(yùn)算精度高等特點(diǎn)，同時(shí)也更適應(yīng)于大規(guī)模集成電路 如 TI 公司的一系列DSP 芯片屬于通用型 DSP 芯片 。 目前， FFT 廣泛應(yīng)用在頻譜分析、匹配濾波、數(shù)字通信、圖像處理、語(yǔ)音識(shí)別、雷達(dá)處理、遙感遙測(cè)、地質(zhì)勘探和無(wú)線保密通訊等眾多領(lǐng)域。傳統(tǒng)的 FFT 使用軟件或 DSP 實(shí)現(xiàn)，高速處理時(shí)實(shí)時(shí)性較難滿足，因此專用集成電路(ASIC)和可編程邏輯器件 (以現(xiàn)場(chǎng)可編程門陣列 FPGA 為代表 )應(yīng)運(yùn)而生。因此，如何更快速、更靈活地實(shí)現(xiàn) FFT 變得越來越重要。這種實(shí)現(xiàn)方法具有軟件設(shè)計(jì)多用性的優(yōu)點(diǎn)，能夠適用于各種需要 FFT運(yùn)算和 FIR 數(shù)字濾波器進(jìn)行信號(hào)處理的應(yīng)用場(chǎng)合，靈活方便。 FPGA 的功能由邏輯結(jié)構(gòu)的配置數(shù)據(jù)決定。采用流水方式對(duì)復(fù)數(shù)數(shù)據(jù)實(shí)現(xiàn)了加窗、 FFT、求模平方三種運(yùn)算，整個(gè)設(shè)計(jì)使用雙基 2 蝶形運(yùn)算單元，采用流水線方式盡量避免瓶頸的出現(xiàn)，提高了系統(tǒng)時(shí)鐘頻率。所以要想使得 DFT在各種科學(xué)和工程計(jì)算中得 到廣泛的應(yīng)用就必須想辦法減少其運(yùn)算量。 圖 采用蝶形運(yùn)算符號(hào)的這種圖示方法，可以用圖 2． 2來表示前面所講到的運(yùn)算。所以， M級(jí)運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為 NNMNC M 2log22)2( ?? 復(fù)數(shù)加次數(shù)為 NNNMC A 2log)2( ?? 而由前面的介紹，直接計(jì)算 N點(diǎn)的 DFT需要 N2次復(fù)數(shù)乘法以及 N(N1)次復(fù)數(shù)加法運(yùn)算。 通過觀察圖 ，第 L級(jí)共有 2L1個(gè)不同的旋轉(zhuǎn)因子。浮點(diǎn)運(yùn)算要比 定點(diǎn)運(yùn) 算 復(fù)雜?，F(xiàn)在以 16位為例，通過表 精度。這種記數(shù)方法就是塊浮點(diǎn)數(shù)記數(shù)方法。 input [15:0] normal_re。 assign d_im[15:0]=normal_im[15:0]。 reg valid。 assigndatain_cf1[31:0]=(shift[1:0]==0)?{douta[33:18],douta[15:0]}:(shift[1:0]==1)?{douta[34:19],douta[16:1]}:(shift[1:0]==2)?{douta[35:20],douta[17:2]}:3239。b0。 end always(posedge clk or negedge rst_n) begin if(!rst_n) state =st0。//cfft address generate enable signal dina[35:0]=0。 addrb[4:0]=0。 addra[4:0]=addr_cf1[4:0]。 dina[35:0]={datain[31],datain[31],datain[31:16],datain[15],datain[15],datain[15:0]}。 blkb=blk_cf。 理工大學(xué)學(xué)士學(xué)位論文 24 dataout_valid=0。 addra[4:0]=datain_t[4:0]。 end st5:begin if(startfft) state=st3。 end else if(d_valid) begin datain_wr=0。b0。 assign blk_cf=rd_ramamp。//cfft dataout output signal wire [4:0] addr_cf1,addr_cf2。 wire [15:0] d_re。 圖 遞歸順序型 FFT 結(jié)構(gòu)框圖 module cfft32( clk, rst_n, slice_number, normal_re, normal_im, normal_valid, startfft, fft_finish, address_a, dataout_a, address_b, dataout_b, dataout_valid, number)。在用 FPGA實(shí)現(xiàn) FFT算法的時(shí)候，經(jīng)常會(huì)使用塊浮點(diǎn)的方式來進(jìn)行。 理工大學(xué)學(xué)士學(xué)位論文 16 采用變形補(bǔ)碼后，任何小于 l的 正數(shù)，兩個(gè)符號(hào)位都是 0，即 00．nxxx ...21；任何大于 l的負(fù)數(shù)，兩個(gè)符號(hào)位都是“ 1”，即 11．nxx ...21；如果兩個(gè)數(shù)相加后，其結(jié)果的符號(hào)位出現(xiàn)“ 01”或“ 10”兩種組合時(shí)，表示發(fā)生溢出。本課題也是采用的圖 。很明顯原址計(jì)算可以節(jié)省存儲(chǔ)資源，從而降低硬件的成本。圖中 用到關(guān)系式mkNk m WW ?/。 設(shè)序列 x(n)的長(zhǎng)度為 N，并且有以下的條件成立 N=2M， M為自然數(shù) 1(r)和 2(r)是 x(n)按 n的奇偶性分解成的兩個(gè) N/2 點(diǎn)的子序列，如下式所示 12,.. .1,0),2()(1 ??? Nrrxrx 12,...,1,0),12()(2 ???? Nrrxr 那么