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

　　0 引言

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

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

　　1 基4-FFT算法基本原理

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

　　基4-FFT算法的基本運(yùn)算是4點DFT。一個4點的DFT運(yùn)算的表達(dá)式為：

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

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

　　2 1024點FFT算法模塊的設(shè)計

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

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

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

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

　　2.2蝶形運(yùn)算單元

　　2.2.1蝶形整體結(jié)構(gòu)

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

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

　　2.2.2復(fù)乘器設(shè)計

　　對于復(fù)乘單元的設(shè)計，常見的復(fù)乘方式為：

　　式中：i為虛數(shù)單位。

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

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

　　2.2.3數(shù)據(jù)溢出控制

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

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

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

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

       

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

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

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

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

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

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

　　2.4 FFT算法仿真結(jié)果

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

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

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

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

　　3 結(jié)束語

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