FFT(快速傅里葉變換)是一種非常重要的算法,，在信號處理,、圖像處理、生物信息學,、計算物理,、應用數(shù)學等方面都有著廣泛的應用。在高速數(shù)字信號處理中,，F(xiàn)FT的處理速度往往是整個系統(tǒng)設計性能的關鍵所在,。FPGA(現(xiàn)場可編程門陣列)是一種具有大規(guī)模可編程門陣列的器件,，不僅具有ASIC(專用集成電路)快速的特點,，更具有很好的系統(tǒng)實現(xiàn)的靈活性,?；贔PGA的設計可以滿足實時數(shù)字信號處理的要求，在市
場競爭中具有很大的優(yōu)勢,。因此,，F(xiàn)PGA為高速FFT算法的實現(xiàn)提供了一個很好的平臺。

1 FFT算法的硬件實現(xiàn)
1．1 系統(tǒng)框圖
    本設計利用流水線技術來提高系統(tǒng)的性能,，系統(tǒng)框圖,，如圖1所示。其中,，地址產(chǎn)生單元生成RAM讀寫地址,，寫使能信號以及相關模塊的啟動、控制信號,，是系統(tǒng)的控制核心,；4點蝶形運算單元的最后一級輸出不是順序的；旋轉因子產(chǎn)生單元生成復乘運算中的旋轉因子的角度數(shù)據(jù),；旋轉因子ROM中預置了每一級運算中所需的旋轉因子,。

    在FPGA設計中，為提高系統(tǒng)的運行速度,，而將指令分為幾個子操作,，每個子操作由不同的單元完成，這樣，每一級的電路結構得到簡化,，從而減少輸入到輸出間的電路延時,，在較小的時鐘周期內就能夠完成這一級的電路功能。在下一個時鐘周期到來時,，將前一級的結果鎖存為該級電路的輸入,，這樣逐級鎖存，由最后一級完成最終結果的輸出,。也就是說,，流水線技術是將待處理的任務分解為相互有關而又相互
獨立、可以順序執(zhí)行的子任務來逐步實現(xiàn),。本設計中,，4點蝶形運算單元、旋轉因子復乘模塊以及最后的精度截取模塊采用流水線技術來處理,。
1．2 基4蝶形運算算法原理
   
    式(1)為基4蝶形運算單元的一般表達式,，其中，,，N為FFT運算的點數(shù),，本設計中為1 024，p為旋轉因子W的相位角,，其規(guī)律將在1.4節(jié)討論,。X(0)、X(1),、X(2),、X(3)為原始數(shù)據(jù)，順序輸入RAM后蝶形倒序輸出,，與旋轉因子復乘再進行4點蝶形運算,，而X1(0)、X1(1),、X1(2),、X1(3)即為第1級蝶形運算的結果。此時RAM存儲的原始數(shù)據(jù)已經(jīng)清空,，將第1級蝶形運算結果再存回RAM中,，按照一定的地址輸出后，與第2級的旋轉因子復乘,、4點蝶形運算,，得到第2級蝶形運算結果，依此類推,。由于蝶形運算為同址操作,，所以第2級的RAM寫地址即為第一級的RAM讀地址,，每一級的RAM讀地址規(guī)律將在1．3節(jié)中討論。
    1024點的基4-FFT共需要5級蝶形運算,，每級需要計算256個蝶形,，其傳統(tǒng)實現(xiàn)框圖如圖2所示。

    考慮到第一級蝶形運算不需要旋轉因子,，所以第一級的旋轉因子復乘模塊可以省略,，但本設計的硬件結構需要循環(huán)利用，一般情況下,，可以對第一級數(shù)據(jù)進行×1運算,，再進行4點蝶形運算。不過,，考慮到我們并不關心每一級蝶形運算后的結果,，本文提出了一種蝶形運算的新結構：即先進行前一級的4點蝶形運算，再進行本級的與旋轉因子復乘運算,，如圖3所示,。

    可以看出，圖3減少了一個旋轉因子復乘模塊,，不但節(jié)約了一次乘法運算時間,，也省略了第一級旋轉因子，更好地利用了硬件結構,。
    首先,，在QuartusⅡ環(huán)境中對4點蝶形運算時序仿真，采用流水線設計,，連續(xù)輸入連續(xù)輸出,，仿真結果如圖4所示,。

    由圖4可以看出,，輸出比輸入延時6個時鐘，這在系統(tǒng)的控制核心地址產(chǎn)生單元的設計中需要考慮到,。
1．3 地址產(chǎn)生與時序控制
    對于1 024．點基4 FFT運算,，需要5級蝶形運算，每一級運算都要有寫地址和讀地址,，根據(jù)FFT同址運算的特點可知,，當前的寫地址即是上一級蝶形運算的讀地址。因此完成FFT運算需要設計6級RAM地址,。其中第1級的寫地址即是數(shù)據(jù)輸入的順序地址,，不予討論。最后一級讀地址為數(shù)據(jù)正序輸出所需的地址,。其余4級為1 024點數(shù)據(jù)對應的FFT蝶形運算,。
    第一級讀取節(jié)點地址的順序應該是：(0,，256，512．768),，(1,，257，513,，769),，……，(255,，511．767,，1 023)。易觀察其讀地址的規(guī)律如下：設讀取次序的二進制編碼為bit[9：0],；則讀地址的二進制編碼為{bit[1：O],，bit[9：2]}，并且依次可以推出第2,、3,、4級的讀地址二進制編碼分別為{bit[9：8]，bit[1：0],，bit[7：2]},，{bit[9：6]，bit[1：0],，bit[5：2]},、{bit[9：4]，bit[1：0],，bit[3：2]},，而最后一級輸出數(shù)據(jù)的地址二進制編碼則為：{bit[1：0]，bit[3：2],，bit[5：4],，bit[7：6]，bit[9：8]},。圖5給出了第1級讀地址和第2級讀地址的部分數(shù)據(jù),，也可以看出第2級的寫地址即是第1級的讀地址。

    圖1中的地址產(chǎn)生單元作為系統(tǒng)的控制核心,，不僅要生成每一級的RAM讀寫地址,，還要產(chǎn)生RAM寫使能信號、輸出有效信號以及4點蝶形運算單元和旋轉因子產(chǎn)生單元的啟動信號,，由于時序電路還需要考慮器件延時,，例如上文提到的4點蝶形運算輸出比輸入延時6個時鐘，以及RAM存取數(shù)據(jù)輸出比輸入延時1個時鐘,，這些都需要在控制核心中考慮到,。
1．4 旋轉因子產(chǎn)生
    對于1 024點FFT蝶形運算,，需要1 024個旋轉角度(即2π的1 024等份)，其中第一級不需要復乘運算,，第6級只是將數(shù)據(jù)進行整序沒有運算單元,，其他4級都需要旋轉因子。本設計采用將旋轉因子預置于ROM中,，通過查找表方法得出每一級運算的所需的旋轉因子,。根據(jù)旋轉因子的可約性，后幾級運算所需的旋轉因子都可以在第一級運算的旋轉因子中找到,，因此無需另外存儲,。旋轉因子在ROM中的存儲規(guī)律是：旋轉因子相位角p處存儲旋轉因子W=*****。定義一個10 bit的計數(shù)器count[9：0],，則第2,、3、4,、5級ROM的相位角規(guī)律按照Verilog語法可表示為

    為了節(jié)省資源,，本設計只在ROM單元中存儲了前256個旋轉因子數(shù)據(jù)，即第一象限因子其余象限的因子可通過象限轉換后得到,，這樣就大大節(jié)省了存儲單元的硬件資源,。圖6為旋轉因子產(chǎn)生單元在QuartusⅡ環(huán)境中仿真結果的部分數(shù)據(jù)。

2 系統(tǒng)仿真結果
    輸入數(shù)據(jù)為s=1 024×cos(2π×f_in×t),，其中f_in=50 M,，F(xiàn)s=80 MHz，n=40,，t=0：1／Fs：(n-1)／Fs,，利用QuartusⅡ軟件對系統(tǒng)在100 MHz的時鐘環(huán)境下進行了仿真，將仿真輸出結果轉換成tbl文件并利用Matlab軟件讀取后,，得到如圖7所示的頻譜數(shù)據(jù)圖(實部數(shù)據(jù)部分),。

    圖8所示為Maflab自帶FFT函數(shù)對于輸入相同1 024點數(shù)據(jù)的FFT計算結果(同樣為實部數(shù)據(jù)部分)。
    通過比較可以看到,，本設計的仿真結果與Matlab的仿真結果基本一致,，可以正確高效地計算出1 024點FFT數(shù)據(jù)。

3 結束語
    本設計全部由Verilog HDL語言實現(xiàn),，采用自頂向下的設計方法，完成了一種基于FPGA的1 024點16位FFT算法,，共需要5級運算,，每級需要計算256個蝶形。提出了將蝶形運算先進行前一級的蝶形加減運算,，再進行本級的與旋轉因子復乘運算的結構,。由前所述,，平均每個蝶形運算需要4個時鐘周期，所以理論上完成1 024點FFT的總時鐘周期為N=256×4×5=5 120,；假設使用的時鐘為100MHz,，那么將耗時T=5 120×(1／100)=51．2μs，這與仿真結果51．32μs基本一致,。