毛宇河 伍松

摘要：在分析研究FPGA的可并行運算性質(zhì)及快速高效地進行二維快速傅里葉變換的計算過程的基礎(chǔ)上，實現(xiàn)了FPGA支持的32位多并行2DFFT處理器的設(shè)計與仿真研究。設(shè)計利用ouanLlsII 13.0進行分析、布線與綜合，利用Modelsim SE仿真平臺進行仿真測試，并將結(jié)果與MATLAB計算結(jié)果進行對比驗證。結(jié)果表明：該處理器充分利用FPGA的并行性和處理能力，解決了普通2DFFT處理器的計算緩慢問題，同時具有運算速度快，結(jié)構(gòu)簡易且可重構(gòu)性能佳等特點。

關(guān)鍵詞：現(xiàn)場可編程門陣列（FPGA）;二維快速傅里葉變換（2DFFT）：并行結(jié)構(gòu)

中圖分類號：TP332;TN911.7DOI：10.16375/j.cnki.cn45-1395/t.2020.01.013

0引言

隨著2DFFT在聲學(xué)、通信、醫(yī)學(xué)、圖像處理等領(lǐng)域中的不斷發(fā)展，對于數(shù)字信號處理量的需求日益增大，而對于能處理超大容量數(shù)據(jù)的二維快速傅里葉變換在硬件實現(xiàn)方面的發(fā)展也越來越不容小視。到目前為止，2DFFT的硬件實現(xiàn)方式主要以3種為主：專用集成電路（ASIC）芯片、專用數(shù)字信號處理（DSP）芯片和現(xiàn)場可編程門陣列（FPGA）芯片。最初為滿足計算的實時性，以定制高速ASIC的方式來完成FFT處理器的計算過程成為當(dāng)時2DFFT硬件實現(xiàn)的主要方式。而隨著技術(shù)發(fā)展，現(xiàn)今國內(nèi)大多采用的則是DSP芯片技術(shù)，又由于多總線結(jié)構(gòu)的加入，使DSP芯片技術(shù)的運行速度大大提高。但由于現(xiàn)代通信技術(shù)的興起，DSP技術(shù)的計算速度和其他技術(shù)指標(biāo)已漸漸無法滿足工程師們的要求，于是FPGA技術(shù)應(yīng)運而生。FPGA將DsP和ASCI的優(yōu)點集聚一身，具有高速度、高精度、低功耗、成本低、開發(fā)周期短的特點，并且其資源富裕，擁有高強的可配置性，并行結(jié)構(gòu)和流水線結(jié)構(gòu)都易于在其芯片上進行實現(xiàn)，成為了高速實現(xiàn)2DFFT算法的不二選擇。華南理工大學(xué)的黃俊彥等采用基于ARM7處理器實現(xiàn)基4-FFT的方法對FFT運算過程高效處理，但由于ARM處理器自身功能的局限性，難以對數(shù)據(jù)處理提供更高的速度，因此，采用ARM處理器實現(xiàn)FFT計算的快速性是難以做到的。華中科技大學(xué)的高英華則是利用ASIC處理器對大點數(shù)的二維FFT進行設(shè)計實現(xiàn)，但由于ASIC處理器的速度性、適用范圍的局限性、以及自身無法媲美FPGA芯片性價比等諸多原因，逐漸被FPGA芯片所代替，因此該設(shè)計的實用性越來越低。云南大學(xué)的楊軍等采用FPGA芯片完成了可實現(xiàn)高精度結(jié)果的二維FFT處理器的設(shè)計研究，但由于此研究過多的對處理器結(jié)果精度進行了把控，對處理器的快速性和高效性未能有更多的考慮，因此，該設(shè)計產(chǎn)生的處理器尚不完美。

本文分析研究了FPGA的可并行運算性質(zhì)及快速高效地進行二維快速傅里葉變換的計算過程，同時實現(xiàn)了FPGA支持的32位多并行2DFFT處理器的設(shè)計與仿真研究。該數(shù)據(jù)處理器較普通的2DFFT處理器而言，極大程度地提高了處理器在FPGA上的運算能力，通過并行性提升了運算的快速性，并同時具有運算水平高，安全性能強，設(shè)計結(jié)構(gòu)簡易且可重構(gòu)性能佳等特點。

1 2DFFT算法與并行結(jié)構(gòu)

1.12DFFT算法原理

對于N₁行N₂列（其中N₁、N₂為2的自然數(shù)次冪）的二維空域均勻采樣序列x（n₁，n₂），其二維DFT系數(shù)可為X_F（k₁，k₂），其定義式如下：

其中，x（n）為均勻采樣序列，k=0，1，…，N-1.由此可知，2DFFT計算可進行分解，將其變?yōu)镹₁個N₂點的FFT的運算過程，將二維的問題分解成一維問題。

由上面的定義式可知，二維快速傅里葉變換通常可采用行列分解算法進行計算，即利用其可分性，將二維的FFT拆分成行方向的FFT和列方向的FFT，然后按先后次序進行計算。通常而言，一維FFT算法的行列先后順序?qū)?DFFT運算結(jié)果沒有很大影響，只要能保證2DFFT中行方向FFT和列方向FFT分別進行了計算即可。而通常2DFFT的處理過程如圖1所示，其中①、②分別代表2DFFT中行方向和列方向的FFT計算過程。由圖1可知，F(xiàn)FT的計算方法的優(yōu)化過程，是提升2DFFT算法計算效率的關(guān)鍵因素。

1.2并行蝶形運算結(jié)構(gòu)

22DFFT多并行處理器的總體設(shè)計

對于2DFFT的軟件設(shè)計過程，主要是運用A1tera公司提供的Quartus II 13.0開發(fā)平臺，采用VerilogHDL硬件描述語言來實現(xiàn)對于32位的2DFFT的IP核的研究與設(shè)計，再通過IP核的搭建來完成對于32位2DFFT數(shù)據(jù)處理器的總體設(shè)計。

為了便于對總體結(jié)構(gòu)的描述，將著重以雙蝶形運算模塊并行結(jié)構(gòu)進行敘述。雙蝶形運算模塊并行結(jié)構(gòu)，其總體結(jié)構(gòu)如圖3所示。整個系統(tǒng)由狀態(tài)控制器（FSM）、蝶形處理單元（BFU）、地址儲存控制器（AddressStorage Control，ASC）、并行結(jié)構(gòu)的蝶形運算計數(shù)器（Butterfly Counter，BFUC）、數(shù)據(jù)存儲器（RandomAc-cess Memory，RAM）、旋轉(zhuǎn)因子儲存器（Twiddle Factor Storage，TFS）以及復(fù)數(shù)乘法（Multiplier，Mult）組成。當(dāng)中，虛線框中區(qū)域，即蝶形運算單元及乘法器這兩部分為此IP核的主要核心，合稱為蝶形運算模塊。該系統(tǒng)的設(shè)計，其優(yōu)勢之處在于程序進行了參數(shù)化設(shè)置，即可由實際情況，隨時對旋轉(zhuǎn)因子、初始數(shù)據(jù)、數(shù)據(jù)地址及蝶形運算單元個數(shù)進行靈活修改。

文中IP核的內(nèi)部設(shè)計，其工作流程如圖4所示，簡述如下：Step 1由蝶形運算計數(shù)器BFUC為地址儲存控制器ASC及狀態(tài)控制器FSM發(fā)出計數(shù)信號;Step 2在狀態(tài)控制器FSM發(fā)出的復(fù)位信號的控制下，IP核整體處于復(fù)位歸零的準(zhǔn)備狀態(tài);Step 3一方面在時鐘信號的控制下，由FSM向具有并行結(jié)構(gòu)的蝶形處理單元BFU和數(shù)據(jù)儲存器RAM發(fā)出使能信號，另一方面由地址儲存控制器ASC向數(shù)據(jù)存儲器RAM和ROM旋轉(zhuǎn)因子儲存器TFS分別發(fā)出地址信號，再從ROM中按照地址提取所需數(shù)據(jù)信號，為蝶形運算單元提供計算所需的旋轉(zhuǎn)因子W_n;Step 4在雙方面的支持下，單次蝶形運算的計算流程如下：首先在RAM的使能信號的驅(qū)動下，由地址存儲器為RAM輸入的地址信號為蝶形運算模塊提供兩對輸入數(shù)據(jù)，再在蝶形運算使能信號的驅(qū)使下，利用蝶形運算單元BFU及復(fù)數(shù)乘法器Mult的相互作用，以及ROM提供的旋轉(zhuǎn)因子，同時完成兩次蝶形運算，并將運算的結(jié)果重新返回到RAM中，替換原先輸出的那兩對數(shù)據(jù)，至此就完成了兩對數(shù)據(jù)的運算;Step 5再在輸入的使能信號的驅(qū)動下，繼續(xù)完成下面兩對數(shù)據(jù)的蝶形運算過程，循環(huán)往復(fù)，直至完成所有行方向的FFT，并通過地址存儲控制器ASC的作用，將RAM當(dāng)中的數(shù)據(jù)進行重新排序選擇，實現(xiàn)32階方陣的轉(zhuǎn)置，將行方向變成列方向;繼續(xù)循環(huán)進行蝶形運算過程，直至完成所有列方向FFT，至此得出2DFFT的最終計算結(jié)果。再將計算結(jié)果通過輸出端口輸出數(shù)據(jù)，完成整個計算的過程。

以上則是對雙并行蝶形運算過程進行的過程說明，四并行蝶形運算的情況只需將雙蝶形運算中的雙蝶形運算結(jié)構(gòu)模塊變?yōu)樗牡芜\算結(jié)構(gòu)模塊，其結(jié)果即可類似得到。

蝶形運算模塊是本2DFFT的IP核運算過程的核心模塊，本模塊主要包含兩部分，即蝶形運算單元（BFU）和復(fù)數(shù)乘法器（Mult）。蝶形運算部分的主要運算過程為復(fù)數(shù)的加減法和乘法，因此，本設(shè)計主要通過蝶形運算單元和復(fù)數(shù)乘法器來分別完成這兩部分的計算，并通過蝶形運算單元與狀態(tài)機、旋轉(zhuǎn)因子儲存模塊和數(shù)據(jù)存儲模塊進行相互連接，形成與其他單元的相互聯(lián)通，從而良性完成蝶形運算計算過程。另外，本模塊采用的雙并行、四并行的并行結(jié)構(gòu)，可成倍有效地解決單蝶形帶來的計算緩慢的問題，使RAM對于數(shù)據(jù)的吞吐效率得以顯著提升。另外由于蝶形運算模塊采用了并行結(jié)構(gòu)，使得地址儲存控制器ASC中命令的行數(shù)也成倍地減少，同時也讓地址儲存控制器的運行效率極大提高，使系統(tǒng)的運算處理能力大大加強。

3 21）FFT多并行處理器的RTL級描述

2DFFT多并行處理器是利用32位多并行2DFFT的IP核搭建來完成。因此，對于此IP核的RTL級描述過程將變得尤為重要。系統(tǒng)的RTL級描述過程，是作為了解整個系統(tǒng)硬件構(gòu)成的主要途徑。

通過使用OuartusII開發(fā)平臺來完成對于IP核的RTL級硬件描述過程，以此得到所需的雙并行和四并行蝶形運算的RTL級原理圖。其中，雙并行蝶形運算的RTL級原理圖如圖5所示。

如圖5所示，①為狀態(tài)控制單元，是本系統(tǒng)中的主要控制單元，用于向其他單元發(fā)送狀態(tài)信號，控制單元模塊的運行和清零;②為蝶形運算計數(shù)單元，主要用于驅(qū)動狀態(tài)控制器單元和地址儲存控制單元，通過其中的計‘?dāng)?shù)器的增加來使?fàn)顟B(tài)機和地址存儲控制器進行運作，是主要的驅(qū)動單元;③為地址儲存控制單元，用于為蝶形運算模塊和旋轉(zhuǎn)因子儲存器發(fā)送數(shù)據(jù)地址，以便保持?jǐn)?shù)據(jù)傳輸和接收的準(zhǔn)確性;④為旋轉(zhuǎn)因子儲存單元，專門用于為蝶形運算模塊輸入旋轉(zhuǎn)因子;⑤為RAM數(shù)據(jù)儲存單元，主要用于存放、輸入和輸出數(shù)據(jù);⑥為系統(tǒng)設(shè)計中的關(guān)鍵部分，它是擁有并行結(jié)構(gòu)的蝶形運算模塊單元，是2DFFT設(shè)計中的主要運算部分。由于在圖5中⑥是由兩個蝶形運算模塊構(gòu)成的總模塊單元，因此系統(tǒng)采用的是雙并行結(jié)構(gòu)。而且并行結(jié)構(gòu)只需將⑥中蝶形運算模塊buff module的數(shù)量變?yōu)?個后，便類似可得。

4仿真驗證及測試分析

為了驗證并行結(jié)構(gòu)的2DFFT的速度和性能是否達到要求，將利用OuartusII 13.0軟件平臺對本設(shè)計進行仿真測試。

本設(shè)計采用A1teraCvclorleIIILS作為目標(biāo)開發(fā)板，對單蝶形運算系統(tǒng)、雙并行蝶形運算系統(tǒng)和四并行蝶形運算系統(tǒng)將采用EP3CLS200F484C7作為目標(biāo)芯片，在Ouartus II 13.0軟件平臺上進行分析、綜合、布線、裝配、時序分析等過程后，得到最終結(jié)果。由于最終結(jié)果共包含32×32個數(shù)據(jù)，數(shù)據(jù)過多，為了方便比較說明，僅將前三行仿真結(jié)果進行圖像展示。單蝶形運算系統(tǒng)、雙并行蝶形運算系統(tǒng)和四并行蝶形運算系統(tǒng)在Modelsim SE 10.4中在50MHz下的仿真計算的前三行結(jié)果分別如圖6-圖8所示。圖中r₁、r₂、r₃、r₄、r₅、r₆、r₇、r₈為結(jié)果數(shù)據(jù)的實數(shù)部分，i₁、i₂、i₃、i₄、i₅、i₆、i₇、i₈為結(jié)果數(shù)據(jù)的虛數(shù)部分，且每個方塊代表一行結(jié)果。

2DFFT在MArLAB中使用FFT2函數(shù)的前三行計算結(jié)果如圖9所示，其中圖9（a）為計算結(jié)果的實數(shù)部分，圖9（b）為計算結(jié)果的虛數(shù)部分。

本系統(tǒng)的仿真計算時間測試結(jié)果如表1所不。

使用MATLAB中FFT2函數(shù)得到的運行時間結(jié)果如圖10所示。

由圖10可知，本設(shè)計的計算效率己遠(yuǎn)遠(yuǎn)超過了MArLAB的計算效率。

再將本文設(shè)計的雙并行蝶形運算處理器和四并行蝶形運算處理器的仿真測試性能，同已有或不同算法的處理器的性能進行比較，如表2所示。

由表2可見：在相同頻率相同F(xiàn)FT點數(shù)的情況下，本文的設(shè)計計算速度優(yōu)于已有的很多FFT處理器，且隨著并行倍數(shù)的增大，速度也在成倍的升高。

因此，通過圖6-圖9中的結(jié)果數(shù)據(jù)對比，可以說明，使用OuartusII 13.0設(shè)計出來的2DFFT的IP核，其計算能力與MATLAB相差不大，正負(fù)性保持一致，且結(jié)果基本相同;再通過對圖10、表1中仿真計算時間測試結(jié)果與MATLAB中FFT2函數(shù)計算時間的對比以及與各已有處理器計算性能進行對比，可分析得出，將蝶形運算系統(tǒng)進行雙并行或四并行的并行化處理后形成的并行結(jié)構(gòu)體系，可為2DFFT提供非常快的運算速度，基本超過了絕大多數(shù)已有處理器的處理效率，遠(yuǎn)超MATLAB處理2DFFT的能力，達到了設(shè)計預(yù)期的快速性與高效性，實現(xiàn)了2DFFT處理器的高速處理能力。再通過對表1內(nèi)部數(shù)據(jù)的對比，可分析得出，隨著并行倍數(shù)的提高，蝶形運算模塊處理數(shù)據(jù)的能力也成倍攀升，系統(tǒng)的運算效率也是不斷提高，高速能力的體現(xiàn)也是越發(fā)的突出，因此能夠說明，多倍的并行結(jié)構(gòu)的確能夠使系統(tǒng)達到高速能力，且能力也會隨并行的倍數(shù)不斷提升。

雖然計算速度較快，但結(jié)果仍有少許差異。造成差異的原因在于：由于蝶形運算所用到的旋轉(zhuǎn)因子的數(shù)據(jù)類型是浮點數(shù)的，且在VHDL語言中很難使用浮點數(shù)進行四則運算，因此該設(shè)計在計算前將所有旋轉(zhuǎn)因子擴大了128倍;但對數(shù)據(jù)進行了單次蝶形運算后，輸送回來的數(shù)據(jù)，又將采用截斷后7位的方法將結(jié)果縮小128倍，將所得到的結(jié)果覆蓋掉原來從RAM輸出的數(shù)據(jù);后又按相同的方法再進行下一次的蝶形運算，直至RAM中該位置上的數(shù)據(jù)完成了行方向和列方向共10次的蝶形運算，即相當(dāng)于一個最終結(jié)果在之前的過程中共被截斷過10次，因此產(chǎn)生誤差。但與MATLAB計算出的數(shù)據(jù)比較得知，通過IP核生成的數(shù)據(jù)與真實結(jié)果相差不大，且正負(fù)完全一致無誤。后面需對設(shè)計進行進一步的優(yōu)化，減小計算誤差，使本設(shè)計系統(tǒng)更加實用化。

5結(jié)論

運用對蝶形運算模塊采用并行結(jié)構(gòu)的設(shè)計理念完成了一個高效快速的基于FPGA支持的32位多并行2DFFT處理器的研究設(shè)計。該處理器通過對程序的優(yōu)化，實現(xiàn)不同倍數(shù)的蝶形運算并行結(jié)構(gòu)，同時具有運算水平強，計算過程安全穩(wěn)定性高，硬件結(jié)構(gòu)簡易和可重構(gòu)性能高等特點。該設(shè)計不僅能發(fā)揮FPGA芯片的并行性能，同時也解決了高精度樣本數(shù)據(jù)計算過程緩慢的問題，對工程應(yīng)用具備一定的意義和價值。