基于FPGA的高速流水線(xiàn)FFT算法實(shí)現

　　0 引言

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

　　FPGA(現場(chǎng)可編程門(mén)陣列)是一種具有大規?？删幊涕T(mén)陣列的器件，不僅具有專(zhuān)用集成電路(ASIC)快速的特點(diǎn)，更具有很好的系統實(shí)現的靈活性。FPGA可通過(guò)開(kāi)發(fā)工具實(shí)現在線(xiàn)編程。與CPLD(復雜可編程邏輯器件)相比，FPGA屬寄存器豐富型結構，更加適合于完成時(shí)序邏輯控制。因此，FPGA為高速FFT算法的實(shí)現提供了一個(gè)很好的平臺。

　　1 基4-FFT算法基本原理

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

　　基4-FFT算法的基本運算是4點(diǎn)DFT。一個(gè)4點(diǎn)的DFT運算的表達式為：

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

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

　　2 1024點(diǎn)FFT算法模塊的設計

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

　　下面對主要單元進(jìn)行分析。

　　2.1旋轉因子產(chǎn)生模塊

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

　　2.2蝶形運算單元

　　2.2.1蝶形整體結構

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

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

　　2.2.2復乘器設計

　　對于復乘單元的設計，常見(jiàn)的復乘方式為：

　　式中：i為虛數單位。

　　這種乘法表達式需要4個(gè)實(shí)數乘法運算和2個(gè)加減運算，設計中對表達式進(jìn)行如下變換：

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

　　2.2.3數據溢出控制

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

　　2.3地址產(chǎn)生與總時(shí)序控制

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

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

       

　　式中iAN=i×A×N：i=2，1，3，為輸出4點(diǎn)數據的倒序序號，當i為0時(shí)數據直接輸出，無(wú)需對ROM進(jìn)行讀取。

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

　　綜上所述，可以得到如圖3所示流水線(xiàn)工作圖。

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

　　圖3中，ROM_addr為分別計算3個(gè)旋轉因子的地址，M1、M2、M3分別為每個(gè)蝶形單元的3次復乘。蝶形運算單元對4個(gè)輸入數據A／B／C／D進(jìn)行計算，輸出結果4個(gè)數據為A′／B′／C′／D′?？梢钥闯?，在這16個(gè)時(shí)鐘單元中，共有4個(gè)蝶形運算同時(shí)處于流水線(xiàn)工作中，因此每個(gè)蝶形運算平均只需4個(gè)時(shí)鐘周期就可以完成。

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

　　2.4 FFT算法仿真結果

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

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

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

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

　　3 結束語(yǔ)

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