FFT算法是計算DFT的高效算法。算法最初由J.W.Cooley和J.W.Tukey于1965年提出，之后又有新的算法不斷涌現，總的來說發展方向有兩個：一是針對N等于2的整數次冪的算法，如基2算法、基4算法和分裂基算法等； 另一個是N不等于2 的整數次冪的算法，如素因子算法、Winograd算法等。其中基2算法是目前所常用的FFT算法，其核心思想是將N點的序列逐次分解為（N-1）/2點，最后分解為2點DFT進行計算，從而消除DFT中大量的重復運算。

　　FFT算法可從時域或頻域對序列進行分解：

　?、贂r間抽取法（DIT），即直接將序列x（n）按奇、偶逐次分成奇數子序列和偶數子序列，然后通過計算子序列的DFT來實現整個序列的DFT；

　?、?頻率抽取法（DIF），即將頻域X（k）的序號k按照奇、偶逐次分解成偶數點子序列和奇數點子序列，然后計算子序列的DFT，得到整個頻域內的DFT。

　　時間抽取法和頻率抽取法的計算復雜程度和所需要的計算量都是相同的，且由兩種方法不同的分解形式可知：時間抽取法需要對輸入數據序列x（n）進行重新排序，頻率抽取法需要對輸出數據序列X［k］進行進行排序。

　　目前FFT算法已經廣泛應用于數字信號處理、圖像處理、石油勘探和地震預測等眾多領域。與此同時，為了便于FFT算法在工程實踐中的應用，各大FPGA生產商也都紛紛推出了具有相關功能的IP模塊庫。其中由Xilinx公司研發的IP核Fast Fourier Transform V7.1提供了FFT算法多種可選的計算參數、結構、數據輸入輸出流的順序方式，可以根據用戶的需求方便地實現FFT算法。

　　2 Xilinx FFT IP核功能實現

　　Xilinx IP核功能是基于復雜系統功能的硬件描述語言（HDL）設計文件，這些驗證的功能對于所有的Xilinx FPGA器件的結構都能夠達到最優化，且提供硬件描述語言（VHDL，Verilog）的功能仿真模型，可以在標準EDA仿真工具中進行設計和調試。

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

　　Xilinx FFT IP核有四種結構可供選擇，用戶可以在邏輯資源使用的多少和轉換時間的長短之間進行取舍，具體情況分別如下：

　?、?流水線，Streaming I/O結構：允許連續的數據處理，使用最多的邏輯資源。

　?、?基4，Burst I/O結構：提供數據導入/導出階段和處理階段，導入數據和處理數據時單獨進行的。此結構擁有較小的結構，但是轉換時間較長。

　　③ 基2，Burst I/O結構：使用較少的邏輯資源，同基4階段，提供兩階段的過程。

　?、?基2 Lite Burst I/O結構：這是一種基于基2結構的變體，采用了時分復用的方法使用了最少的邏輯資源，但是轉換時間最長。

　　對于Burst I/O結構，使用DIT抽取法；流水線，Streaming I/O結構則使用DIF抽取法。

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

　　Xilinx FFT IP核V5.0支持三種算法型：全精度無壓縮、塊浮點型和定點壓縮（壓縮比由用戶自定義）。對于全精度無壓縮結構，數據通道內任意一位有意義的整數都將被保留，在運算過程中產生的小數部分都被截斷或者取整。此種結構，對于定點算法，經過多級乘法操作以后，數據位寬將加倍遞增，其輸出位寬為（輸入位寬+log2（數據轉換長度）+1）bits。對于塊浮點型，對于一幀數據里面的任何一數據點有相同的壓縮比，這個壓縮比值由塊指數（Block Exponent）作為輸出值顯示，而且只有在FFT IP核檢測到將會產生數據溢出的時候，才會進行壓縮運算。

　　本文所采用的是定點壓縮結構。該結構相對于全精度無壓縮結構，能夠大大減少FPGA內部資源Xtreme DSP Slices和塊RAM的使用，而相對于塊浮點型，可靈活調節壓縮比。定點壓縮結構的壓縮比例表（Scale_SCH）完全由用戶自定義得到。壓縮比例是按照1、2、4或者8對每一階進行壓縮，即對應于分別向右移位0、1、2或者3。如果壓縮不充分，則蝶形輸出結果會超出其動態范圍，引起數據溢出。對于Burst I/O結構，Scale_SCH的表示方法：對于每一階的壓縮比都由指定的一個2 bit的數表示，零階的2 bit數為最低位，具體形式為［？N4，N3，N2，N1，N0］，每一個2 bit數分別對應著相應階數的壓縮比。

　　例：對于基4結構，數據轉換長度N=1024，Scale_SCH=［01 10 00 11 10］則表示對階0右移位2，對階1右移位3，對階2右移位0，對階3右移位2，對階4右移位1。經驗總結（可以防止產生數據溢出）：對于1024點的基4，Burst I/O結構，Scale_SCH=［10 10 10 10 11］；而對于1024點的基2結構，Scale_SCH=［01 01 01 01 01 01 01 01 01 10］。

　　對于流水線，Streaming I/O結構，把臨近的一對基2階組在一起，即階0和階1為組0，階2和階3為組1，等等。Scale_SCH的表示方法：對于每一組的壓縮比都由指定的一個2 bit的數表示，零組的2 bit數為最低位，具體形式為［？N4，N3，N2，N1，N0］，每一個2 bit數分別對應著相應組的壓縮比，表示同組內的兩個基2階有相同的壓縮比。例：數據長度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表示。經驗總結（可以防止產生數據溢出）：N=512時，Scale_SCH=［01 10 10 10 11］；N=1024時，Scale_SCH=［10 10 10 10 11］。

　　壓縮比例Scale_SCH的位寬，對于流水線，Streaming I/O結構和基4，Burst I/O結構，為2*ceil（0.5*log2（N））；對于基2，Burst I/O結構和基2 Lite Burst I/O結構，為2*log2（N），其中N為轉換數據長度。

　　3 FFT IP核的仿真驗證

　　1）IP核配置：

　　Page 1：（配置實現結構）

　　Page 2：（數據位寬以及數據處理）

　　Page 3：（配置數據緩存空間）

　　接口說明：

　　信號名稱

　　傳輸方向

　　說明

　　XN_RE

　　Input

　　輸入操作數實部，以2的補碼輸入。

　　XN_IM

　　Input

　　輸入操作數虛部，以2的補碼輸入。

　　START

　　Input

　　當此信號變高時，開始輸入數據，隨后直

　　接進行FFT 轉換操作和數據輸出

　　SCALE_SCH

　　Input

　　進行數據縮減運算有用，其總的效果是輸出結果/N

　　SCALE_SCH_WE

　　Input

　　作為SCALE_SCH 的使能信號

　　FWD_INV

　　Input

　　用以指示IP Core為FFT還是IFFT， 1為FFT

　　UNLOAD

　　Input

　　對于Burst I/O結構，此信號將開始以自然順序輸出處理的結果。對于流水線結構和比特逆序輸出的情況，此端口不是必要的。

　　FWD_INV_WE

　　Input

　　作為FWD_INV端口的使能信號

　　RESET

　　Input

　　FFT核復位信號

　　CLK

　　Input

　　工作時鐘，與輸入數據流有關

　　XK_RE

　　Output

　　輸出數據總線實部，以2的補碼輸出

　　XK_IM

　　Output

　　輸出數據總線虛部，以2的補碼輸出

　　XN_INDEX

　　Output

　　位寬等于log2（N），輸入數據的下標

　　XK_INDEX

　　Output

　　位寬等于log2（N），輸出數據的下標

　　RFD

　　Output

　　輸入數據有效信號，高電平有效

　　DV

　　Output

　　輸出數據有效指示信號，當輸出端口存在有效數據時變高

　　BUSY

　　Output

　　IP Core 工作狀態的指示信號，在進行FFT轉換時為高電平

　　EDONE

　　Output

　　高有效。在DONE信號變高的前一個時鐘變為高電平

　　DONE

　　Output

　　高有效。在FFT完成后變高，且只存在一個時鐘。在DONE變高后，IP Core 開始輸出計算結果。

　　通過例化調用Xilinx IP核來實現一個512點、數據位寬和相位因子位寬都為10 bit的FFT算法模塊，時鐘頻率為 50MHz（時鐘頻率越高，可以獲得更高的復用倍數，節省更多的資源面積），采用流水線，Streaming I/O和定點壓縮結構。為了方便驗證FFT IP核功能的正確性：以零開始計數，在每個時鐘上升沿到來時，進行加1得到的數據，分別作為其輸入信號的實部和輸入信號的虛部。Scale_SCH=［01 10 10 10 11］，在ISE 14.1中建工程，例化調用Xilinx FFT IP核，然后利用ModelSimSE 6.5進行仿真，其仿真時序如圖2所示。

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