基於FPGA的高速流水線FFT算法實現

　　0 引言

本文引用地址：http://www.eepw.com.cn/article/82350.htm

　　有限長序列的DFT(離散傅立葉變換)特點是能夠將頻域的數據離散化成有限長的序列。但由於DYT本身運算量相當大，限制了它的實際應用。FFT(快速傅立葉變換)算法是作為DFT的快速算法提出，它將長序列的DFT分解為短序列的DFT，大大減少了運算量，使得DFT算法在頻譜分析、濾波器設計等領域得到了廣泛的應用。

　　FPGA(現場可編程門陣列)是一種具有大規模可編程門陣列的器件，不僅具有專用集成電路(ASIC)快速的特點，更具有很好的系統實現的靈活性。FPGA可通過開發工具實現在線編程。與CPLD(複雜可編程邏輯器件)相比，FPGA屬寄存器豐富型結構，更加適合於完成時序邏輯控制。因此，FPGA為高速FFT算法的實現提供了一個很好的平臺。

　　1 基4-FFT算法基本原理

　　在FFT各類算法中，基2-FFT算法是最簡單的一種，但其運算量與基4-FFT算法相比則大得多，分裂基算法綜合了基4和基2算法的特點，雖然具有最少的復乘運算量，但其L蝶形運算控制的複雜性也限制了其在硬體上的實現，因此，本設計採用了基4-FFT算法結構。

　　基4-FFT算法的基本運算是4點DFT。一個4點的DFT運算的表達式為：

       

　　式(1)對於輸出變量進行了二進位倒序，便於在運算過程中進行同址運算，節省了運算過程中所需存儲器單元的數量。

　　按DIT(時間抽取)的1 024點的基4-FFT共需5級蝶形運算，每級從RAM中讀取的數據經過蝶形運算後原址存入存儲單元準備下一級運算。算法的第1級為一組N=1 024點的基4蝶形運算，共256個蝶形，每個蝶形的距離為256點；第2級為4組N=256點的基4蝶形運算，每組64個蝶形，每個蝶形的距離為64點。後3級類推。這種算法每一級的運算具有相對獨立性，每級運算都採用同址運算，因此，本設計只使用了2個1 k×16 bits的RAM單元。運算過程中所需的旋轉因子的值經過查詢預設的正弦與餘弦ROM表得到。

　　2 1024點FFT算法模塊的設計

　　本設計的總體框圖如圖1所示。整個模塊的輸入包括16位帶符號實部和虛部數據輸入、FFF啟動信號，輸出包括16位帶符號實部和虛部數據輸出、輸出有效數據區間標誌。內部結構包括2個1 k×16 bits的實部和虛部雙口RAM存儲單元、蝶形運算單元、旋轉因子生成模塊(包括正弦因子查詢表、餘弦因子查詢表和象限轉換模塊)、RAM和ROM存儲器地址控制單元、倒序模塊以及時序總控制單元。

       

　　下面對主要單元進行分析。

　　2.1旋轉因子產生模塊

　　在整個FFT運算過程中，需要存儲一組旋轉因子表用於蝶形運算，如第1級運算需要的旋轉因子有W01024，W11024，…，W10231024，根據旋轉因子的可約性，後幾級運算所需的旋轉因子都可以在這一組數據中查到，因此無需另外存儲。為了更節省存儲資源，本設計只在ROM單元中存儲了前256個旋轉因子數據，即第1象限因子W01024，W11024，…，W2551024，。其餘象限的因子通過象限轉換後得到。這樣便可以節省3／4的ROM存儲單元的硬體資源。

　　2.2蝶形運算單元

　　2.2.1蝶形整體結構

　　蝶形運算單元包括輸入輸出寄存器、串／並轉換、並／串轉換和複數乘法器等。從基本的基4蝶形運算表達式可以看出，每一級的輸出數據在進入下一級運算之前都要首先與旋轉因子WnkN進行相乘。本設計採用如圖2的蝶形運算器結構。

       

　　這種結構是經過優化的蝶形運算器結構，文獻[3]給出了這一結構的具體分析，這樣的結構與傳統的需要3個復乘單元的蝶形結果相比，因為採用了流水線控制，硬體上節省了2個復乘單元，而輸出同樣只需4個時鐘周期，工作效率並未降低。在FPGA設計中，一個乘法器的引入，尤其是高位數的乘法器的引入，將很大程度地影響系統整體的運行速率，並且將佔用大量的資源。因此，這種改進方案更有利於FFT算法的高效實現。

　　2.2.2復乘器設計

　　對於復乘單元的設計，常見的復乘方式為：

       

　　式中：i為虛數單位。

　　這種乘法表達式需要4個實數乘法運算和2個加減運算，設計中對表達式進行如下變換：

      

　　式(3)這種復乘方式只需要3個實數乘法運算和5個加減就可以完成復乘運算，減少了乘法器數量。式中(c+s)值可以在進行象限轉換的同時通過計算得到，而無需另外存儲。

　　2.2.3數據溢出控制

　　為了防止數據計算過程中的溢出，上述蝶形單元中的加減法運算單元對於輸入的4個有符號複數數據採取了符號位擴展相加後再對計算結果進行1／4倍壓縮的方法進行計算。而對於乘法單元則採用了刻度(scaling)的方法，將複數數據(16位)與旋轉因子(8位)相乘後，得到24位數據結果刻度為16位數據後，再存人RAM單元中參與下一級運算。經過這樣處理後，有效地防止了整個系統在運算過程中出現的數據溢出情況，保證了最終運算結果的可靠性。

　　2.3地址產生與總時序控制

　　在FFT運算過程中，地址的產生包括複數數據存儲RAM的讀寫地址(RAM_addr)產生和旋轉因子表的讀取地址產生。對於不同級運算情況下，RAM讀寫的控制必須按DIT的倒序規則進行，這在程序中就需要若干個變量來控制。假設控制級數的變量是L，每級的蝶形運算距離是D，當前計算蝶形所在的組為第S組，共N組，當前計算蝶形所在組中的位置是第A個蝶形，那麼每個蝶形的4個輸人數據地址分別為：

        
 
　　ROM讀取地址ROM_addr可按如下式子計算得到： 

       

　　式中iAN=i×A×N：i=2，1，3，為輸出4點數據的倒序序號，當i為0時數據直接輸出，無需對ROM進行讀取。

　　本設計中採用的RAM模塊為QuartusⅡ軟體中的雙口RAM模塊，此模塊存儲與讀取可以同時進行。系統單獨完成一個蝶形運算總共需要11個時鐘周期，為了能夠充分利用乘法器的運行效率，設計採用了流水線工作方式，平均完成一個蝶形運算只需4個時鐘周期。複數乘法器的工作時序佔整個工作時序的75％，具有較高的工作效率。

　　綜上所述，可以得到如圖3所示流水線工作圖。

　　圖3中，RAM_addr為分別計算4個數據地址，地址計算結果將交替存人寄存器組a和b中。這種控制方式類似於Pingpong RAM的控制方式，適用於流水線工作時序中，可以較大地提高系統的工作效率。地址寄存器組a(或b)中的第1個地址在用於保存完本次蝶形運算數據的第1個計算結果數據之後的，將被立即寫入下一個蝶形第1個數據讀取地址，可見這種流水線方式具有非常高的工作效率。

       

　　圖3中，ROM_addr為分別計算3個旋轉因子的地址，M1、M2、M3分別為每個蝶形單元的3次復乘。蝶形運算單元對4個輸入數據A／B／C／D進行計算，輸出結果4個數據為A′／B′／C′／D′。可以看出，在這16個時鐘單元中，共有4個蝶形運算同時處於流水線工作中，因此每個蝶形運算平均只需4個時鐘周期就可以完成。

　　需要指出的是，在所有蝶形運算結束後，即第5級運算完成後，所存儲在RAM中的數據是四進位倒序的，為了能在輸出端得到正確的1024點頻域數據，在輸出時必須進行四進位倒序輸出，輸出的數據可以直接用於後續的數據分析等工作。

　　2.4 FFT算法仿真結果

　　在QuartusⅡ軟體中利用simulator tool工具在100 MHz的時鐘環境下對系統進行了仿真。輸入時域數據為一個矩形窄脈衝信號，完成整個FFT運算的耗時僅為51.28μs。仿真得到的矢量波形文件的部分結果如圖4所示。

        

　　將仿真輸出結果轉換成tbl文件並利用MATLAB軟體讀取後，得到如圖5所示的頻譜數據圖(實部數據部分)。

        
 
　　圖6所示為MATLAB自帶FFT()函數對於輸入相同1 024點數據的FFT計算結果(同樣為實部數據部分)。
        
       

　　通過對比可以看到，本設計的仿真結果與MAT-LAB計算的結果基本一致。只在較小值受到了有限字長效應的影響。就總體而言，本設計能夠正確而高效地計算輸入的1 024點數據的頻域數據值，數據能夠有效地用於實際的頻譜分析過程中。

　　3 結束語

　　1024點基4-FFT算法共需要5級運算，每級需要計算256個蝶形，由前所述，平均每個蝶形運算需要4個時鐘周期，所以理論上完成1 024點FFT的總時鐘周期為N=256×4×5=5120；假設使用的時鐘為100MHz，那麼將總共耗時T=5120×(1／100)=51.2μs，這與仿真結果51.28μs基本一致。將所設計的FFT程序模塊在Altera公司的自帶DSP單元的stratix系列FPGA上進行綜合後，除了乘法器以及存儲單元外，所佔據資源僅為1 619個邏輯單元。因此，本設計方案能夠在FPGA有限的資源下實現較高效率的FFT算法。