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

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

1 按頻率抽取的基――4FFT算法原理
對于序列長度為N(N為2的整數次冪)的FFT算法主要有基-2 FFT和基-4 FFT兩種。計算一次基-2FFT需要二次復乘和兩次復加；計算一次基-4 FFT需要三次復乘和八次復加。從運算次數上看，基-2 FFT較為簡單，但是因為基-2 FFT的復數運算較為復雜，所以在硬件實現上反而要比基-4 FFT占用的資源更多。為了滿足對數據高速處理的要求，在此選擇在FP-GA上實現基-4 FFT的算法。
根據定義，對于長度為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作為復數操作數進行運算，由式(2)可得簡化計算式：

式(3)就是在FPGA上實現基-4 FFT算法的基本運算法則。