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

作者：駱林依王英徐圓飛張華平梁星時間：2019-01-29 來源：電子產品世界

加入技術交流群
- 掃碼加入
  和技術大咖面對面交流
  海量資料庫查詢

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

本文引用地址：http://2s4d.com/article/201901/397266.htm

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

　　關鍵詞：FFT;硬件實現;基 2 算法;模塊化設計;流水線結構;遞歸結構

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

　　0 引言

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

　　1 FFT算法原理

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

　　DFT 的運算公式為：

0.1.jpg

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

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

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

1.1.jpg

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

　　2 兩種設計方案

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

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

　　流水結構中實現512點基 2 FFT 須重復調用9次三個通用模塊，完成9級運算。數據順序逐級流入，根據級數計數信號來控制各模塊的調整。

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

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

　　3 FPGA的硬件編程實現

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

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

　　以下來詳細描述本設計中各個模塊的硬件實現方法。

　　3.1 數據存儲重排模塊

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

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

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

　　3.2旋轉因子調用模塊

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

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

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

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

　　按照這種規(guī)律，運算數據與 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 函數結果相比較，達到系統(tǒng)所要求精度。

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

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

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