【正文】 x(n)的 DFT 為 ?? ?? ?? n knNn knN WnxWnxkX )()()( ?? ?? ??? ?? 12/ 0 )12(212/ 0 2 )12()2( N r rkNN r krN WrxWrx ?? ???? ? 12/ 0 2212/ 0 1 )()( N r krNN r kN WrxWrx 由于 krNkrNjkrNjkrN WeeW 2 2/22222 ??? ??ππ 所以 1,.. .,1,0)()()()()( 2112/0 2/212/0 2/1?????? ?? ????NkkXWkXWrxWWrxkW kNNrkrNkNNrkrN （ ） 其中)(1kX和)(2k分別為 1rx和(2r的 N/2 點(diǎn) DFT，即 理工大學(xué)學(xué)士學(xué)位論文 8 )]([)()()]([)()(212/02/22112/02/11rxDFTWrxkXrxDFTWrxkXNrkrNNrkrN?????????? （ ） （ ） 又由于)(1kX和)(2k都是以 N/2 為周期，且 kNNkN WW ??? 2 所以 X(k)又可 以表示為如下所示的表達(dá)式 12,...,1,0)()()( 21 ???? NkkXWkXkX kN （ ） 12,...1,0)()()2( 21 ????? NkkXWkXNk kN （ ） 這樣一個(gè) N點(diǎn)的 DFT就被拆分成為了兩個(gè) N/2點(diǎn)的 DFT。從上面的說明中可以看出， N點(diǎn)DFT的乘法和加法運(yùn)算次數(shù)均與 N2成正比。 國內(nèi)方面，我國的 FPGA 技術(shù)起步較晚，但是進(jìn)入 21 世紀(jì)后，發(fā)展非常迅速?？删幊踢壿嬈骷膽?yīng)用不僅使電子產(chǎn)品性能有了很大改善，而且也使數(shù)字系統(tǒng)設(shè)計(jì)方法發(fā)生了根本性變革。 通用數(shù)字信號(hào)處理芯片 通用數(shù)字信號(hào)處理芯片即 DSP 處理器， 按照 DSP 的用途，可分為通用型 DSP芯片和專用型 DSP 芯片 。所以， DFT 在各種數(shù)字信號(hào)處理中起著核心作用，而 DFT 的快速算法快速傅立葉變換 (Fast Fourier Transform， FFT)就成為了數(shù)字信號(hào)處理的最基本技術(shù)之一，對(duì)FFT 算法及其實(shí)現(xiàn)方式的研究是很有意義的。速度上 ASIC更占優(yōu)勢(shì)，但是隨著點(diǎn)數(shù)的增加，芯片面積將迅速擴(kuò)大，也就意味著成本的提高。 此外，數(shù)字濾波在圖像處理、語音識(shí)別和模式識(shí)別等數(shù)字信號(hào)處理中占有重要地位。但是，通用 DSP 處理器構(gòu)成的 FFT 處理器和 FIR 數(shù)字濾波器采用循環(huán)編碼算法，程序量小，但存在大量的冗余運(yùn)算，需要許多跳轉(zhuǎn)操作，處理速度較慢，難以滿足現(xiàn)代數(shù)字信號(hào)處理高速、大規(guī)模、理工大學(xué)學(xué)士學(xué)位論文 3 實(shí)時(shí)性的要求。工 作時(shí)，這些配置數(shù)據(jù)存放在片內(nèi)的SRAM 或者熔絲圖上。 20xx 年劉國棟等也使用基 2 算法設(shè)計(jì)了 FFT 單元，他使用了 ALTERA 高性能的Stratix 器件對(duì) 512 點(diǎn)、 1024 點(diǎn)、 2048 點(diǎn)、 4096 點(diǎn)和 8192 點(diǎn)都進(jìn)行了分析。 在前面已經(jīng)講到， N點(diǎn) DFT的復(fù)乘次數(shù)等于 N2。在圖 ， N=23=8，式 ()給出了 X(O)～ X(3)的計(jì)算方法，而式 ()給出了 X(4)～ X(7)的計(jì)算方法。 N1時(shí)， N(N1)是約等于 N2的。 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中。 定點(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ā)生溢出。這里討論的為有符號(hào)數(shù)?？偟膩碚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]。 理工大學(xué)學(xué)士學(xué)位論文 20 input [15:0] normal_im。 reg [4:0] datain_t。 wire start_cfft。b0。 always(posedge clk or negedge rst_n) //input datain_valid sync。 else case(state) st0 : begin //initial state if(d_valid) state = st1。// ram signal blka=1。 wrdb=1。 wrda=wr_ram。 blka=datain_blk。 dinb[35:0]=0。 wrdb=1。 blka=datain_blk。 else state=st4。 datain_blk=1。 assign dataout_b[13:0]=(dataout_valid)?{dataout_cf2[35],dataout_cf2_t2[12:0]}:1439。 理工大學(xué)學(xué)士學(xué)位論文 21 assign fft_finish=finish_butterfly。 wire [35:0] dataout_cf1,dataout_cf2。 wire d_valid。其程序設(shè)計(jì)如下。 塊浮點(diǎn)數(shù)記數(shù)方法廣泛用于信號(hào)處理領(lǐng)域，如執(zhí)行 FFT變換，它消耗的硬件資源要比浮點(diǎn)數(shù)少得多。數(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)位要丟掉。因此在大型數(shù)據(jù)處理系統(tǒng)的 FFT算法中，較多采用的是圖 法。這種利用同一存儲(chǔ)單元存儲(chǔ)蝶形運(yùn)算計(jì)算輸入、輸出數(shù)據(jù)的 方法就稱為原址計(jì)算。將前面兩次分解的過程綜合起來，就得到了一個(gè)完整的 8點(diǎn) DITFFT運(yùn)算流圖，如圖 。本課題采用的就是 DITFFT這一算法。當(dāng) N1時(shí)， N(N1)≈N2。但也存在以下的缺點(diǎn)： IP 核價(jià)格昂貴（ Altera 公司的 FFT IP 核售價(jià)為 7995 美元）， 且 IP 核源代碼不對(duì)外開放，不利于二次開發(fā)； IP 核針對(duì)通用的設(shè)計(jì)，在某些特殊的應(yīng)用場(chǎng)合不一定最優(yōu)因此還難以在我國基層應(yīng)用領(lǐng)域普及。現(xiàn)在已廣泛用于計(jì)算機(jī) 硬件、工業(yè)控制、智能儀表、通信設(shè)備和醫(yī)療電子儀器等多個(gè)領(lǐng)域。 FFT 的國內(nèi)外發(fā)展研究現(xiàn)狀 針對(duì) FFT 和 FIR 數(shù)字濾波器的硬件實(shí)現(xiàn)方案主要有三種途徑： DSP 處理器、專用集成電路 ASIC、可編程邏輯器件，其中可編程邏輯器件以 FPGA 為代 表 。由數(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ì) 算問題。而FPGA 內(nèi)部含有硬件乘法器，大量的存儲(chǔ)單元和可編程 I/O，十分適合于 FFT 處理器的實(shí)現(xiàn)，而且相對(duì) ASIC，成本低廉，可以反復(fù)編程，便于 調(diào)試，也更具市場(chǎng)競(jìng)爭(zhēng)力。與模擬濾波器相比，數(shù)字濾波器可以滿足濾波器幅度和相位特性的嚴(yán)格要求，可以克服模擬濾波器所無法克服的電壓漂移、溫度漂移和噪聲等問題。在進(jìn)行大點(diǎn)數(shù) FFT 計(jì)算和 FIR 數(shù)字濾波時(shí)，并行算法與 DSP 處理器的尋址能力不相 適應(yīng)，不能有效利用數(shù)據(jù)傳輸?shù)膸捄瓦\(yùn)算能力，造成硬件資源的浪費(fèi)。使用無 SRAM 的 FPGA，在工作前需要從芯片外部加載配置數(shù)據(jù)。 20xx 年魯欣等也設(shè)計(jì)了 4096 點(diǎn) FFT，但是他使用了 1024 點(diǎn)的 FFT IP 核進(jìn)行了擴(kuò)展設(shè)計(jì)，如果系統(tǒng)輸入時(shí)鐘為 50MHz，計(jì)算時(shí)間為 。其實(shí)一個(gè) N點(diǎn) DFT可以看做是由幾個(gè)較短的 DFT組成的。由圖 ，要完成一個(gè)蝶形運(yùn)算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法運(yùn)算。當(dāng) N=210=1024時(shí)，可以求得直接計(jì)算 N點(diǎn)的 DFT和使用基 2DITFFT算法的所需乘法次數(shù)的比值為 )2/( 22 ??NN N 這樣，運(yùn)算效率就提高了 200多倍。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距 B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，則蝶形運(yùn)算可表示成如下形式： pNLLpNLLWBJXJXBJ WBJXJXJX )()()( )()()( 11 11 ????? ???? ?? ?? 其中 p=J2ML； J=0,1,...,2L1。 定點(diǎn)數(shù)加減法的溢出及檢測(cè)方法 在定點(diǎn)小數(shù)機(jī)器中，數(shù)的表示范圍為 |X|1。 表 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)的。 理工大學(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)。 input normal_valid。 //ram control signal and databus ,address bus reg [35:0] dina,dinb。 reg datain_wr,datain_blk。 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。 if(!rst_n) valid=0。 else