用fpga實(shí)現(xiàn)fft算法

《用fpga實(shí)現(xiàn)fft算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、用FPGA實(shí)現(xiàn)FFT算法

2、第1內(nèi)容顯示中引言　　DFT(DiscreteFourierTransformation)是數(shù)字信號(hào)分析與處理如圖形、語(yǔ)音及圖像等領(lǐng)域的重要變換工具，直接計(jì)算DFT的計(jì)算量與變換區(qū)間長(zhǎng)度N的平方成正比。當(dāng)N較大時(shí)，因計(jì)算量太大，直接用DFT算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的?？焖俑盗⑷~變換(FastFourierTransformation，簡(jiǎn)稱FFT)使DFT運(yùn)算效率提高1～2個(gè)數(shù)量級(jí)。其原因是當(dāng)N較大時(shí)，對(duì)DFT進(jìn)行了基4和基2分解運(yùn)算。FFT算法除了必需的數(shù)據(jù)存儲(chǔ)器ram和旋轉(zhuǎn)因子rom外，仍需較復(fù)雜的運(yùn)算和控制電路單元，即使現(xiàn)在,實(shí)

3、現(xiàn)長(zhǎng)點(diǎn)數(shù)的FFT仍然是很困難。本文提出的FFT實(shí)現(xiàn)算法是基于FPGA之上的，算法完成對(duì)一個(gè)序列的FFT計(jì)算，完全由脈沖觸發(fā)，外部只輸入一脈沖頭和輸入數(shù)據(jù)，便可以得到該脈沖頭作為起始標(biāo)志的N點(diǎn)FFT輸出結(jié)果。由于使用了雙ram，該算法是流型(Pipelined)的，可以連續(xù)計(jì)算N點(diǎn)復(fù)數(shù)輸入FFT，即輸入可以是分段N點(diǎn)連續(xù)復(fù)數(shù)數(shù)據(jù)流。采用DIF(DecimationInFrequency)-FFT和DIT(DecimationInTime)-FFT對(duì)于算法本身來(lái)說(shuō)是無(wú)關(guān)緊要的，因?yàn)閮煞N情況下只是存儲(chǔ)器的讀寫地址有所變動(dòng)而已，不影響算法的結(jié)構(gòu)和流程，也不會(huì)對(duì)算法復(fù)雜度有何影響。算

4、法實(shí)現(xiàn)的可以是基2/4混合基FFT，也可以是純基4FFT和純基2FFT運(yùn)算。傅立葉變換和逆變換對(duì)于變換長(zhǎng)度為N的序列x(n)其傅立葉變換可以表示如下：　　　　　NnkX(k)=DFT[x(n)]=Σx(n)表中存儲(chǔ)的是N點(diǎn)旋轉(zhuǎn)因子表?？刂颇K產(chǎn)生所有的控制信號(hào)，存儲(chǔ)器1和2的讀寫地址、寫使能、運(yùn)算模塊的啟動(dòng)信號(hào)及因子表的讀地址等信號(hào)。當(dāng)然對(duì)于運(yùn)算模塊為基16/8復(fù)用模塊時(shí)，控制模塊就需要產(chǎn)生模式選擇信號(hào)，如對(duì)于運(yùn)算模塊是基4/2模塊時(shí)，該信號(hào)就決定了內(nèi)部運(yùn)算模塊是進(jìn)行基4運(yùn)算還是基2運(yùn)算。存儲(chǔ)器1作為當(dāng)前輸入標(biāo)志對(duì)應(yīng)輸入N點(diǎn)數(shù)據(jù)的緩沖器，存儲(chǔ)器2作為中間結(jié)果存儲(chǔ)器，用于存儲(chǔ)

5、運(yùn)算模塊計(jì)算出的各Pass的結(jié)果。在圖中的各種地址、使能和數(shù)據(jù)的緊密配合下，經(jīng)過(guò)一定延時(shí)后輸出計(jì)算結(jié)果及其對(duì)應(yīng)指示標(biāo)志。圖2只是一定點(diǎn)或浮點(diǎn)的FFT實(shí)現(xiàn)模塊，如果是塊浮點(diǎn)運(yùn)算，則必須加入一個(gè)數(shù)據(jù)因子控制器，控制每遍運(yùn)算過(guò)程中的數(shù)據(jù)大小，并根據(jù)各個(gè)Pass的乘性因子之和的大小，對(duì)最終輸出進(jìn)行大小控制，以保證每段FFT運(yùn)算輸出增益一致?！　⊥獠枯斎霝镹點(diǎn)數(shù)據(jù)段流和啟動(dòng)信號(hào)(N點(diǎn)之間如無(wú)間隔，則每N數(shù)據(jù)點(diǎn)輸入一脈沖信號(hào))，一方面，外部數(shù)據(jù)存入存儲(chǔ)器1中，同時(shí)通過(guò)控制模塊的控制，讀出存儲(chǔ)器1中的前段N點(diǎn)數(shù)據(jù)和Rom表中的因子及相關(guān)控制信號(hào)送入運(yùn)算核心模塊進(jìn)行各個(gè)Pass的運(yùn)算，每個(gè)

6、Pass的輸出都存入存儲(chǔ)器2中，最后一個(gè)Pass的計(jì)算結(jié)果存入存儲(chǔ)器2中，并在下一個(gè)啟動(dòng)頭到來(lái)后，輸出計(jì)算結(jié)果。對(duì)圖2的實(shí)現(xiàn)，除去運(yùn)算模塊，關(guān)鍵是各個(gè)Pass數(shù)據(jù)因子讀寫地址及控制信號(hào)的配合。速度、資源和精度　　假定輸入數(shù)據(jù)的速率為fin，則每數(shù)據(jù)的持續(xù)時(shí)間T=1/fin，運(yùn)算模塊的計(jì)算時(shí)鐘頻率為fa，對(duì)于N(N=2p，p即為Pass數(shù)目)點(diǎn)FFT計(jì)算時(shí)延與Pass數(shù)目直接相關(guān)。如果使用基2運(yùn)算不考慮控制開銷，純粹的計(jì)算時(shí)延為td=p×N×T×fin/fa。顯然在fa>p×fin時(shí)，在N點(diǎn)內(nèi)可完成FFT運(yùn)算。否則不能完成，即不能實(shí)現(xiàn)流型的變換。這在N很大且輸入數(shù)據(jù)速率

7、較高時(shí)以FPGA實(shí)現(xiàn)幾乎是不可能的，而且內(nèi)部計(jì)算時(shí)鐘過(guò)高容易導(dǎo)致電路的工作不穩(wěn)定。設(shè)基2時(shí)的最小可流型工作運(yùn)算頻率為fa0，則使用基4實(shí)現(xiàn)流型的變換，計(jì)算時(shí)鐘fa=fa0就可以。而使用基8時(shí)計(jì)算時(shí)鐘fa=fa0便可完成，基16時(shí)為fa0的1/4。上面所討論的是純基運(yùn)算，當(dāng)N不為4的冪次方時(shí)(如N=2048=16×16×8，運(yùn)算模塊為基16/8復(fù)用模塊)，而又希望使用較低倍的時(shí)鐘完成運(yùn)算時(shí)，圖2中的運(yùn)算模塊必然包括基4/2復(fù)用模塊(即基16/8復(fù)用模塊)，這也就是前面提到復(fù)用模塊的主要用意。由上面的分析可以得出結(jié)論，如果計(jì)算使用的基越大，完成速度越快?！　〉?，使用基16/8

8、模塊所使用的邏輯資源要比基4/2模塊多將近一倍，這是因?yàn)榛?6/8復(fù)用模塊是以基4模塊和基4/2復(fù)用模塊構(gòu)建而成。當(dāng)然，可以直接實(shí)現(xiàn)基16/8復(fù)用模塊，但用FPGA很難解決復(fù)雜度和成本問(wèn)題。另外，如果流型運(yùn)算間隔比N點(diǎn)數(shù)據(jù)長(zhǎng)度長(zhǎng)一倍以上，可以考慮在較低的計(jì)算時(shí)鐘下使用基2運(yùn)算模塊實(shí)現(xiàn)流型FFT?！　∵\(yùn)算結(jié)果的精度直接與計(jì)算過(guò)程中數(shù)據(jù)和因子位數(shù)(浮點(diǎn)算法)相關(guān)，如果中間計(jì)算的位數(shù)、存儲(chǔ)數(shù)據(jù)位數(shù)和Rom表中的位數(shù)越大，輸出精度就越大。當(dāng)然，位數(shù)增大后邏輯運(yùn)算資源和存儲(chǔ)資源都會(huì)直線上升。浮點(diǎn)、塊浮點(diǎn)和定點(diǎn)FFT　　根據(jù)運(yùn)