【正文】 addra[4:0]=datain_t[4:0]。 addra[4:0]=addr_cf1[4:0]。 dinb[35:0]=dataout_cf2[35:0]。 addrb[4:0]=0。 dataout_valid=0。 dina[35:0]={datain[31],datain[31],datain[31:16],datain[15],datain[15],datain[15:0]}。 addra[4:0]=0。 if(finish_butterfly) state=st5。 else state = st0。 always(posedge clk or negedge rst_n)//write data into the pingpong ram if(!rst_n) begin datain_wr=1。 if(!rst_n) valid=0。b0。 assigndatain_cf2[31:0]=(shift[1:0]==0)?{doutb[33:18],doutb[15:0]}:(shift[1:0]==1)?{doutb[34:19],doutb[16:1]}:(shift[1:0]==2)?{doutb[35:20],doutb[17:2]}:3239。 wire [1:0] shift。 reg datain_wr,datain_blk。 wire [31:0] datain_cf1,datain_cf2。 //ram control signal and databus ,address bus reg [35:0] dina,dinb。 output [3:0] number。 input normal_valid。這種結(jié)構(gòu)的優(yōu)點(diǎn)是只有一個(gè)蝶形運(yùn)算單元，所占的硬件資源少，結(jié)構(gòu)簡(jiǎn)單，穩(wěn)定 性能好，缺點(diǎn)是運(yùn)算速度緩慢，且時(shí)序控制較為復(fù)雜。 理工大學(xué)學(xué)士學(xué)位論文 18 3 FFT 的算法設(shè)計(jì) FFT 處理 器的實(shí)現(xiàn)框圖 本論文主要研究的是 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)。由于在執(zhí)行算術(shù)運(yùn)算時(shí)需要大量的硬件資源，所以浮點(diǎn)數(shù)記數(shù)方法的使用成本很高。 表 16位有符號(hào)數(shù)的定標(biāo)表示法 Q表示 S表示 十進(jìn)制數(shù)表示范圍 Q15 1=x= Q14 2=x= Q13 4=x= Q12 8=x= Q11 16=x= Q10 32=x= Q9 64=x= Q8 128=x= Q7 256=x= Q6 512=x= Q5 1024=x= Q4 2048=x= Q3 4096=x= Q2 8192=x= Q1 16384=x= Q0 32768=x=32767 有限字長(zhǎng)效應(yīng) 和單片機(jī)、 DSP等器件一樣， FPGA也是不能直接處理模擬信號(hào)的。為了判斷“溢出”是否發(fā)生，可以采用雙符號(hào)位法，也稱為“變形補(bǔ)碼”或“模 4補(bǔ)碼”，從 而可使模 2補(bǔ)碼所能表示的數(shù)的范圍擴(kuò)大一倍。 定點(diǎn)數(shù)加減法的溢出及檢測(cè)方法 在定點(diǎn)小數(shù)機(jī)器中，數(shù)的表示范圍為 |X|1。這種結(jié)構(gòu)的信號(hào)流圖有一個(gè)非常特別的優(yōu)點(diǎn)就是前一級(jí)的旋轉(zhuǎn)因子剛好是后一級(jí)上一半蝶形運(yùn)算的旋轉(zhuǎn)因子，且順序不變，如果旋轉(zhuǎn)因子的計(jì)算采用查表法，只要構(gòu)造出一個(gè) N/2點(diǎn)的NpW，就可以 用它來計(jì)算 N、 N/ N/ ...長(zhǎng)度的 FFT。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距 B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，則蝶形運(yùn)算可表示成如下形式： pNLLpNLLWBJXJXBJ WBJXJXJX )()()( )()()( 11 11 ????? ???? ?? ?? 其中 p=J2ML； J=0,1,...,2L1。因?yàn)檫@樣，當(dāng)計(jì)算完一個(gè)蝶形以后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元 i以此類推，當(dāng) M級(jí)運(yùn)算都計(jì)算完畢以后，原來存放輸入序列數(shù)據(jù)的 N個(gè)存儲(chǔ)單元中便依次存放了 X(k)的 N個(gè)值。當(dāng) N=210=1024時(shí)，可以求得直接計(jì)算 N點(diǎn)的 DFT和使用基 2DITFFT算法的所需乘法次數(shù)的比值為 )2/( 22 ??NN N 這樣，運(yùn)算效率就提高了 200多倍。依次類推，經(jīng)過 M1次分解，最后將 N點(diǎn) DFT分解成 N/2個(gè) 2點(diǎn) DFT。由圖 ，要完成一個(gè)蝶形運(yùn)算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法運(yùn)算。 由于這兩種算法的基本原理是相同的，所以下面主要介紹 DITFFT算法。其實(shí)一個(gè) N點(diǎn) DFT可以看做是由幾個(gè)較短的 DFT組成的。那么對(duì)于 N個(gè) k值，一共需要 N2次復(fù)數(shù)乘法以及 N(N1)次復(fù)數(shù)加法運(yùn)算。 20xx 年魯欣等也設(shè)計(jì)了 4096 點(diǎn) FFT，但是他使用了 1024 點(diǎn)的 FFT IP 核進(jìn)行了擴(kuò)展設(shè)計(jì)，如果系統(tǒng)輸入時(shí)鐘為 50MHz，計(jì)算時(shí)間為 。使用 IP 核構(gòu)建數(shù)字信號(hào)處理系統(tǒng)具有諸多優(yōu)點(diǎn)，如開發(fā)周期短、性能穩(wěn)定、可靠、維護(hù)方便等。使用無 SRAM 的 FPGA，在工作前需要從芯片外部加載配置數(shù)據(jù)。因此，可編程邏輯器件是設(shè)計(jì)數(shù)字系統(tǒng)的理想器件。在進(jìn)行大點(diǎn)數(shù) FFT 計(jì)算和 FIR 數(shù)字濾波時(shí)，并行算法與 DSP 處理器的尋址能力不相 適應(yīng)，不能有效利用數(shù)據(jù)傳輸?shù)膸捄瓦\(yùn)算能力，造成硬件資源的浪費(fèi)。鑒于此種趨勢(shì)，作者將基于 FPGA的 FFT 和 FIR 數(shù)字濾波器設(shè)計(jì)與實(shí)現(xiàn)作為了研究課題。與模擬濾波器相比，數(shù)字濾波器可以滿足濾波器幅度和相位特性的嚴(yán)格要求，可以克服模擬濾波器所無法克服的電壓漂移、溫度漂移和噪聲等問題。其中，離散傅立葉變換（ Discretetime Fourier Transform， DFT）和卷積是信號(hào)處理中兩個(gè)最基本也是最常用的運(yùn)算，它們涉及到信號(hào)與系統(tǒng)的分析與綜合這一廣泛的信號(hào)處理領(lǐng)域。而FPGA 內(nèi)部含有硬件乘法器，大量的存儲(chǔ)單元和可編程 I/O，十分適合于 FFT 處理器的實(shí)現(xiàn)，而且相對(duì) ASIC，成本低廉，可以反復(fù)編程，便于 調(diào)試，也更具市場(chǎng)競(jìng)爭(zhēng)力。 本文應(yīng)用 Verilog 語言完成 32 點(diǎn)基 2 復(fù)數(shù)的 FFT 處理系統(tǒng)設(shè)計(jì)，包括蝶形運(yùn)算單元設(shè)計(jì)、存儲(chǔ)單元設(shè)計(jì)、塊浮點(diǎn)單元設(shè)計(jì)、地址產(chǎn)生單元設(shè)計(jì)、功能切換單元設(shè)計(jì)以及時(shí)序控制單元的設(shè)計(jì)工作。由數(shù)字信號(hào)處理的基本理論可知，卷積可以轉(zhuǎn)化為 DFT 來實(shí)現(xiàn)，實(shí)際上其他許多算法，如相關(guān)、譜分析等也都可以轉(zhuǎn)化 DFT 來實(shí)現(xiàn)；此外，各種系統(tǒng)的分析、設(shè)計(jì)和實(shí)現(xiàn)中都會(huì)用到 DFT 的計(jì) 算問題。有限沖激響應(yīng)（ FIR）濾波器可以保證嚴(yán)格的線性相位。 FFT 的國(guó)內(nèi)外發(fā)展研究現(xiàn)狀 針對(duì) FFT 和 FIR 數(shù)字濾波器的硬件實(shí)現(xiàn)方案主要有三種途徑： DSP 處理器、專用集成電路 ASIC、可編程邏輯器件，其中可編程邏輯器件以 FPGA 為代 表 。 專用集成電路芯片 ASIC 在集成電路界 ASIC 被認(rèn)為是一種為專門目的而設(shè)計(jì)的集成電路?，F(xiàn)在已廣泛用于計(jì)算機(jī) 硬件、工業(yè)控制、智能儀表、通信設(shè)備和醫(yī)療電子儀器等多個(gè)領(lǐng)域。配置數(shù)據(jù)可以存儲(chǔ)在片外的 EPROM 或其他存儲(chǔ)體上，人們可以控制加載過程，在現(xiàn)場(chǎng)修改器件的邏輯功能，即所謂現(xiàn)場(chǎng)編程。但也存在以下的缺點(diǎn)： IP 核價(jià)格昂貴（ Altera 公司的 FFT IP 核售價(jià)為 7995 美元）， 且 IP 核源代碼不對(duì)外開放，不利于二次開發(fā)； IP 核針對(duì)通用的設(shè)計(jì)，在某些特殊的應(yīng)用場(chǎng)合不一定最優(yōu)因此還難以在我國(guó)基層應(yīng)用領(lǐng)域普及。 20xx 年劉在爽、盧瑩瑩對(duì) FPGA 實(shí)現(xiàn) FIR 數(shù)字濾波器也進(jìn)行研究，討論了乘累加和基于 CSD（ Canonic signed Digital，標(biāo)準(zhǔn)有符號(hào)數(shù)）編碼的數(shù)字濾波器的設(shè)計(jì)。當(dāng) N1時(shí)， N(N1)≈N2?；谶@一思想，可以將 N點(diǎn) DFT分解為幾個(gè)較短的 DFT，這樣一來乘法次數(shù)將大大減少，能夠非常明顯地降低 DFT的運(yùn)算量。本課題采用的就是 DITFFT這一算法。由圖 ，經(jīng)過一次分解后，計(jì)算一個(gè) N點(diǎn) DFT共需要計(jì)算兩個(gè) N/2點(diǎn)DFT可和 N/2個(gè)蝶形運(yùn)算。將前面兩次分解的過程綜合起來，就得到了一個(gè)完整的 8點(diǎn) DITFFT運(yùn)算流圖，如圖 。圖 FFT算法與直接計(jì)算 DFT所需乘法次數(shù)的比較曲線。這種利用同一存儲(chǔ)單元存儲(chǔ)蝶形運(yùn)算計(jì)算輸入、輸出數(shù)據(jù)的 方法就稱為原址計(jì)算。L=1,2,...,M 下標(biāo) L表示第 L級(jí)運(yùn)算， XI， (J)則表示第 L級(jí)運(yùn)算后數(shù)組元素 X(J)的值。因此在大型數(shù)據(jù)處理系統(tǒng)的 FFT算法中，較多采用的是圖 法。在運(yùn)算過程中如出現(xiàn)大于 1的現(xiàn)象，稱為“溢出”。數(shù)的變形補(bǔ)碼定義為： [x]補(bǔ) =x 當(dāng) 2x≥O [x]補(bǔ) =4+x 當(dāng) 0x≥2 或用同余式表示為： [x]補(bǔ) =4+X (mod 4) 下式也同樣成立： [x]補(bǔ) +[y]補(bǔ) =[x+y]補(bǔ) (mod 4) 為了得到兩數(shù)變形補(bǔ)碼之和等于兩數(shù)和的變形補(bǔ)碼，同樣必須： 兩個(gè)符號(hào)位都看做數(shù)碼一樣參加運(yùn)算； 兩數(shù)進(jìn)行以 4為模的加法，即最高符號(hào)位上產(chǎn)生的進(jìn)位要丟掉。模擬信號(hào)必須利用 A/D轉(zhuǎn)換成數(shù)字信號(hào)以后才能利用 FPGA處理。 塊浮點(diǎn)數(shù)記數(shù)方法廣泛用于信號(hào)處理領(lǐng)域，如執(zhí)行 FFT變換，它消耗的硬件資源要比浮點(diǎn)數(shù)少得多。基 2FFT 模塊設(shè)計(jì)主要由 6 個(gè)部分組成：蝶形運(yùn)算單元、存儲(chǔ)單元、地址生成單元、功能切換單元、塊浮點(diǎn)單元和時(shí)序控制單元 [4]，如圖 所示。其程序設(shè)計(jì)如下。 input startfft。 wire d_valid。 reg wrda,wrdb。 wire [35:0] dataout_cf1,dataout_cf2。 wire [3:0] address_w。 理工大學(xué)學(xué)士學(xué)位論文 21 assign fft_finish=finish_butterfly。b0。 assign dataout_b[13:0]=(dataout_valid)?{dataout_cf2[35],dataout_cf2_t2[12:0]}:1439。 else valid=d_valid。 datain_blk=1。 end st1: state=st2。 else state=st4。 wrda=1。 blka=datain_blk。 end st2 : begin// write the first bank data to ram1 cf_address_gen_en=0。 wrdb=1。 blkb=blk_cf。 dinb[35:0]=0。 wrda=datain_wr。 blka=datain_blk。// ram signal blka=blk_cf。 wrda=wr_ram。 //disable the b block of the ram1 blkb=1。 wrdb=1。 end st1 : begin// write the data to ram