【正文】 FFT 算法的設(shè)計(jì)學(xué)士學(xué)位論文 理工大學(xué)學(xué)士學(xué)位論文 II 摘 要 快速傅立葉變換 (FFT)作為時(shí)域和頻域轉(zhuǎn)換的基本運(yùn)算，是數(shù)字譜分析的必要前提。而FPGA 內(nèi)部含有硬件乘法器，大量的存儲(chǔ)單元和可編程 I/O，十分適合于 FFT 處理器的實(shí)現(xiàn)，而且相對(duì) ASIC，成本低廉，可以反復(fù)編程，便于 調(diào)試，也更具市場(chǎng)競(jìng)爭(zhēng)力。Verilog。其中，離散傅立葉變換（ Discretetime Fourier Transform， DFT）和卷積是信號(hào)處理中兩個(gè)最基本也是最常用的運(yùn)算，它們涉及到信號(hào)與系統(tǒng)的分析與綜合這一廣泛的信號(hào)處理領(lǐng)域。在不同應(yīng)用場(chǎng)合，需要不同性能要求的 FFT 處理器。與模擬濾波器相比，數(shù)字濾波器可以滿足濾波器幅度和相位特性的嚴(yán)格要求，可以克服模擬濾波器所無(wú)法克服的電壓漂移、溫度漂移和噪聲等問題。 隨著數(shù)字信號(hào)處理技術(shù)的發(fā)展，在消費(fèi)電子領(lǐng)域要求處理速度更快、功耗更低、集成度更高和產(chǎn) 品開發(fā)周期更短，因此許多數(shù)字信號(hào)處理的實(shí)現(xiàn)方法被不斷提出，其中基于 FPGA 的數(shù)字信號(hào)處理實(shí)現(xiàn)技術(shù)就是其中的重要技術(shù)之一。鑒于此種趨勢(shì)，作者將基于 FPGA的 FFT 和 FIR 數(shù)字濾波器設(shè)計(jì)與實(shí)現(xiàn)作為了研究課題。 專用 DSP 芯片是為特定的 DSP 運(yùn)算而設(shè)計(jì)的，更適合特殊的運(yùn)算，如數(shù)字濾波、卷積和 FFT，如 Motorola 公司的 DSP56200， Zoran 公司的 ZR34881， Inmos公司的 IMSA100 等就屬于專用型 DSP 芯片 。在進(jìn)行大點(diǎn)數(shù) FFT 計(jì)算和 FIR 數(shù)字濾波時(shí)，并行算法與 DSP 處理器的尋址能力不相 適應(yīng)，不能有效利用數(shù)據(jù)傳輸?shù)膸捄瓦\(yùn)算能力，造成硬件資源的浪費(fèi)。因此，任何的線路改版都需要重新設(shè)計(jì)并且重新制造，這不僅增加開發(fā)成本，而且造成產(chǎn)品快速上市的障礙，不太適合處理算法和參數(shù)經(jīng)常改變的場(chǎng)合。因此，可編程邏輯器件是設(shè)計(jì)數(shù)字系統(tǒng)的理想器件?，F(xiàn)場(chǎng)可編程門陣列（ FPGA）是 20 世紀(jì) 80 年代中期由美國(guó) Xilinx 公司首先推出的大規(guī)模可編程邏輯器件。使用無(wú) SRAM 的 FPGA，在工作前需要從芯片外部加載配置數(shù)據(jù)。 目前在國(guó)際上，兩大 FPGA 巨頭 Xilinx 和 Altera 除了 FPGA 的生產(chǎn)外還與其第三方合作伙伴致力于 IP 核的開發(fā)。使用 IP 核構(gòu)建數(shù)字信號(hào)處理系統(tǒng)具有諸多優(yōu)點(diǎn)，如開發(fā)周期短、性能穩(wěn)定、可靠、維護(hù)方便等。 20xx 年羅雪茍、詹陽(yáng)分析了使用 FPGA 實(shí)現(xiàn) FFT 的幾種方法，對(duì)這幾種方法的優(yōu)缺點(diǎn)進(jìn)行了討論。 20xx 年魯欣等也設(shè)計(jì)了 4096 點(diǎn) FFT，但是他使用了 1024 點(diǎn)的 FFT IP 核進(jìn)行了擴(kuò)展設(shè)計(jì)，如果系統(tǒng)輸入時(shí)鐘為 50MHz，計(jì)算時(shí)間為 。 第 2 章為離散福利葉變換的快速算法的基本理論； 第 3 章為基于 modelsim的 FFT 算法的設(shè)計(jì) 第 4 章為基于 verilog 語(yǔ)言的 32 點(diǎn)基 2 復(fù)數(shù)的 FFT 的設(shè)計(jì)與仿真 最后一章為結(jié)論 最后對(duì)整篇論文進(jìn)行了總結(jié)和討論。那么對(duì)于 N個(gè) k值，一共需要 N2次復(fù)數(shù)乘法以及 N(N1)次復(fù)數(shù)加法運(yùn)算。如果 N取 1024，那么 N2將達(dá)到 1,048,576。其實(shí)一個(gè) N點(diǎn) DFT可以看做是由幾個(gè)較短的 DFT組成的。比較常用的 FFT 算法有基 2FFT和基 4FFT 兩種。 由于這兩種算法的基本原理是相同的，所以下面主要介紹 DITFFT算法。通常為了后續(xù)說(shuō)明的方便，和其它許多文獻(xiàn)一樣，在本文中也將式 ()和式 ()的運(yùn)算用圖 。由圖 ，要完成一個(gè)蝶形運(yùn)算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法運(yùn)算。通過對(duì)比可以看出，只進(jìn)行過這樣的次分解就使得運(yùn)算量減少了近一半，充分說(shuō)明了這樣分解對(duì)減少 DFT的運(yùn)算量是十分有效的。依次類推，經(jīng)過 M1次分解，最后將 N點(diǎn) DFT分解成 N/2個(gè) 2點(diǎn) DFT。 圖 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)成。當(dāng) N=210=1024時(shí)，可以求得直接計(jì)算 N點(diǎn)的 DFT和使用基 2DITFFT算法的所需乘法次數(shù)的比值為 )2/( 22 ??NN N 這樣，運(yùn)算效率就提高了 200多倍。 (1)原址計(jì)算 由 圖 ， DITFFT的運(yùn)算過程是很有規(guī)律的。因?yàn)檫@樣，當(dāng)計(jì)算完一個(gè)蝶形以后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元 i以此類推，當(dāng) M級(jí)運(yùn)算都計(jì)算完畢以后，原來(lái)存放輸入序列數(shù)據(jù)的 N個(gè)存儲(chǔ)單元中便依次存放了 X(k)的 N個(gè)值。每個(gè)蝶形都要乘以因子pW。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距 B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，則蝶形運(yùn)算可表示成如下形式： pNLLpNLLWBJXJXBJ WBJXJXJX )()()( )()()( 11 11 ????? ???? ?? ?? 其中 p=J2ML； J=0,1,...,2L1。 當(dāng) N=8時(shí)，這種規(guī)律就可以用圖 。這種結(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，就可以 用它來(lái)計(jì)算 N、 N/ N/ ...長(zhǎng)度的 FFT。 浮點(diǎn)表示法所能表示的數(shù)值范圍將遠(yuǎn)遠(yuǎn)大于定點(diǎn)表示法。 定點(diǎn)數(shù)加減法的溢出及檢測(cè)方法 在定點(diǎn)小數(shù)機(jī)器中，數(shù)的表示范圍為 |X|1。 x=， Y=，那么 [x]補(bǔ) =， [y]補(bǔ) =，同理可得： [x+y]補(bǔ) =，兩個(gè)負(fù)數(shù)相加的結(jié)果成為正數(shù)，這同樣是錯(cuò)誤的。為了判斷“溢出”是否發(fā)生，可以采用雙符號(hào)位法，也稱為“變形補(bǔ)碼”或“模 4補(bǔ)碼”，從 而可使模 2補(bǔ)碼所能表示的數(shù)的范圍擴(kuò)大一倍。 定點(diǎn)數(shù)的定標(biāo) 數(shù)的定標(biāo)就是根據(jù)需要，人為地指定小數(shù)點(diǎn)的位置，這 主要是由于在利用 FPGA進(jìn)行數(shù)字系統(tǒng)設(shè)計(jì)的時(shí)候無(wú)法將小數(shù)直接表示出來(lái)。 表 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)的。進(jìn)行舍位就會(huì)自然而然的引入誤差，這種誤差屬于運(yùn)算量化誤差，也稱為運(yùn)算噪聲。由于在執(zhí)行算術(shù)運(yùn)算時(shí)需要大量的硬件資源，所以浮點(diǎn)數(shù)記數(shù)方法的使用成本很高。塊浮點(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。 理工大學(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)。這種形式的 FFT 只有一個(gè)蝶形運(yùn)算單理工大學(xué)學(xué)士學(xué)位論文 19 元，蝶形運(yùn)算按遞歸的方式，根據(jù)蝶形圖從左向右、從上向下先計(jì)算第一級(jí)的每個(gè)蝶形，然后 計(jì)算第二級(jí)、第三級(jí)，逐級(jí)地循環(huán)運(yùn)算，直至第 N/2 log2N 個(gè)蝶形，完成 N 點(diǎn) FFT的全部運(yùn)算。這種結(jié)構(gòu)的優(yōu)點(diǎn)是只有一個(gè)蝶形運(yùn)算單元，所占的硬件資源少，結(jié)構(gòu)簡(jiǎn)單，穩(wěn)定 性能好，缺點(diǎn)是運(yùn)算速度緩慢，且時(shí)序控制較為復(fù)雜。 input rst_n。 input normal_valid。 output [13:0] dataout_a。 output [3:0] number。 assign d_valid=normal_valid。 //ram control signal and databus ,address bus reg [35:0] dina,dinb。 wire [35:0] douta,doutb。 wire [31:0] datain_cf1,datain_cf2。//cfft read write and blk_en signal wire finish_butterfly。 reg datain_wr,datain_blk。 wire [15:0] d_im_conj。 wire [1:0] shift。wr_ram。 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。 assigndataout_cf2_t[24:0]={dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35:18]}number[3:0]。b0。b0。 if(!rst_n) valid=0。 else if(d_valid) datain[31:0]={d_re[15:0],d_im_conj[15:0]}。 always(posedge clk or negedge rst_n)//write data into the pingpong ram if(!rst_n) begin datain_wr=1。 理工大學(xué)學(xué)士學(xué)位論文 22 end else begin datain_wr=1。 else state = st0。 end st3: begin // start the cfft ram1。 if(finish_butterfly) state=st5。 理工大學(xué)學(xué)士學(xué)位論文 23 end default:state=st0。 addra[4:0]=0。 addrb[4:0]=0。 dina[35:0]={datain[31],datain[31],datain[31:16],datain[15],datain[15],datain[15:0]}。 dinb[35:0]=0。 dataout_valid=0。 addra[4:0]=datain_t[4:0]。 addrb[4:0]=0。 dina[35:0]=dataout_cf1[35:0]。 dinb[35:0]=dataout_cf2[35:0]。 dataout_valid=0。 addra[4:0]=addr_cf1[4:0]。 dataout_valid=~wr_ram。 addra[4:0]=datain_t[4: