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

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

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

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

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

5、里葉變換為：Xg=':舊片“次”,-I（HE前相應的傅里葉逆交換為IA'lri）二*->這說明IFFT可以由FFT求出。因此，F(xiàn)FT和IFFT處理器可以用統(tǒng)一的硬件結(jié)構(gòu)來實現(xiàn)。對于FFT,設(shè)序列x（n）的長度為N=4p（p為整數(shù)），則基4頻率抽取蝶菜運算單元方程為：編輯版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，學上面的公式中八力基1HF算法流圖中的蝶茸單元的級數(shù)y=*LII5短乂4/7+45取3I'IJ在取口,14s-1u-川X：W；一-三3FFT/IFFT的硬件實現(xiàn)我們采用Xilinx公司的Virtex-II系列FPGA來實現(xiàn)FFT/IFFT處理器。3.1 蝶形運算單元結(jié)構(gòu)基4頻率抽取FFT計算一共包括了10g4(N)級運算，其中，在每一級中包含了N/4個基4蝶形運算，蝶形運算器如圖1所示。Virtex-II系列FPGA有內(nèi)嵌18bitx18bit補碼乘法器以及大容量用戶可配置RAM,非常適合做大規(guī)模

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

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

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

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

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

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

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