基于FPGA的高速流水線FFT算法實現(xiàn)
0 引言
本文引用地址:http://butianyuan.cn/article/82350.htm有限長序列的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算法。
評論