基于FPGA流水線結(jié)構(gòu)并行FFT的設(shè)計(jì)與實(shí)現(xiàn)

離散傅里葉變換DFT在通信、控制、信號(hào)處理、圖像處理、生物信息學(xué)、計(jì)算物理、應(yīng)用數(shù)學(xué)等領(lǐng)域中有著廣泛的應(yīng)用。FFT算法是作為DFT快速算法提出的，它將長(zhǎng)序列的DFT分解為短序列的DFT，大大減少了運(yùn)算量。FFT的FPGA實(shí)現(xiàn)同時(shí)具有軟件編程的靈活性和ASIC電路的快速性等優(yōu)點(diǎn)，成為快速實(shí)時(shí)實(shí)現(xiàn)FFT的一種重要手段。文章意在設(shè)計(jì)一種高速率高吞吐率的FFT處理器，以滿足實(shí)時(shí)處理要求。

1 數(shù)學(xué)模型

FFT的基本思想是利用旋轉(zhuǎn)因子的周期性、對(duì)稱性和可約性將一個(gè)長(zhǎng)度為N的序列的DFT逐次分解為較短的DFT來(lái)計(jì)算，而總的運(yùn)算次數(shù)比直接DFT運(yùn)算要少得多，達(dá)到提高速度的目的。根據(jù)旋轉(zhuǎn)因子的周期性、對(duì)稱性和可約性，我們可以得到如式(1)的一系列有用結(jié)果。

2 結(jié)構(gòu)說(shuō)明

2.1 流水線結(jié)構(gòu)

硬件結(jié)構(gòu)實(shí)現(xiàn)FFT的常用形式有4種：遞歸結(jié)構(gòu)，流水線結(jié)構(gòu)，并行迭代結(jié)構(gòu)和全并行結(jié)構(gòu)。設(shè)計(jì)采用流水線結(jié)構(gòu)，流水線結(jié)構(gòu)一般在FFT實(shí)現(xiàn)的每一級(jí)均采用一個(gè)運(yùn)算單元，前一級(jí)算結(jié)果直接用于下一級(jí)運(yùn)算而無(wú)需等到本級(jí)運(yùn)算全部完成，因此，可提高運(yùn)算速度。遞歸結(jié)構(gòu)的運(yùn)算的時(shí)間較長(zhǎng)，并行迭代結(jié)構(gòu)對(duì)數(shù)據(jù)存取帶寬要求很高，全并行結(jié)構(gòu)資源消耗過(guò)大，均不適用。

2.2 并行處理

FFT作為時(shí)域和頻域轉(zhuǎn)換的基本運(yùn)算，是數(shù)字頻譜分析的必要前提，超級(jí)的運(yùn)算能力在雷達(dá)處理、觀測(cè)、跟蹤、定時(shí)定位處理、高速圖像處理、保密無(wú)線通訊和數(shù)字通信、濾波等的應(yīng)用上極為強(qiáng)烈，而實(shí)時(shí)系統(tǒng)對(duì)FFT的運(yùn)算速度要求更高。提高FFT速度的一種有效解決方法是并行運(yùn)算，如采用多個(gè)蝶形運(yùn)算單元并行處理。

綜上，設(shè)計(jì)選取流水結(jié)構(gòu)，4路并行處理結(jié)構(gòu)。

3 硬件設(shè)計(jì)

3.1 邏輯設(shè)計(jì)

FFT邏輯框架如圖1，為了構(gòu)造高速率高吞吐量的FFT，設(shè)計(jì)4路并行輸入輸出，采用基4與基2混合FFT，F(xiàn)FT512采用基4蝶形算法，其余則采用基2蝶形算法。

流水結(jié)構(gòu)的FFT處理器的基本結(jié)構(gòu)如圖2所示。實(shí)際設(shè)計(jì)由3個(gè)部分組成：運(yùn)算單元、數(shù)據(jù)交換單元和重排單元。

運(yùn)算單元完成蝶形運(yùn)算，是處理器的核心，其運(yùn)算速度直接決定整個(gè)FFT處理器的速度。由于4組輸入數(shù)據(jù)同時(shí)進(jìn)入蝶形運(yùn)算，所以處理速度為串行的4倍。其中，每個(gè)蝶形單元均采用流水線技術(shù)設(shè)計(jì)。運(yùn)算單元啟動(dòng)后，每個(gè)周期處理4組數(shù)據(jù)，完成4輸入4輸出的FFT。

數(shù)據(jù)交換單元是處理器的關(guān)鍵，實(shí)現(xiàn)對(duì)前一級(jí)蝶形運(yùn)算單元輸出數(shù)據(jù)的交換，以滿足下一級(jí)蝶形運(yùn)算的配對(duì)需求。實(shí)現(xiàn)方法為每一級(jí)的輸入均采用順序輸入，內(nèi)部用FIFO緩存數(shù)據(jù)，按照逆序形式配對(duì)數(shù)據(jù)，等待數(shù)據(jù)到來(lái)，將加法結(jié)果輸出，減法結(jié)果存至FIFO中，待加法結(jié)果輸出完畢，繼續(xù)輸出減法結(jié)果，如此輸出結(jié)果即為順序輸出。

數(shù)據(jù)重排單元負(fù)責(zé)對(duì)最終計(jì)算結(jié)果進(jìn)行重新排序，以實(shí)現(xiàn)自然序數(shù)輸出。512點(diǎn)基4框架圖如圖3所示，在512基4運(yùn)算完成后，輸出數(shù)據(jù)的順序并不是所需順序，需要進(jìn)行調(diào)整，由輸入數(shù)據(jù)與輸入數(shù)據(jù)的地址特點(diǎn)發(fā)現(xiàn)，倒序RAM的讀地址即完成順序輸出。

3.2 時(shí)序設(shè)計(jì)

流水示意圖如圖4所示，詳細(xì)說(shuō)明如下：

FFT64模塊的5級(jí)流水：第1級(jí)，前64組輸入數(shù)據(jù)的實(shí)部、虛部均寄存在FIFO中，當(dāng)?shù)?5組數(shù)據(jù)到來(lái)時(shí)，與FIFO中寄存的第一組數(shù)據(jù)做蝶形運(yùn)算，將相減的結(jié)果繼續(xù)存在FIFO中待用，相加運(yùn)算將在第二級(jí)進(jìn)行;第2級(jí)，前64個(gè)周期，做蝶形加法，結(jié)果記為add，第65個(gè)周期起，從FIFO中讀數(shù)給add;第3級(jí)，前64個(gè)周期，add賦給第一級(jí)緩存寄存器，第65個(gè)周期起，把a(bǔ)dd賦給乘法器的輸入端;第4級(jí)，前64個(gè)周期，把第一級(jí)緩存寄存器賦值給第二級(jí)緩存寄存器，第65個(gè)周期起，做乘法運(yùn)算;第5級(jí)，前64個(gè)周期，把第二級(jí)緩存寄存器的值賦給輸出端，第65個(gè)周期起，把乘法器輸出累加的結(jié)果賦給輸出端;

FFT512模塊的6級(jí)流水：第1級(jí)，當(dāng)輸入有效信號(hào)拉高時(shí)，將第一組輸入數(shù)據(jù)放入第一級(jí)緩存器中，寄存第二至四組數(shù)據(jù)，待接乘法器輸入端。同時(shí)，從rom中讀取旋轉(zhuǎn)因子;第2級(jí)，第一路緩存至第二級(jí)緩存中，其余三路做乘法運(yùn)算;第3級(jí)，第一路緩存至第三級(jí)緩存中，其余三路做復(fù)數(shù)乘法的加法運(yùn)算;第4級(jí)，四路數(shù)據(jù)均做緩存;第5級(jí)，做如圖3中的第一個(gè)蝶形運(yùn)算。其中，乘以-j運(yùn)算可以用顛倒相加來(lái)完成，如此可以節(jié)省乘法器資源;第6級(jí)，做如圖3中的第二個(gè)蝶形運(yùn)算，同時(shí)將輸出有效信號(hào)拉高。

FFT32、FFT16、FFT8、FFT4、FFT2、FFT1與FFT_64流水原理一致，只是控制位數(shù)不同，其分別為32、16、8、4、2、1。

4 驗(yàn)證設(shè)計(jì)

Testbench是一種驗(yàn)證手段，通常包含3個(gè)部分，激勵(lì)生成、待測(cè)設(shè)計(jì)、輸出校驗(yàn)。針對(duì)設(shè)計(jì)搭建的testbench如圖5所示，從文件中讀取向量i_data_real、i_data_imag，經(jīng)過(guò)FFT處理得到結(jié)果o_data_relal、o_data_imag，并根據(jù)end信號(hào)將向量寫入相應(yīng)文檔中，與正確結(jié)果進(jìn)行比對(duì)。

5 仿真結(jié)果

ISE仿真波形如圖6所示，輸出文件經(jīng)與MATLAB對(duì)比驗(yàn)證正確。圖(1)為整體仿真波形，輸出有效信號(hào)拉高后，數(shù)據(jù)連續(xù)輸出。圖(2)為FFT 512模塊局部仿真波形，輸入有效信號(hào)拉高后，第6個(gè)周期輸出有效，與分析的流水級(jí)數(shù)相吻合。

6 綜合結(jié)果

綜合后得到資源利用情況如表1，我們發(fā)現(xiàn)，并行處理帶來(lái)面積的增大，如何在實(shí)際問(wèn)題中平衡速度與面積尤為重要。

7 結(jié)束語(yǔ)

文章用FPGA實(shí)現(xiàn)了512點(diǎn)FFT處理器，采用Verilog硬件描述語(yǔ)言進(jìn)行RTL級(jí)描述，并完成綜合、布局布線。經(jīng)過(guò)ISE仿真，結(jié)果與MATLAB仿真輸出結(jié)果吻合。處理器先采用時(shí)域基2蝶形算法，后采用時(shí)域基4蝶形算法，并行處理4個(gè)蝶形運(yùn)算單元，并同時(shí)采用流水線結(jié)構(gòu)，大幅度提高了處理器速度，可進(jìn)行實(shí)時(shí)FFT運(yùn)算。在設(shè)計(jì)中用FIFO存儲(chǔ)中間數(shù)據(jù)，并將旋轉(zhuǎn)因子固定為乘法器IP的常數(shù)系數(shù)，以進(jìn)一步提高處理器的速度。因?yàn)椴捎貌⑿薪Y(jié)構(gòu)，所以FPGA硬件資源消耗較多，系統(tǒng)功耗也相應(yīng)增大，如何根據(jù)系統(tǒng)實(shí)際需求找到速度與資源的平衡至關(guān)重要。