摘要
本文介紹了一種基于Xilinx IP核的FFT算法的設計與實現(xiàn)方法。在分析FFT算法模塊圖的基礎上，以Xilinx Spartan-3A
DSP系列FPGA為平臺，通過調(diào)用FFT IP核，驗證FFT算法在中低端FPGA中的可行性和可靠性。

1 FFT算法簡介
FFT(Fast Fourier Transform)算法是計算DFT(Discrete Fourier Transform)的高效算法。算法最初由J.W.Cooley和J.W.Tukey于1965年提出，之后又有新的算法不斷涌現(xiàn)，總的來說發(fā)展方向有兩個：一是針對N等于2的整數(shù)次冪的算法，如基2算法、基4算法和分裂基算法等； 另一個是N不等于2 的整數(shù)次冪的算法， 如素因子算法、Winograd算法等。其中基2算法是目前所常用的FFT算法，其核心思想是將N點的序列逐次分解為(N-1)/2點，最后分解為2點DFT進行計算，從而消除DFT中大量的重復運算。FFT算法可從時域或頻域?qū)π蛄羞M行分解：①時間抽取法(decimation in time,DIT)，即直接將序列x(n)按奇、偶逐次分成奇數(shù)子序列和偶數(shù)子序列，然后通過計算子序列的DFT來實現(xiàn)整個序列的DFT； ② 頻率抽取法(decimation in frequency,DIF)，即將頻域X(k)的序號k按照奇、偶逐次分解成偶數(shù)點子序列和奇數(shù)點子序列，然后計算子序列的DFT，得到整個頻域內(nèi)的DFT。時間抽取法和頻率抽取法的計算復雜程度和所需要的計算量都是相同的，且由兩種方法不同的分解形式可知：時間抽取法需要對輸入數(shù)據(jù)序列x(n)進行重新排序，頻率抽取法需要對輸出數(shù)據(jù)序列X[k]進行進行排序。目前FFT算法已經(jīng)廣泛應用于數(shù)字信號處理、圖像處理、石油勘探和地震預測等眾多領域。與此同時，為了便于FFT算法在工程實踐中的應用，各大FPGA生產(chǎn)商也都紛紛推出了具有相關功能的IP(Intellectual Property)模塊庫。其中由Xilinx公司研發(fā)的IP核Fast Fourier Transform V5.0提供了FFT算法多種可選的計算參數(shù)、結(jié)構(gòu)、數(shù)據(jù)輸入輸出流的順序方式，可以根據(jù)用戶的需求方便地實現(xiàn)FFT算法。

2 Xilinx FFT IP核功能實現(xiàn)
Xilinx IP核功能是基于復雜系統(tǒng)功能的硬件描述語言(HDL)設計文件，這些驗證的功能對于所有的Xilinx FPGA器件的結(jié)構(gòu)都能夠達到最優(yōu)化，且提供硬件描述語言(VHDL,Verilog)的功能仿真模型，可以在標準EDA仿真工具中進行設計和調(diào)試。

Xilinx FFT IP核V5.0是Xilinx公司配套其FPGA開發(fā)工具ISE10.1推出的，其最大的系統(tǒng)時鐘頻率達到了550MHz，最大的數(shù)據(jù)吞吐量達到550MSPS，最高可進行65536點的FFT運算，最大輸入數(shù)據(jù)和相位因子位寬為24bit（位寬越大，動態(tài)范圍越大），支持所有的主流Xilinx FPGA芯片。同時，Xilinx FFT IP核V5.0可以實現(xiàn)變換長度為N點實數(shù)或復數(shù)形式的FFT變換及FFT逆變換(IFFT)，N的取值范圍是(8~65536)。輸入數(shù)據(jù)實部和虛部都要以位寬為Mbits的二進制補碼(Two's-Complement)形式表示，M取值范圍是(8~24)；同樣，相位因子位寬取值范圍也是(8~24)。數(shù)據(jù)、相位因子以及輸出數(shù)據(jù)重排序的緩存數(shù)據(jù)，在FFT實現(xiàn)的過程中，都可以用塊RAM(Block RAM)或者分布式RAM(Distributed RAM)進行存儲。對于Burst I/O結(jié)構(gòu)， 塊RAM可以存儲任意點數(shù)的數(shù)據(jù)和相位因子，而分布式RAM則只能存儲點數(shù)不大于1024點的數(shù)據(jù)和相位因子；對于Streaming I/O結(jié)構(gòu)，可采用混合存儲的方法，先選擇使用塊RAM存儲器的階數(shù)的數(shù)量，然后對剩余的采用分布式RAM。

Xilinx FFT IP核有四種結(jié)構(gòu)可供選擇，用戶可以在邏輯資源使用的多少和轉(zhuǎn)換時間的長短之間進行取舍，具體情況分別如下。① 流水線，Streaming I/O結(jié)構(gòu)：允許連續(xù)的數(shù)據(jù)處理，使用最多的邏輯資源。② 基4，Burst I/O結(jié)構(gòu)：提供數(shù)據(jù)導入/導出階段和處理階段，導入數(shù)據(jù)和處理數(shù)據(jù)時單獨進行的。此結(jié)構(gòu)擁有較小的結(jié)構(gòu)，但是轉(zhuǎn)換時間較長。③ 基2，Burst I/O結(jié)構(gòu)：使用較少的邏輯資源，同基4階段，提供兩階段的過程。④ 基2 Lite Burst I/O結(jié)構(gòu)：這是一種基于基
2結(jié)構(gòu)的變體，采用了時分復用的方法使用了最少的邏輯資源，但是轉(zhuǎn)換時間最長。

對于Burst I/O結(jié)構(gòu)，使用DIT抽取法；流水線，Streaming I/O結(jié)構(gòu)則使用DIF抽取法。

在實際硬件操作中，模塊的執(zhí)行速度是很重要的參數(shù)，因此本文進行的是基于流水線，Streaming I/O結(jié)構(gòu)的仿真驗證，進行連續(xù)的數(shù)據(jù)處理。流水線，Streaming I/O結(jié)構(gòu)對一系列基2蝶形處理引擎采用流水線技術設計，且每個蝶形處理引擎都有自己獨立的存儲體對輸入數(shù)據(jù)和中間數(shù)據(jù)進行存儲（如圖1）。這種結(jié)構(gòu)下，F(xiàn)FT IP核具有同時處理當前幀N點數(shù)據(jù)，載入下一幀N點數(shù)據(jù)，輸出前一幀N點數(shù)據(jù)的能力。

Xilinx FFT IP核V5.0支持三種算法類型：全精度無壓縮、塊浮點型和定點壓縮（壓縮比由用戶自定義）。

對于全精度無壓縮結(jié)構(gòu)，數(shù)據(jù)通道內(nèi)任意一位有意義的整數(shù)都將被保留，在運算過程中產(chǎn)生的小數(shù)部分都被截斷或者取整。此種結(jié)構(gòu)，對于定點算法，經(jīng)過多級乘法操作以后，數(shù)據(jù)位寬將加倍遞增，其輸出位寬為（輸入位寬+log2(數(shù)據(jù)轉(zhuǎn)換長度)+1）bits。

對于塊浮點型，對于一幀數(shù)據(jù)里面的任何一數(shù)據(jù)點有相同的壓縮比，這個壓縮比值由塊指數(shù)(Block Exponent)作為輸出值顯示，而且只有在FFT IP核檢測到將會產(chǎn)生數(shù)據(jù)溢出的時候，才會進行壓縮運算。

本文所采用的是定點壓縮結(jié)構(gòu)。該結(jié)構(gòu)相對于全精度無壓縮結(jié)構(gòu)，能夠大大減少FPGA內(nèi)部資源Xtreme DSP Slices和塊RAM的使用，而相對于塊浮點型，可靈活調(diào)節(jié)壓縮比。定點壓縮結(jié)構(gòu)的壓縮比例表(Scale_SCH)完全由用戶自定義得到。壓縮比例是按照1、2、4或者8對每一階進行壓縮，即對應于分別向右移位0、1、2或者3。如果壓縮不充分，則蝶形輸出結(jié)果會超出其動態(tài)范圍，引起數(shù)據(jù)溢出。對于Burst I/O結(jié)構(gòu)，Scale_SCH的表示方法：對于每一階的壓縮比都由指定的一個2bits的數(shù)表示，零階的2bits數(shù)為最低位，具體形式為[?N4,N3,N2,N1,N0]，每一個2bits數(shù)分別對應著相應階數(shù)的壓縮比。例：對于基4結(jié)構(gòu)，數(shù)據(jù)轉(zhuǎn)換長度N=1024，Scale_SCH=[01 10 00 1110]則表示對階0右移位2，對階1右移位3，對階2右移位0，對階3右移位2，對階4右移位1。經(jīng)驗總結(jié)（可以防止產(chǎn)生數(shù)據(jù)溢出）：對于1024點的基4，Burst I/O結(jié)構(gòu)，Scale_SCH=[10 10 10 10 11]；而對于1024點的基2結(jié)構(gòu)，Scale_SCH=[01 01 01 01 01 01 01 01 01 10]。

對于流水線，Streaming I/O結(jié)構(gòu)，把臨近的一對基2階組在一起，即階0和階1為組0，階2和階3為組1，等等。Scale_SCH的表示方法：對于每一組的壓縮比都由指定的一個2bits的數(shù)表示，零組的2bits數(shù)為最低位，具體形式為[?N4,N3,N2,N1,N0]，每一個2bits數(shù)分別對應著相應組的壓縮比，表示同組內(nèi)的兩個基2階有相同的壓縮比。例：數(shù)據(jù)長度N=1024，Scale_SCH=[10 10 00 01 11]表示對組0（階0和階1）右移位3，對組1（階2和階3）右移位1，對組2（階4和階5）沒有移位，對組3（階6和階7）右移位2，對組4（階8和階9）右移位2。若變換長度N不是4的冪次方的時候，最后一組只包含一個基2階，只能用00或者01表示。經(jīng)驗總結(jié)（可以防止產(chǎn)生數(shù)據(jù)溢出）：N=512時，Scale_SCH=[01 10 10 10 11]；N=1024時，Scale_SCH=[10 10 10 10 11]。

壓縮比例Scale_SCH的位寬，對于流水線，Streaming I/O結(jié)構(gòu)和基4，Burst I/O結(jié)構(gòu)，為2*ceil(0.5*log2(N))；對于基2，Burst I/O結(jié)構(gòu)和基2 Lite Burst I/O結(jié)構(gòu)，為2* log2(N)，其中N為轉(zhuǎn)換數(shù)據(jù)長度。

3 FFT IP核的仿真驗證
通過例化調(diào)用Xilinx IP核來實現(xiàn)一個512點、數(shù)據(jù)位寬和相位因子位寬都為16bit的FFT算法模塊，時鐘頻率為50MHz（時鐘頻率越高，可以獲得更高的復用倍數(shù)，節(jié)省更多的資源面積），采用流水線，Streaming I/O和定點壓縮結(jié)構(gòu)，完成在中低端FPGA上的調(diào)試，驗證其可靠性和可行性。為了方便驗證FFT IP核功能的正確性：以零開始計數(shù)，在每個時鐘上升沿到來時，進行加一運算得到的數(shù)據(jù)，分別作為其輸入信號的實部和輸入信號的虛部。Scale_SCH=[01 10 10 10 11]，在ISE10.1中建工程，例化調(diào)用Xilinx FFT IP核，然后利用ModelSimSE6.5進行仿真，其仿真時序如圖2所示。

時序驗證方面：可以看出整個時序在實現(xiàn)中是完全正確的。從時序圖可以看出：busy信號高的的時候表明FFT IP核正在進行FFT運算，busy信號拉低后表明運算已經(jīng)結(jié)束，要向外輸出FFT運算結(jié)果；edone信號在done信號之前一個周期到達；此時，done信號拉高一個周期，表明FFT運算完成；而且，由于進行的是512點的FFT運算，所以，每間隔512個時鐘周期，edone和done信號都會拉高一次；rfd信號一直拉高，表明輸入數(shù)據(jù)一直傳送到FFT IP核的輸入端口，跟采用流
水線，Streaming I/O結(jié)構(gòu)，可以進行連續(xù)數(shù)據(jù)處理是一致的；dv信號一直為高，表明輸出的信號一直有效。

功能驗證方面：根據(jù)FFT IP核在流水線，Streaming I/O結(jié)構(gòu)下，間隔每一幀數(shù)據(jù)需要三幀才能輸出計算結(jié)果的特點，可以推算出上面仿真圖形里面輸出結(jié)果時刻對應著[94:605]+ [94:605]*j的FFT輸出結(jié)果。把Matlab里面通過仿真得到的結(jié)果，按照Scale_SCH的比例進行壓縮，與上面得到的結(jié)果是一致的，表明了FFT IP核是正常工作的。

4 結(jié)語
本文主要通過對FFT IP核的整體測試，驗證FFT算法在中低端FPGA中的可行性和可靠性。在選用流水線結(jié)構(gòu)實現(xiàn)FFT的基礎上，采用定點壓縮結(jié)構(gòu)，減少了數(shù)據(jù)的讀取和處理時間，更好的滿足了FFT處理數(shù)據(jù)的需要。