基 2 FFT 算法的模塊化硬件實(shí)現與比較

作者 駱林依¹，王英喆²，徐圓飛²，張華平³，梁星¹(1.北華航天工業(yè)學(xué)院 電子與控制工程學(xué)院，河北 廊坊 065000;2.北京航星機器制造有限公司，北京 100013;3.鄭州中興智城實(shí)業(yè)有限公司，河南 鄭州 450016)

　　摘要：隨著(zhù)快速傅里葉變化(FFT)在信號處理應用領(lǐng)域的廣泛應用，不同場(chǎng)合對硬件實(shí)現的 FFT 算法結構提出了多樣化的要求，針對這種需求在硬件編程設計中將 FFT 分割成模塊化的三部分：數據存儲重排模塊、旋轉因子調用模塊、蝶形運算模塊。通過(guò)時(shí)序調用可組成不同結構的 FFT 處理器，實(shí)現流水結構與遞歸結構兩種方案，分別側重于處理速度與資源占用量?jì)煞矫娴膬?yōu)勢。在FPGA硬件設計中使用 Verilog 語(yǔ)言完成代碼編程，實(shí)現了兩種結構的 512 點(diǎn)基 2 算法的快速傅里葉變換，使用 Modelsim 完成功能仿真。與 MATLAB 中 FFT 函數對比驗證了結果的正確性。最后通過(guò)比較二者的處理速度和資源占用量，給出了方案性能分析，及兩種方案的最佳適用場(chǎng)合。

　　關(guān)鍵詞：FFT;硬件實(shí)現;基 2 算法;模塊化設計;流水線(xiàn)結構;遞歸結構

　　*基金項目：河北省北華航天工業(yè)學(xué)院碩士研究生科研項目(YKY-2016-02)。

　　0 引言

　　快速傅里葉變換(FFT)作為信號處理的一種高效手段已經(jīng)被廣泛應用在許多工程中。但不同的應用場(chǎng)合對 FFT 算法的實(shí)現有不同的特性要求。研究的主要熱點(diǎn)在于硬件資源的占用量與運算速度^[1-3]。而這兩者又是互相制衡的關(guān)系。所以有必要比較實(shí)現 FFT 算法的多種方案?；? 2 算法具有算法簡(jiǎn)單、時(shí)序清晰、在高速實(shí)時(shí)數據處理中不容易出錯的優(yōu)點(diǎn)。所以本文簡(jiǎn)要介紹了基 2 FFT 的算法化簡(jiǎn)原理，設計實(shí)現了將 FFT 處理器劃分為通用化的三個(gè)模塊。通過(guò)簡(jiǎn)單的時(shí)序調用就可以實(shí)現基 2 FFT 的兩種性能側重不同的方案。以適應多種工程需求，并分析了兩種方案在不同場(chǎng)合的應用。

　　1 FFT算法原理

　　FFT(Fast Fourier Transformation)是離散傅氏變換(DFT)的快速算法

　　DFT 的運算公式為：

　　FFT 通過(guò)將離散序列逐級分解成為短序列，并利用旋轉因子的周期性和對稱(chēng)性^[4]簡(jiǎn)化了 DFT 的運算過(guò)程，提高了 DFT 的運算效率 ^[5-6]。

　　FFT算法的本質(zhì)就是對數據逐級做蝶形運算。如圖1所示是一個(gè)基2蝶形單元。蝶形運算為復數運算。每次運算由兩個(gè)輸入數據的實(shí)部虛部和相對應的復數旋轉因子共同參與，運算結果成為下一級的輸入數據。

　　由以下公式可以看出：一個(gè)基 2 蝶形運算單元中含有一個(gè)復數乘法和兩個(gè)復數加法。在硬件實(shí)現中可將復數運算化簡(jiǎn)成實(shí)數運算^[7-8]。

　　從上兩式可以看出,(BrWr-BiWi)和(BrWi+BiWr)在上下兩式中是重復出現的，所以可以在蝶形模塊中得到運算化簡(jiǎn)。

　　2 兩種設計方案

　　遞歸結構處理速度較慢，但占用資源量少;流水線(xiàn)結構中量每一級運算都在同時(shí)進(jìn)行著(zhù)，輸出數據除了剛開(kāi)始的一段時(shí)間延遲，之后會(huì )不間斷地輸出結果。因此，可提高運算速度。

　　第一種設計方案是流水線(xiàn)^[9-10]串行結構，系統框圖如圖2所示。流水線(xiàn)結構的特點(diǎn)是把整體設計分為幾個(gè)順序的流程，這幾個(gè)流程是單項串聯(lián)的。數據在每一個(gè)流程中只運算一次，總是在將上一級的運算結果傳遞給下一級。直至一組數據經(jīng)過(guò)所有流程完成運算。這種結構開(kāi)始運算后的每一個(gè)流程都在同時(shí)高效的利用，處理來(lái)自上一級的連續數據流，所以在第一組數據開(kāi)始輸出后，之后的結果數據就會(huì )不間斷地輸出。

　　流水結構中實(shí)現512點(diǎn)基 2 FFT 須重復調用9次三個(gè)通用模塊，完成9級運算。數據順序逐級流入，根據級數計數信號來(lái)控制各模塊的調整。

　　第二種設計方案是遞歸結構^[11-12]，遞歸結構是指運算重復利用兩組存儲空間，每一級的運算都要用到上一級的運算結果。遞歸結構系統框圖如圖3所示。其關(guān)鍵部分是時(shí)序控制模塊，作用是控制運算節奏，記錄運算級數，從而控制排序模塊在不同運算級的 RAM 讀寫(xiě)規律以及旋轉因子模塊的地址選取。

　　在數據排序模塊中，遞歸結構只占用兩組 RAM 存儲空間。數據交叉存儲在兩組 RAM 存儲中。采用乒乓 RAM 結構交錯寫(xiě)入讀取數據，無(wú)需中間級的等待時(shí)間，可減小系統的運算速度。

　　3 FPGA的硬件編程實(shí)現

　　FPGA實(shí)現的系統主要有三個(gè)通用模塊構成：數據存儲重排模塊、旋轉因子調用模塊、蝶形運算模塊。

　　本硬件設計中輸入數據序列的長(cháng)度為 512，輸入數據的位寬為 30 位的有符號數，最終輸出數據的位寬也是 30 位的有符號數。

　　以下來(lái)詳細描述本設計中各個(gè)模塊的硬件實(shí)現方法。

　　3.1 數據存儲重排模塊

　　FFT 中每級參與蝶形運算的兩個(gè)數據是按規律挑取的。假設 L 級運算，每級中兩個(gè)運算數據按原位置排列會(huì )相差2(L-1)的距離。所以數據存儲重排模塊的作用就是將上一級的運算結果數據存儲并按規律重新排序，使得輸出的數據剛好是要進(jìn)行下一級蝶形運算的兩個(gè)數。

　　在本模塊中，控制存儲空間 RAM 的讀寫(xiě)規律尤為關(guān)鍵。因為在 FFT 系統中，對 RAM 的讀寫(xiě)速度直接影響到系統的運行速度。利用雙口 RAM 對數據的讀和寫(xiě)同時(shí)進(jìn)行以提高系統運算效率，節省運算時(shí)間。

　　每級數據調用位置不同，所以在編程時(shí)，要考慮每一級數據的排序規律，寫(xiě)入通用模塊中，在 FFT 調用時(shí)根據運算級數控制數據的讀取地址方式。本設計中 RAM 有兩種存取方式：第一級數據按照二進(jìn)制碼位倒敘寫(xiě)入，順序讀出。2 到 9 級寫(xiě)入地址順序，讀出地址間距為 1。經(jīng)過(guò)驗證這樣的排序方式可以滿(mǎn)足各級蝶形運算數的配對要求。

　　3.2旋轉因子調用模塊

　　旋轉因子調用模塊的作用是存儲并按規律抽出旋轉因子給蝶形運算模塊。當參與 FFT 運算的點(diǎn)數確定時(shí)，所需的旋轉因子值就是固定不變的。所以在硬件實(shí)現中，可以在系統運行之前將旋轉因子數值表計算出來(lái)，并存儲在 ROM 中。

　　旋轉因子的調用跟運算級數有關(guān)，通過(guò)改變旋轉因子的取數時(shí)間間隔和地址間隔，生成9種不同的旋轉因子調用規律。寫(xiě)入通用模塊中。由時(shí)序控制模塊中的運算級數計數器判斷在程序運行中需要調用的旋轉因子。

　　512 點(diǎn)的序列根據旋轉因子的周期性和對稱(chēng)性共需要用到 256 個(gè)旋轉因子。本設計共 9 級，假設第 L 級，則每級中會(huì )用到 2(L-1)個(gè)旋轉因子。每級運算中會(huì )分為2(9-L)個(gè)運算組，同一級的每組用到的旋轉因子都是相同的。每組中會(huì )用到本級所有的旋轉因子。

　　根據 RAM 的取數規律，會(huì )按順序取完每組中的第一個(gè)蝶形運算所需要的數據，他們所用到的旋轉因子是同一個(gè)，運算完所有組的第一個(gè)蝶形，再取每組的下一個(gè)蝶形運算所需要的數據，這樣按順序把每組中所需要的數據取完，完成一級運算。

　　按照這種規律，運算數據與 ROM 讀出的旋轉因子相配合，可以減少 ROM 讀地址的改變次數。這樣 ROM 的取數更清晰簡(jiǎn)單，不同旋轉因子取數的地址只用改變一次。如圖 4，以 8 點(diǎn) FFT 運算為例給出排序后的運算數據與旋轉因子的對照表。

　　3.3 蝶形運算模塊

　　由于本設計中只用到一種運算基，所以只用一個(gè)基 2 蝶形單元就可以實(shí)現對數據的流水線(xiàn)處理。

　　本設計中 512 點(diǎn)的 FFT 共有 9 級運算，蝶形運算模塊內部采用流水結構，可將從 RAM 中輸出的數據不間斷地進(jìn)行計算。每級順序進(jìn)行 256 次蝶形運算。

　　本設計中的蝶形運算流程如圖 5 所示。通過(guò)上述對公式的化簡(jiǎn)分析可得，一次蝶形運算本質(zhì)上可轉化為 4 次實(shí)數乘法和 6 次實(shí)數加法運算。內部劃分為三級流水結構，數據和旋轉因子并行輸入計算。提高了模塊運算效率。

　　4 仿真結果

　　本設計采用 Verilog 硬件語(yǔ)言在quartus 16.0 平臺編寫(xiě)，在 modelsim 上通過(guò)仿真，驗證結果與 matlab 中的 FFT 函數結果相比較，達到系統所要求精度。

　　流水結構的 modelsim 仿真結果如圖6所示，仿真采用 50 M 時(shí)鐘，在 105240 ns 時(shí)輸出使能信號拉高有效，開(kāi)始連續的輸出運算結果數據。

　　流水線(xiàn)結構大幅度提高了處理器速度，同時(shí)不可避免的加大了資源占用量。本設計的資源占用情況見(jiàn)表 1.

　　遞歸結構的 modelsim 仿真結果如圖7所示，仿真采用 50 M 時(shí)鐘，在 10500 ns 時(shí)開(kāi)始輸出數據，由圖中仿真結果可以看出，兩種設計在運算一次 512 點(diǎn)FFT的時(shí)間上非常接近，只是流水結構在輸出第一組結果數據后可連續不斷的輸出下一組數據，遞歸結構則需要再等待一次完整運算時(shí)間，才能輸出下一組結果數據。

　　遞歸結構的資源占用量較流水結構相比減少很多。資源占用情況見(jiàn)表 2。

　　5 結果比較

　　FPGA實(shí)現中流水結構的資源占用量較大，但用流水線(xiàn)結構可以提高系統的工作頻率和吞吐率。將處理器速度得到了大幅度的提高，可應用在實(shí)時(shí)性要求高的數據處理場(chǎng)合。進(jìn)行實(shí)時(shí)的 FFT 運算。

　　從上面的分析可以看出，遞歸結構兩次運算輸出結果所需時(shí)間間隔較長(cháng)。但在硬件實(shí)現中需要的存儲資源量很少。本設計通過(guò)采用乒乓 RAM 結構和降低蝶形運算單元中乘法數目的方法，節約了硬件資源，降低了設計成本。適合于應用在對速度要求不高低成本的處理系統中。

　　通過(guò)比較二者資源量和數據，可以發(fā)現資源與速度在硬件實(shí)現中是互相制約的。所以要參照 FFT 所運用的場(chǎng)合和用途來(lái)選擇最合適的算法。本設計中利用三個(gè)固定模塊可快速靈活的改變算法優(yōu)勢，滿(mǎn)足資源和速度的兩種需求。

　　參考文獻

　　[1]劉智.基于FPGA實(shí)現的FFT速度與規模分析[J].科技視界,2014(21):192-193.

　　[2]杜兆勝.基于FPGA的FFT硬件架構設計與實(shí)現[D].長(cháng)春理工大學(xué),2016.

　　[3]余雷.基于FPGA的32點(diǎn)FFT算法的設計與實(shí)現[D].西安電子科技大學(xué),2014.

　　[4]錢(qián)輝,史瑤,龔敏,高博.結合頻譜移位的二維傅里葉變換FPGA實(shí)現[J].電子器件,2017,40(05):1092-1096.

　　[5]顧艷麗,周洪敏.基于FPGA的新型高速FFT算法研究與實(shí)現[J].電子器件,2008(4):1249-1251.

　　[6]王曉君,龍騰,周希元.二維級聯(lián)流水結構大點(diǎn)數FFT運算器實(shí)現研究[J].無(wú)線(xiàn)電工程,2010,40(11):19-22.

　　[7]于洪松.基于FPGA的實(shí)時(shí)圖像頻域處理[D].中國科學(xué)院研究生院(長(cháng)春光學(xué)精密機械與物理研究所),2014.

　　[8]唐英杰,鐘凱.一種基于FPGA的高速FFT處理器實(shí)現[J].科技廣場(chǎng),2015(12):15-17.

　　[9]王英喆,杜蓉.基于FPGA流水線(xiàn)結構并行FFT的設計與實(shí)現[J].電子設計工程,2015,23(4):47-50.

　　[10]和玉梅.局部流水FFT處理器設計[J].蘭州理工大學(xué)學(xué)報,2014,40(6):83-89.

　　[11]趙冬冬.基于FPGA的1024點(diǎn)FFT算法實(shí)現[D]. 蘇州大學(xué),2014.

　　[12]楊晶,康寧,王元慶.基于低成本FPGA的FFT設計實(shí)現[J].電子器件,2013,36(4):506-509.

　　作者簡(jiǎn)介：

　　駱林依(1994-)，女，碩士生，主要研究方向：信號采集與處理。

本文來(lái)源于科技期刊《電子產(chǎn)品世界》2019年第2期第31頁(yè)，歡迎您寫(xiě)論文時(shí)引用，并注明出處