用FPGA實現FFT算法(圖)
——
加入技術交流群
dft(discrete fourier transformation)是數字信號分析與處理如圖形、語音及圖像等領域的重要變換工具，直
接計算dft的計算量與變換區間長度n的平方成正比。當n較大時，因計算量太大，直接用dft算法進行譜分析和信號的實時處理是不切實際的。快速傅立葉變換(fast fourier transformation，簡稱fft)使dft運算效率提高1～2個數量級。其原因是當n較大時，對dft進行了基4和基2分解運算。fft算法除了必需的數據存儲器ram和旋轉因子rom外，仍需較復雜的運算和控制電路單元，即使現在,實現長點數的fft仍然是很困難。本文提出的fft實現算法是基于fpga之上的，算法完成對一個序列的fft計算，完全由脈沖觸發，外部只輸入一脈沖頭和輸入數據，便可以得到該脈沖頭作為起始標志的n點fft輸出結果。由于使用了雙ram，該算法是流型(pipelined)的，可以連續計算n點復數輸入fft，即輸入可以是分段n點連續復數數據流。采用dif(decimation in frequency)-fft和dit(decimation in time)-fft對于算法本身來說是無關緊要的，因為兩種情況下只是存儲器的讀寫地址有所變動而已，不影響算法的結構和流程，也不會對算法復雜度有何影響。算法實現的可以是基2/4混合基fft，也可以是純基4fft和純基2fft運算。
傅立葉變換和逆變換
對于變換長度為n的序列x(n)其傅立葉變換可以表示如下：
n
nk
式（１）
其中，w=exp(-2π/n)。
當點數n較大時，必須對式(1)進行基4/基2分解，以短點數實現長點數的變換。而idft的實現在dft的基礎上就顯得較為簡單了：
式（２）由式(2)可以看出，在fft運算模塊的基礎上，只需將輸入序列進行取共軛后再進行fft運算，輸出結果再取一次共軛便實現了對輸入序列的idft運算，因子1/n對于不同的數據表示格式具體實現時的處理方式是不一樣的。idft在fft的基礎上輸入和輸出均有一次共軛操作，但它們共用一個內核，仍然是十分方便的。
基4和基2
基4和基2運算流圖及信號之間的運算關系如圖1所示：
（a）基４蝶形算法
（b）基２蝶形算法
以基4為例，令a=r0+j
評論