基 2 FFT 算法的模塊化硬件實現(xiàn)與比較

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

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

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

本文引用地址：http://www.butianyuan.cn/article/201901/397266.htm

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

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

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

　　0 引言

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

　　1 FFT算法原理

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

　　DFT 的運(yùn)算公式為：

0.1.jpg

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

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

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

1.1.jpg

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

　　2 兩種設(shè)計方案

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

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

　　流水結(jié)構(gòu)中實現(xiàn)512點(diǎn)基 2 FFT 須重復(fù)調(diào)用9次三個通用模塊，完成9級運(yùn)算。數(shù)據(jù)順序逐級流入，根據(jù)級數(shù)計數(shù)信號來控制各模塊的調(diào)整。

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

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

　　3 FPGA的硬件編程實現(xiàn)

　　FPGA實現(xiàn)的系統(tǒng)主要有三個通用模塊構(gòu)成：數(shù)據(jù)存儲重排模塊、旋轉(zhuǎn)因子調(diào)用模塊、蝶形運(yùn)算模塊。

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

　　以下來詳細(xì)描述本設(shè)計中各個模塊的硬件實現(xiàn)方法。

　　3.1 數(shù)據(jù)存儲重排模塊

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

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

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

　　3.2旋轉(zhuǎn)因子調(diào)用模塊

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

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

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

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

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

　　3.3 蝶形運(yùn)算模塊

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

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

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

　　4 仿真結(jié)果

　　本設(shè)計采用 Verilog 硬件語言在quartus 16.0 平臺編寫，在 modelsim 上通過仿真，驗證結(jié)果與 matlab 中的 FFT 函數(shù)結(jié)果相比較，達(dá)到系統(tǒng)所要求精度。

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

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

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

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

　　5 結(jié)果比較

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

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

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

　　參考文獻(xiàn)

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

　　[2]杜兆勝.基于FPGA的FFT硬件架構(gòu)設(shè)計與實現(xiàn)[D].長春理工大學(xué),2016.

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

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

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

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

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

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

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

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