基于FPGA的高速定點(diǎn)FFT算法的設計方案

引 言
快速傅里葉變換(FFT)作為計算和分析工具，在眾多學(xué)科領(lǐng)域(如信號處理、圖像處理、生物信息學(xué)、計算物理、應用數學(xué)等)有著(zhù)廣泛的應用。在高速數字信號處理領(lǐng)域，如雷達信號處理，FFT的處理速度往往是整個(gè)系統設計性能的關(guān)鍵所在。
針對高速實(shí)時(shí)信號處理的要求，軟件實(shí)現方法顯然滿(mǎn)足不了其需要。近年來(lái)現場(chǎng)可編程門(mén)陣列(FPGA)以其高性能、高靈活性、友好的開(kāi)發(fā)環(huán)境、在線(xiàn)可編程等特點(diǎn)，使得基于FPGA的設計可以滿(mǎn)足實(shí)時(shí)數字信號處理的要求，在市場(chǎng)競爭中具有很大的優(yōu)勢。
在FFT算法中，數據的寬度通常都是固定的寬度。然而，在FFT的運算過(guò)程中，特別是乘法運算中，運算的結果將不可避免地帶來(lái)誤差。因此，為了保證結果的準確性，采用定點(diǎn)分析是非常必要的。

1 FFT算法原理
FFT算法的基本思想就是利用權函數的周期性、對稱(chēng)性、特殊性及周期N的可互換性，將較長(cháng)序列的DFT運算逐次分解為較短序列的DFT運算。針對N=2的整數次冪，FFT算法有基-2算法、基-4算法、實(shí)因子算法和分裂基算法等。這里，從處理速度和占用資源的角度考慮，選用基-4按時(shí)間抽取FFT算法 (DIT)。對于N=4γ，基-4 DIT具有log4N=γ次迭代運算，每次迭代包含N／4個(gè)蝶形單元。蝶形單元的運算表達式為：

其信號流如圖1。式中：A，B，C，D和A′，B′，C′，D′均為復數據；W=e-j2π/N。進(jìn)行1次蝶形運算共需3次復乘和8次復加運算。N=64 點(diǎn)的基-4DIT信號流其輸入數據序列是按自然順序排列的，輸出結果需經(jīng)過(guò)整序。64點(diǎn)數據只需進(jìn)行3次迭代運算，每次迭代運算含有N／4=16個(gè)蝶形單元。

2 FFT算法的硬件實(shí)現
2．1 流水線(xiàn)方式FFT算法的實(shí)現
為了提高FFT工作頻率和節省FPGA資源，采用3級流水線(xiàn)結構實(shí)現64點(diǎn)的FFT運算。流水線(xiàn)處理器的結構如圖2所示。

每級均由延時(shí)單元、轉接器(SW)、蝶形運算和旋轉因子乘法4個(gè)模塊組成，延時(shí)節拍由方框中的數字表示。各級轉接器和延時(shí)單元起到對序列進(jìn)行碼位抽取并將數據拉齊的作用。每級延時(shí)在FPGA內部用FIFO實(shí)現，不需要對序列進(jìn)行尋址即可實(shí)現延時(shí)功能。數據串行輸入，經(jīng)過(guò)3級流水處理后，串行輸出。