基于FPGA的64點FFT處理器設計

0 引 言
    DFT作為DSP領域中時域和頻域轉換的基本運算，存在運算量太大的缺點，導致其應用受到局限。 DFT快速算法FFT的提出，簡化了DFT的運算過程，使其在實時信號處理領域中得到廣泛應用。FFT實現(xiàn)的方法包括軟件實現(xiàn)和硬件實現(xiàn)兩種。采用軟件實現(xiàn)FFT的方法存在計算慢，實現(xiàn)過程復雜等缺點，所以目前比較流行的方式是采用硬件實現(xiàn)FFT。硬件實現(xiàn)的具體方法可以分為ASIC方法、FPGA方法、 DSP方法和通用處理機方法等。
    FPGA是20世紀80年代中期出現(xiàn)的一種新的電子設計自動化技術，具有集成度高，邏輯實現(xiàn)能力強，設計靈活等優(yōu)勢。在FPGA上實現(xiàn)數(shù)字信號處理，即用純數(shù)字邏輯進行DSP模塊設計，為高速數(shù)字信號處理算法提供了實現(xiàn)途徑。在此，采用FPGA方法設計64點FFT處理器。
    現(xiàn)有的FFT模塊可以對多點數(shù)據(jù)進行運算，但是存在運算周期長。結構復雜，硬件資源耗費大等缺陷。采用64點FFT可以通過優(yōu)化結構來快速處理多點數(shù)數(shù)據(jù)。目前設計的64點FFT處理器主要采用以專用處理單元取代常規(guī)FFT處理單元的方法，或者按照固定幾何結構設計FFT處理器的方法。這里所介紹的64 點FFT處理器是在固定幾何結構設計方法的基礎上加以改進，將輸入的64點數(shù)據(jù)均勻分成8組，并行輸入給FFT運算單元，進行FFT運算。通過對蝶形運算單元進行優(yōu)化設計，所設計的64點FFT處理器模塊較之以往的FFT模塊，節(jié)省了硬件資源，提高了運算效率。通過ModelSim仿真實驗證明，在外部工作時鐘頻率為40 MHz下，對隨機生成的序列進行64點FFT運算處理，運算時間為10μs，縮短了現(xiàn)有FFT模塊的運算時間。

1 按頻率抽取的基——4FFT算法原理
    對于序列長度為N(N為2的整數(shù)次冪)的FFT算法主要有基-2 FFT和基-4 FFT兩種。計算一次基-2FFT需要二次復乘和兩次復加；計算一次基-4 FFT需要三次復乘和八次復加。從運算次數(shù)上看，基-2 FFT較為簡單，但是因為基-2 FFT的復數(shù)運算較為復雜，所以在硬件實現(xiàn)上反而要比基-4 FFT占用的資源更多。為了滿足對數(shù)據(jù)高速處理的要求，在此選擇在FP-GA上實現(xiàn)基-4 FFT的算法。
    根據(jù)定義，對于長度為N的序列x(N)(0≤N≤N-1)，它的DFT可表示為：

  
式中：WnkN=e-J2π/Nnk稱為旋轉因子。直接計算DFT，需要的計算量為N2次復乘和N(N-1)次復加。當N很大時，運算量相當大，無法滿足實時處理的要求。因此利用旋轉因子的對稱性、周期性和可約性，把長序列分解成為短序列來進行快速傅里葉變換。
    由式(1)可以得到4個子序列：

  
    利用旋轉因子WnkN的特性，如：將A，B，C，D作為復數(shù)操作數(shù)進行運算，由式(2)可得簡化計算式：

  
    式(3)就是在FPGA上實現(xiàn)基-4 FFT算法的基本運算法則。
    不同于以往的基-4 FFT算法，這里是將輸入的64點數(shù)據(jù)以8位輸入數(shù)據(jù)為一組，共分成8組的方式輸入給FFT運算單元進行FFT運算的。完整的FFT蝶形運算共分6級，經(jīng)歷196個循環(huán)狀態(tài)。將來自存儲單元的數(shù)據(jù)輸入到FFT運算單元中，前三級是按8位1組的方法，分為8組進行運算；后三級是將前三級運算所得到的中間數(shù)據(jù)送入運算單元進行運算。經(jīng)過FFT運算后，將所得到運算結果寫入存儲單元中保存。結果以倒位序方式輸出，需要經(jīng)過調整位序變換成為自然順序輸出。

2 FFT運算器設計
2．1 系統(tǒng)的整體結構
    一個完整的FFT運算單元應該包括以下幾個組成部分：
    全局控制單元包括控制器和地址產(chǎn)生單元，用于調控整個FFT運算系統(tǒng)，生成蝶形運算單元以及其他子單元所需的地址，控制各子單元時序，保證其正常有序地工作；
    蝶形運算器單元 由蝶形運算器和旋轉因子存儲單元(ROM)組成，負責將送入的輸人數(shù)據(jù)進行蝶形運算，是FFT運算器的核心單元；
    存儲寄存器單元 采用兩個RAM乒乓通信，通過通信接口單元接收總線控制信號，負責存儲輸入數(shù)據(jù)、中間數(shù)據(jù)和運算所得最終結果。
    系統(tǒng)整體框圖如圖1所示。

3 實驗結果驗證
    這里的FFT運算器通過硬件描述語言VHDL代碼進行編寫，在ModelSimSE PLUS 6．1f環(huán)境下完成系統(tǒng)仿真，波形仿真如圖3所示。
    由波形仿真圖可以看出，地址控制單元以3位二進制編碼定義各子單元的地址，存儲的數(shù)據(jù)在時序信號和地址總線單元控制下進行FFT運算。實驗證明，當外部時鐘頻率為40 MHz時，可以對隨機生成的64點序列進行FFT定點運算，運算時間為10μs。

4 結 語
    這里的FFT運算器采用定點數(shù)處理，當處理浮點數(shù)時，系統(tǒng)存在處理異常、數(shù)據(jù)溢出等問題。但是由于可以迅速處理多點數(shù)信號，因此在數(shù)字圖像處理、實時通信系統(tǒng)的調試和解調等方面具有一定的實際意義，達到了使用FPGA實現(xiàn)DSP算法的目的。
    本文在以下方面有所創(chuàng)新：
    (1)輸入的64位數(shù)據(jù)以8位共8組的方式并行輸入，將FFT運算流程分為6級，整個FFT運算過程清晰，結構合理，提高了運行效率。
    (2)使用2塊雙口RAM作為存儲器，采用“乒乓操作”，在一個時鐘周期內保證數(shù)據(jù)傳遞的單向性，減少了數(shù)據(jù)傳輸?shù)娜哂?，提高了精度?br />    (3)將整個FFT運算器進行模塊化設計，在控制模塊的調配下，各個子模塊準確工作，保證了運算的可靠性。