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

　　0 引言

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

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

　　1 基4-FFT算法基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　對(duì)于復(fù)乘單元的設(shè)計(jì)，常見(jiàn)的復(fù)乘方式為：

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

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

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

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

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

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

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

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

       

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

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

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

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

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

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

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

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

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

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

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

　　3 結(jié)束語(yǔ)

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