用FPGA實(shí)現(xiàn)FFT算法(圖)
——
加入技術(shù)交流群
dft(discrete fourier transformation)是數(shù)字信號(hào)分析與處理如圖形、語音及圖像等領(lǐng)域的重要變換工具，直
接計(jì)算dft的計(jì)算量與變換區(qū)間長度n的平方成正比。當(dāng)n較大時(shí)，因計(jì)算量太大，直接用dft算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的?？焖俑盗⑷~變換(fast fourier transformation，簡稱fft)使dft運(yùn)算效率提高1～2個(gè)數(shù)量級(jí)。其原因是當(dāng)n較大時(shí)，對dft進(jìn)行了基4和基2分解運(yùn)算。fft算法除了必需的數(shù)據(jù)存儲(chǔ)器ram和旋轉(zhuǎn)因子rom外，仍需較復(fù)雜的運(yùn)算和控制電路單元，即使現(xiàn)在,實(shí)現(xiàn)長點(diǎn)數(shù)的fft仍然是很困難。本文提出的fft實(shí)現(xiàn)算法是基于fpga之上的，算法完成對一個(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(decimation in frequency)-fft和dit(decimation in time)-fft對于算法本身來說是無關(guān)緊要的，因?yàn)閮煞N情況下只是存儲(chǔ)器的讀寫地址有所變動(dòng)而已，不影響算法的結(jié)構(gòu)和流程，也不會(huì)對算法復(fù)雜度有何影響。算法實(shí)現(xiàn)的可以是基2/4混合基fft，也可以是純基4fft和純基2fft運(yùn)算。
傅立葉變換和逆變換
對于變換長度為n的序列x(n)其傅立葉變換可以表示如下：
n
nk
式（１）
其中，w=exp(-2π/n)。
當(dāng)點(diǎn)數(shù)n較大時(shí)，必須對式(1)進(jìn)行基4/基2分解，以短點(diǎn)數(shù)實(shí)現(xiàn)長點(diǎn)數(shù)的變換。而idft的實(shí)現(xiàn)在dft的基礎(chǔ)上就顯得較為簡單了：
式（２）由式(2)可以看出，在fft運(yùn)算模塊的基礎(chǔ)上，只需將輸入序列進(jìn)行取共軛后再進(jìn)行fft運(yùn)算，輸出結(jié)果再取一次共軛便實(shí)現(xiàn)了對輸入序列的idft運(yùn)算，因子1/n對于不同的數(shù)據(jù)表示格式具體實(shí)現(xiàn)時(shí)的處理方式是不一樣的。idft在fft的基礎(chǔ)上輸入和輸出均有一次共軛操作，但它們共用一個(gè)內(nèi)核，仍然是十分方便的。
基4和基2
基4和基2運(yùn)算流圖及信號(hào)之間的運(yùn)算關(guān)系如圖1所示：
?。╝）基４蝶形算法
?。╞）基２蝶形算法
以基4為例，令a=r0+j
評論