基于fpga的快速傅里葉變換的fpga實(shí)現(xiàn)

基于fpga的快速傅里葉變換的fpga實(shí)現(xiàn)

0fpga簡(jiǎn)介有限段的dft（分散傅里葉變換）特征是將頻域中的數(shù)據(jù)離散簡(jiǎn)化為有限段。但由于DFT本身運(yùn)算量相當(dāng)大,限制了它的實(shí)際應(yīng)用。FFT(快速傅里葉變換)算法是作為DFT的快速算法提出,它將長(zhǎng)序列的DFT分解為短序列的DFT,大大減少了運(yùn)算量,使得DFT算法在頻譜分析、濾波器設(shè)計(jì)等領(lǐng)域得到了廣泛的應(yīng)用。FPGA(現(xiàn)場(chǎng)可編程門陣列)是一種具有大規(guī)?？删幊涕T陣列的器件,不僅具有專用集成電路(ASIC)快速的特點(diǎn),更具有很好的系統(tǒng)實(shí)現(xiàn)的靈活性。FPGA可通過(guò)開發(fā)工具實(shí)現(xiàn)在線編程。與CPLD(復(fù)雜可編程邏輯器件)相比,FPGA屬寄存器豐富型結(jié)構(gòu),更加適合于完成時(shí)序邏輯控制。因此,FPGA為高速FFT算法的實(shí)現(xiàn)提供了一個(gè)很好的平臺(tái)。1輸出變量的同址運(yùn)算在FFT各類算法中,基2-FFT算法是最簡(jiǎn)單的一種,但其運(yùn)算量與基4-FFT算法相比則大得多,分裂基算法綜合了基4和基2算法的特點(diǎn),雖然具有最少的復(fù)乘運(yùn)算量,但其L蝶形運(yùn)算控制的復(fù)雜性也限制了其在硬件上的實(shí)現(xiàn),因此,本設(shè)計(jì)采用了基4-FFT算法結(jié)構(gòu)?；?-FFT算法的基本運(yùn)算是4點(diǎn)DFT。一個(gè)4點(diǎn)的DFT運(yùn)算的表達(dá)式為:[X′(0)X′(2)X′(1)X′(3)]=[11111-11-11-j-1j1j-1-j][X(0)W0ΝX(1)WΚ0ΝX(2)W2Κ0ΝX(3)W3Κ0Ν](1)??????X′(0)X′(2)X′(1)X′(3)??????=??????11111?1?jj11?1?11?1j?j?????????????X(0)W0NX(1)WK0NX(2)W2K0NX(3)W3K0N???????(1)式(1)對(duì)于輸出變量進(jìn)行了二進(jìn)制倒序,便于在運(yùn)算過(guò)程中進(jìn)行同址運(yùn)算,節(jié)省了運(yùn)算過(guò)程中所需存儲(chǔ)器單元的數(shù)量。按DIT(時(shí)間抽取)的1024點(diǎn)的基4-FFT共需5級(jí)蝶形運(yùn)算,每級(jí)從RAM中讀取的數(shù)據(jù)經(jīng)過(guò)蝶形運(yùn)算后原址存入存儲(chǔ)單元準(zhǔn)備下一級(jí)運(yùn)算。算法的第1級(jí)為一組N=1024點(diǎn)的基4蝶形運(yùn)算,共256個(gè)蝶形,每個(gè)蝶形的距離為256點(diǎn);第2級(jí)為4組N=256點(diǎn)的基4蝶形運(yùn)算,每組64個(gè)蝶形,每個(gè)蝶形的距離為64點(diǎn)。后3級(jí)類推。這種算法每一級(jí)的運(yùn)算具有相對(duì)獨(dú)立性,每級(jí)運(yùn)算都采用同址運(yùn)算,因此,本設(shè)計(jì)只使用了2個(gè)1k×16bits的RAM單元。運(yùn)算過(guò)程中所需的旋轉(zhuǎn)因子的值經(jīng)過(guò)查詢預(yù)設(shè)的正弦與余弦ROM表得到。210輸出有效數(shù)據(jù)區(qū)本設(shè)計(jì)的總體框圖如圖1所示。整個(gè)模塊的輸入包括16位帶符號(hào)實(shí)部和虛部數(shù)據(jù)輸入、FFT啟動(dòng)信號(hào),輸出包括16位帶符號(hào)實(shí)部和虛部數(shù)據(jù)輸出、輸出有效數(shù)據(jù)區(qū)間標(biāo)志。內(nèi)部結(jié)構(gòu)包括2個(gè)1k×16bits的實(shí)部和虛部雙口RAM存儲(chǔ)單元、蝶形運(yùn)算單元、旋轉(zhuǎn)因子生成模塊(包括正弦因子查詢表、余弦因子查詢表和象限轉(zhuǎn)換模塊)、RAM和ROM存儲(chǔ)器地址控制單元、倒序模塊以及時(shí)序總控制單元。下面對(duì)主要單元進(jìn)行分析。2.1旋轉(zhuǎn)因子的存儲(chǔ)在整個(gè)FFT運(yùn)算過(guò)程中,需要存儲(chǔ)一組旋轉(zhuǎn)因子表用于蝶形運(yùn)算,如第1級(jí)運(yùn)算需要的旋轉(zhuǎn)因子有W0102401024,W1102411024,…,W1023102410231024,根據(jù)旋轉(zhuǎn)因子的可約性,后幾級(jí)運(yùn)算所需的旋轉(zhuǎn)因子都可以在這一組數(shù)據(jù)中查到,因此無(wú)需另外存儲(chǔ)。為了更節(jié)省存儲(chǔ)資源,本設(shè)計(jì)只在ROM單元中存儲(chǔ)了前256個(gè)旋轉(zhuǎn)因子數(shù)據(jù),即第1象限因子W0102401024,W1102411024,…,W2551024,。其余象限的因子通過(guò)象限轉(zhuǎn)換后得到。這樣便可以節(jié)省3/4的ROM存儲(chǔ)單元的硬件資源。2.2蝴蝶生產(chǎn)單元2.2.1旋轉(zhuǎn)因子法蝶形運(yùn)算單元包括輸入輸出寄存器、串/并轉(zhuǎn)換、并/串轉(zhuǎn)換和復(fù)數(shù)乘法器等。從基本的基4蝶形運(yùn)算表達(dá)式可以看出,每一級(jí)的輸出數(shù)據(jù)在進(jìn)入下一級(jí)運(yùn)算之前都要首先與旋轉(zhuǎn)因子WnkΝ進(jìn)行相乘。本設(shè)計(jì)采用如圖2的蝶形運(yùn)算器結(jié)構(gòu)。這種結(jié)構(gòu)是經(jīng)過(guò)優(yōu)化的蝶形運(yùn)算器結(jié)構(gòu),文獻(xiàn)給出了這一結(jié)構(gòu)的具體分析,這樣的結(jié)構(gòu)與傳統(tǒng)的需要3個(gè)復(fù)乘單元的蝶形結(jié)果相比,因?yàn)椴捎昧肆魉€控制,硬件上節(jié)省了2個(gè)復(fù)乘單元,而輸出同樣只需4個(gè)時(shí)鐘周期,工作效率并未降低。在FPGA設(shè)計(jì)中,一個(gè)乘法器的引入,尤其是高位數(shù)的乘法器的引入,將很大程度地影響系統(tǒng)整體的運(yùn)行速率,并且將占用大量的資源。因此,這種改進(jìn)方案更有利于FFT算法的高效實(shí)現(xiàn)。2.2.2i型白砂糖復(fù)乘對(duì)于復(fù)乘單元的設(shè)計(jì),常見(jiàn)的復(fù)乘方式為:x′+y′i=(x+yi)(c+si)=xc-ys+i(yc+xs)(2)式中:i為虛數(shù)單位。這種乘法表達(dá)式需要4個(gè)實(shí)數(shù)乘法運(yùn)算和2個(gè)加減運(yùn)算,設(shè)計(jì)中對(duì)表達(dá)式進(jìn)行如下變換:x′+y′i=(x+yi)(c+si)=x(c+s)-(y+x)s+i[x(s+c)+(y-x)c](3)式(3)這種復(fù)乘方式只需要3個(gè)實(shí)數(shù)乘法運(yùn)算和5個(gè)加減就可以完成復(fù)乘運(yùn)算,減少了乘法器數(shù)量。式中(c+s)值可以在進(jìn)行象限轉(zhuǎn)換的同時(shí)通過(guò)計(jì)算得到,而無(wú)需另外存儲(chǔ)。2.2.3計(jì)算和顯示算法為了防止數(shù)據(jù)計(jì)算過(guò)程中的溢出,上述蝶形單元中的加減法運(yùn)算單元對(duì)于輸入的4個(gè)有符號(hào)復(fù)數(shù)數(shù)據(jù)采取了符號(hào)位擴(kuò)展相加后再對(duì)計(jì)算結(jié)果進(jìn)行1/4倍壓縮的方法進(jìn)行計(jì)算。而對(duì)于乘法單元?jiǎng)t采用了刻度(scaling)的方法,將復(fù)數(shù)數(shù)據(jù)(16位)與旋轉(zhuǎn)因子(8位)相乘后,得到24位數(shù)據(jù)結(jié)果刻度為16位數(shù)據(jù)后,再存入RAM單元中參與下一級(jí)運(yùn)算。經(jīng)過(guò)這樣處理后,有效地防止了整個(gè)系統(tǒng)在運(yùn)算過(guò)程中出現(xiàn)的數(shù)據(jù)溢出情況,保證了最終運(yùn)算結(jié)果的可靠性。2.3計(jì)算地址讀取方式在FFT運(yùn)算過(guò)程中,地址的產(chǎn)生包括復(fù)數(shù)數(shù)據(jù)存儲(chǔ)RAM的讀寫地址(RAM_addr)產(chǎn)生和旋轉(zhuǎn)因子表的讀取地址產(chǎn)生。對(duì)于不同級(jí)運(yùn)算情況下,RAM讀寫的控制必須按DIT的倒序規(guī)則進(jìn)行,這在程序中就需要若干個(gè)變量來(lái)控制。假設(shè)控制級(jí)數(shù)的變量是L,每級(jí)的蝶形運(yùn)算距離是D,當(dāng)前計(jì)算蝶形所在的組為第S組,共N組,當(dāng)前計(jì)算蝶形所在組中的位置是第A個(gè)蝶形,那么每個(gè)蝶形的4個(gè)輸入數(shù)據(jù)地址分別為:{RAΜ_addr1=(Ν-S)(D×4)+ARAΜ_addr2=RAΜ_addr1+dRAΜ_addr3=RAΜ_addr2+dRAΜ_addr4=RAΜ_addr3+d(4)ROM讀取地址ROM_addr可按如下式子計(jì)算得到:RΟΜ_addr={iAΝiAΝ≤255512-iAΝ255<iAΝ≤512iAΝ-512512<iAΝ≤7681024-iAΝiAΝ>768(5)式中iAN=i×A×N:i=2,1,3,為輸出4點(diǎn)數(shù)據(jù)的倒序序號(hào),當(dāng)i為0時(shí)數(shù)據(jù)直接輸出,無(wú)需對(duì)ROM進(jìn)行讀取。本設(shè)計(jì)中采用的RAM模塊為QuartusⅡ軟件中的雙口RAM模塊,此模塊存儲(chǔ)與讀取可以同時(shí)進(jìn)行。系統(tǒng)單獨(dú)完成一個(gè)蝶形運(yùn)算總共需要11個(gè)時(shí)鐘周期,為了能夠充分利用乘法器的運(yùn)行效率,設(shè)計(jì)采用了流水線工作方式,平均完成一個(gè)蝶形運(yùn)算只需4個(gè)時(shí)鐘周期。復(fù)數(shù)乘法器的工作時(shí)序占整個(gè)工作時(shí)序的75%,具有較高的工作效率。綜上所述,可以得到如圖3所示流水線工作圖。圖3中,RAM_addr為分別計(jì)算4個(gè)數(shù)據(jù)地址,地址計(jì)算結(jié)果將交替存入寄存器組a和b中。這種控制方式類似于PingpongRAM的控制方式,適用于流水線工作時(shí)序中,可以較大地提高系統(tǒng)的工作效率。地址寄存器組a(或b)中的第1個(gè)地址在用于保存完本次蝶形運(yùn)算數(shù)據(jù)的第1個(gè)計(jì)算結(jié)果數(shù)據(jù)之后的,將被立即寫入下一個(gè)蝶形第1個(gè)數(shù)據(jù)讀取地址,可見(jiàn)這種流水線方式具有非常高的工作效率。圖3中,ROM_addr為分別計(jì)算3個(gè)旋轉(zhuǎn)因子的地址,M1、M2、M3分別為每個(gè)蝶形單元的3次復(fù)乘。蝶形運(yùn)算單元對(duì)4個(gè)輸入數(shù)據(jù)A/B/C/D進(jìn)行計(jì)算,輸出結(jié)果4個(gè)數(shù)據(jù)為A′/B′/C′/D′?？梢钥闯?在這16個(gè)時(shí)鐘單元中,共有4個(gè)蝶形運(yùn)算同時(shí)處于流水線工作中,因此每個(gè)蝶形運(yùn)算平均只需4個(gè)時(shí)鐘周期就可以完成。需要指出的是,在所有蝶形運(yùn)算結(jié)束后,即第5級(jí)運(yùn)算完成后,所存儲(chǔ)在RAM中的數(shù)據(jù)是四進(jìn)制倒序的,為了能在輸出端得到正確的1024點(diǎn)頻域數(shù)據(jù),在輸出時(shí)必須進(jìn)行四進(jìn)制倒序輸出,輸出的數(shù)據(jù)可以直接用于后續(xù)的數(shù)據(jù)分析等工作。2.4數(shù)值結(jié)果對(duì)比在QuartusⅡ軟件中利用simulatortool工具在100MHz的時(shí)鐘環(huán)境下對(duì)系統(tǒng)進(jìn)行了仿真。輸入時(shí)域數(shù)據(jù)為一個(gè)矩形窄脈沖信號(hào),完成整個(gè)FFT運(yùn)算的耗時(shí)僅為51.28μs。仿真得到的矢量波形文件的部分結(jié)果如圖4所示。將仿真輸出結(jié)果轉(zhuǎn)換成tbl文件并利用MATLAB軟件讀取后,得到如圖5所示的頻譜數(shù)據(jù)圖(實(shí)部數(shù)據(jù)部分)。圖6所示為MATLAB自帶FFT()函數(shù)對(duì)于輸入相同1024點(diǎn)數(shù)據(jù)的FFT計(jì)算結(jié)果(同樣為實(shí)部數(shù)據(jù)部分)。通過(guò)對(duì)比可以看到,本設(shè)計(jì)的仿真結(jié)果與MATLAB計(jì)算的結(jié)果基本一致。只在較小值受到了有限字長(zhǎng)效應(yīng)的影響。就總體而言,本設(shè)計(jì)能夠正確而高效地計(jì)算輸入的1024點(diǎn)數(shù)據(jù)的頻域數(shù)據(jù)值,數(shù)據(jù)能夠有效地用于實(shí)際的頻譜分析過(guò)程中。3fft的fpga仿真1024點(diǎn)基4-FFT算法共需要5級(jí)運(yùn)算,每級(jí)需要計(jì)算256個(gè)蝶形,由前所述,平均每個(gè)蝶形運(yùn)算需要4個(gè)時(shí)鐘周期,所以理論上完成1024點(diǎn)FFT的總時(shí)鐘周期