作者 駱林依1，王英喆2，徐圓飛2，張華平3，梁星1(1.北華航天工業學院 電子與控制工程學院，河北 廊坊 065000;2.北京航星機器製造有限公司，北京 100013;3.鄭州中興智城實業有限公司，河南 鄭州 450016)
本文引用地址：http://www.eepw.com.cn/article/201901/397266.htm摘要：隨著快速傅立葉變化(FFT)在信號處理應用領域的廣泛應用，不同場合對硬體實現的 FFT 算法結構提出了多樣化的要求，針對這種需求在硬體編程設計中將 FFT 分割成模塊化的三部分：數據存儲重排模塊、旋轉因子調用模塊、蝶形運算模塊。通過時序調用可組成不同結構的 FFT 處理器，實現流水結構與遞歸結構兩種方案，分別側重於處理速度與資源佔用量兩方面的優勢。在FPGA硬體設計中使用 Verilog 語言完成代碼編程，實現了兩種結構的 512 點基 2 算法的快速傅立葉變換，使用 Modelsim 完成功能仿真。與 MATLAB 中 FFT 函數對比驗證了結果的正確性。最後通過比較二者的處理速度和資源佔用量，給出了方案性能分析，及兩種方案的最佳適用場合。
關鍵詞：FFT;硬體實現;基 2 算法;模塊化設計;流水線結構;遞歸結構
*基金項目：河北省北華航天工業學院碩士研究生科研項目(YKY-2016-02)。
0 引言
快速傅立葉變換(FFT)作為信號處理的一種高效手段已經被廣泛應用在許多工程中。但不同的應用場合對 FFT 算法的實現有不同的特性要求。研究的主要熱點在於硬體資源的佔用量與運算速度[1-3]。而這兩者又是互相制衡的關係。所以有必要比較實現 FFT 算法的多種方案。基 2 算法具有算法簡單、時序清晰、在高速實時數據處理中不容易出錯的優點。所以本文簡要介紹了基 2 FFT 的算法化簡原理，設計實現了將 FFT 處理器劃分為通用化的三個模塊。通過簡單的時序調用就可以實現基 2 FFT 的兩種性能側重不同的方案。以適應多種工程需求，並分析了兩種方案在不同場合的應用。
1 FFT算法原理
FFT(Fast Fourier Transformation)是離散傅氏變換(DFT)的快速算法
DFT 的運算公式為：
FFT 通過將離散序列逐級分解成為短序列，並利用旋轉因子的周期性和對稱性[4]簡化了 DFT 的運算過程，提高了 DFT 的運算效率 [5-6]。
FFT算法的本質就是對數據逐級做蝶形運算。如圖1所示是一個基2蝶形單元。蝶形運算為複數運算。每次運算由兩個輸入數據的實部虛部和相對應的複數旋轉因子共同參與，運算結果成為下一級的輸入數據。
由以下公式可以看出：一個基 2 蝶形運算單元中含有一個複數乘法和兩個複數加法。在硬體實現中可將複數運算化簡成實數運算[7-8]。
從上兩式可以看出,(BrWr-BiWi)和(BrWi+BiWr)在上下兩式中是重複出現的，所以可以在蝶形模塊中得到運算化簡。
2 兩種設計方案
遞歸結構處理速度較慢，但佔用資源量少;流水線結構中量每一級運算都在同時進行著，輸出數據除了剛開始的一段時間延遲，之後會不間斷地輸出結果。因此，可提高運算速度。
第一種設計方案是流水線[9-10]串行結構，系統框圖如圖2所示。流水線結構的特點是把整體設計分為幾個順序的流程，這幾個流程是單項串聯的。數據在每一個流程中只運算一次，總是在將上一級的運算結果傳遞給下一級。直至一組數據經過所有流程完成運算。這種結構開始運算後的每一個流程都在同時高效的利用，處理來自上一級的連續數據流，所以在第一組數據開始輸出後，之後的結果數據就會不間斷地輸出。
流水結構中實現512點基 2 FFT 須重複調用9次三個通用模塊，完成9級運算。數據順序逐級流入，根據級數計數信號來控制各模塊的調整。
第二種設計方案是遞歸結構[11-12]，遞歸結構是指運算重複利用兩組存儲空間，每一級的運算都要用到上一級的運算結果。遞歸結構系統框圖如圖3所示。其關鍵部分是時序控制模塊，作用是控制運算節奏，記錄運算級數，從而控制排序模塊在不同運算級的 RAM 讀寫規律以及旋轉因子模塊的地址選取。
在數據排序模塊中，遞歸結構只佔用兩組 RAM 存儲空間。數據交叉存儲在兩組 RAM 存儲中。採用桌球 RAM 結構交錯寫入讀取數據，無需中間級的等待時間，可減小系統的運算速度。
3 FPGA的硬體編程實現
FPGA實現的系統主要有三個通用模塊構成：數據存儲重排模塊、旋轉因子調用模塊、蝶形運算模塊。
本硬體設計中輸入數據序列的長度為 512，輸入數據的位寬為 30 位的有符號數，最終輸出數據的位寬也是 30 位的有符號數。
以下來詳細描述本設計中各個模塊的硬體實現方法。
3.1 數據存儲重排模塊
FFT 中每級參與蝶形運算的兩個數據是按規律挑取的。假設 L 級運算，每級中兩個運算數據按原位置排列會相差2(L-1)的距離。所以數據存儲重排模塊的作用就是將上一級的運算結果數據存儲並按規律重新排序，使得輸出的數據剛好是要進行下一級蝶形運算的兩個數。
在本模塊中，控制存儲空間 RAM 的讀寫規律尤為關鍵。因為在 FFT 系統中，對 RAM 的讀寫速度直接影響到系統的運行速度。利用雙口 RAM 對數據的讀和寫同時進行以提高系統運算效率，節省運算時間。
每級數據調用位置不同，所以在編程時，要考慮每一級數據的排序規律，寫入通用模塊中，在 FFT 調用時根據運算級數控制數據的讀取地址方式。本設計中 RAM 有兩種存取方式：第一級數據按照二進位碼位倒敘寫入，順序讀出。2 到 9 級寫入地址順序，讀出地址間距為 1。經過驗證這樣的排序方式可以滿足各級蝶形運算數的配對要求。
3.2旋轉因子調用模塊
旋轉因子調用模塊的作用是存儲並按規律抽出旋轉因子給蝶形運算模塊。當參與 FFT 運算的點數確定時，所需的旋轉因子值就是固定不變的。所以在硬體實現中，可以在系統運行之前將旋轉因子數值表計算出來，並存儲在 ROM 中。
旋轉因子的調用跟運算級數有關，通過改變旋轉因子的取數時間間隔和地址間隔，生成9種不同的旋轉因子調用規律。寫入通用模塊中。由時序控制模塊中的運算級數計數器判斷在程序運行中需要調用的旋轉因子。
512 點的序列根據旋轉因子的周期性和對稱性共需要用到 256 個旋轉因子。本設計共 9 級，假設第 L 級，則每級中會用到 2(L-1)個旋轉因子。每級運算中會分為2(9-L)個運算組，同一級的每組用到的旋轉因子都是相同的。每組中會用到本級所有的旋轉因子。
根據 RAM 的取數規律，會按順序取完每組中的第一個蝶形運算所需要的數據，他們所用到的旋轉因子是同一個，運算完所有組的第一個蝶形，再取每組的下一個蝶形運算所需要的數據，這樣按順序把每組中所需要的數據取完，完成一級運算。
按照這種規律，運算數據與 ROM 讀出的旋轉因子相配合，可以減少 ROM 讀地址的改變次數。這樣 ROM 的取數更清晰簡單，不同旋轉因子取數的地址只用改變一次。如圖 4，以 8 點 FFT 運算為例給出排序後的運算數據與旋轉因子的對照表。
3.3 蝶形運算模塊
由於本設計中只用到一種運算基，所以只用一個基 2 蝶形單元就可以實現對數據的流水線處理。
本設計中 512 點的 FFT 共有 9 級運算，蝶形運算模塊內部採用流水結構，可將從 RAM 中輸出的數據不間斷地進行計算。每級順序進行 256 次蝶形運算。
本設計中的蝶形運算流程如圖 5 所示。通過上述對公式的化簡分析可得，一次蝶形運算本質上可轉化為 4 次實數乘法和 6 次實數加法運算。內部劃分為三級流水結構，數據和旋轉因子並行輸入計算。提高了模塊運算效率。
4 仿真結果
本設計採用 Verilog 硬體語言在quartus 16.0 平臺編寫，在 modelsim 上通過仿真，驗證結果與 matlab 中的 FFT 函數結果相比較，達到系統所要求精度。
流水結構的 modelsim 仿真結果如圖6所示，仿真採用 50 M 時鐘，在 105240 ns 時輸出使能信號拉高有效，開始連續的輸出運算結果數據。
流水線結構大幅度提高了處理器速度，同時不可避免的加大了資源佔用量。本設計的資源佔用情況見表 1.
遞歸結構的 modelsim 仿真結果如圖7所示，仿真採用 50 M 時鐘，在 10500 ns 時開始輸出數據，由圖中仿真結果可以看出，兩種設計在運算一次 512 點FFT的時間上非常接近，只是流水結構在輸出第一組結果數據後可連續不斷的輸出下一組數據，遞歸結構則需要再等待一次完整運算時間，才能輸出下一組結果數據。
遞歸結構的資源佔用量較流水結構相比減少很多。資源佔用情況見表 2。
5 結果比較
FPGA實現中流水結構的資源佔用量較大，但用流水線結構可以提高系統的工作頻率和吞吐率。將處理器速度得到了大幅度的提高，可應用在實時性要求高的數據處理場合。進行實時的 FFT 運算。
從上面的分析可以看出，遞歸結構兩次運算輸出結果所需時間間隔較長。但在硬體實現中需要的存儲資源量很少。本設計通過採用桌球 RAM 結構和降低蝶形運算單元中乘法數目的方法，節約了硬體資源，降低了設計成本。適合於應用在對速度要求不高低成本的處理系統中。
通過比較二者資源量和數據，可以發現資源與速度在硬體實現中是互相制約的。所以要參照 FFT 所運用的場合和用途來選擇最合適的算法。本設計中利用三個固定模塊可快速靈活的改變算法優勢，滿足資源和速度的兩種需求。
參考文獻
[1]劉智.基於FPGA實現的FFT速度與規模分析[J].科技視界,2014(21):192-193.
[2]杜兆勝.基於FPGA的FFT硬體架構設計與實現[D].長春理工大學,2016.
[3]餘雷.基於FPGA的32點FFT算法的設計與實現[D].西安電子科技大學,2014.
[4]錢輝,史瑤,龔敏,高博.結合頻譜移位的二維傅立葉變換FPGA實現[J].電子器件,2017,40(05):1092-1096.
[5]顧豔麗,周洪敏.基於FPGA的新型高速FFT算法研究與實現[J].電子器件,2008(4):1249-1251.
[6]王曉君,龍騰,周希元.二維級聯流水結構大點數FFT運算器實現研究[J].無線電工程,2010,40(11):19-22.
[7]於洪松.基於FPGA的實時圖像頻域處理[D].中國科學院研究生院(長春光學精密機械與物理研究所),2014.
[8]唐英傑,鍾凱.一種基於FPGA的高速FFT處理器實現[J].科技廣場,2015(12):15-17.
[9]王英喆,杜蓉.基於FPGA流水線結構並行FFT的設計與實現[J].電子設計工程,2015,23(4):47-50.
[10]和玉梅.局部流水FFT處理器設計[J].蘭州理工大學學報,2014,40(6):83-89.
[11]趙冬冬.基於FPGA的1024點FFT算法實現[D]. 蘇州大學,2014.
[12]楊晶,康寧,王元慶.基於低成本FPGA的FFT設計實現[J].電子器件,2013,36(4):506-509.
作者簡介：
駱林依(1994-)，女，碩士生，主要研究方向：信號採集與處理。
本文來源於科技期刊《電子產品世界》2019年第2期第31頁，歡迎您寫論文時引用，並註明出處