基于FPGA的32位多并行2DFFT處理器的設計

毛宇河 伍松

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

關鍵詞：現場可編程門陣列（FPGA）;二維快速傅里葉變換（2DFFT）：并行結構

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

0引言

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

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

1 2DFFT算法與并行結構

1.12DFFT算法原理

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

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

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

1.2并行蝶形運算結構

22DFFT多并行處理器的總體設計

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

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

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

以上則是對雙并行蝶形運算過程進行的過程說明，四并行蝶形運算的情況只需將雙蝶形運算中的雙蝶形運算結構模塊變為四蝶形運算結構模塊，其結果即可類似得到。

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

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

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

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

如圖5所示，①為狀態控制單元，是本系統中的主要控制單元，用于向其他單元發送狀態信號，控制單元模塊的運行和清零;②為蝶形運算計數單元，主要用于驅動狀態控制器單元和地址儲存控制單元，通過其中的計‘數器的增加來使狀態機和地址存儲控制器進行運作，是主要的驅動單元;③為地址儲存控制單元，用于為蝶形運算模塊和旋轉因子儲存器發送數據地址，以便保持數據傳輸和接收的準確性;④為旋轉因子儲存單元，專門用于為蝶形運算模塊輸入旋轉因子;⑤為RAM數據儲存單元，主要用于存放、輸入和輸出數據;⑥為系統設計中的關鍵部分，它是擁有并行結構的蝶形運算模塊單元，是2DFFT設計中的主要運算部分。由于在圖5中⑥是由兩個蝶形運算模塊構成的總模塊單元，因此系統采用的是雙并行結構。而且并行結構只需將⑥中蝶形運算模塊buff module的數量變為4個后，便類似可得。

4仿真驗證及測試分析

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

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

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

本系統的仿真計算時間測試結果如表1所不。

使用MATLAB中FFT2函數得到的運行時間結果如圖10所示。

由圖10可知，本設計的計算效率己遠遠超過了MArLAB的計算效率。

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

由表2可見：在相同頻率相同FFT點數的情況下，本文的設計計算速度優于已有的很多FFT處理器，且隨著并行倍數的增大，速度也在成倍的升高。

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

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

5結論

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