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

　　FFT算法可從時(shí)域或頻域?qū)π蛄羞M(jìn)行分解：

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

　?、?頻率抽取法（DIF），即將頻域X（k）的序號(hào)k按照奇、偶逐次分解成偶數(shù)點(diǎn)子序列和奇數(shù)點(diǎn)子序列，然后計(jì)算子序列的DFT，得到整個(gè)頻域內(nèi)的DFT。

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

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

　　2 Xilinx FFT IP核功能實(shí)現(xiàn)

　　Xilinx IP核功能是基于復(fù)雜系統(tǒng)功能的硬件描述語言（HDL）設(shè)計(jì)文件，這些驗(yàn)證的功能對(duì)于所有的Xilinx FPGA器件的結(jié)構(gòu)都能夠達(dá)到最優(yōu)化，且提供硬件描述語言（VHDL，Verilog）的功能仿真模型，可以在標(biāo)準(zhǔn)EDA仿真工具中進(jìn)行設(shè)計(jì)和調(diào)試。

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

　　Xilinx FFT IP核有四種結(jié)構(gòu)可供選擇，用戶可以在邏輯資源使用的多少和轉(zhuǎn)換時(shí)間的長短之間進(jìn)行取舍，具體情況分別如下：

　?、?流水線，Streaming I/O結(jié)構(gòu)：允許連續(xù)的數(shù)據(jù)處理，使用最多的邏輯資源。

　?、?基4，Burst I/O結(jié)構(gòu)：提供數(shù)據(jù)導(dǎo)入/導(dǎo)出階段和處理階段，導(dǎo)入數(shù)據(jù)和處理數(shù)據(jù)時(shí)單獨(dú)進(jìn)行的。此結(jié)構(gòu)擁有較小的結(jié)構(gòu)，但是轉(zhuǎn)換時(shí)間較長。

　?、?基2，Burst I/O結(jié)構(gòu)：使用較少的邏輯資源，同基4階段，提供兩階段的過程。

　?、?基2 Lite Burst I/O結(jié)構(gòu)：這是一種基于基2結(jié)構(gòu)的變體，采用了時(shí)分復(fù)用的方法使用了最少的邏輯資源，但是轉(zhuǎn)換時(shí)間最長。

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

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

　　Xilinx FFT IP核V5.0支持三種算法型：全精度無壓縮、塊浮點(diǎn)型和定點(diǎn)壓縮（壓縮比由用戶自定義）。對(duì)于全精度無壓縮結(jié)構(gòu)，數(shù)據(jù)通道內(nèi)任意一位有意義的整數(shù)都將被保留，在運(yùn)算過程中產(chǎn)生的小數(shù)部分都被截?cái)嗷蛘呷≌４朔N結(jié)構(gòu)，對(duì)于定點(diǎn)算法，經(jīng)過多級(jí)乘法操作以后，數(shù)據(jù)位寬將加倍遞增，其輸出位寬為（輸入位寬+log2（數(shù)據(jù)轉(zhuǎn)換長度）+1）bits。對(duì)于塊浮點(diǎn)型，對(duì)于一幀數(shù)據(jù)里面的任何一數(shù)據(jù)點(diǎn)有相同的壓縮比，這個(gè)壓縮比值由塊指數(shù)（Block Exponent）作為輸出值顯示，而且只有在FFT IP核檢測到將會(huì)產(chǎn)生數(shù)據(jù)溢出的時(shí)候，才會(huì)進(jìn)行壓縮運(yùn)算。

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

　　例：對(duì)于基4結(jié)構(gòu)，數(shù)據(jù)轉(zhuǎn)換長度N=1024，Scale_SCH=［01 10 00 11 10］則表示對(duì)階0右移位2，對(duì)階1右移位3，對(duì)階2右移位0，對(duì)階3右移位2，對(duì)階4右移位1。經(jīng)驗(yàn)總結(jié)（可以防止產(chǎn)生數(shù)據(jù)溢出）：對(duì)于1024點(diǎn)的基4，Burst I/O結(jié)構(gòu)，Scale_SCH=［10 10 10 10 11］；而對(duì)于1024點(diǎn)的基2結(jié)構(gòu)，Scale_SCH=［01 01 01 01 01 01 01 01 01 10］。

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

　　壓縮比例Scale_SCH的位寬，對(duì)于流水線，Streaming I/O結(jié)構(gòu)和基4，Burst I/O結(jié)構(gòu)，為2*ceil（0.5*log2（N））；對(duì)于基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核的仿真驗(yàn)證

　　1）IP核配置：

　　Page 1：（配置實(shí)現(xiàn)結(jié)構(gòu)）

　　Page 2：（數(shù)據(jù)位寬以及數(shù)據(jù)處理）

　　Page 3：（配置數(shù)據(jù)緩存空間）

　　接口說明：

　　信號(hào)名稱

　　傳輸方向

　　說明

　　XN_RE

　　Input

　　輸入操作數(shù)實(shí)部，以2的補(bǔ)碼輸入。

　　XN_IM

　　Input

　　輸入操作數(shù)虛部，以2的補(bǔ)碼輸入。

　　START

　　Input

　　當(dāng)此信號(hào)變高時(shí)，開始輸入數(shù)據(jù)，隨后直

　　接進(jìn)行FFT 轉(zhuǎn)換操作和數(shù)據(jù)輸出

　　SCALE_SCH

　　Input

　　進(jìn)行數(shù)據(jù)縮減運(yùn)算有用，其總的效果是輸出結(jié)果/N

　　SCALE_SCH_WE

　　Input

　　作為SCALE_SCH 的使能信號(hào)

　　FWD_INV

　　Input

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

　　UNLOAD

　　Input

　　對(duì)于Burst I/O結(jié)構(gòu)，此信號(hào)將開始以自然順序輸出處理的結(jié)果。對(duì)于流水線結(jié)構(gòu)和比特逆序輸出的情況，此端口不是必要的。

　　FWD_INV_WE

　　Input

　　作為FWD_INV端口的使能信號(hào)

　　RESET

　　Input

　　FFT核復(fù)位信號(hào)

　　CLK

　　Input

　　工作時(shí)鐘，與輸入數(shù)據(jù)流有關(guān)

　　XK_RE

　　Output

　　輸出數(shù)據(jù)總線實(shí)部，以2的補(bǔ)碼輸出

　　XK_IM

　　Output

　　輸出數(shù)據(jù)總線虛部，以2的補(bǔ)碼輸出

　　XN_INDEX

　　Output

　　位寬等于log2（N），輸入數(shù)據(jù)的下標(biāo)

　　XK_INDEX

　　Output

　　位寬等于log2（N），輸出數(shù)據(jù)的下標(biāo)

　　RFD

　　Output

　　輸入數(shù)據(jù)有效信號(hào)，高電平有效

　　DV

　　Output

　　輸出數(shù)據(jù)有效指示信號(hào)，當(dāng)輸出端口存在有效數(shù)據(jù)時(shí)變高

　　BUSY

　　Output

　　IP Core 工作狀態(tài)的指示信號(hào)，在進(jìn)行FFT轉(zhuǎn)換時(shí)為高電平

　　EDONE

　　Output

　　高有效。在DONE信號(hào)變高的前一個(gè)時(shí)鐘變?yōu)楦唠娖?/p>

　　DONE

　　Output

　　高有效。在FFT完成后變高，且只存在一個(gè)時(shí)鐘。在DONE變高后，IP Core 開始輸出計(jì)算結(jié)果。

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

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