基于FPGA IP核的FFT實(shí)現

1 算法原理
FFT算法是基于離散傅里葉變換(DFT)，如式(1)和式(2)：

求和運算的嵌套分解以及復數乘法的對稱(chēng)性得以實(shí)現。其中一類(lèi)FFT算法為庫利一圖基(Cooley-Tukey)基r按頻率抽選(DIF)法，將輸入序列循環(huán)分解為N／r個(gè)長(cháng)度為r的序列，并需要logr N級運算。算法的核心操作是蝶型運算，蝶型運算的速度直接影響著(zhù)整個(gè)設計的速度。
基4頻域抽取FFT算法是指把輸出序列X(k)按其除4的余數不同來(lái)分解為越來(lái)越短的序列，實(shí)現x(n)的DFT算法。FFT的每一級的運算都是有N／4個(gè)蝶形運算構成，第m級的一個(gè)蝶形運算的四節點(diǎn)分別為Xm(k)，Xm(k+N／4m)，Xm(k+2N／4m)以及Xm(k+3N／4m)，所以每一個(gè)蝶形運算結構完成以下基本迭代運算：

式(3)～式(6)中：m表示第m級蝶形算法；k為數據所在的行數；N為所要計算的數據的點(diǎn)數；WN為旋轉因子。
將輸入序列循環(huán)分解為4點(diǎn)序列的基4分解，使用4點(diǎn)FFT在乘法上更具優(yōu)勢，Altera的：FFT兆核選用的就是基4運算，若N是2的奇數冪的情況下，FFT IP核則自動(dòng)在完成轉換的最后使用基2運算。

2 FFT兆核(IP)函數
FFT Core支持4種I／O數據流結構：流(Stream-ing)、變量流(Variable Streaming)、緩沖突發(fā)(BufferedBurt)、突發(fā)(Burst)。流結構允許輸入數據連續處理，并輸出連續的復數據流，這個(gè)過(guò)程不需要停止FFT函數數據流的進(jìn)出。變量流結構允許輸入數據連續處理，并產(chǎn)生一個(gè)與流結構相似連續輸出數據流。緩沖突發(fā)數據流結構的FFT需要的存儲器資源比流動(dòng)I／O數據流結構少，但平均模塊吞吐量減少。突發(fā)數據流結構的執行過(guò)程和緩沖突發(fā)結構相同，不同的是，對于給定參數設置，突發(fā)結構在降低平均吞吐量的前提下需要更少的存儲資源。

3 FFT處理器引擎結構
FFT兆核函數可以通過(guò)定制參數來(lái)使用兩種不同的引擎結構：四輸出(Quad-outlput)或單輸出(Signal-output)引擎結構。為了增加FFT兆核函數的總吞吐量，也可以在一個(gè)FFT兆核函數變量中使用多個(gè)并行引擎。本文建立一個(gè)基于QuartusⅡ7.O計算24位512點(diǎn)FFT工程，采用四輸出FFT引擎結構，如圖1所示。

復取樣數據X[k，m]從內部存儲器并行讀出并由變換開(kāi)關(guān)(SW)重新排序，排序后的取樣數據由基4處理器處理并得到復數輸出G[k，m]，由于基4按頻率抽選(DIF)分解方法固有的數字特點(diǎn)，在蝶形處理器輸出上僅需要3個(gè)復數乘法器完成3次乘旋轉因子(有一個(gè)因子為1，不需要乘)計算。這種實(shí)現結構在一個(gè)單時(shí)鐘周期內計算所有四個(gè)基4蝶形復數輸出。
同時(shí)，為了辨別取樣數據的最大動(dòng)態(tài)范圍，四個(gè)輸出由塊浮點(diǎn)單元(BFPU)并行估計，丟棄適當的最低位(LSB)，在寫(xiě)入內部存儲器之前對復數值進(jìn)行四舍五入并行重新排序。對于要求轉換時(shí)間盡量小的應用，四輸出引擎結構是最佳的選擇；對于要求資源盡量少的應用，單輸出引擎結構比較合適。為了增加整個(gè)FFT吞吐量，可以采用多并行的結構。

4 系統驗證
4．1 工程仿真
選擇CycloneⅡ系列的EP2C70F896C8芯片來(lái)實(shí)現，先在QuartusⅡ軟件下進(jìn)行綜合仿真，初始化參數設置FFT變換長(cháng)度為512點(diǎn)，數據和旋轉因子精度為24 b，選擇緩沖突發(fā)的數據流結構，四輸出引擎并行FFT引擎個(gè)數為4個(gè)，復數乘法器結構為“4／Mults／2Adders”。EP2C70F896C8芯片包括68 416個(gè)邏輯單元，31 112個(gè)寄存器單元，最大用戶(hù)輸入／輸出引腳622個(gè)，總RAM達1 152 000 b，其布線(xiàn)資源由密布的可編程開(kāi)關(guān)來(lái)實(shí)現相互間的連接，這種結構完全符合實(shí)現FFT電路的要求。
經(jīng)綜合和時(shí)序分析得知：其工作時(shí)鐘頻率
69．58 MHz(period=14．372 ns)，進(jìn)行一次蝶形運算只需約14 ns，全部512點(diǎn)數據處理完成則需14．372×4×512=29．3μs滿(mǎn)足時(shí)序要求。具體綜合結果如圖2所示，為Quartus軟件環(huán)境下仿真得到。

圖3則表明了FFT的綜合邏輯結果，為編譯成功后的RTL級電路描述。