基于FPGA的FFT實(shí)現(xiàn)

1、基于FPG刖FFT實(shí)現(xiàn)隨著多年的研究，F(xiàn)FT算法已經(jīng)趨于成熟，有組合數(shù)FFT算法和以維諾格蘭為代表的一類傅立葉變換算法，實(shí)現(xiàn)的算法原理也是基于這些算法?，F(xiàn)成可編程門陣列(FPGA)是八十年代中期出現(xiàn)的新型高密度可編程邏輯器件，它是在PAL、GAL、EPLD等可編程器件的基礎(chǔ)上進(jìn)一步發(fā)展的產(chǎn)物。隨著超大規(guī)模集成電路工藝的不斷提高，單一芯片內(nèi)部可容納上百萬(wàn)個(gè)晶體管，F(xiàn)PGA/CPLD芯片的規(guī)模也越來(lái)越大，其單片邏輯門數(shù)目已達(dá)到上百萬(wàn)門，它所能實(shí)現(xiàn)的功能也越來(lái)越強(qiáng)。用FPGA實(shí)現(xiàn)FFT處理器具有硬件系統(tǒng)簡(jiǎn)單、功耗低的優(yōu)點(diǎn)，同時(shí)具有開(kāi)放時(shí)間短、成本較低的優(yōu)勢(shì)。其中大部分的研究是針對(duì)FPGA的結(jié)構(gòu)特點(diǎn)，

2、充分使用了其RAM和靈活的邏輯資源實(shí)現(xiàn)并行處理和陣列處理來(lái)提高運(yùn)算速度從而減少計(jì)算時(shí)間；也有部分提高運(yùn)算精度和速度，提出自定義浮點(diǎn)格式FFT處理器的FPGA硬件實(shí)現(xiàn)方案；最近也有對(duì)FFT算法中部分計(jì)算的研究改進(jìn)，使之更加適合FPGA結(jié)構(gòu)，提高運(yùn)算速度。具體計(jì)劃如下：1) 9月30日前完成課程論文計(jì)劃書(shū)。2) 9月15日10月1日，在這段時(shí)間里通過(guò)借閱相關(guān)書(shū)籍以及網(wǎng)上的相關(guān)資料，了解FFT的FPGA實(shí)現(xiàn)的原理。3) 10月7日10月27日，這這期間，通過(guò)前段時(shí)間對(duì)原理的學(xué)習(xí)，在掌握基本的方法的情況下，參考書(shū)籍中提供的資料，學(xué)會(huì)用硬件描述語(yǔ)言VHDL進(jìn)行編程設(shè)計(jì)，并基于FFT對(duì)FPGA進(jìn)行實(shí)現(xiàn)。4

3、) 10月28日11月9日，進(jìn)行MATLAB程序的編寫(xiě)及仿真。5) 11月10日16日，通過(guò)學(xué)習(xí)以及參考書(shū)籍中的相關(guān)資料，撰寫(xiě)論文。6) 11月18日前提交論文。編輯版word摘要及其逆變換IFFF（快64、256、1024點(diǎn)提出一種利用并行算法來(lái)實(shí)現(xiàn)FFT（快速傅里葉變換）速傅里葉逆變換）的設(shè)計(jì)方法。該處理器可由用戶動(dòng)態(tài)配置成復(fù)數(shù)FFT或其逆變換IFFTo關(guān)鍵詞：FPGA,FFT,IFFT編輯版word1引言高速實(shí)時(shí)數(shù)字信號(hào)處理對(duì)系統(tǒng)性能要求很高，因此，幾乎所有的通用DSP都難以實(shí)現(xiàn)這一要求。可編程邏輯器件允許設(shè)計(jì)人員利用并行處理技術(shù)實(shí)現(xiàn)高速信號(hào)處理算法，并且只需單個(gè)器件就能實(shí)現(xiàn)期望的性能。

4、在數(shù)據(jù)通信這樣的應(yīng)用中，常常需要進(jìn)行高速、大規(guī)模的FFT及其逆變換IFFT運(yùn)算。當(dāng)通用的DSP無(wú)法達(dá)到速度要求時(shí)，唯一的選擇是增加處理器的數(shù)目，或采用定制門陣列產(chǎn)品。現(xiàn)在，隨著微電子技術(shù)的發(fā)展，采用現(xiàn)場(chǎng)可編程門陣列（FPGA）進(jìn)行數(shù)字信號(hào)處理發(fā)展迅速。采用現(xiàn)場(chǎng)可編程器件不僅加速了產(chǎn)品上市時(shí)間，還可滿足現(xiàn)在和下一代便攜式設(shè)計(jì)所需要的成本、性能、尺寸等方面的要求，并提供系統(tǒng)級(jí)支持。本文研究了基于FPGA的FFT及其逆變換IFFT處理器的硬件電路實(shí)現(xiàn)方法。在系統(tǒng)時(shí)鐘頻率為100MHz時(shí)，1024點(diǎn)復(fù)位FFT的計(jì)算時(shí)間只需要10巧左右。2基4FFT/IFFT算法序列x（n）,n=0,.,N-1的離散傅

5、里葉變換為：Xg=':舊片“次”,-I（HE前相應(yīng)的傅里葉逆交換為IA'lri）二*->這說(shuō)明IFFT可以由FFT求出。因此，F(xiàn)FT和IFFT處理器可以用統(tǒng)一的硬件結(jié)構(gòu)來(lái)實(shí)現(xiàn)。對(duì)于FFT,設(shè)序列x（n）的長(zhǎng)度為N=4p（p為整數(shù)），則基4頻率抽取蝶菜運(yùn)算單元方程為：編輯版wordX(tj)=C.rOi)+.rC*i:1+J+2X(>-)十rtw4-3-r1)l!X(n十*-*:J=15Jir(rr+51Kr'(>+"rg1-3>W+2Xr'1)=j(h).rCw+-ij_|_t3)，5"4axr-*r(A+3X-J”V

6、(/f+3x4f'=Ln燈)卜+4"i)一+2X4-7)-H和+3x4，學(xué)上面的公式中八力基1HF算法流圖中的蝶茸單元的級(jí)數(shù)y=*LII5短乂4/7+45取3I'IJ在取口,14s-1u-川X：W；一-三3FFT/IFFT的硬件實(shí)現(xiàn)我們采用Xilinx公司的Virtex-II系列FPGA來(lái)實(shí)現(xiàn)FFT/IFFT處理器。3.1 蝶形運(yùn)算單元結(jié)構(gòu)基4頻率抽取FFT計(jì)算一共包括了10g4(N)級(jí)運(yùn)算，其中，在每一級(jí)中包含了N/4個(gè)基4蝶形運(yùn)算，蝶形運(yùn)算器如圖1所示。Virtex-II系列FPGA有內(nèi)嵌18bitx18bit補(bǔ)碼乘法器以及大容量用戶可配置RAM,非常適合做大規(guī)模

7、算術(shù)運(yùn)算。圖1所示的蝶形運(yùn)算器可以在一個(gè)時(shí)鐘周期內(nèi)完成一次基4蝶形運(yùn)算。其中，操作數(shù)A、B、C、D存放在RAM中，三個(gè)18位放置因子W1、W2、W3存放在ROM中。由于運(yùn)算結(jié)果可能會(huì)超過(guò)原數(shù)據(jù)，所以要進(jìn)行量化移位12。3.2 并行運(yùn)算結(jié)構(gòu)通用DSP的蝶算單元通常是從內(nèi)存中順序讀入四個(gè)操作數(shù)A、B、C、D,因而計(jì)算速度受到了很大限制。而使用FPGA可充分利用并行計(jì)算技術(shù)在一個(gè)時(shí)鐘編輯版word周期內(nèi)并行讀取四個(gè)操作數(shù)，以便完成一次基4蝶形運(yùn)算。我們采用四對(duì)RAMX2（分別存放實(shí)部和虛部）來(lái)存儲(chǔ)蝶算中的操作數(shù)A、B、C、Do如圖2所示,處理器在每個(gè)時(shí)鐘周期從RAM中讀出數(shù)據(jù)A、B、C、D送入蝶形運(yùn)

8、算器（圖1）運(yùn)算結(jié)果AO、BO、CO、DO在下一個(gè)時(shí)鐘周期寫(xiě)回原地址。rhMti色父一ToT*-0-RAMD淞IAi修以蛆理（同址運(yùn)第J叫T甲址坨,-址：地'地W>1皿M仆仆n（崛K立而*I：&心鳥(niǎo)他留培內(nèi)圖2中的四對(duì)RAMX2的地址A0,A1,A2,A3分別對(duì)應(yīng)公式（3）中的n,n+4p-s-1,n+2X4p-s-1,n+3X4p-s-1。A0,A1,A2,A3可以按下述方法產(chǎn)生:設(shè)a,b為兩個(gè)遞減計(jì)數(shù)器，它們組成一個(gè)大的計(jì)數(shù)器Counter=ax4p-1+b。如圖3所示。編輯版wordROTATEn（x,m）表示把x（n位二進(jìn)制）循環(huán)左移m位。則圖2中四個(gè)操作數(shù)地址為

9、：A。ROTATE“IM.儲(chǔ)A=ROTATE乩+.2-JrROTATE仍+2,2口（HUKC1TATK,附+2uJ式（4）中每個(gè)地址對(duì)應(yīng)一個(gè)RAMX2的入口地址。設(shè)操作數(shù)地址A的四進(jìn)制表達(dá)式為A=（Kp-1.KiK0）4o定義Mk為A的所有四進(jìn)制位數(shù)和除以4的余數(shù)*f.mod（W匣，4.（3）j0式（5）中，mod為求余運(yùn)算?？梢宰C明地址A0,A1,A2,A3的Mk值互不相同，取值范圍是0,1,2,3。因此我們采取如圖2所示的并行存儲(chǔ)結(jié)構(gòu)：所有Mk=0的操作數(shù)都存放在RAMA中，Mk=1的操作數(shù)都存放在RAMB中，Mk=2的操作數(shù)都存放在RAMC中，Mk=3的操作數(shù)都存放在RAMD中。通過(guò)以上

10、地址映射，我們可以在一個(gè)時(shí)鐘周期并行讀取四個(gè)操作數(shù)地址，完成蝶形運(yùn)算。3.3 放置因子的生成為了加快FFT/IFFT運(yùn)算速度，我們采用查表的方式來(lái)得到放置因子W1,W2,W3（圖1）,我們采用3對(duì)ROMX2（實(shí)部和虛部）來(lái)存放復(fù)數(shù)W1,W2,W3,三個(gè)ROM的入口地址都為c?？梢宰C明，把圖3中的計(jì)數(shù)器b的低2（p-a-1泣都置為0所得到的值即為c的值。即：編輯版word3.4 FFT/IFFT芯片整體結(jié)構(gòu)FFT/IFFT芯片整體結(jié)構(gòu)如圖4所示。在式（2）中討論過(guò)，我們可以用FFT來(lái)計(jì)算IFFT,只需要先求出輸入序列的共腕X*（k）,然后進(jìn)行正常的蝶形運(yùn)算，在輸出時(shí)再進(jìn)行一次求共腕運(yùn)算。所謂復(fù)位

11、的共腕是對(duì)它的虛部取反，實(shí)部不變。因此，我們可以把處理器動(dòng)態(tài)地配置成FFT或其逆變換IFFT。為了充分利用I/O帶寬、連續(xù)地進(jìn)行FFT/IFFT。為了充分利用I/O帶寬、連續(xù)地進(jìn)行FFT/IFFT。我們采用了乒乓緩沖存儲(chǔ)結(jié)構(gòu)，如圖4所示。由于FFT/IFFT計(jì)算采用的是同址計(jì)算，每次蝶形運(yùn)算結(jié)果要寫(xiě)回原地址中,所以，RAMX和RAMY有輸入和工作兩種模式。這里，我們把RAMX和RAMY配置成乒乓結(jié)構(gòu)，當(dāng)RAMX處于工作模式時(shí)，RAMY處于輸入狀態(tài)。當(dāng)一次64/256/1024點(diǎn)FFT/IFFT完成后，RAMX和RAMY將自動(dòng)切換到另一個(gè)狀態(tài)。這樣，輸入序列就可以連續(xù)地輸入到FFT/IFFT處理

12、器中進(jìn)行變換，以達(dá)到實(shí)時(shí)處理的要求。輸出結(jié)果存放在RAMZ中，可以由用戶讀出。4測(cè)試結(jié)果這個(gè)電路采用VerilogHDL完成設(shè)計(jì)，采用Virtex-IIXC2V250實(shí)現(xiàn)。使用VilinxISE4.2i完成整套流程，圖5是部分仿真波形（modelsim+sdf）。在系統(tǒng)時(shí)鐘為100MHz時(shí)，完成一次1024點(diǎn)復(fù)數(shù)FFT/IFFT需要12.8的。相比之下，TI公司的TMS320C67（主頻167MHz）需要120gAD公司的ADSP21160（主頻100MHz）需要90的?？梢?jiàn)，基于FPGA的FFT/IFFT處理器由于其硬件上的并行性，速度遠(yuǎn)遠(yuǎn)快于一般的通用DSP。5結(jié)束語(yǔ)FPGA具有成千上萬(wàn)的

13、查找表和觸發(fā)器，因此，F(xiàn)PGA平臺(tái)可以利用更低的成編輯版word本達(dá)到此通用DSP更快的速度。采用FPGA技術(shù)，還可以獲得高性能，滿足成本要求，并享有快速有效地對(duì)新設(shè)計(jì)進(jìn)行優(yōu)化的靈活性。針對(duì)這一特性，本文研制了一種基于并行算法的FFT/IFFT處理器，可以廣泛應(yīng)用在高速信號(hào)處理系統(tǒng)中。T%輸入工作HIMIi&UEI承八工作KAMYI用-0艇歸因于»M-r-A*JCFffdKFT聞I卜TTHFT芯片作沐”.葉編輯版word參考文獻(xiàn)1 W.R.KnightandR.Kaiser.ASimpleFiexed-PointErrorBoundfortheFastFourierTransform.IEEETrans.Acoustics,SpeechandSignalProc.,Dec,1979Vol.27,No.6:6156202 L.R.RabinerandB.Gold.TheotyandApplicationofDigitalSignalProcessing.Prentice-HallInc.,En