基于Altera MegaCore實現FFT的方法

0 引 言

FFT(快速傅里葉變換)是計算離散傅里葉變換(DFT)的高效算法，它把計算N 點DFT 的乘法運算量從N2 次下降到N/2log2N 次。FFT 的出現對數字信號處理的發展起著至關重要的作用，它可應用于傅里葉變換所能涉及的任何領域，為廣泛應用數學方法處理數字信號開辟了新局面[ 1 ] 。

傳統的FFT 實現方法是通過軟件(軟件編程)和硬件(專用芯片ASIC)這兩種方法來實現，而近年來，FPGA 發展十分迅速，這給FFT 設計提供了一個新思路[2]。為了更好地滿足設計人員的需要，各大公司相繼推出了I P 模塊，本文提出了一種采用Altera 公司的IP Core FFT MegaCore來實現FFT 的簡單方法。

1 FFT MegaCore核的性能

Altera 公司的FFT MegaCore 是一個高性能、高參數化的快速傅里葉變換處理器，可以高效的完成FFT 和IFFT 運算，支持的器件系列包括Stratix Ⅱ、StratixGX、StratixⅡGX、Stratix、Cyclone、CycloneⅡ以及CycloneⅢ等，采用基2/4頻域抽取(DIF)FFT算法，運算長度從64 到16384，使用嵌入式內存，系統最大時鐘頻率大于300MHz。FFT 處理器可以設置兩種不同的引擎結構：四輸出和單輸出，結構圖如圖1 和圖2 所示[3]。

為了增加F F T 兆核函數的總吞吐量，也可以在一個FFT 兆核函數變量中使用多個并行引擎。復取樣數據X[k，m]從內部存儲器并行讀出并由變換開關(SW)重新排序，排序后的取樣數據由基4 處理器處理并得到復數輸出G [ k ，m]，由于基4 按頻率抽選(DIF)分解方法固有的數字特點，在蝶形處理器[ 4 ]輸出上僅需要3 個復數乘法器完成3 次乘旋轉因子( 有一個因子為1 ，不需要乘) 計算。這種實現結構在一個單時鐘周期內計算所有四個基4 蝶形復數輸出。同時，為了辨別取樣數據的最大動態范圍，四個輸出由塊浮點單元(BFPU)并行估計，丟棄適當的最低位(LSB)，在寫入內部存儲器之前對復數值進行四舍五入并行重新排序。

若要求轉換時間盡量小，四輸出是最佳選擇;若要求資源盡量少，單輸出比較合適。FFT 處理器支持3 種I/O 數據流結構：連續型、緩沖突發型、突發型。連續型允許在處理過程中連續輸入數據;緩沖突發型與連續型相比，占用內存資源較小，但這是以減少平均吞吐量為代價的;突發型與緩沖突發型類似，但占用內存資源更少，也是以減少平均吞吐量為代價的。

圖1 FFT處理器四輸出引擎結構

圖2 FFT處理器單輸出引擎結構

2 整體方案

整體方案設計框圖如圖3 所示。輸入緩沖器和輸出緩沖器分別存儲預處理數據和F F T 變換結果，F F T 運算器負責F F T 運算;控制器為輸入緩沖器和輸出緩沖器提供讀寫地址和控制運算時序及緩沖器的讀寫操作。下面重點介紹FFT 運算器的實現。

圖3 整體方案設計框圖