用FPGA實(shí)現FFT算法

引言

　　DFT(Discrete Fourier Transformation)是數字信號分析與處理如圖形、語(yǔ)音及圖像等領(lǐng)域的重要變換工具，直接計算DFT的計算量與變換區間長(cháng)度N的平方成正比。當N較大時(shí)，因計算量太大，直接用DFT算法進(jìn)行譜分析和信號的實(shí)時(shí)處理是不切實(shí)際的?？焖俑盗⑷~變換(Fast Fourier Transformation，簡(jiǎn)稱(chēng)FFT)使DFT運算效率提高1～2個(gè)數量級。其原因是當N較大時(shí)，對DFT進(jìn)行了基4和基2分解運算。FFT算法除了必需的數據存儲器ram和旋轉因子rom外，仍需較復雜的運算和控制電路單元，即使現在,實(shí)現長(cháng)點(diǎn)數的FFT仍然是很困難。本文提出的FFT實(shí)現算法是基于FPGA之上的，算法完成對一個(gè)序列的FFT計算，完全由脈沖觸發(fā)，外部只輸入一脈沖頭和輸入數據，便可以得到該脈沖頭作為起始標志的N點(diǎn)FFT輸出結果。由于使用了雙ram，該算法是流型(Pipelined)的，可以連續計算N點(diǎn)復數輸入FFT，即輸入可以是分段N點(diǎn)連續復數數據流。采用DIF(Decimation In Frequency)-FFT和DIT(Decimation In Time)-FFT對于算法本身來(lái)說(shuō)是無(wú)關(guān)緊要的，因為兩種情況下只是存儲器的讀寫(xiě)地址有所變動(dòng)而已，不影響算法的結構和流程，也不會(huì )對算法復雜度有何影響。算法實(shí)現的可以是基2/4混合基FFT，也可以是純基4FFT和純基2FFT運算。

傅立葉變換和逆變換

對于變換長(cháng)度為N的序列x(n)其傅立葉變換可以表示如下：

 　　　　式（１）

其中，W="exp"(-2π/N)。 當點(diǎn)數N較大時(shí)，必須對式(1)進(jìn)行基4/基2分解，以短點(diǎn)數實(shí)現長(cháng)點(diǎn)數的變換。而IDFT的實(shí)現在DFT的基礎上就顯得較為簡(jiǎn)單了：

　　　　　　　　　　　　　　　　　　　式（２）

由式(2)可以看出，在FFT運算模塊的基礎上，只需將輸入序列進(jìn)行取共軛后再進(jìn)行FFT運算，輸出結果再取一次共軛便實(shí)現了對輸入序列的IDFT運算，因子1/N對于不同的數據表示格式具體實(shí)現時(shí)的處理方式是不一樣的。IDFT在FFT的基礎上輸入和輸出均有一次共軛操作，但它們共用一個(gè)內核，仍然是十分方便的。

基4和基2
基4和基2運算流圖及信號之間的運算關(guān)系如圖1所示：
（a）基４蝶形算法 （b）基２蝶形算法

　　以基4為例，令A="r0"+j