作者Email: smz_wxd@sohu.com
1．引言
DFT及其快速算法FFT是信號處理領域的核心組成部分。FFT算法多種多樣，按數據組合方式不同一般分時域和頻域，按數據抽取方式的不同又可分為基2，基4等。各算法的優缺點視不同的制約因素而不同。FFT的實現方法也多種多樣，可以用軟體實現，也可以用硬體實現，用軟體在PC機或工作站上實現則計算速度很慢。一般多結合具體系統用硬體實現。例如用單片機或DSP實現。但是速度仍然很慢，難以與快速的A/D器件匹配。在雷達信號處理領域主要追求的目標是速度，即實時性的要求非常高。針對這種快速信號處理的要求及FPGA器件的特點，本文採用的是一種基2固定幾何結構的FFT算法。採用的是Altera公司推出的最新器件Stratix來做硬體仿真。Stratix器件是一款採用高性能結構體系的PLD器件。它結合了強大內核性能，大存儲帶寬，數位訊號處理（DSP）功能，高速I/O性能和模塊化設計與一體的PLD。其內嵌的DSP模塊具有很高的乘法運算速度。在用VHDL編程時可以用MegaWizard的方法指定用DSP模塊生成乘法器，用這種乘法器來做蝶形，用多個蝶形來構成FFT運算級，通過循環即可實現FFT核心運算的並行化。用Altera公司的Quartus軟體做邏輯分析和波形分析。Quartus軟體具有很強的硬體仿真和邏輯分析功能，它可將用VHDL編寫的硬體描述綜合到FPGA中。
2．算法介紹
為了說明問題的方便，下面以基2，八點FFT為例加以說明。傳統的基2變幾何結構算法如下（圖一）：箭頭上的數字代表旋轉因子 中的k。圖中輸入採用的是按碼位顛倒的順序排放的。輸出是自然順序。這種結構的特點是每個蝶形的輸出數據仍然放在原來的輸入的數據存儲單元內，這樣只需要2N個存儲單元（FFT中的數據是複數形式，每點需要兩個單元存儲）。其缺點是不同級的同一位置蝶形的輸入數據的尋址不固定，難以實現循環控制。用FPGA編程時難以並行實現，數據處理速度慢。當FFT的點數增加時更是如此。通過觀察傳統結構的FFT算法可以發現，如果將第一級中間的兩個蝶形交換，則可以得到如下結構（圖二）：
對此結構進行進一步的變換，將第二級的輸出不送回原處而是將其存儲起來並按順序存放，則第三級中間的兩個蝶形跟著調換，並把輸入按順序排列，就變成了如下（圖三）所示的固定結構的FFT了。在蝶形變換的同時，其旋轉因子也跟著調換。
出數據的順序是不變的，因此每級幾何結構是固定的。用這種結構尋址方便，易於用FPGA編程，實現內部並行的FFT硬體結構，從而明顯加快FFT的運算速度。
3．FPGA硬體實現
FPGA器件的特點是可用硬體描述語言對其進行靈活編程。利用FPGA廠商提供的軟體可仿真硬體的功能。使硬體設計如同軟體設計一樣靈活方便。縮短了系統研發周期。利用JTAG接口可對其進行ISP(In System Programmable 在系統編程)提高了系統的靈活性。隨著晶片集成度的提高，單片FPGA內不僅擁有大量的邏輯單元而且還能集成RAM,ROM,I/O及DSP塊等。從而使SOC(System On_a_Chip 片上系統)成為現實。本文採用的是Altera公司的Stratix系列晶片的EP1s25。用Altera公司的QuartusII2.0軟體做硬體仿真和邏輯分析。並將輸出結果與Matlab仿真結果進行了比較。系統框圖如下（圖四）：
代碼用VHDL硬體描述語言實現。本系統的結構特點是：1。為提高數據精度，系統全部用16位寬。用data_array，write_array和fly_array三個數組實現了內核的並行處理，可在10個時鐘周期內算完32點復FFT。時鐘周期為25納秒，因此32點FFT只需250納秒。2。實現了數據的流水輸入輸出。在計算第i組數據的同時，第i-1組的數據FFT結果正在串行輸出，第i+1組的數據則正在串行輸入。因為內核計算是並行的，速度快，所以可以有很高的串行輸入。本系統的A/D採樣頻率可達200MHz。仿真所用的信號是：
x(t)= (0.5*sin(2*n*pi/4.7)+0.5*sin(2*n*pi/16.3)+0.1*rand(1,32))*1000
輸入數據為32點複數，系統仿真波形如下（局部）：
用FPGA輸出的FFT的結果（圖六）和用Matlab計算的FFT理論結果（圖七）,其頻譜如下：
此信號是由兩個正弦波疊加一個隨機函數構成的。信噪比為14db。為切合工程實際，仿真信號採用的是實信號，其頻譜具有對稱性，因此圖中只取32點仿真結果的一半即16點便可。
4．結論
通過比較可以看出仿真結果與理論值吻合的很好。Altera公司採用傳統結構的FFT算法其32點的運算時間大於1.0us。用DSP做的32點FFT時間也要1.0us以上。本系統的最大優勢在於利用FPGA器件豐富的邏輯資源，內嵌的RAM,ROM塊及其靈活的可編程特性採用固定幾何結構的FFT算法使運算速度較傳統方法有了很大提高。當然付出的代價是用這種並行的結構需求的硬體資源很多。隨著晶片集成度的不斷提高，用這種並行結構實現的FFT運算其優越性將越來越明顯。而且用這種結構實現的FFT很容易擴展。只需要增加蝶形的個數和循環次數即可。詳細說明見 VHDL源程序。